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.