A new approach to parse context-free grammars is presented. It relies on discriminating-reverse, DR(
k), parsers, with a Tomita-like nondeterminism-controlling graph-structured stack (GSS) algorithm.
The advantage of this generalized discriminating-reverse (GDR) approach over GLR lies on the possibility of using DR(k) parsers, which combine full LR(k) parsing power with a small number of states even for k > 1.
This can greatly reduce nondeterminism originating from limited parsing power, as it is typical of the restricted direct LR
parsers (SLR, LALR) commonly used in Tomita’s algorithm.
Furthermore, relying on a DR parser allows a GSS that associates nodes to symbols instead of direct-LR states, and makes easier
computation of the shared forest.
Moreover, DR(k) parsers have been shown to be linear for LR(k) gram- mars, and the DR(k) parser efficiency has been practically found to be very similar to direct LR(k) parsers.
The paper first presents the nondeterministic DR(k) generation algo- rithm (for non-LR(k) grammars). Then, it discusses the corresponding adaptation of the GSS algorithm and shows how the shared forest com- putation
is naturally handled.