Projeto do Compilador - Analisador de cima para baixo

Aprendemos no último capítulo que a técnica de análise de cima para baixo analisa a entrada e começa a construir uma árvore de análise a partir do nó raiz, movendo-se gradualmente para os nós folha. Os tipos de análise de cima para baixo são descritos abaixo:

Análise descendente recursiva

A descida recursiva é uma técnica de análise de cima para baixo que constrói a árvore de análise a partir do topo e a entrada é lida da esquerda para a direita. Ele usa procedimentos para cada entidade terminal e não terminal. Essa técnica de análise analisa recursivamente a entrada para fazer uma árvore de análise, que pode ou não exigir rastreamento posterior. Mas a gramática associada a ele (se não for fatorada à esquerda) não pode evitar o retrocesso. Uma forma de análise descendente recursiva que não requer nenhum rastreamento posterior é conhecida comopredictive parsing.

Essa técnica de análise é considerada recursiva, pois usa gramática livre de contexto, que é recursiva por natureza.

Back-tracking

Os analisadores de cima para baixo começam no nó raiz (símbolo de início) e comparam a string de entrada com as regras de produção para substituí-las (se houver correspondência). Para entender isso, pegue o seguinte exemplo de CFG:

S → rXd | rZd
X → oa | ea
Z → ai

Para uma string de entrada: read, um analisador de cima para baixo, se comportará assim:

Ele começará com S nas regras de produção e corresponderá seu rendimento à letra mais à esquerda da entrada, ou seja, 'r'. A própria produção de S (S → rXd) combina com ele. Portanto, o analisador de cima para baixo avança para a próxima letra de entrada (ou seja, 'e'). O analisador tenta expandir o 'X' não terminal e verifica sua produção a partir da esquerda (X → oa). Não corresponde ao próximo símbolo de entrada. Portanto, o analisador de cima para baixo retrocede para obter a próxima regra de produção de X, (X → ea).

Agora, o analisador combina todas as letras de entrada de maneira ordenada. A string é aceita.

Analisador Preditivo

O analisador preditivo é um analisador descendente recursivo, que tem a capacidade de prever qual produção será usada para substituir a string de entrada. O analisador preditivo não sofre retrocessos.

Para realizar suas tarefas, o analisador preditivo usa um ponteiro de antecipação, que aponta para os próximos símbolos de entrada. Para tornar o rastreamento retroativo do analisador livre, o analisador preditivo impõe algumas restrições à gramática e aceita apenas uma classe de gramática conhecida como gramática LL (k).

A análise preditiva usa uma pilha e uma tabela de análise para analisar a entrada e gerar uma árvore de análise. Tanto a pilha quanto a entrada contêm um símbolo de fim$para denotar que a pilha está vazia e a entrada foi consumida. O analisador se refere à tabela de análise para tomar qualquer decisão sobre a combinação de entrada e elemento de pilha.

Na análise descendente recursiva, o analisador pode ter mais de uma produção para escolher para uma única instância de entrada, enquanto no analisador preditivo, cada etapa tem no máximo uma produção para escolher. Pode haver casos em que não haja produção correspondente à string de entrada, fazendo com que o procedimento de análise falhe.

LL Parser

Um analisador LL aceita a gramática LL. A gramática LL é um subconjunto da gramática livre de contexto, mas com algumas restrições para obter a versão simplificada, a fim de obter uma implementação fácil. A gramática LL pode ser implementada por meio de ambos os algoritmos, a saber, descida recursiva ou baseada em tabelas.

O analisador LL é denotado como LL (k). O primeiro L em LL (k) analisa a entrada da esquerda para a direita, o segundo L em LL (k) representa a derivação mais à esquerda e o próprio k representa o número de olhares à frente. Geralmente k = 1, então LL (k) também pode ser escrito como LL (1).

Algoritmo de análise LL

Podemos nos ater ao determinístico LL (1) para explicação do analisador, pois o tamanho da tabela cresce exponencialmente com o valor de k. Em segundo lugar, se uma dada gramática não é LL (1), então geralmente não é LL (k), para qualquer k dado.

É fornecido a seguir um algoritmo para análise LL (1):

Input: 
   string ω 
   parsing table M for grammar G

Output:
   If ω is in L(G) then left-most derivation of ω,
   error otherwise.

Initial State : $S on stack (with S being start symbol)
   ω$ in the input buffer

SET ip to point the first symbol of ω$.

repeat
   let X be the top stack symbol and a the symbol pointed by ip.

   if X∈ Vt or $
      if X = a
         POP X and advance ip.
      else
         error()
      endif
      
   else	/* X is non-terminal */
      if M[X,a] = X → Y1, Y2,... Yk    
         POP X
         PUSH Yk, Yk-1,... Y1 /* Y1 on top */
         Output the production X → Y1, Y2,... Yk 
      else
         error()
      endif
   endif
until X = $	/* empty stack */

Uma gramática G é LL (1) se A → α | β são duas produções distintas de G:

• para nenhum terminal, tanto α quanto β derivam cadeias que começam com a.

• no máximo um de α e β pode derivar string vazia.

• se β → t, então α não deriva nenhuma string começando com um terminal em FOLLOW (A).