❧ Parsing LR(0) ❧

Introdução14.1

Na aula anterior, vimos uma forma mecânica de construir um analisador sintático descendente usando LL(1). O parser olhava para o topo da pilha, olhava para o próximo token da entrada e consultava uma tabela para decidir qual produção deveria expandir. Hoje vamos trocar a direção da ideia: em vez de começar pelo símbolo inicial e tentar expandi-lo até chegar à entrada, o analisador LR(0) começa olhando para a própria entrada e tenta descobrir quais pedaços dela já formam o lado direito de alguma produção.

Essa frase parece pesada no início, mas a intuição é simples. O parser LR(0) vai lendo tokens e empilhando informações. Quando percebe que o topo da pilha corresponde ao corpo completo de uma produção, ele reduz esse corpo para o cabeçalho da produção.

Por exemplo, se a gramática tem:

$$ S \to a $$

Se a entrada contém a, o parser pode reconhecer que a forma um S. Então ele reduz:

$$ a \Rightarrow S $$

Essa redução é a operação inversa de uma derivação comum. Em uma derivação normal, partimos de S e chegamos em a. No parsing bottom-up, vemos a na entrada e reconstruímos que aquilo veio de S.

Retomada: o que o LL(1) fazia14.2

Antes de entrar no LR(0), vamos retomar uma gramática pequena usando a estratégia LL(1).

Considere:

$$ \begin{split} S &\to aS \mid b \end{split} $$

Essa gramática gera cadeias com zero ou mais a seguidos por um b final.

Exemplos aceitos:

• b
• ab
• aab
• aaab

No LL(1), a pergunta principal era:

Qual produção devo escolher quando o topo da pilha é um não terminal?

Para isso, calculávamos FIRST e FOLLOW.

$$ FIRST(S) = \{a, b\} $$

Como não há produção vazia, o FOLLOW(S) quase não influencia a escolha das produções neste exemplo.

$$ FOLLOW(S) = \{\$\} $$

A tabela LL(1) fica:

Não terminal	a	b	$
S	$S \to aS$	$S \to b$	erro

Simulando a entrada aab$:

Pilha	Entrada	Ação
$ S	a a b $	usa $S \to aS$
$ S a	a a b $	casa a
$ S	a b $	usa $S \to aS$
$ S a	a b $	casa a
$ S	b $	usa $S \to b$
$ b	b $	casa b
$	$	aceita

Repare no comportamento: o LL(1) tenta prever a estrutura da entrada antes de consumir tudo. Ele expande S para aquilo que espera encontrar.

O LR(0) faz o movimento oposto. Ele consome símbolos e tenta reduzir o que já foi encontrado.

O que significa LR(0)14.3

A sigla LR(0) também descreve o comportamento do analisador.

• O L significa left-to-right. A entrada é lida da esquerda para a direita.
• O R significa rightmost derivation in reverse. O parser reconstrói uma derivação mais à direita, mas de trás para frente.
• O 0 significa que o algoritmo não usa símbolo de lookahead para decidir reduções.

Esse último ponto é importante. O LR(0) decide reduzir apenas olhando para o estado atual do autômato. Ele não consulta o próximo token para decidir se uma redução é apropriada. Por isso, LR(0) é mais simples, mas também mais limitado que SLR, LR(1) e LALR.

A ideia do parser ascendente14.4

Considere a gramática:

$$ S \to aS \mid b $$

Uma derivação comum de aab seria:

$$ \begin{split} S &\Rightarrow aS \\ &\Rightarrow aaS \\ &\Rightarrow aab \end{split} $$

O parser bottom-up tenta fazer o caminho inverso:

$$ \begin{split} aab &\Rightarrow aaS \\ &\Rightarrow aS \\ &\Rightarrow S \end{split} $$

Cada passo inverso é uma redução.

Quando o parser vê b, pode reduzir b para S, porque existe a produção:

$$ S \to b $$

Depois, quando o topo da pilha tem aS, pode reduzir aS para S, porque existe:

$$ S \to aS $$

Então a ideia operacional é:

• empilhar símbolos enquanto ainda não há um corpo completo de produção;
• reduzir quando o topo da pilha corresponde ao lado direito de uma produção;
• aceitar quando tudo foi reduzido ao símbolo inicial e a entrada acabou.

Por que precisamos de estados14.5

Se o parser guardasse apenas símbolos na pilha, ele teria dificuldade para saber em que ponto da gramática está. Por isso, o LR(0) usa uma pilha com estados, que representam conjuntos de possibilidades sobre o progresso da análise. Para construir esses estados, usamos itens LR(0).

Gramática aumentada14.6

O primeiro passo de qualquer construção LR é aumentar a gramática.

Se a gramática original tem símbolo inicial S, criamos um novo símbolo inicial S' e uma nova produção:

$$ S' \to S $$

Essa nova produção serve para marcar o ponto exato em que a análise deve aceitar a entrada. Quando o autômato chegar ao item:

$$ S' \to S \cdot $$

Nesse caso, se a entrada estiver no fim, o parser aceita.

Itens LR(0)14.7

Um item LR(0) é uma produção com um ponto em alguma posição do lado direito. O ponto indica quanto da produção já foi reconhecido.

Considere:

$$ A \to XYZ $$

Os itens possíveis são:

$$ \begin{split} A &\to \cdot XYZ \\ A &\to X \cdot YZ \\ A &\to XY \cdot Z \\ A &\to XYZ \cdot \end{split} $$

Cada posição do ponto tem uma leitura.

Item	Interpretação
$A \to \cdot XYZ$	ainda não reconhecemos nada do corpo
$A \to X \cdot YZ$	já reconhecemos X, falta YZ
$A \to XY \cdot Z$	já reconhecemos XY, falta Z
$A \to XYZ \cdot$	reconhecemos o corpo inteiro, podemos reduzir

Um item completo é aquele em que o ponto está no fim.

$$ A \to \alpha \cdot $$

Esse item indica uma redução pela produção:

$$ A \to \alpha $$

Closure14.8

A função Closure completa um conjunto de itens com todas as possibilidades que ficam implícitas quando o ponto aparece antes de um não terminal.

A regra é:

Se um conjunto contém um item $A \to \alpha \cdot B \beta$ e B é um não terminal, então adicionamos todos os itens $B \to \cdot \gamma$ para cada produção $B \to \gamma$.

Em palavras: se o parser pode precisar reconhecer um B agora, então ele também precisa considerar todas as formas pelas quais B pode começar.

Exemplo de Closure14.8.1

Considere:

$$ \begin{split} S' &\to S \\ S &\to aS \mid b \end{split} $$

Começamos com:

$$ S' \to \cdot S $$

O ponto está antes de S, e S é não terminal. Então adicionamos as produções de S com ponto no início:

$$ \begin{split} S' &\to \cdot S \\ S &\to \cdot aS \\ S &\to \cdot b \end{split} $$

Esse conjunto é o fechamento do item inicial.

Goto14.9

A função Goto(I, X) responde à pergunta:

Se estou no conjunto de itens I e reconheço o símbolo X, para qual conjunto de itens eu vou?

O procedimento tem duas etapas:

• mover o ponto sobre o símbolo X em todos os itens onde X aparece logo depois do ponto;
• aplicar Closure ao conjunto resultante.

Exemplo de Goto14.9.1

Considere o conjunto:

$$ I_0 = \left\{ \begin{array}{l} S' \to \cdot S \\ S \to \cdot aS \\ S \to \cdot b \end{array} \right\} $$

Calculando Goto(I0, a), olhamos para os itens que têm a depois do ponto.

$$ S \to \cdot aS $$

Movemos o ponto:

$$ S \to a \cdot S $$

Como o ponto ficou antes de S, aplicamos Closure e adicionamos as produções de S com ponto no início.

$$ Goto(I_0, a) = \left\{ \begin{array}{l} S \to a \cdot S \\ S \to \cdot aS \\ S \to \cdot b \end{array} \right\} $$

Estrutura da tabela LR(0)14.10

A tabela LR(0) tem duas partes.

Parte	Colunas	Conteúdo
ACTION	terminais e $	shift, reduce, accept ou erro
GOTO	não terminais	número do próximo estado

As ações mais importantes são:

Ação	Notação	Significado
Shift	sN	consome um terminal e empilha o estado N
Reduce	rK	reduz pela produção numerada K
Accept	acc	aceita a entrada
Erro	vazio	não há movimento válido

Para preencher a tabela:

• se existe uma transição por terminal a do estado I para o estado J, colocamos sJ em ACTION[I, a];
• se existe uma transição por não terminal A do estado I para o estado J, colocamos J em GOTO[I, A];
• se o estado contém um item completo $A \to \alpha \cdot$, colocamos a redução $A \to \alpha$ nas colunas de ação;
• se o item completo for a produção aumentada $S' \to S \cdot$, não colocamos redução comum: colocamos acc na coluna $.

No LR(0) puro, uma redução comum entra em todas as colunas de ACTION. Isso acontece porque o LR(0) não usa lookahead para restringir onde a redução pode ser feita. A exceção é a produção aumentada, que marca apenas a aceitação da entrada.

Exemplo 1: gramática mínima14.11

Vamos começar com a menor gramática possível.

$$ S \to a $$

Ela reconhece apenas a cadeia a.

Passo 1: aumentar a gramática14.11.1

Numeramos as produções para facilitar as reduções.

$$ \begin{array}{rcl} (0) & S' & \to S \\ (1) & S & \to a \end{array} $$

Passo 2: construir os estados14.11.2

O item inicial é:

$$ S' \to \cdot S $$

Aplicando Closure:

$$ I_0 = \left\{ \begin{array}{l} S' \to \cdot S \\ S \to \cdot a \end{array} \right\} $$

Agora calculamos as transições.

Com S:

$$ Goto(I_0, S) = I_1 = \left\{ \begin{array}{l} S' \to S \cdot \end{array} \right\} $$

Com a:

$$ Goto(I_0, a) = I_2 = \left\{ \begin{array}{l} S \to a \cdot \end{array} \right\} $$

O autômato tem três estados:

Estado	Itens
I0	$S' \to \cdot S$, $S \to \cdot a$
I1	$S' \to S \cdot$
I2	$S \to a \cdot$

Transições:

Origem	Símbolo	Destino
I0	S	I1
I0	a	I2

Passo 3: montar a tabela14.11.3

Terminais: a, $.

Não terminais: S.

Estado	ACTION a	ACTION $	GOTO S
0	s2		1
1		acc
2	r1	r1

No estado 2, temos o item completo:

$$ S \to a \cdot $$

Por isso a linha recebe r1, que significa reduzir pela produção:

$$ (1)\ S \to a $$

Passo 4: simular a$14.11.4

No LR(0), a pilha guarda estados. Para fins didáticos, também mostraremos os símbolos reconhecidos.

Pilha	Entrada	Ação
0	a $	ACTION[0,a] = s2
0 a 2	$	ACTION[2,$] = r1, reduz $S \to a$
0 S 1	$	ACTION[1,$] = acc

Na redução $S \to a$, removemos da pilha o corpo a e seu estado associado. Depois olhamos o estado que ficou no topo, que é 0, e consultamos GOTO[0,S] = 1. Por isso a pilha vira 0 S 1.

Exemplo 2: vários a antes de b14.12

Agora vamos usar a gramática retomada no início da aula.

$$ S \to aS \mid b $$

Ela reconhece cadeias como b, ab, aab e aaab.

Passo 1: aumentar e numerar14.12.1

$$ \begin{array}{rcl} (0) & S' & \to S \\ (1) & S & \to aS \\ (2) & S & \to b \end{array} $$

Passo 2: estado inicial14.12.2

Começamos com:

$$ S' \to \cdot S $$

Como o ponto está antes de S, adicionamos as produções de S.

$$ I_0 = \left\{ \begin{array}{l} S' \to \cdot S \\ S \to \cdot aS \\ S \to \cdot b \end{array} \right\} $$

Passo 3: transições a partir de I014.12.3

Com S:

$$ I_1 = Goto(I_0, S) = \left\{ \begin{array}{l} S' \to S \cdot \end{array} \right\} $$

Com a:

$$ I_2 = Goto(I_0, a) = \left\{ \begin{array}{l} S \to a \cdot S \\ S \to \cdot aS \\ S \to \cdot b \end{array} \right\} $$

Com b:

$$ I_3 = Goto(I_0, b) = \left\{ \begin{array}{l} S \to b \cdot \end{array} \right\} $$

Passo 4: transições a partir de I214.12.4

O estado I2 é:

$$ I_2 = \left\{ \begin{array}{l} S \to a \cdot S \\ S \to \cdot aS \\ S \to \cdot b \end{array} \right\} $$

Com S:

$$ I_4 = Goto(I_2, S) = \left\{ \begin{array}{l} S \to aS \cdot \end{array} \right\} $$

Com a:

$$ Goto(I_2, a) = I_2 $$

Isso acontece porque depois de ler outro a, estamos novamente na situação de precisar reconhecer um S.

Com b:

$$ Goto(I_2, b) = I_3 $$

Passo 5: coleção canônica completa14.12.5

Estado	Itens
I0	$S' \to \cdot S$, $S \to \cdot aS$, $S \to \cdot b$
I1	$S' \to S \cdot$
I2	$S \to a \cdot S$, $S \to \cdot aS$, $S \to \cdot b$
I3	$S \to b \cdot$
I4	$S \to aS \cdot$

Transições:

Origem	Símbolo	Destino
I0	S	I1
I0	a	I2
I0	b	I3
I2	S	I4
I2	a	I2
I2	b	I3

Passo 6: tabela LR(0)14.12.6

Terminais: a, b, $.

Não terminais: S.

Estado	ACTION a	ACTION b	ACTION $	GOTO S
0	s2	s3		1
1			acc
2	s2	s3		4
3	r2	r2	r2
4	r1	r1	r1

As reduções são:

• r1: reduzir por $S \to aS$;
• r2: reduzir por $S \to b$.

Passo 7: simular aab$14.12.7

Entrada:

$$ aab\$ $$

Pilha	Entrada	Ação
0	a a b $	s2
0 a 2	a b $	s2
0 a 2 a 2	b $	s3
0 a 2 a 2 b 3	$	r2, reduz $S \to b$
0 a 2 a 2 S 4	$	r1, reduz $S \to aS$
0 a 2 S 4	$	r1, reduz $S \to aS$
0 S 1	$	acc

Vamos interpretar as reduções finais. Primeiro, o parser leu aab. Quando chegou ao estado 3, reconheceu b como um S.

$$ b \Rightarrow S $$

Depois, o topo tinha aS, então reduziu:

$$ aS \Rightarrow S $$

Depois, de novo havia aS no topo, então reduziu mais uma vez:

$$ aS \Rightarrow S $$

Ao final, tudo virou um único S, e a entrada acabou. Por isso a cadeia foi aceita.

Exemplo 3: recursão à esquerda simples14.13

Um ponto importante do LR(0) é que ele lida naturalmente com recursão à esquerda. Isso é diferente do parser descendente recursivo e do LL(1), que teriam problema direto com uma produção como:

$$ E \to E + n \mid n $$

Essa gramática gera somas de um ou mais números, como:

• n
• n+n
• n+n+n

Ela é recursiva à esquerda porque E aparece no início da produção E -> E + n.

Passo 1: aumentar e numerar14.13.1

$$ \begin{array}{rcl} (0) & E' & \to E \\ (1) & E & \to E + n \\ (2) & E & \to n \end{array} $$

Passo 2: estado inicial14.13.2

$$ I_0 = \left\{ \begin{array}{l} E' \to \cdot E \\ E \to \cdot E + n \\ E \to \cdot n \end{array} \right\} $$

Passo 3: transições14.13.3

De I0, com E:

$$ I_1 = \left\{ \begin{array}{l} E' \to E \cdot \\ E \to E \cdot + n \end{array} \right\} $$

De I0, com n:

$$ I_2 = \left\{ \begin{array}{l} E \to n \cdot \end{array} \right\} $$

De I1, com +:

$$ I_3 = \left\{ \begin{array}{l} E \to E + \cdot n \end{array} \right\} $$

De I3, com n:

$$ I_4 = \left\{ \begin{array}{l} E \to E + n \cdot \end{array} \right\} $$

Passo 4: coleção canônica14.13.4

Estado	Itens
I0	$E' \to \cdot E$, $E \to \cdot E + n$, $E \to \cdot n$
I1	$E' \to E \cdot$, $E \to E \cdot + n$
I2	$E \to n \cdot$
I3	$E \to E + \cdot n$
I4	$E \to E + n \cdot$

Transições:

Origem	Símbolo	Destino
I0	E	I1
I0	n	I2
I1	+	I3
I3	n	I4

Passo 5: tabela LR(0)14.13.5

Terminais: n, +, $.

Não terminal: E.

Estado	ACTION n	ACTION +	ACTION $	GOTO E
0	s2			1
1		s3	acc
2	r2	r2	r2
3	s4
4	r1	r1	r1

As reduções são:

• r1: reduzir por $E \to E + n$;
• r2: reduzir por $E \to n$.

Passo 6: simular n+n$14.13.6

Pilha	Entrada	Ação
0	n + n $	s2
0 n 2	+ n $	r2, reduz $E \to n$
0 E 1	+ n $	s3
0 E 1 + 3	n $	s4
0 E 1 + 3 n 4	$	r1, reduz $E \to E + n$
0 E 1	$	acc

Esse exemplo mostra uma diferença importante em relação ao LL(1). A recursão à esquerda não causa loop no LR(0), porque o parser não tenta expandir E antes de consumir entrada. Ele primeiro lê n, reduz para E, depois continua a partir desse E.

Quando o LR(0) falha14.14

Nem toda gramática pode ser analisada por LR(0). O problema aparece quando um mesmo estado exige duas decisões diferentes para a mesma entrada da tabela. Os conflitos principais são:

Conflito	Significado
shift/reduce	o estado quer empilhar um símbolo e também reduzir
reduce/reduce	o estado quer reduzir por duas produções diferentes

O caso mais comum é shift/reduce. Ele acontece quando um estado contém ao mesmo tempo:

• um item que ainda pode avançar com algum terminal;
• um item completo que manda reduzir.

Como o LR(0) não olha o próximo token para decidir, a redução seria colocada em todas as colunas de ACTION. Se alguma dessas colunas já tinha um shift, aparece conflito.

Comparação entre LL(1) e LR(0)14.15

Aspecto	LL(1)	LR(0)
Direção conceitual	top-down	bottom-up
Leitura da entrada	esquerda para direita	esquerda para direita
Derivação	mais à esquerda	mais à direita ao contrário
Pilha	símbolos esperados	estados e símbolos reconhecidos
Tabela	escolhe produções	escolhe shift, reduce, goto e accept
Base da decisão	FIRST, FOLLOW e lookahead	itens LR(0) e estado atual
Recursão à esquerda	problema	natural
Poder de reconhecimento	menor	maior que LL(1), mas ainda limitado

Roteiro manual para construir uma tabela LR(0)14.16

Quando receber uma gramática, siga sempre a mesma sequência.

1. Aumente a gramática com uma nova produção inicial.
2. Numere as produções.
3. Monte o item inicial com ponto no começo.
4. Calcule o Closure do item inicial para obter I0.
5. Para cada estado, aplique Goto para cada símbolo que aparece depois de algum ponto.
6. Repita até não aparecer nenhum estado novo.
7. Monte a tabela com colunas de ACTION e GOTO.
8. Coloque shift nas transições por terminais.
9. Coloque goto nas transições por não terminais.
10. Coloque reduce nos estados com itens completos.
11. Coloque accept no estado que contém a produção aumentada completa.
12. Simule uma cadeia para testar a tabela.

Exercícios14.17

Exercício 114.17.1

Construa a tabela LR(0) para:

$$ S \to c $$

Depois simule a cadeia:

$$ c\$ $$

Exercício 214.17.2

Construa a tabela LR(0) para:

$$ S \to aS \mid c $$

Depois simule:

$$ aac\$ $$

Exercício 314.17.3

Construa a tabela LR(0) para:

$$ E \to E * n \mid n $$

Depois simule:

$$ n*n\$ $$

Exercício 414.17.4

Considere:

$$ \begin{split} S &\to A \\ A &\to aA \mid b \end{split} $$

Faça:

1. a gramática aumentada;
2. a coleção canônica de itens;
3. a tabela LR(0);
4. a simulação da cadeia aab$.

Resumo14.18

O LR(0) troca a perspectiva do parser. Em vez de prever qual produção deve gerar a entrada, ele observa a entrada e reconstrói quais produções poderiam ter gerado os pedaços já reconhecidos.

Os conceitos principais são:

• a gramática aumentada define o estado de aceitação;
• os itens LR(0) indicam o progresso dentro das produções;
• Closure adiciona possibilidades quando o ponto está antes de um não terminal;
• Goto move o ponto e cria transições entre estados;
• a tabela LR(0) usa ACTION para terminais e GOTO para não terminais;
• shift consome entrada;
• reduce substitui um corpo de produção pelo seu cabeçalho;
• accept termina a análise com sucesso.

O mais importante para a prática é dominar a construção da tabela. Depois que a tabela está pronta, a simulação é mecânica: consultar estado, olhar entrada, aplicar ação e atualizar a pilha.