Computational model for parsing expression grammars

Abstract: Parsing Expression Grammars (PEGs) have recently gained significant practical relevance, being adopted in compilers such as those for Python and Zig, as well as in parsing libraries for many modern programming languages. Despite their popularity, the computational foundations of PEGs remain less explored than those of classical grammar formalisms.

In this talk, I will present a new computational model for PEGs that extends deterministic pushdown automata. This model enables a structural study of Parsing Expression Languages (PEL): in particular, we show that PELs contain the Boolean closure of the regular closure of deterministic context-free languages (DCFLs) and are closed under left concatenation with this class.

We also propose a two-way variation of the model. For this version, we develop a linear-time simulation algorithm, analogous to Cook’s classical algorithm for two-way DPDAs. These results bridge the gap between theoretical and practical aspects of PEGs, offering a foundation for further complexity-theoretic and algorithmic analysis.

formal languages and automata theory

Audience: researchers in the topic

( paper | slides | video )

One FLAT World Seminar