Use este identificador para citar ou linkar para este item:
http://hdl.handle.net/1843/ESBF-9TELDQ
Tipo: | Tese de Doutorado |
Título: | Adaptable parsing expression grammars |
Autor(es): | Leonardo Vieira dos Santos Reis |
Primeiro Orientador: | Roberto da Silva Bigonha |
Primeiro Coorientador: | Vladimir Oliveira Di Iorio |
Primeiro membro da banca : | Vladimir Oliveira Di Iorio |
Segundo membro da banca: | Fernando Magno Quintao Pereira |
Terceiro membro da banca: | Mariza Andrade da Silva Bigonha |
Quarto membro da banca: | Martin Alejandro Musicante |
Quinto membro da banca: | 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 |
Idioma: | Inglês |
Editor: | Universidade Federal de Minas Gerais |
Sigla da Instituição: | UFMG |
Tipo de Acesso: | Acesso Aberto |
URI: | http://hdl.handle.net/1843/ESBF-9TELDQ |
Data do documento: | 17-Nov-2014 |
Aparece nas coleções: | Teses de Doutorado |
Arquivos associados a este item:
Arquivo | Descrição | Tamanho | Formato | |
---|---|---|---|---|
leonardovieiradossantosreis.pdf | 2.96 MB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.