YAGLR: Yet Another Generalized LR Parser

We have developed a new generalized LR parsing algorithm called YAGLR. The parsing algorithm uses graph-structure stacks similar to Tomita's algorithm, but the merge operations on the graph-structure stack is more deeper. Since YAGLR has an effective merge operations, the speed in parsing time and the reduction in memory space are remarkable. Because of YAGLR's effective merge operations, even if tree-structure stacks are used in YAGLR instead of graph-structure stack, this will not cause heavy loss of memory space and still the compactness and reduction of memory space is retained. The realization of tree-structure stack is more simpler than graph-structure stack which is one of the important factor for the implimentation of YAGLR. YAGLR's parsing time is in the order of Ω(n3) for any CFG. We also present the experimental results which supports this fact. We conclude that YAGLR has advantages of both Earley's and Tomita's algorithm.