Construction of Efficient Generalized LR Parsers

Miguel Angel Alonso Pardo
David Cabrero Souto
Manuel Vilares Ferro

to appear in Lecture Notes in Computer Science, Springer-Verlag, Berlin-Heidelberg-New York, 1998.


Abstract

We show how LR parsers for the analysis of arbitrary context-free grammars can be derived from classical Earley's parsing algorithm. The result is a Generalized LR parsing algorithm working at complexity O(n3) in the worst case, which is achieved by the use of dynamic programming to represent the non-deterministic evolution of the stack instead of graph-structured stack representations, as has often been the case in previous approaches. The algorithm behaves better in practical cases, achieving linear complexity on LR grammars. Experimental results show the performance of our proposal.


Miguel Angel Alonso Pardo / alonso@dc.fi.udc.es
David Cabrero Souto / cabrero@dc.fi.udc.es
Manuel Vilares Ferro / vilares@dc.fi.udc.es