RNGSGLR: Generalization of the Context-Aware Scanning Architecture for All Character-Level Context-Free Languages

Abstract

The limitations of traditional parsing architecture are well known. Even when paired with parsing methods that accept all context-free grammars (CFGs), the resulting combination for any given CFG accepts only a limited subset of corresponding character-level context-free languages (CFL). We present a novel scanner-based architecture that for any given CFG accepts all corresponding character-level CFLs. It can directly parse all possible specifications consisting of a grammar and regular definitions. The architecture is based on right-nulled generalized LR (RNGLR) parsing and is a generalization of the context-aware scanning architecture. Our architecture does not require any disambiguation rules to resolve lexical conflicts, it conceptually has an unbounded parser and scanner lookahead and it is streaming. The added robustness and flexibility allow for easier grammar development and modification.

Keywords

• context-aware scanning
• pseudo-scannerless parsing
• scanner conflict resolution
• generalized LR (GLR)
• right-nulled GLR (RNGLR)
• scannerless GLR (SGLR)