A New Approach to the Construction of Generalized LR Parsing Algorithms

Miguel Angel Alonso Pardo
David Cabrero Souto
Manuel Vilares Ferro

in R. Mitkov, N. Nicolov and N. Nikolov (eds.), Proc. of Recent Advances in Natural Language Processing (RANLP'97) pp. 171-178, Tzigov Chark, Bulgaria, 1997.


We present a Generalized LR parsing algorithm for unrestricted context-free grammars working in complexity O(n3). It differs from previous approaches in the use of dynamic programming techniques to cope with the non determinism, instead of a graph-structured stack. The steps for deriving our algorithm from classical Earley's parsing algorithm are shown.

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