Please use this identifier to cite or link to this item: https://hdl.handle.net/1822/64257

TitleExtending the BiYacc framework with ambiguous grammars
Author(s)Macedo, José Nuno Castro de
Advisor(s)Saraiva, João
Mendes, Jorge Cunha
Issue date2018
Abstract(s)Contrarily to most conventional programming languages where certain symbols are used so as to create non-ambiguous grammars, most recent programming languages allow ambiguity. This results in the necessity for a generic parser that can deal with this ambiguity without loss of performance. Currently, there is a GLR parser generator written in Haskell, integrated in the BiYacc system, developed by Departamento de Informática (DI), Universidade do Minho (UM), Portugal in collaboration with the National Institute of Informatics, Japan. In this thesis, this necessity for a generic parser is attacked by developing disambiguation filters for this system which improve its performance, as well as by implementing various known optimizations to this parser generator. Finally, performance tests are used to measure the results of the developed work.
Contrariamente às linguagens de programação mais convencionais em que certos símbolos eram utilizados por forma a criar gramáticas não ambíguas, as linguagens mais recentes permitem ambiguidade, que por sua vez cria a necessidade de um parser genérico que consiga lidar com esta ambiguidade sem grandes perdas de performance. Atualmente, existe um gerador de parsers GLR em Haskell integrado no sistema BiYacc, desenvolvido pelo DI, UM, Portugal, em colaboração com o National Institute of Informatics, Japão. Nesta tese, são desenvolvidos filtros de desambiguidade para este sistema que aumentam a sua performance, assim como são feitas otimizações a vários níveis e se implementa um gerador de parsers usando um algoritmo GLL, que poderá trazer várias vantagens a nível de performance comparativamente com o algoritmo GLR atualmente implementado. Finalmente, são feitos testes de performance para avaliar os resultados do trabalho desenvolvido.
TypeMaster thesis
DescriptionDissertação de mestrado em Computer Science
URIhttps://hdl.handle.net/1822/64257
AccessOpen access
Appears in Collections:BUM - Dissertações de Mestrado
DI - Dissertações de Mestrado

Files in This Item:
File Description SizeFormat 
José-Nuno-Castro-de-Macedo-dissertacao_a72424.pdf461,29 kBAdobe PDFView/Open

Partilhe no FacebookPartilhe no TwitterPartilhe no DeliciousPartilhe no LinkedInPartilhe no DiggAdicionar ao Google BookmarksPartilhe no MySpacePartilhe no Orkut
Exporte no formato BibTex mendeley Exporte no formato Endnote Adicione ao seu ORCID