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.