A Type-Directed Algorithm to Generate Random Well-Formed Parsing Expression Grammars

• Elton Maximo Cardoso UFOP
• Daniel Freitas Pereira UFJF
• Regina Sarah Monferrari Amorim De Paula UFJF
• Leonardo Vieira Dos Santos Reis UFJF
• Rodrigo Geraldo Ribeiro UFOP

Resumo

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.

Palavras-chave: type-system, PEG, program-generation