Bounded-graph construction for noncanonical discriminating-reverse parsers

Abstract

We present a new approach for the construction of NDR parsers, which defines a new form of items and keeps track of bounded sequences of subgraph connections. This improves the precise recovery of conflicts' right-hand contexts over the basic looping approach, and thus allows to extend the class of accepted grammars. Acceptance of at least all LALR(k) grammars, for a given k, is guaranteed. Moreover, the construction needs no subgraph copies. Since bounded-graph and basic looping constructions onlydi ffer in the accuracyo f the conflicts' right-hand contexts computation, the NDR parsing algorithm remains unchanged.