Towards a discriminating-reverse Tomita-like parser with reduced nondeterminism

Abstract

A new approach to generalized parsing for context-free grammars is presented, which uses an underlying discriminating-reverse, DR(k), parser with a Tomita-like nondeterminism-controlling graph-structured stack, GSS, algorithm. The advantage of the new generalized discriminating-reverse, GDR, approach over GLR would lie 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 may allow to greatly reduce nondeterminism originating from limited parsing power (as it is typical of the restricted form of (direct) LR parsers currently used in Tomita algorithm) and to a further simplification of the GSS by associating nodes to symbols instead of direct-LR states. Moreover, DR(k) parsing time complexity has been shown to be linear for LR(k) grammars, and DR(k) parser efficiency has been practically found to be very similar to direct LR(k) parsers. The paper shows the nondeterministic DR(k) generation algorithm (for non-LR(k) grammars) and the corresponding adaptation of the GSS algorithm.