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

The paper demonstrates that by a slight change in the Early's algorithm a O(n) time performance for every LR(k) grammar can be obtained without use of lookahead. This was conjectured by Early in his PhD Thesis [Commun. ACM 13, No.2, 94-102 (1970; Zbl 0185.434 (01))]. A new algorithm for recognition of general context-free languages is proposed. Like Early's algorithm it takes \(O(n^ 3)\) time when it runs on general context-free grammars. But it runs in O(n) time and space for the large class of LR regular grammars, (an extension of LR(k) grammars). This is the main theoretical result of the paper and a sketch of its proof is presented. The paper contains also an informal description of the algorithm as well as a comparative example on a simple grammar with this algorithm and Early's algorithm.