SLL(k) analysis in Byacc EVALUATED

Detalhes: 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.

Discussão: novembro 9, 2018, 10:30

Publicação

Obra sujeita a Direitos de Autor

Orientação

AUTOR

Jorge Manuel Mendes Macêdo (ist170035)

ORIENTADOR

Pedro Manuel Guerra e Silva Reis dos Santos

Departamento de Engenharia Informática (DEI)

Professor Auxiliar