Practical nondeterministic DR(k) parsing on graph-structured stack

Abstract

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) grammars, 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 algorithm (for non-LR(k) grammars). Then, it discusses the corresponding adaptation of the GSS algorithm and shows how the shared forest computation is naturally handled.