Analisador sintático descendente recursivo
Um analisador sintático descendente recursivo é um analisador sintático descendente construído a partir de subrotinas mutualmente recursivas (ou qualquer equivalência não recursiva como uma pilha) em que cada subrotina geralmente implementa uma das regras de produção da gramática. Cada subrotina fica associada a um elemento não-terminal da gramática. Consequentemente, a estrutura do programa resultante se assemelha bastante à gramática que ele reconhece.
Um analisador sintático preditivo (ou analisador sintático preditor) é um analisador sintático descendente recursivo que não requer backtracking. Ele só é possível para a classe de gramáticas LL(k), que são gramáticas livres de contexto para as quais existem algum inteiro positivo k que permite um analisador sintático descendente recursivo para decidir qual produção usar analisando somente os k tokens seguintes na entrada de dados. (Portanto, as gramáticas LL(k) excluem todas as gramáticas ambíguas, assim como todas as gramáticas que contêm recursividade à esquerda. O algoritmo entraria em laço infinito. Qualquer gramática livre de contexto pode ser transformada numa gramática equivalente que não possui recursividade à esquerda, mas a remoção da recursividade a esquerda nem sempre resulta numa gramática LL(k).) Um analisador sintático preditivo possui complexidade linear.
Um analisador sintático descendente com cópia determina qual produção usar por tentativa e erro (por exemplo, diferentes regras com mesmo lado esquerdo, A ::= aB | aC | cD). O algoritmo só retorna ao consumir toda a entrada (sucesso) ou ao esgotar todas as possibilidades de produção (falha). Ele não é limitado às gramáticas LL(k), mas o término não é garantido a menos que a gramática seja LL(k). Mesmo que termine, essa técnica pode levar a complexidade exponencial, e geralmente consome muita memória, o que a torna praticamente inutilizada atualmente.
Apesar dos analisadores sintáticos preditivos serem bastante usados, os programadores geralmente preferem criar analisador LR ou LALR através de geradores de analisador sintáticos sem a transformação da gramática numa forma LL(k).
Geradores de analisadores sintáticos descendentes recursivos incluem JavaCC (para Java), Coco/R (C#, Java), ANTLR (C, C++, Java, Python, C#, Objective-C), pyparsing (Python) e Spirit (C++, parte da biblioteca Boost).
[editar] Ver também
[editar] Referências
- Pedro Sergio Nicolletti. Análise Sintática Parte 2. Material de Aula de Compiladores. Universidade Federal de Campina Grande. Página visitada em 21 de julho de 2008.
- Compilers: Principles, Techniques, and Tools, 1ª ed., Alfred V Aho, Ravi Sethi e Jeffrey D Ullman. Seção 4.4.
- Modern Compiler Implementation in Java, Second Edition, Andrew Appel, 2002, ISBN 0-521-82060-X.
- Recursive Programming Techniques, W.H. Burge, 1975, ISBN 0-201-14450-6
- Crafting a Compiler with C, Charles N Fischer and Richard J LeBlanc, Jr, 1991, ISBN 0-8053-2166-7.
- Compiling with C# and Java, Pat Terry, 2005, ISBN 0-321-26360-X, 624
- Algorithms + Data Structures = Programs, Niklaus Wirth, 1975, ISBN 0-13-022418-9
- Compiler Construction, Jonatan Rugarn, 1996, ISBN 0-201-40353-6
