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 . 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), (C#, Java), (C, C++, Java, Python, C#, Objective-C), pyparsing (Python) e Spirit (C++, parte da biblioteca Boost).