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).

Referências

Pedro Sergio Nicolletti. «Análise Sintática Parte 2» (PDF). Material de Aula de Compiladores. Universidade Federal de Campina Grande. Consultado em 21 de julho de 2008. Arquivado do original (PDF) em 24 de agosto de 2009
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