Minhas Aventuras com "Parsing": LR Parser (parte 2)

Continuando a minha descrição do LR parser, vejamos a sua arquitetura e o algorítimo básico. Um LR Parser é normalmente implementado como um autômato descendente (ou autômato com pilha), que é (digamos) uma máquina de estados "turbinada" com uma pilha, movido por duas tabelas.


O esquema acima (adaptado da Wikipedia) mostra os principais componentes:

• Um buffer de entrada, onde são armazenados o terminal sendo tratado e os terminais seguintes de look ahead. Um terminal especial representa o final da entrada.
  
• Uma pilha, onde são colocados os estado atual (no topo) e os estados anteriores.
• Uma tabela de desvios, usada para determinar qual o próximo estado após o reconhecimento de um não terminal.
  
• Uma tabela de ações, que determina a ação a ser tomada em função do estado atual e do conteúdo do buffer de entrada.

Além de reconhecer se um texto obedece à gramática, o LR parser pode gerar facilmente a redução (lista de regras usadas no reconhecimento). Entretanto a lista é gerada como uma "redução à esquerda" que deve ser invertida ao final.

Existem quatro tipos de ações a serem tratadas:

• Shift: o terminal atual é consumido (removido do buffer de entrada) e um novo estado (definido na ação) é colocado no topo da pilha (passando a ser o estado atual e empurrando para baixo os estados anteriores).
• Reduce: indica o reconhecimento de uma regra. O número da regra é escrito na saída. Para cada símbolo no lado direito da regra um estado é retirado da pilha. O novo estado é definido através da tabela de desvio, conforme o estado que ficou no topo da pilha e o não terminal que foi reconhecido.
• Sucesso: foi completado o reconhecimento do texto.
• Erro: o texto de entrada não obedece às regras da gramática.
  

O Parser é executado inciando a pilha com o primeiro estado e executando as ações até que seja obtido um sucesso ou erro.

Vejamos um exemplo rápido com a gramática

S -> aA
A -> b
A -> aA

A tabela correspondente é:
Acompanhando a análise de aab:


No próximo post da série vamos ver o trabalho pesado: a geração das tabelas a partir das regras da gramática.