A New Approach to the Construction of Generalized LR Parsing Algorithms

We present a Generalized LR parsing algorithm for unrestricted context-free grammars working in complexity O(n³). 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.