Projeto do Compilador - Analisador Bottom-Up

A análise de baixo para cima começa nos nós de folha de uma árvore e funciona na direção ascendente até atingir o nó raiz. Aqui, começamos a partir de uma frase e, em seguida, aplicamos as regras de produção de maneira inversa para chegar ao símbolo inicial. A imagem abaixo mostra os analisadores bottom-up disponíveis.

Análise Shift-Reduzir

A análise de redução de deslocamento usa duas etapas exclusivas para análise de baixo para cima. Essas etapas são conhecidas como etapa de mudança e etapa de redução.

• Shift step: A etapa de mudança refere-se ao avanço do ponteiro de entrada para o próximo símbolo de entrada, que é chamado de símbolo de mudança. Este símbolo é colocado na pilha. O símbolo deslocado é tratado como um único nó da árvore de análise.

• Reduce step: Quando o analisador encontra uma regra gramatical completa (RHS) e a substitui por (LHS), isso é conhecido como etapa de redução. Isso ocorre quando o topo da pilha contém uma alça. Para reduzir, uma função POP é executada na pilha que sai da alça e a substitui pelo símbolo não terminal LHS.

LR Parser

O analisador LR é um analisador não recursivo, de redução de deslocamento, de baixo para cima. Ele usa uma ampla classe de gramática livre de contexto, o que o torna a técnica de análise de sintaxe mais eficiente. Os analisadores LR também são conhecidos como analisadores LR (k), onde L representa a varredura da esquerda para a direita do fluxo de entrada; R representa a construção da derivação mais à direita ao contrário, e k denota o número de símbolos de antevisão para tomar decisões.

Existem três algoritmos amplamente usados ​​disponíveis para construir um analisador LR:

• SLR (1) - Analisador LR Simples:
  • Funciona na menor classe de gramática
  • Poucos estados, portanto, uma mesa muito pequena
  • Construção simples e rápida
• LR (1) - Analisador LR:
  • Funciona no conjunto completo de gramática LR (1)
  • Gera uma grande tabela e um grande número de estados
  • Construção lenta
• LALR (1) - Analisador Look-Ahead LR:
  • Funciona no tamanho intermediário da gramática
  • O número de estados é o mesmo que em SLR (1)

Algoritmo de análise LR

Aqui, descrevemos um algoritmo de esqueleto de um analisador LR:

token = next_token()

repeat forever
   s = top of stack
   
   if action[s, token] = “shift si” then
      PUSH token
      PUSH si 
      token = next_token()
      
   else if action[s, token] = “reduce A::= β“ then 
      POP 2 * |β| symbols
      s = top of stack
      PUSH A
      PUSH goto[s,A]
      
   else if action[s, token] = “accept” then
      return
      
   else
      error()

LL vs. LR

LL	LR
Faz uma derivação mais à esquerda.	Faz uma derivação mais à direita ao contrário.
Começa com o não terminal raiz na pilha.	Termina com o não terminal raiz na pilha.
Termina quando a pilha está vazia.	Começa com uma pilha vazia.
Usa a pilha para designar o que ainda é esperado.	Usa a pilha para designar o que já é visto.
Constrói a árvore de análise de cima para baixo.	Constrói a árvore de análise de baixo para cima.
Retira continuamente um não-terminal da pilha e empurra o lado direito correspondente.	Tenta reconhecer um lado direito da pilha, abre-o e empurra o não terminal correspondente.
Expande os não terminais.	Reduz os não terminais.
Lê os terminais quando tira um da pilha.	Lê os terminais enquanto os empurra para a pilha.
Pré-encomende a travessia da árvore de análise.	Percurso pós-pedido da árvore de análise.