A generalized LR(1) parser for extended context-free grammars

Tomita's Generalized LR(1) parser (GLR) algorithm for CF grammars runs in a linear time onLR(1) grammars and degrades to a polynomial bound otherwise. We address an aspect uncovered by such parsers: to accept Extended CF (ECF) grammars, which contain regular expressions (RE) in the rule right-hand side, also representable by a DFA Transition Net (TN). We define and analyze a new Extended GLR (1) algorithm that combines a recent LR(1) parsing algorithm for TNs with the classic GLR techniques, namely the use of a Graph-Structured Stack to compactly represent different pushdown stacks that evolve in parallel. Our parser is proved correct and is supported by an interactive tool.