Please use this identifier to cite or link to this item: http://hdl.handle.net/1843/ESBF-9TELDQ
Type: Tese de Doutorado
Title: Adaptable parsing expression grammars
Authors: Leonardo Vieira dos Santos Reis
First Advisor: Roberto da Silva Bigonha
First Co-advisor: Vladimir Oliveira Di Iorio
First Referee: Vladimir Oliveira Di Iorio
Second Referee: Fernando Magno Quintao Pereira
Third Referee: Mariza Andrade da Silva Bigonha
metadata.dc.contributor.referee4: Martin Alejandro Musicante
metadata.dc.contributor.referee5: Roberto ierusalimchy
Abstract: 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.
Subject: Compiladores (Computadores)
Computação
Linguagem de programação (Computadores) Sintaxe
language: Inglês
Publisher: Universidade Federal de Minas Gerais
Publisher Initials: UFMG
Rights: Acesso Aberto
URI: http://hdl.handle.net/1843/ESBF-9TELDQ
Issue Date: 17-Nov-2014
Appears in Collections:Teses de Doutorado

Files in This Item:
File Description SizeFormat 
leonardovieiradossantosreis.pdf2.96 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.