Analisador Shift-Reduce
O analisador decide a cada passo qual das quatro ações possíveis deve ser executada.
Essas ações são:
-
Shift (Empilhar): O analisador empilha o primeiro símbolo do buffer de entrada para o topo da pilha.
-
Reduce (Reduzir): O analisador encontrou um handle no topo da pilha. Ele desempilha os símbolos do handle e empilha o não-terminal correspondente do lado esquerdo da produção.
-
Accept (Aceitar): A análise foi bem-sucedida. Isso ocorre quando o buffer de entrada está vazio e a pilha contém apenas o símbolo inicial da gramática.
-
Error (Erro): O analisador chega a um estado em que nenhuma das ações acima pode ser executada. Isso significa que a cadeia de entrada não pertence à linguagem gerada pela gramática (erro de sintaxe).
Exemplo (com tabela de análise)
Vamos analisar a cadeia id * id usando a mesma gramática do exemplo anterior.
Note
Para a análise, usamos um símbolo
$para marcar o fim da pilha e da entrada.
| Pilha | Entrada (Buffer) | Ação | Justificativa |
|---|---|---|---|
$ | id * id $ | Shift | A pilha está vazia, a única ação é mover o id para a pilha. |
$ id | * id $ | Reduce ( | O id no topo da pilha é um handle para F. |
$ F | * id $ | Reduce ( | F no topo da pilha é um handle para T. |
$ T | * id $ | Shift | T não forma um handle completo com *. Empilhamos *. |
$ T * | id $ | Shift | Empilhamos o id para tentar formar um handle. |
$ T * id | $ | Reduce ( | id no topo da pilha é um handle para F. |
$ T * F | $ | Reduce ( | A sequência T * F no topo da pilha é um handle para T. |
$ T | $ | Reduce ( | T no topo da pilha é um handle para E. |
$ E | $ | Accept | A entrada está vazia e a pilha contém o símbolo inicial E. |