Analisador sintático LR

Um analisador sintático LR (também chamado parser LR) é um algoritmo de análise sintática para gramáticas livres de contexto. Ele lê a entrada de texto da esquerda para a direita e produz uma derivação mais à direita (por isso LR, do termo em inglês left-right, diferente do analisador sintático LL). Outro termo usado é analisador sintático LR(x), no qual $x$ refere-se à quantidade de símbolos posteriores ao símbolo atual (ainda não consumidos da entrada) que são usados para tomar decisões na análise. Geralmente esse valor é 1, sendo omitido. Uma gramática livre de contexto é chamada LR(x) se existe uma analisador sintático LR(x) para ela.

Um analisador sintático LR é dito um analisador sintático de ascendente (bottom-up) pois ele tenta deduzir as produções da gramática a partir dos nós folha da árvore. Várias linguagens de programação são descritas por uma gramática LR(1), ou pelo menos parecida, e por isso os analisadores sintáticos LR são geralmente usados por compiladores para realizar a análise sintática do código fonte. Uma exceção notável é a linguagem de programação C++.

Os analisadores sintáticos LR podem ser implementados muito eficientemente, o que é muito útil para compiladores, por exemplo. Raramente são produzidos manualmente, sendo geralmente construídos por um gerador de análise sintática ou um compilador de compiladores. Dependendo da forma como a tabela de análise sintática é gerada, o analisador é chamado SLR (simples), LALR (quando há análise de símbolos posteriores) e canônico (ou LR(1)). Os analisadores LALR podem lidar com mais tipos de gramáticas que o SLR; o canônico pode lidar com mais tipos de gramáticas que o LALR.

Arquitetura

Caso geral

O analisador sintático é uma máquina de estado finito que consiste de:

um buffer de entrada;
uma pilha no qual é armazenada uma lista de estados anteriores;
uma tabela de próximo estado que indica para onde o novo estado deve se mover;
uma tabela de ação que indica uma regra gramatical a aplicar no estado e símbolo atual na entrada de dados.

Algoritmo

O algoritmo do analisador sintático LR é definido como:

A pilha é inicializada com [0]. O estado atual será sempre o estado no topo da pilha.
Dado o estado atual e o símbolo atual na entrada, uma ação é procurada na tabela de ação:
- uma mudança de estado sn:
  - o símbolo terminal atual é removido da entrada
  - o estado n é inserido na pilha (tornando-se o estado atual)
- uma redução rm:
  - o número m é escrito no fluxo de saída
  - para cada símbolo à direita da regra m, um estado é removido da pilha
  - dado o então estado atual no topo da pilha e a regra m, um novo estado é procurado na tabela de próximo estado, tornando-se o estado atual ao ser inserido na pilha
- uma aceitação: a cadeia de caracteres é aceita
- sem ação: um erro de sintaxe é retornado
O passo 2 é repetido até que a haja uma aceitação ou um erro de sintaxe.

Exemplo

A gramática abaixo será usada para o exemplo a seguir. Ela trata expressões matemáticas, no qual é aceito somas e multiplicações entre uns e zeros.

(1) E → E * B

(2) E → E + B

(3) E → B

(4) B → 0

(5) B → 1

deve-se analisar sintaticamente a seguinte entrada:

1 + 1

Tabelas de ação e próximo estado

	ação					próximo estado
estado	*	+	0	1	$	E	B
0			s1	s2		3	4
1	r4	r4	r4	r4	r4
2	r5	r5	r5	r5	r5
3	s5	s6			acc
4	r3	r3	r3	r3	r3
5			s1	s2			7
6			s1	s2			8
7	r1	r1	r1	r1	r1
8	r2	r2	r2	r2	r2

A tabela de ação é classificada por um estado do analisador sintático e um símbolo terminal (incluindo o terminal especial $ que indica o final da entrada de dados) e contém três tipos de ações:

mudança de estado (shift), escrito sn e indicando que o próximo estado é n
redução (reduce), escrito rm e indicado que a redução com a regra gramatical m deve ser feita
aceitação (accept), escrito acc e indicando que o analisador sintático aceita a entrada de dados

A tabela de próximo passo é classificada por um estado do analisador sintático e por um símbolo não terminal. Ela indica qual o próximo estado do analisado se um símbolo não-terminal foi reconhecido.

Procedimento de análise

A tabela abaixo ilustra cada passo do processo. Aqui o estado refere-se ao elemento no todo da pilha (mais à direita), e a próxima ação é determinada referindo-se à tabela de ação acima. Notar que um $ é adicionado no final da entrada de dados para indicar o fim do texto.

Estado	Entrada de dados	Saída de dados	Pilha	Próxima ação
0	1+1$		[0]	mudança de estado para 2
2	+1$		[0,2]	reduz 5
4	+1$	5	[0,4]	reduz 3
3	+1$	5,3	[0,3]	mudança de estado para 6
6	1$	5,3	[0,3,6]	mudança de estado para 2
2	$	5,3	[0,3,6,2]	reduz 5
8	$	5,3,5	[0,3,6,8]	reduz 2
3	$	5,3,5,2	[0 3]	aceita

O estado inicial do analisador é sempre 0, armazenado na pilha. O primeiro valor terminal encontrado pelo parser é 1, e de acordo com a tabela de ação deve haver uma mudança de estado para 2. No estado 2 a tabela de ação indica que qualquer terminal que apareça, deve-se realizar uma redução com a regra gramatical 5. Por isso escreve-se 5 da saída de dados, retira-se um estado da pilha e adiciona-se na pilha o estado da tabela de próximo estado (que no caso é 4).

Apesar disso a tabela de ação do estado 4 indica que deve-se realizar uma redução com a regra 3. Então escreve-se 3 na saída de dados, retira-se um estado da pilha, encontra-se um novo estado na tabela de próximo estado (que no caso é 3).

O próximo terminal no parser é +, e de acordo com a tabela de ação deve-se ir para o estado 6. O próximo terminal é 1, significando que deve-se realizar uma mudança para o estado 2. Assim como o 1 anterior, é feita uma redução para B, indo-se para o estado 8. Nesse estado sempre é feita uma redução pela regra 2.

Finalmente é lido o terminal $ da entrada de dados, o que significa que, de acordo com a tabela de ação (o estado atual é 3), o analisador sintático aceita a entrada de dados.