Analisadores Sintáticos Ascendentes vs Analisadores Sintáticos Descendentes

Analisadores Sintáticos Descendentes

A Análise Descendente é mais fácil de entender e implementar Parte da raiz (não-terminal inicial) e tenta criar a árvore de cima para baixo. Para cada não-terminal, tenta adequar a cadeia de tokens (lida na entrada) a uma de suas produções.O desafio é escolher a produção adequada.Se a produção tiver não-terminais, faz um processo similar para aquele não-terminal.O processo de construção da árvore lembra uma derivação mais à esquerda da cadeia.

Um analisador sintático descendente recursivo é um analisador sintático descendente construído a partir de subrotinas mutuamente recursivas (ou qualquer equivalência não recursiva como uma pilha) em que cada sub-rotina geralmente implementa uma das regras de produção da gramática. Cada sub-rotina 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).

Fonte: Wikipedia

Analisadores Sintáticos Ascendentes

É mais poderosa (aplicável em mais linguagens) que a Descendente. Geralmente, usado apenas em geradores semi-automáticos de parsers.Parte das folhas (tokens) e tenta crescer a árvore até a raiz (símbolo inicial). Para isso, compara a seqüência de símbolos o lado direito (ou corpo) das produções para tentar criar um ramo da árvore. Diz-se que a seqüência é “reduzida” ao não-terminal do lado esquerdo da produção.

...