Novas Técnicas para Analisadores Sintáticos Tipo Matriz de Transição
Autores
|
3652 |
Estevam Gilberto de Simone
|
16,14
|
|
3653 |
16,14
|
Informações:
Publicações do PESC
O método de análise sintática por matrizes de transição proposto por [Gries, 68] é totalmente reelaborado. É proposta uma definição equivalente pata a classe de gramáticas reconhecida pelo método. É fornecido um algoritmo construtor mais eficiente para as tabelas de controle do analisador. É alterada a definição das funções que controlam o analisador e fornecido seu novo algoritmo. Estas novas funções são representáveis em tabelas que permitem determinar seus pontos inacessíveis e são fornecidos algoritmos de compactação das tabelas que permitem reduzir grandemente o espaço ocupado, preservado o formato matricial.
Paralelamente é desenvolvido um algoritmo de recuperação de erros que permite uma recuperação sofisticada e precisa, sem utilizar informação adicional às tabelas do analisador, sem degradar o desempenho do analisador para programas corretos e corrigindo de alguma forma as imprecisões na detecção do erro pelo analisador.
Demonstra-se que as tabelas originais de um analisador de gramáticas por matrizes de transição são menores que suas correspondentes para gramáticas SLR (1) e que o analisador por matrizes de transição é mais rápido que o correspondente analisador SLR(1).
Transition matrices have been used in parsing, since the method was proposed by [Gries, 68]. We present here a completely new version of the method, with a new equivalent definition for the class of grammars accepted.
New, more efficient algorithms are presented both for parsing and for the construction of the parsing tables. The control functions are redefined, and allow the determination of inaccesible points and table compression.
In parallel, an algorithm for error recovery is presented which results in a sophisticate and accurate recovery, which need no information besides the one in the parsing tables, and which introduces no degradation of the performance in the parser.
It is shown that the original tables of the transition matrix parser are srnaller than the corresponding sLR(1) parsers, and also faster.