Analisador sintático GLR
O analisador sintático GLR (do inglês "Generalized Left-to-right Rightmost derivation parser") é uma extensão do analisador sintático LR que trata do problema do não determinismo em gramáticas ambíguas. Foi introduzido por Masaru Tomita no seu artigo publicado em 1984[1][2]. Este também pode ser encontrado na literatura com o nome de "analisador sintático paralelo" (do inglês parallel parser).
Apesar do algoritmo ser uma adaptação do analisador sintático LR, os princípios da versão original continuam os mesmos. O objetivo de Tomita era reconhecer texto em linguagem natural de maneira completa e efetiva. O analisador sintático LR tradicional não consegue lidar com o não determinismo e a natureza ambígua das linguagens naturais. Nestes casos o analisador sintático GLR ser utilizado sem problemas.
O Algoritmo [3] editar
Em suma o algoritmo do analisador GLR funciona de maneira similar ao algoritmo implementado pelo seu antecessor, o LR. A diferença entre este algoritmo e seu antecessor é que no primeiro, dada uma gramática particular, ele irá processar todas as possíveis interpretações da entrada utilizando uma abordagem de busca em largura. Por outro lado um gerador de analisadores sintáticos GLR converte a gramática de entrada em tabelas sintáticas de maneira similar ao gerador LR tradicional. Porém, enquanto uma tabela sintática gerada por um analisador LR permite apenas um único estado de transição, a tabela sintática gerada pelo analisador GLR permite vários estados de transições. Na realidade, a abordagem do GLR permite a ocorrência de conflitos para mudança de estado/redução e redução/redução.
Quando uma transição conflitante é encontrada a pilha do analisador é dividida em duas ou mais pilhas, onde o estado corresponde a cada possível transição está no topo de cada sub-pilha. Então, a próxima marca contida na entrada é lida e usada para determinar a próxima transição no topo de cada uma das sub-pilhas, além disso o processo de divisão pode acontecer novamente. Se nenhum estado no topo da pilha e a marca da entrada resultarem em, pelo menos, uma transição então o caminho percorrido na tabela do analisador é inválido e pode ser descartado.
Vantagens editar
Quando implementado com cuidado, o algoritmo do GLR tem a mesma complexidade dos algoritmos CYK e de Earley, ambos com complexidade O(n3).
O algoritmo GLR ainda conta com duas vantagens adicionais:
- O tempo necessário para rodar o algoritmo é proporcional ao grau de não determinismo encontrado na gramática. No caso particular de gramáticas determinísticas o algoritmo roda em ordem O(n), o que não acontece para os algoritmos CYK e de Earley.
- O algoritmo GLR pode ser considerado um algoritmo on-line, isso quer dizer que ele consome as marcas da entrada numa ordem especifica e a gasta a maioria do tempo de processamento após o consumo de cada marca.
Na prática, a maioria das linguagens de programação são determinísticas ou a maior parte de suas instruções são determinísticas. Isso quer dizer que qualquer não-determinismo pode ser resolvido com um pequeno número de marcas. Comparado com os outros algoritmos que lidam com as gramáticas livre de contexto o algoritmo GLR é o que tem o melhor desempenho para as gramáticas em que a maior parte é determinística, isso por que apenas uma pilha estará ativa durante a maior parte do processo de análise sintática.
Implementações editar
Referências editar
- ↑ Tomita, Masaru (1984). «LR parsers for natural languages». COLING. 10th International Conference on Computational Linguistics. pp. 354–357
- ↑ Tomita, Masaru (1985). «An efficient context-free parsing algorithm for natural languages». IJCAI. International Joint Conference on Artificial Intelligence. pp. 756–764
- ↑ Grune, Dick e Jacobs, Ceriel J.H (2008). Parsing Techniques. A Practical Guide. [S.l.]: Springer Science+Business Media. ISBN 978-0-387-20248-8