Adaptable parsing expression grammars
Carregando...
Data
Autor(es)
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Tese de doutorado
Título alternativo
Primeiro orientador
Membros da banca
Vladimir Oliveira Di Iorio
Fernando Magno Quintao Pereira
Mariza Andrade da Silva Bigonha
Martin Alejandro Musicante
Roberto ierusalimchy
Fernando Magno Quintao Pereira
Mariza Andrade da Silva Bigonha
Martin Alejandro Musicante
Roberto ierusalimchy
Resumo
Geradores automático de analisadores sintáticos tem sido usados por mais de 50 anos. Ferramentas tais como o YACC automaticamente geram um analisador sintático a partir de uma definição formal da sintaxe da linguagem, que usualmente é baseada em uma gramática livre do contexto. A principal motivação para geradores automáticos de analisadores sintáticos é garantir que o compilador está correto e que reconhece todas as sentenças da linguagem que se pretende especificar, visto que com uma implementação manual é muito difícil de garantir que todos os programas de uma linguagem serão corretamente analisados. Apesar das vantagens mencionadas acima, geradores automáticos de analisadores sintáticos ainda não suportam linguagens que permitem modificar o seu próprio conjunto de regras dinamicamente. Faltam modelos apropriados para descrever tais linguagens, assim como geradores automáticos de analisadores sintáticos eficientes. Portanto, os analisadores sintáticos dessas linguagens são manualmente implementados. Nessa tese é apresentado o projeto e modelo formal de Adaptable Parsing Expression Grammars (APEG), uma extensão de Parsing Expression Grammar (PEG) que permite a manipulação do conjunto de regras sintáticas durante a análise do programa de entrada. Mostramos, também, que APEG é poderoso o suficiente para definir linguagens que exigem a modificação de seu conjunto de regras dinamicamente e analisadores sintáticos gerados a partir do modelo são eficientes para serem usado na prática.
Abstract
Parser generators have been used for more than 50 years. Tools like YACC can automatically build a parser from a formal definition of the syntax of a language, usually based on context-free grammars (CFG). The main motivation for automatic parser generation is compiler correctness and recognition completeness, since with manual implementation it is very difficult to guarantee that all programs in a given language will be correctly analysed. Despite the advantagens mentioned above, the technology of automatic parser generation is still not available for languages that allow on-the-fly modifications on their own set of grammar rules. There is a lack of appropriate formal models for describing the syntax of these languages, therefore efficient parsers may not be automatically generated, requiring handwritting code.In this thesis, we present the design and formal definition of Adaptable Parsing Expression Grammars (APEG), an extension to the Parsing Expression Grammar (PEG) model that allows the modification of production rules during the analysis of an input string. We also show that APEG is capable to define languages that require on-the-fly modifications and allows automatic generation of parsers that are reasonably efficient to be used in practice.
Assunto
Compiladores (Computadores), Computação, Linguagem de programação (Computadores) Sintaxe
Palavras-chave
Gramáticas adaptáveis, PEG, Análise sintática, Sinaxe, APEG