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

Žiga Leber, Matej Črepinšek, Marjan Mernik and Tomaž Kosar
Additional contact information
Žiga Leber: Faculty of Electrical Engineering and Computer Science, University of Maribor, Koroška cesta 46, 2000 Maribor, Slovenia
Matej Črepinšek: Faculty of Electrical Engineering and Computer Science, University of Maribor, Koroška cesta 46, 2000 Maribor, Slovenia
Marjan Mernik: Faculty of Electrical Engineering and Computer Science, University of Maribor, Koroška cesta 46, 2000 Maribor, Slovenia
Tomaž Kosar: Faculty of Electrical Engineering and Computer Science, University of Maribor, Koroška cesta 46, 2000 Maribor, Slovenia

Mathematics, 2022, vol. 10, issue 14, 1-48

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) (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/14/2436/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/14/2436/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:14:p:2436-:d:861775

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().