Análise Sintática LR
Prof. Alexandre Monteiro
Baseado em material cedido pelo Prof. Euclides Arcoverde
Recife
‹#›
Contatos

Prof. Guilherme Alexandre Monteiro Reinaldo

Apelido: Alexandre Cordel

E-mail/gtalk: [email protected]
[email protected]

Site: http://www.alexandrecordel.com.br/fbv

Celular: (81) 9801-1878
Análise Sintática LR

É uma técnica de análise sintática bottom-up (ascendente)

Também chamada de shift-reduce

Usada em vários geradores automáticos de parsers
•Exemplo: JavaCC, yacc, CUP
3
Analisador Sintática LR

Existem diversos tipos de analisadores LR(k)

O nome LR(k) indica
• Left-to-right – a ordem de leitura dos tokens é da
esquerda para a direita
• Rigthmost derivation – encontra uma derivação mais
à direita (porém, de trás para a frente)
• K token são olhados à frente (lookahead)
4
Analisador Sintática LR

O tipo que veremos é chamado LR(0)

Alguns tipos importantes são
•SLR(1) – Simple LR(1)
•LALR(1) – Look-Ahead LR(1)

O LALR(1) é usado nos principais geradores de parsers
5
Assuntos

Sobre o parser LR(0) veremos
•Princípios de funcionamento
•Construção do autômato LR(0)
•Construção das tabelas ACTION e GOTO
•Exemplo de execução
6
Princípios de Funcionamento
Funcionamento

Símbolos terminais lidos de uma entrada
•Na prática, são os tokens, obtidos um por
vez por meio do lexer

Símbolos terminais (já lidos da entrada) e não-terminais
podem ser inseridos em uma pilha
8
Funcionamento




As ações do parser são construídas com base num
autômato construído a partir da gramática
Cada símbolo inserido na pilha, levará o autômato a
um novo estado
Assim, na pilha, junto com cada símbolo haverá o
estado do autômato
O “estado atual” será o estado no topo da pilha
9
Funcionamento

A medida que lê os terminais (tokens), o parser poderá
realizar certas ações, de acordo com o estado atual
•SHIFT
•REDUCE
•ACCEPT
•ERROR
10
Ações

Ação SHIFT <estado>
•Pega o próximo terminal da entrada e insere
no topo da pilha
•Realizada quando o parser precisa de mais
informações sobre a entrada para formar a
árvore
•Junto com o terminal, insere o próximo
estado
11
Ações

Ação REDUCE X
• Realizada quando o parser reconhecer que os
símbolos no topo da pilha formam a cadeia 
- Na árvore (se for criada), X será pai de toda a cadeia 
• O parser remove toda a cadeia  da pilha e observa
o estado atual (no topo)
• Insere o símbolo X junto com o próximo estado (que
dependerá do estado atual)
12
Ações

Ação ACCEPT
•Indica que a entrada terminou e está
correta (toda a árvore pode ser criada)

Ação ERROR
•Indica que a entrada está errada
13
Funcionamento


A escolha das ações do parser será dada por uma tabela
ACTION
Outra tabela auxiliar usada é a tabela GOTO, usada apenas
quando a ação for “reduce”
14
Funcionamento

Tabela ACTION
•Diz qual ação será tomada, de acordo com o
estado atual e o próximo token

Tabela GOTO (usada durante um reduce)
•Diz qual o próximo estado, de acordo com o
estado atual e o símbolo não-terminal que
foi reduzido
15
Autômato e Tabelas


Veremos a seguir como é construído o autômato a partir de
uma gramática qualquer dada
Depois, a partir do autômato, veremos como criar as
tabelas ACTION e GOTO
16
Construção do Autômato LR(0)
Construção do Autômato

O primeiro passo é estender a gramática com a
produção S’S (ou S’S$), onde:
• S é o símbolo inicial original
• $ indica fim de arquivo (EOF)

Essa gramática é chamada de gramática
estendida
18
Itens LR(0)

Indicam em que parte de uma produção a
análise sintática pode estar, num certo
instante
• Um ponto é usado para indicar a posição

Para cada produção X  YZW , temos os itens
•X 
•X 
•X 
•X 
.YZW
Y.ZW
YZ.W
YZW.
19
Autômato LR(0)

Os itens serão usados para criar um autômato
em que
• Cada estado é uma coleção de itens
• As transições entre estados acontecem quando um
símbolo (terminal ou não) é lido/reconhecido
• Não existe estado final
20
Autômato LR(0)


O estado inicial será o item S’.S
Para todo item X.Y , com Y não-terminal,
adicionar ao mesmo estado os itens
• Y. , para toda produção de Y

Para todo item X.Y , criar uma transição
que:
• Lê o símbolo Y (terminal ou não)
• Leva ao estado formado por XY.
21
Autômato LR(0)


Depois de concluído o autômato, os estados devem ser
numerados, para facilitar
O autômato pode, então, ser usado para criar as tabelas
ACTION e GOTO do parser
22
Construção das Tabelas
Relembrando as Tabelas

Tabela ACTION
•Diz qual ação será tomada, de acordo com o
estado atual e o próximo token

Tabela GOTO (usada após um reduce)
•Diz qual o próximo estado, de acordo com o
estado atual e o símbolo não-terminal que
foi reduzido
24
Construção das Tabelas



Para criar ambas as tabelas, é preciso analisar
os itens LR(0) de cada estado do autômato
Descreveremos apenas as situações em que as
entradas das tabelas são bem definidas
Nos demais casos, subentende-se que a ação é
de erro
25
Tabela GOTO


A tabela GOTO é a mais simples de construir
Se o estado tiver um item com um ponto antes
de um não-terminal N, assim: X.N
• Quando o não-terminal reduzido for N, ir para o
estado do autômato que tem o ponto depois do
não-terminal, assim: XN.
26
Tabela ACTION

Se o estado tiver um item com um ponto antes de um
terminal t assim: X.t
•Fazer um SHIFT, quando o próximo símbolo
for t
•Ir para o estado que tem o ponto depois do
terminal, assim: Xt.
27
Tabela ACTION

Se o estado tiver um item com um ponto no
final da produção assim: X.
• Fazer um REDUCE para a produção X , qualquer
que seja o próximo símbolo
• Observação: Após o parser realizar o reduce, ele
consultará a tabela GOTO para decidir o próximo
estado
28
Tabela ACTION

Um caso especial será definido quando o estado tiver o item
S’S.
•Neste caso, a ação será ACCEPT, apenas se
o próximo símbolo for $
29
Exemplo de Execução
Exemplo (quadro)
0)
S:
stmt $
1)
stmt: ID ':=' expr
2)
expr: expr '+' ID
3)
expr: expr '-' ID
4)
expr: ID
31
Exemplo (autômato)
State 0
0)S:
. stmt $
1)stmt:
. ID ':=' expr
State 1
0)S:
State 3
1) stmt:
2) expr:
3) expr:
4) expr:
ID ':=' . expr
. expr '+' ID
. expr '-' ID
. ID
stmt . $
State 2
1)stmt:
ID . ':=' expr
32
Exemplo (autômato)
State 0
0) S: . stmt $
1) stmt: . ID ':=' expr
GOTO
2 on stmt
SHIFT 1 on ID
State 1
1) stmt: ID . ':=' expr
SHIFT 3 on ':='
4) expr: . ID
GOTO
6 on expr
SHIFT 5 on ID
State 7
2) expr: expr '+' . ID
SHIFT 9 on ID
State 4
0) S: stmt
State 8
3) expr: expr '-' . ID
SHIFT 10 on ID
$.
State 5
4) expr: ID .
State 2
0) S: stmt . $
SHIFT 4 on $
State 3
1) stmt: ID ':=' . expr
2) expr: . expr '+' ID
State 6
1) stmt: ID ':=' expr .
2) expr: expr . '+' ID
3) expr: expr . '-' ID
SHIFT 7 on '+'
SHIFT 8 on '-'
State 9
2) expr: expr '+' ID .
State 10
3) expr: expr '-' ID .
3) expr: . expr '-' ID
33
Exemplo (Tabelas)
0
1
2
3
4
5
6
7
8
9
10
Action Table
Goto Table
ID ':=' '+' '-'
$ stmt expr
s1
g2
s3
s4
s5
g6
acc acc acc acc acc
r4 r4 r4 r4 r4
r1 r1 s7 s8 r1
s9
s10
r2 r2 r2 r2 r2
r3 r3 r3 r3 r3
34
Exemplo: a:= b + c - d
Stack
0/S
0/S 1/a
0/S 1/a 3/:=
0/S 1/a 3/:= 5/b
0/S 1/a 3/:=
0/S 1/a 3/:= 6/expr
0/S 1/a 3/:= 6/expr 7/+
0/S 1/a 3/:= 6/expr 7/+ 9/c
0/S 1/a 3/:=
0/S 1/a 3/:= 6/expr
0/S 1/a 3/:= 6/expr 8/0/S 1/a 3/:= 6/expr 8/- 10/d
0/S 1/a 3/:=
0/S 1/a 3/:= 6/expr
0/S
0/S 2/stmt
0/S 2/stmt 4/$
Remaining Input
a:= b + c - d
:= b + c - d
b+c-d
+c-d
+c-d
+c-d
c-d
-d
-d
-d
d
$
$
$
$
$
Action
s1
s3
s5
r4
g6 on expr
s7
s9
r2
g6 on expr
s8
s10
r3
g6 on expr
r1
g2 on stmt
s4
35
accept
Exemplo

O que acontece ao tentar criar as tabelas de parsing LR(0)
para a gramática abaixo?
E → 1 E
| 1
36
Conflitos na Criação de Parsers LR
Conflitos


Um mesmo estado do autômato pode ter itens
que permitam mais de uma ação, gerando
conflitos na criação das tabelas
Conflitos possíveis:
• SHIFT/REDUCE: em um mesmo estado, o parser não
consegue decidir se faz um shift ou um reduce
• REDUCE/REDUCE: em um mesmo estado, o parser
pode fazer reduce para duas produções diferentes
e ele não consegue decidir qual escolher
38
Conflitos em Parsers LR(0)


Os tipos de conflitos citados podem aparecer com qualquer
técnica de construção de parser LR
Para ilustrar, veremos como esses conflitos acontecem na
construção de parsers LR(0)
39
Conflitos em Parsers LR(0)

Se o estado tiver um item X.t e outro
X.
• O primeiro item indica que se deve fazer um shift
de t, enquanto o segundo indica para fazer um
reduce para a produção X
• Conflito SHIFT/REDUCE !
• É o que aconteceria na gramática
E → 1 E
| 1
40
Conflitos em Parsers LR(0)

Se o estado tiver um item X. e outro Y.
•Neste caso, o parser poderia fazer o reduce
para duas produções diferentes
•Conflito REDUCE/REDUCE !
41
Tratamento de Conflitos

Dependendo do caso, os conflitos podem ser
tratados das seguintes maneiras
• Alterando a gramática, ou
• Definindo precedências para as produções, ou
• Usando outra técnica LR (SLR, LALR, etc.)
- Veremos a SLR...
42
Parser SLR
Parser SLR

É um caso simples de parser LR(1)
•“Simple LR(1)”

Vamos comparar a técnica LR(0) vista antes com o princípio
dos parsers LR(1)
44
LR(0) x LR(1)

O parser LR(0) visto antes tem o número 0 no
nome porque a ação a ser tomada (shift ou
reduce) independe do próximo token
• Ele poderia simplesmente fazer a ação olhando só
para os símbolos que já estão na pilha
• Olha “zero” tokens adiante

Já um parser LR(1) confere 1 token à frente
para escolher a ação
• Pode ter uma ação específica para cada token
45
Parser SLR


Não veremos como construir um parser LR(1)
canônico, mas veremos o SLR(1), que é mais
simples
O LR(1) canônico usa um autômato especial
chamado autômato LR(1)
• Não veremos...

Mas a técnica SLR(1) usa o mesmo autômato
LR(0) que vimos até agora
46
Parser SLR

O parser SLR(1)
•Funciona de maneira muito parecida com o
LR(0)
•É baseado no mesmo autômato LR(0)
•Na prática, a diferença para o LR(0) será
apenas na construção da tabela
47
Parser SLR

Na construção da tabela ACTION para o parser
SLR(1), uma ação só será escolhida se o
próximo símbolo (1 à frente) estiver “correto”
• O critério para escolha da ação “SHIFT” não mudará
em relação ao parser LR(0), porque essa ação já
considera o próximo símbolo
• Já o “REDUCE X” só será a ação válida para os
tokens que podem aparecer após o não-terminal X
48
Parser SLR

Os símbolos que podem vir após o não-terminal X são
exatamente o conjunto FOLLOW(X) visto em aulas passadas
49
Conjunto FOLLOW

FOLLOW (N)
•Aplicado a não-terminais N quaisquer

É o conjunto de terminais que podem aparecer à direita do
não-terminal N, em alguma cadeia derivada pela gramática
•Se o símbolo inicial deriva uma cadeia “... N
t ...” então t faz parte de FOLLOW(A)
50
Parser SLR

Assim, na construção da tabela ACTION de um parser SLR,
se tiver um item X. em um estado do autômato...
•A ação naquele estado será REDUCE X,
apenas para os símbolos que estão em
FOLLOW(X)

O restante é idêntico ao LR(0)...
51
Parser SLR


Com essa simples alteração no critério de escolha para a
ação REDUCE, essa técnica consegue tratar mais gramáticas
do que a LR(0)
Ela evita que aconteça alguns casos de conflitos SHIFT /
REDUCE como o que vimos no início da aula
52
Exemplo

Dada a gramática abaixo
(0) S → E
(1) E → 1 E
(2) E → 1
•Construir as tabelas de parsing SLR
53
Exemplo

Estados
Estado 0
S → • E
E → • 1 E
E → • 1
Estado 2
S → E •
Estado 3
E → 1 E •
Estado 1
E → 1 • E
E → 1 •
E → • 1 E
E → • 1
54
Exemplo

Tabelas de parsing SLR
action
goto
state 1
$
E
0
s1
2
1 s1/r2 r2
3
2
acc
3
r1
r1

FOLLOW(E) = {$}, então REDUCE só é valido para $
state
0
1
2
3
action
goto
1
$
E
s1
2
s1
r2
3
acc
r1
55
Parser SLR

A análise sintática SLR é uma extensão simples e
eficaz da análise LR(0)
• Ela é capaz de tratar quase todas as estruturas práticas de
linguagens de programação


No entanto, existem algumas poucas situações que a
análise SLR é incapaz de tratar
Para esses casos, é comum usar um método LR(1) mais
avançado (que não veremos) que é o chamado LALR(1)
• Usado no CUP, yacc e diversos outros geradores de parsers
56
Exercício SLR

Dada a gramática abaixo
E → n + E
| n
•Construir as tabelas de parsing SLR
•Fazer o reconhecimento de “n+n+n”
57
Exemplo

Estados
Estado 0
S → • E
E → • n + E
E → • n
Estado 1
E → n • + E
E → n •
Estado 2
S → E •
Estado 3
E → n + • E
E → • n + E
E → • n
Estado 4
E → n + E •
58
Exercício

Tabelas de parsing SLR
state
0
1
2
3
4
action
goto
n
+
$
E
s1
s3
r2
g2
acc
s1
g4
r1
59
Exercício

Reconhecimento de “n+n+n”
Stack
0/S
0/S 1/n
0/S 1/n 3/+
0/S 1/n 3/+ 1/n
0/S 1/n 3/+ 1/n 3/+
0/S 1/n 3/+ 1/n 3/+ 1/n
0/S 1/n 3/+ 1/n 3/+ 4/E
0/S 1/n 3/+ 4/E
0/S 1/E
0/S 1/E 2/$
Remaining Input
n+n+n
+n+n
n+n
+n
n
$
$
$...
$
Action
s1
s3
s1
s3
s1
r2
g4
r1...
g2
acc
60
Exercício LR(0)

Dada a gramática abaixo
(1)
(2)
(3)
(4)
(5)
E
E
E
B
B
→
→
→
→
→
E * B
E + B
B
0
1
•Construir as tabelas de parsing LR(0)
•Fazer o reconhecimento de “1+1”
61
Exercício

Tabelas de parsing LR(0)
state
0
1
2
3
4
5
6
7
8
*
r4
r5
s5
r3
r1
r2
ACTION
+
0
1
$
s1 s2
r4 r4 r4 r4
r5 r5 r5 r5
s6
acc
r3 r3 r3 r3
s1 s2
s1 s2
r1 r1 r1 r1
r2 r2 r2 r2
GOTO
E
B
3
4
7
8
62
Exercício

Estado
0
2
4
3
6
2
8
3
Reconhecimento de “1+1”
Entrada de dados
1+1$
+1$
+1$
+1$
1$
$
$
$
Saída de dados
5
5,3
5,3
5,3
5,3,5
5,3,5,2
Pilha
[0]
[0,2]
[0,4]
[0,3]
[0,3,6]
[0,3,6,2]
[0,3,6,8]
[0 3]
Próxima ação
shift 2
reduce 5
reduce 3
shift 6
shift 2
reduce 5
reduce 2
aceita
63
Bibliografia

AHO, A., LAM, M. S., SETHI, R., ULLMAN, J. D.,
Compiladores: princípios, técnicas e ferramentas. Ed.
Addison Wesley. 2a Edição, 2008 (Capítulo 4)
64