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
Publicado
03/10/2022
CARDOSO, Elton Maximo; PEREIRA, Daniel Freitas; DE PAULA, Regina Sarah Monferrari Amorim; REIS, Leonardo Vieira Dos Santos; RIBEIRO, Rodrigo Geraldo. A Type-Directed Algorithm to Generate Random Well-Formed Parsing Expression Grammars. In: SIMPÓSIO BRASILEIRO DE LINGUAGENS DE PROGRAMAÇÃO (SBLP), 26. , 2022, Uberlândia. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2022 . p. 8–14.