Parsing Reflective Grammars

Abstract

Existing technology can parse arbitrary context-free grammars, but only a single, static grammar per input. In order to support more powerful syntax-extension systems, we propose reflective grammars, which can modify their own syntax during parsing. We demonstrate and prove the correctness of an algorithm for parsing reflective grammars. The algorithm is based on Earley's algorithm, and we prove that it performs asymptotically no worse than Earley's algorithm on ordinary context-free grammars.

Related Papers

• → Generalized LR Parsing Algorithm for Grammars with One-Sided Contexts(2016)16 cited
• → Efficient Earley Parsing with Regular Right-hand Sides(2010)11 cited
• → Parsing reflective grammars(2011)10 cited
• → Derivative grammars: a symbolic approach to parsing with derivatives(2019)9 cited