Bounded-connect noncanonical discriminating-reverse parsers

Abstract

The precision of right-hand context covering for conflict resolution is improved over previous NDR parsers, resulting in acceptation of wider subsets of LR-regular and LR-nonregular grammars, including all LALR(k) grammars for a given k. Parser generation combines a new form of DR items and subgraph connections of bounded length, without the need to implement subgraph copies. The NDR parser, whose algorithm remains essentially unchanged, is presented as an extended two-stack pushdown automaton. The technique is illustrated with a detailed example.