Shift-Reduce Parsers for Transition Networks

We give a new direct construction of the shift-reduce ELR(1) parsers for recursive Transition Networks (TN), which is suitable for languages specified by Extended BNF grammars (EBNF). Such parsers are characterized by their absence of conflicts, not just the classical shiftreduce and reduce-reduce types, but also a new type named convergence conflict. Such a condition is proved correct and is more general than the past proposed conditions for the shift-reduce parsing of EBNF grammars or TN’s. The corresponding parser is smaller than a classical one, without any extra bookkeeping. A constraint on TN’s is mentioned, which enables top-down deterministic ELL (1) analysis.