Pest control: A formal model of the Pest parser generator

Parsing expressions grammars (PEGs) are a recognition-based formalism for parsers, which has been gaining popularity because they avoid some problems present in context-free grammar based specifications. In the context of the Rust programming language, the most used PEG-based parser generator is Pest. An interesting feature of Pest grammars is that they support new operators for repetition and handling an implicit stack during parsing. In this work, we propose a formalization of these new constructs and extend a type inference algorithm which guarantee that all well-typed Pest-style grammars do not loop on inputs.