A Type-Directed Algorithm to Generate Random Well-Formed Parsing Expression Grammars - Cardoso, Elton Maximo; Pereira, Daniel Freitas; De Paula, Regina Sarah Monferrari Amorim; Reis, Leonardo Vieira Dos Santos; Ribeiro, Rodrigo Geraldo (Anais do Simpósio Brasileiro de Linguagens de Programação (SBLP); 2022: Anais do XXVI Simpósio Brasileiro de Linguagens de Programação, 2022)
PEGs are recognition formalism proposed by Brian Ford to describe top-down recursive parsers. Unfortunately, to determine whether an arbitrary PEG will terminate when parsing an input is undecidable. As termination is a desired property for parsing tools, Ford proposes a well-formedness test that guarantees every PEG that satisfies it, terminates on any input. Therefore, when experimenting with PEG-based tools using property-based testing, it is mandatory to randomly generate only well-formed PEGs, since a naive generation strategy may lead a PEG-based parser into an infinite loop. To overcome that, we propose an algorithm for generating well-formed PEGs, prove its correctness and implement it as a library in the Racket programming language.