A general context-free parsing algorithm running in linear time on every LR(k) grammar without using lookahead

AbstractA new general context-free parsing algorithm is presented which runs in linear time and space on every LR(k) grammar without using any lookahead and without making use of the LR property. Most of the existing implementations of tabular parsing algorithms, including those using lookahead, can easily be adapted to this new algorithm without a noteworthy loss of efficiency. For some natural right recursive grammars both the time and space complexity will be improved from Ω(n2) to O(n). This makes this algorithm not only of theoretical but probably of practical interest as well