Generalized 𝜀-Skip Discriminating-Reverse Parsing on Graph-Structured Stack

Abstract

We introduce εDR automata, which determine next shift-reduce parsing actions from (typically very short) stack-suffix explorations, while avoiding to process e-deriving nonterminals. We present their use with a Tomita-like graph-structured stack parser, resulting in acceptance of the general class of (reduced) context-free grammars.