III – Análise sintáctica
• Construção de tabelas para parsers LR
• Bibliografia aconselhada:
– Aho, Sethi e Ullman – secção 4.7
– Crespo – secção 5.5, 5.6 e 5.7
– Appel – secção 3.3
Jorge Morais
LFA 1999/2000 - 1
Gramáticas LR(0)
• Podem ser derivadas usando apenas o
símbolo no topo da pilha, fazendo
instruções shift-reduce sem ler nenhum
símbolo à frente
• Demasiado fracas, servem de base às outras
formas de construções de tabelas
Jorge Morais
LFA 1999/2000 - 2
Itens LR(0)
• Proução:
– AXYZ
• Itens LR(0):
–
–
–
–
A.XYZ
AX.YZ
AXY.Z
AXYZ.
• No caso A  , temos apenas o item A  .
Jorge Morais
LFA 1999/2000 - 3
Operação de fecho
• Sendo I um conjunto de itens, fecho(I) é um
novo conjunto construído usando as
seguintes regras:
– Todos os itens em I pertencem a fecho(I)
– Se A   . B  está em fecho(I) e B   é uma
produção da gramática, B  .  é adicionado ao
fecho(I)
Jorge Morais
LFA 1999/2000 - 4
Operação de salto (goto)
• goto(I,X) onde I é um conjunto de itens e X
é um símbolo da gramática
• Fecho do conjunto de itens de todos os itens
da forma A   X .  onde A   . X 
pertence a I
Jorge Morais
LFA 1999/2000 - 5
Construção de conjuntos de itens
• Algoritmo:
– C = {fecho ({S’  . S})}
– Para cada I em C e cada X símbolo da
gramática (até não haver mais itens a adicionar)
• Adicionar goto(I,X) a C
Jorge Morais
LFA 1999/2000 - 6
Exemplo
•
•
•
•
•
•
•
E’  E
EE+T
ET
TT*F
TF
F(E)
F  id
Jorge Morais
LFA 1999/2000 - 7
goto(I0 , X)
I1=goto(I0 , E) = {E’  E . , E  E . + T}
I2=goto(I0 , T) = {E  T . , T  T . * F}
I3=goto(I0 , F) = {T  F .}
I4=goto(I0 , ‘(‘ ) = {F  ( . E ) ,
E  . E + T, E  . T, T  . T * F, T  . F,
F  . ( E ), F  . id}
• I5=goto(I0 , id ) = {F  id .}
•
•
•
•
Jorge Morais
LFA 1999/2000 - 8
Restantes conjuntos
• I6=goto(I1 , +) = {E  E + . T, T  . T * F,
T  . F, F  . ( E ), F  . id}
• I7=goto(I2 , *)={TT*.F,F.( E ),F . id}
• I8=goto(I4 , E) = {F  ( E . ) , E  E . + T}
• I9=goto(I6 , T) = {E  E + T . , T T .* F}
• I10=goto(I8 , F) = {T  T * F .}
• I11=goto(I8 , ‘)’) = {F  ( E ) .}
Jorge Morais
LFA 1999/2000 - 9
Autómato finito
• Cada um dos Ik vai ser um estado dum autómato
finito determinístico
• As transições são dadas por (I,X,goto(I,X))
• O estado inicial será o que contém E’  E
• Este autómato pode ser construído usando a
Construção de Thompson e a construção de
subconjuntos, partindo das transições:
– ({A   . X }, X, {A  X . })
– ({A   . X },  , {X . })
Jorge Morais
LFA 1999/2000 - 10
SLR – Simple LR
• Construir C={I0, I1, ..., In}
• Se {A   . a } pertence a Ii e goto(Ii,a) = Ij ,
então acção(i,a) = shift j
• Se {A   . } pertence a Ii, então para todo o a
em FOLLOW(A), então
acção(i,a) = reduce A  ; A não pode ser S’
• Se {S’  S} pertence a Ii, então acção(i,$) = aceit.
• Se {A   . X } pertence a Ii, X variável (não
terminal), então salto(i,X) = j
Jorge Morais
LFA 1999/2000 - 11
LR(1)
• LR(1) – usa um símbolo de lookahead
• os itens LR(1) são da forma (A  . , a)
onde a é um símbolo terminal
• se  não é , a não tem qualquer significado
• os itens(A  . , a) vão corresponder a uma
redução A  se a for o próximo símbolo
na entrada
Jorge Morais
LFA 1999/2000 - 12
LALR(1) – LookAhead LR(1)
• LALR(1) – diminui número de estados
relativamente a LR(1) e é mais forte que
SLR
• Junta qualquer par de estados iguais que
apenas tenham o símbolo de lookahead
diferente
Jorge Morais
LFA 1999/2000 - 13
Hierarquia de gramáticas
Jorge Morais
LFA 1999/2000 - 14