• Informações do Trabalho

Titulo Uma abordagem para geração de entradas para PEG usando gramáticas LL(1) Subtítulo Autor THIAGO DO VALE CABRAL Orientador LEONARDO VIEIRA DOS SANTOS REIS Resumo Os analisadores LL(k) são uma classe específica de analisadores para Gramáticas Livres de Contexto (CFGs). Ao contrário das Gramáticas de Expressões de Parsing (PEGs), determinar se uma gramática LL(k) arbitrária terminará uma entrada é um problema decidível. Considerando que gramáticas LL(1) com uma pequena restrição descrevem a mesma semântica quando interpretadas como CFGs e quando interpretadas como PEGs, esta monografia propõe-se a gerar um subconjunto de PEGs bem formadas por meio das gramáticas LL(1). Para tal, é proposta uma implementação de um algoritmo, como uma biblioteca na linguagem de programação Racket, que gere gramáticas LL(1) e suas entradas válidas de forma aleatória por meio do processo de derivação de CFGs. Conclui-se que, ao realizar testes baseados em propriedades e analisar a corretude deste algoritmo, as gramáticas geradas aleatóriamente se classificam como PEGs bem formadas. Palavras-Chave PEG, CFG, LL(1), derivação, gramática