Dissertação

{en_GB=SLL(k) analysis in Byacc} {} EVALUATED

{pt=O Byacc é uma ferramenta de geração de analisadores sintáticos, que é bastante utilizada e conhecida devido à técnica de análise que o seu analisador faz, o LALR(1), que consegue aceitar uma ampla gama de gramáticas. No entanto, o processo de análise feito pelo seu analisador LALR(1), requer muita memória para suas tabelas de análise e para as suas máquinas de estados, levando a ter uma velocidade de processamento de análise mais baixa quando comparada com um analisador do tipo LL. A solução apresentada nesta tese corresponde à adaptação da ferramenta Byacc, a fim de passar a gerar um analisador SLL(k) em vez do tradicional, LALR(1), onde o k irá corresponder ao tamanho de antevisão para resolver o problema da factorização que os analisadores do tipo LL têm. Esta tese explica porquê que Byacc foi escolhido para ser adaptado e ainda as diferenças entre estas técnicas de análise, a fim de ser possível depois montar uma arquitetura que alcance a solução pretendida. De seguida, é revelado cada algoritmo usado durante a fase de desenvolvimento e como foram resolvidos alguns problemas, como o cálculo do conjunto FIRSTk e FOLLOWk. No final, são explicados alguns testes feitos ao analisador SLL(k) e comparados com o analisador LALR(1), onde será concluído quanta memória o SLL(k) poderá reduzir e quão rápido o SLL(k) implementado foi, em comparação com a tradicional LALR(1). Os utilizadores do Byacc ganharão uma melhoria quer de velocidade como também de memória, desde que a gramática usada não tenha recursões à esquerda., en=The Byacc is a parser generator tool that is quite used and known due the parser technique that its parser does, the LALR(1), that can accept a wide range of grammars. However, the parsing process done by the LALR(1) parser requires too much memory for its tables and its state machines, leading to a lower parsing process speed when compared with an LL parser. The solution presented in this thesis is about the adaptation of the Byacc tool, in order to generate an SLL(k) parser instead of the traditional LALR(1) parser, where the k will be the length of the lookahead to resolve the factorization problem that LL parser has. This thesis explains why Byacc was chosen to be adapted and the differences between these parsing techniques, in order to be able to build an architecture that achieves the goal solution. Then, each algorithm used during the development phase is shown and how some issues are addressed, like the calculation of the FIRSTk and FOLLOWk set. At the end, some SLL(k) parser tests are revealed and compared them with the LALR(1) parser, where will be concluded how much memory the SLL(k) could reduce and how much faster the SLL(k) implementation is, compared to the traditional LALR(1). The Byacc users will still continue to use the tool as before, gaining an improvement of speed and also with memory, as long as the grammar used does not have left-recursions.}
{pt=Byacc, SLL(k), FIRST$_k$, FOLLOW$_k$, Máquina de estados, Tabela de Análise SLL$^1$(k), en=Byacc, SLL(k), FIRST$_k$, FOLLOW$_k$, DFA, SLL$^1$(k) Parsing table}

Novembro 9, 2018, 10:30

Publicação

Obra sujeita a Direitos de Autor

Orientação

ORIENTADOR

Pedro Manuel Guerra e Silva Reis dos Santos

Departamento de Engenharia Informática (DEI)

Professor Auxiliar