❧ Parsing SLR(1) ❧

Introdução15.1

Na aula anterior, construímos tabelas LR(0). A ideia era simples: montar um autômato de itens, usar shift quando uma transição por terminal existia, usar goto quando uma transição por não terminal existia e usar reduce quando um item estava completo.

O ponto fraco estava exatamente na última parte. No LR(0), quando um estado contém um item completo, a redução entra em todas as colunas de terminais daquela linha. Isso é forte demais. Às vezes a redução só faz sentido quando o próximo símbolo da entrada pertence a um conjunto específico.

Por isso o SLR(1) é uma pequena melhoria sobre o LR(0). Ele não muda a construção do autômato. Ele muda a forma de preencher as reduções na tabela.

Aquecimento: revisão de LR(0)15.2

Antes de introduzir SLR(1), vamos fazer um exercício curto de LR(0) para retomar a mecânica.

Considere a gramática:

$$ \begin{array}{rcl} (0) & S' & \to S \\ (1) & S & \to BB \\ (2) & B & \to aB \\ (3) & B & \to b \end{array} $$

Essa gramática gera cadeias com dois blocos consecutivos, e cada bloco tem zero ou mais a seguidos de um b.

Exemplos aceitos:

• bb
• abb
• bab
• aababb

Estados do autômato15.2.1

O estado inicial é:

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

As transições a partir de I0 são:

Símbolo	Destino
S	I1
B	I2
a	I3
b	I4

Os demais estados são:

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

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

$$ I_3 = \left\{ \begin{array}{l} B \to a \cdot B \\ B \to \cdot aB \\ B \to \cdot b \end{array} \right\} $$

$$ I_4 = \left\{ \begin{array}{l} B \to b \cdot \end{array} \right\} $$

$$ I_5 = \left\{ \begin{array}{l} S \to BB \cdot \end{array} \right\} $$

$$ I_6 = \left\{ \begin{array}{l} B \to aB \cdot \end{array} \right\} $$

Transições restantes:

Origem	Símbolo	Destino
I2	B	I5
I2	a	I3
I2	b	I4
I3	B	I6
I3	a	I3
I3	b	I4

Tabela LR(0)15.2.2

Terminais: a, b, $.

Não terminais: S, B.

Estado	ACTION a	ACTION b	ACTION $	GOTO S	GOTO B
0	s3	s4		1	2
1			acc
2	s3	s4			5
3	s3	s4			6
4	r3	r3	r3
5	r1	r1	r1
6	r2	r2	r2

Essa gramática funciona em LR(0) porque nenhum estado mistura uma redução comum com um shift, nem duas reduções diferentes na mesma linha.

Onde o LR(0) começa a falhar15.3

Agora vamos usar uma gramática pequena em que o autômato LR(0) produz um conflito shift/reduce.

$$ \begin{array}{rcl} (0) & S' & \to S \\ (1) & S & \to Aa \\ (2) & S & \to bA \\ (3) & A & \to b \end{array} $$

Essa gramática aceita duas cadeias:

• ba, pela derivação $S \Rightarrow Aa \Rightarrow ba$;
• bb, pela derivação $S \Rightarrow bA \Rightarrow bb$.

O estado inicial é:

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

O problema aparece ao ler b a partir de I0:

$$ I_3 = \left\{ \begin{array}{l} S \to b \cdot A \\ A \to b \cdot \\ A \to \cdot b \end{array} \right\} $$

Nesse estado, existem duas ideias ao mesmo tempo.

Item	O que ele sugere
$S \to b \cdot A$ e $A \to \cdot b$	se o próximo símbolo for b, devemos fazer shift
$A \to b \cdot$	o b já pode ser reduzido para A

No LR(0), a redução $A \to b$ entraria em todas as colunas. Mas também existe shift na coluna b. Resultado:

Estado	ACTION a	ACTION b	ACTION $
3	r3	s6 / r3	r3

Esse é um conflito shift/reduce.

Intuitivamente, a decisão correta depende do próximo símbolo:

• se o próximo símbolo é a, a entrada deve ser ba, então reduzimos b para A;
• se o próximo símbolo é b, a entrada deve ser bb, então empilhamos o segundo b;
• se a entrada acabou depois de reconhecer o segundo b, a redução $A \to b$ permite completar $S \to bA$.

O LR(0) não consegue expressar essa distinção porque não olha o próximo símbolo. O SLR(1) olha o próximo símbolo apenas para limitar reduções.

A mudança do SLR(1)15.4

O SLR(1) reaproveita a coleção canônica de itens LR(0). A diferença está na regra de preenchimento das reduções.

No LR(0):

Se o estado contém $A \to \alpha \cdot$, colocamos a redução $A \to \alpha$ em todas as colunas de terminais.

No SLR(1):

Se o estado contém $A \to \alpha \cdot$, colocamos a redução $A \to \alpha$ apenas nas colunas dos terminais em $FOLLOW(A)$.

O 1 em SLR(1) indica que a decisão usa um símbolo de lookahead. Ele não cria itens com lookahead, como o LR(1) completo faria. Ele usa os conjuntos FOLLOW, que já conhecemos do LL(1), como aproximação global dos contextos em que uma variável pode aparecer.

Resolvendo o conflito anterior15.4.1

Para a gramática:

$$ \begin{array}{rcl} S & \to Aa \\ S & \to bA \\ A & \to b \end{array} $$

temos:

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

Como A aparece em $S \to Aa$, o terminal a entra em $FOLLOW(A)$.

Como A aparece no fim de $S \to bA$, tudo de $FOLLOW(S)$ entra em $FOLLOW(A)$.

Logo:

$$ FOLLOW(A) = \{a, \$\} $$

No estado problemático:

$$ I_3 = \left\{ \begin{array}{l} S \to b \cdot A \\ A \to b \cdot \\ A \to \cdot b \end{array} \right\} $$

A redução $A \to b$ só entra nas colunas a e $, porque essas são as colunas de $FOLLOW(A)$.

Estado	ACTION a	ACTION b	ACTION $
3	r3	s6	r3

O conflito desaparece. Mas ainda falta terminar a tabela inteira para confirmar que a gramática ficou analisável por SLR(1).

Terminando o exemplo15.4.2

Com a gramática aumentada e numerada:

$$ \begin{array}{rcl} (0) & S' & \to S \\ (1) & S & \to Aa \\ (2) & S & \to bA \\ (3) & A & \to b \end{array} $$

os estados LR(0) são:

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

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

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

$$ I_3 = \left\{ \begin{array}{l} S \to b \cdot A \\ A \to b \cdot \\ A \to \cdot b \end{array} \right\} $$

$$ I_4 = \left\{ \begin{array}{l} S \to Aa \cdot \end{array} \right\} $$

$$ I_5 = \left\{ \begin{array}{l} S \to bA \cdot \end{array} \right\} $$

$$ I_6 = \left\{ \begin{array}{l} A \to b \cdot \end{array} \right\} $$

As transições são:

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

Os conjuntos FOLLOW já calculados são:

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

$$ FOLLOW(A) = \{a, \$\} $$

Assim, a tabela SLR(1) completa fica:

Estado	ACTION a	ACTION b	ACTION $	GOTO S	GOTO A
0		s3		1	2
1			acc
2	s4
3	r3	s6	r3		5
4			r1
5			r2
6	r3		r3

Agora simulamos ba$:

Pilha	Entrada	Ação
0	b a $	s3
0 b 3	a $	r3, reduz $A \to b$
0 A 2	a $	s4
0 A 2 a 4	$	r1, reduz $S \to Aa$
0 S 1	$	acc

E simulamos bb$:

Pilha	Entrada	Ação
0	b b $	s3
0 b 3	b $	s6
0 b 3 b 6	$	r3, reduz $A \to b$
0 b 3 A 5	$	r2, reduz $S \to bA$
0 S 1	$	acc

Esse exemplo mostra exatamente o ganho do SLR(1): no estado 3, o mesmo b já poderia formar um A, mas a redução só é feita quando o próximo símbolo pertence a $FOLLOW(A)$. Quando o próximo símbolo é outro b, o parser continua empilhando.

Algoritmo SLR(1)15.5

O procedimento completo é:

1. Aumentar a gramática com $S' \to S$.
2. Numerar as produções.
3. Construir a coleção canônica de itens LR(0), usando Closure e Goto.
4. Calcular FOLLOW de todos os não terminais.
5. Preencher ACTION com shift para transições por terminal.
6. Preencher GOTO com transições por não terminal.
7. Para cada item completo $A \to \alpha \cdot$, colocar rK apenas nas colunas de $FOLLOW(A)$.
8. Para o item aumentado $S' \to S \cdot$, colocar acc na coluna $.
9. Se alguma célula tiver mais de uma ação, a gramática não é SLR(1).

O passo novo é o passo 7.

Exemplo completo em SLR(1)15.6

Agora vamos resolver a gramática usada no exercício guiado:

$$ \begin{array}{rcl} (0) & S' & \to S \\ (1) & S & \to (L) \\ (2) & S & \to a \\ (3) & L & \to L,S \\ (4) & L & \to S \end{array} $$

Essa gramática reconhece expressões como:

• a
• (a)
• (a,a)
• ((a),a)

O não terminal S representa uma expressão. O não terminal L representa uma lista de expressões separadas por vírgula.

Coleção canônica de itens15.6.1

Estado inicial:

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

Transições de I0:

Símbolo	Destino
S	I1
(	I2
a	I3

Os estados são:

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

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

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

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

$$ I_5 = \left\{ \begin{array}{l} L \to S \cdot \end{array} \right\} $$

$$ I_6 = \left\{ \begin{array}{l} S \to (L) \cdot \end{array} \right\} $$

$$ I_7 = \left\{ \begin{array}{l} L \to L, \cdot S \\ S \to \cdot (L) \\ S \to \cdot a \end{array} \right\} $$

$$ I_8 = \left\{ \begin{array}{l} L \to L,S \cdot \end{array} \right\} $$

Transições completas:

Origem	Símbolo	Destino
I0	S	I1
I0	(	I2
I0	a	I3
I2	L	I4
I2	S	I5
I2	(	I2
I2	a	I3
I4	)	I6
I4	,	I7
I7	S	I8
I7	(	I2
I7	a	I3

Repare em uma coisa importante: a transição de I2 por ( volta para I2. Isso acontece porque, depois de abrir um novo parêntese, estamos novamente no mesmo tipo de situação: precisamos reconhecer uma lista L dentro dos parênteses.

Conjuntos FOLLOW15.6.2

Agora calculamos os FOLLOW, porque eles serão usados para inserir as reduções.

Começamos com:

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

Pela produção $S \to (L)$, o símbolo ) aparece logo depois de L:

$$ \texttt{)} \in FOLLOW(L) $$

Pela produção $L \to L,S$, o primeiro L é seguido por vírgula:

$$ \texttt{,} \in FOLLOW(L) $$

Ainda em $L \to L,S$, o S aparece no fim da produção, então S herda $FOLLOW(L)$.

Pela produção $L \to S$, o S também aparece no fim da produção, então S herda $FOLLOW(L)$.

Logo:

$$ FOLLOW(L) = \{\texttt{)}, \texttt{,}\} $$

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

Lendo o segundo conjunto: depois de um S, pode aparecer fim da entrada, fecha parêntese ou vírgula.

Tabela SLR(1)15.6.3

Terminais: (, ), a, ,, $.

Não terminais: S, L.

Estado	ACTION (	ACTION )	ACTION a	ACTION ,	ACTION $	GOTO S	GOTO L
0	s2		s3			1
1					acc
2	s2		s3			5	4
3		r2		r2	r2
4		s6		s7
5		r4		r4
6		r1		r1	r1
7	s2		s3			8
8		r3		r3

As reduções foram colocadas assim:

Estado	Item completo	Redução	Colunas usadas
I3	$S \to a \cdot$	r2	$FOLLOW(S) = {$, \texttt{)}, \texttt{,}}$
I5	$L \to S \cdot$	r4	$FOLLOW(L) = \{\texttt{)}, \texttt{,}\}$
I6	$S \to (L) \cdot$	r1	$FOLLOW(S) = {$, \texttt{)}, \texttt{,}}$
I8	$L \to L,S \cdot$	r3	$FOLLOW(L) = \{\texttt{)}, \texttt{,}\}$

Essa é a diferença central entre LR(0) e SLR(1). O autômato é o mesmo tipo de autômato. A tabela é preenchida com mais cuidado.

Simulação curta15.6.4

Vamos simular a entrada (a,a)$.

Pilha	Entrada	Ação
0	( a , a ) $	s2
0 ( 2	a , a ) $	s3
0 ( 2 a 3	, a ) $	r2, reduz $S \to a$
0 ( 2 S 5	, a ) $	r4, reduz $L \to S$
0 ( 2 L 4	, a ) $	s7
0 ( 2 L 4 , 7	a ) $	s3
0 ( 2 L 4 , 7 a 3	) $	r2, reduz $S \to a$
0 ( 2 L 4 , 7 S 8	) $	r3, reduz $L \to L,S$
0 ( 2 L 4	) $	s6
0 ( 2 L 4 ) 6	$	r1, reduz $S \to (L)$
0 S 1	$	acc

Comparação: LL(1), LR(0), SLR(1)15.7

Agora podemos organizar as técnicas vistas até aqui.

Técnica	Direção	Derivação	Decisão principal	Informação usada
LL(1)	esquerda para direita	mais à esquerda	qual produção expandir	FIRST e FOLLOW
LR(0)	esquerda para direita	mais à direita ao contrário	empilhar ou reduzir	estado LR(0), sem lookahead
SLR(1)	esquerda para direita	mais à direita ao contrário	empilhar ou reduzir	estado LR(0) e FOLLOW nas reduções

Condições para LL(1)15.7.1

Uma gramática é LL(1) quando, para cada não terminal, o parser consegue escolher uma única produção olhando apenas um símbolo da entrada.

Para produções $A \to \alpha_1 \mid \alpha_2 \mid \cdots \mid \alpha_n$:

• os conjuntos $FIRST(\alpha_i)$ não podem se sobrepor;
• se alguma alternativa deriva $\epsilon$, então $FOLLOW(A)$ não pode se sobrepor aos FIRST das outras alternativas;
• a gramática não pode ter recursão à esquerda direta ou indireta.

O LL(1) é bom para parsers descendentes. Ele é simples de implementar manualmente, mas exige decisões muito cedo.

Condições para LR(0)15.7.2

Uma gramática é LR(0) quando a tabela construída a partir dos itens LR(0) não tem conflitos.

Os conflitos possíveis são:

• shift/reduce: a mesma célula pede empilhar e reduzir;
• reduce/reduce: a mesma célula pede duas reduções diferentes.

No LR(0), qualquer item completo reduz em todas as colunas. Por isso ele falha em muitas gramáticas onde a decisão depende do próximo token.

Condições para SLR(1)15.7.3

Uma gramática é SLR(1) quando a tabela construída com estados LR(0) e reduções limitadas por FOLLOW não tem conflitos.

O SLR(1) resolve alguns conflitos do LR(0), especialmente quando a redução só é válida em certos contextos globais.

Mas ele ainda é uma aproximação. Como usa FOLLOW(A) inteiro, e não o lookahead específico de cada item, pode rejeitar gramáticas que um LR(1) completo aceitaria.

Quem está dentro de quem15.7.4

Dentro da família LR, a relação importante é:

$$ LR(0) \subset SLR(1) \subset LR(1) $$

Todo problema resolvido por LR(0) também é resolvido por SLR(1), porque o SLR(1) só restringe reduções que o LR(0) colocaria em todas as colunas.

Nem todo problema resolvido por SLR(1) é resolvido por LR(0), como vimos no exemplo do conflito shift/reduce.

O LL(1) pertence à família descendente, então a comparação não é simplesmente uma escada operacional com LR(0) e SLR(1). O que podemos dizer em aula sem perder a intuição é:

• LL(1) decide antes de consumir a estrutura, expandindo não terminais;
• LR(0) e SLR(1) decidem depois de reconhecer pedaços da entrada, reduzindo corpos de produção;
• LR(1) é, em geral, mais poderoso que LL(1), mas SLR(1) ainda é uma versão simplificada de LR.

Exercícios finais15.8

Exercício 1: LR(0) ou não?15.8.1

Considere:

$$ \begin{array}{rcl} S' & \to S \\ S & \to aS \\ S & \to b \end{array} $$

Tarefas:

1. Construa a coleção de itens LR(0).
2. Monte a tabela LR(0).
3. Verifique se há conflito.
4. Simule a entrada aab$.

Exercício 2: conflito em LR(0), solução em SLR(1)15.8.2

Use a gramática:

$$ \begin{array}{rcl} S' & \to S \\ S & \to Aa \\ S & \to bA \\ A & \to b \end{array} $$

Tarefas:

1. Construa os estados LR(0).
2. Identifique o estado com conflito shift/reduce.
3. Calcule $FOLLOW(A)$.
4. Monte a tabela SLR(1).
5. Simule ba$ e bb$.

Exercício 3: tabela SLR(1) completa15.8.3

Para a gramática:

$$ \begin{array}{rcl} S' & \to S \\ S & \to (L) \\ S & \to a \\ L & \to L,S \\ L & \to S \end{array} $$

Tarefas:

1. Reconstrua a coleção canônica de itens.
2. Recalcule $FOLLOW(S)$ e $FOLLOW(L)$.
3. Monte a tabela SLR(1) sem consultar a tabela da nota.
4. Simule (a,(a,a))$.

Exercício 4: comparação conceitual15.8.4

Explique com suas palavras:

1. Por que uma redução em LR(0) entra em todas as colunas?
2. Por que uma redução em SLR(1) entra apenas em FOLLOW(A)?
3. Qual conflito o SLR(1) consegue resolver que o LR(0) não resolve?
4. Por que o SLR(1) ainda não é tão preciso quanto o LR(1)?

Próximos passos15.9

O SLR(1) é uma ponte natural entre LR(0) e LR(1). Ele mantém a parte mecânica que já conhecemos, a coleção canônica de itens LR(0), mas usa FOLLOW para evitar reduções fora de contexto.

Em termos práticos:

• LR(0) pergunta apenas: o estado atual permite reduzir?
• SLR(1) pergunta: o estado atual permite reduzir e o próximo símbolo pode aparecer depois dessa variável?

Essa pequena pergunta extra remove vários conflitos sem tornar o algoritmo muito mais complexo.

Na próxima aula, veremos o CLR, também chamado de LR(1) canônico. A diferença principal será levar o lookahead para dentro dos próprios itens, em vez de usar apenas o FOLLOW global do não terminal.