|
Analisador sintático descendente recursivoUm 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, 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). Referências
Ver também |
