III – Análise sintáctica
• Análise sintáctica ascendente LR
• Bibliografia aconselhada:
– Aho, Sethi e Ullman – secção 4.7
– Crespo – secção 5.4
– Appel – secção 3.3
Jorge Morais
LFA 1999/2000 - 1
Vantagem dos parsers LR
• Reconhecem praticamente todas as
construções de linguagens de programação
expressas por gramáticas independentes de
contexto
• É o melhor método conhecido para parsers
não recursivos com instruções shift-reduce,
mantendo o grau de eficiência
Jorge Morais
LFA 1999/2000 - 2
Vantagem dos parsers LR (cont.)
• A classe das gramáticas que podem ser
derivadas com parsers LR contém a classe
das gramáticas que podem ser derivadas
usando parser predictivos
• Pode detectar rapidamente erros, assim que
seja possível numa pesquisa da entrada da
esquerda para a direita
Jorge Morais
LFA 1999/2000 - 3
Modelo dum parser LR
Jorge Morais
LFA 1999/2000 - 4
Elementos dum parser LR
• Tabela de acções – acção(s, a), s estado actual e a
o símbolo na entrada:
–
–
–
–
shift s’, onde s’ é um estado
reduce A  
aceitação
erro
• Tabela de salto (goto) – salto(s, X), s estado actual
e X estado no topo da pilha:
– retorna o estado de destino
Jorge Morais
LFA 1999/2000 - 5
Configurações
• Configuração inicial:
– Pilha: 0
– Entrada: u $
• Configuração final:
– Pilha: s0 X1 s1 ... Xmsm , com acção(sm,a)=aceit.
– Entrada: u’ $
Jorge Morais
LFA 1999/2000 - 6
Algoritmo
• Em cada passo, para a na entrada e s o
estado actual:
– Se acção(s,a) = shift s’, trocar s por s’ na pilha
– Se acção(s,a) = reduce A  , retirar os
elementos relativos a  do topo da pilha,
inserindo A seguido de s’ = salto(a,s’’), onde s’’
é o estado que ficou anteriormente no topo
– Se acção(s,a) = aceitação, aceita a sequência
– Se acção(s,a) = erro, vai para rotina de erro
Jorge Morais
LFA 1999/2000 - 7
Exemplo
1.
2.
3.
4.
5.
6.
•
EE+T
ET
TT*F
TF
F(E)
F  id
Sequência: id * id + id $
Jorge Morais
LFA 1999/2000 - 8
Exemplo – Tabela
S
acção
id
0
+
*
S5
salto
(
)
$
S4
1
S6
2
R2
S7
R2
R2
3
R4
R4
R4
R4
4
S4
R6
R6
R6
6
S5
S4
7
S5
S4
F
1
2
3
8
2
3
9
3
R6
10
8
S6
9
R1
S7
R1
R1
10
R3
R3
R3
R3
11
R5
R5
R5
R5
Jorge Morais
T
Aceit.
S5
5
E
S11
LFA 1999/2000 - 9
Exemplo - Parser
Pilha
0
0 id 5
0F3
0T2
0T2*7
0 T 2 * 7 id 5
0 T 2 * 7 F 10
Jorge Morais
Entrada
id*id+id$
*id+id$
*id+id$
*id+id$
id+id$
+id$
+id$
Acção
Shift
Reduce F  id
Reduce T  F
Shift
Shift
Reduce F  id
Reduce TT*F
LFA 1999/2000 - 10
Exemplo – Parser (cont.)
Pilha
0T2
0E1
0E1+6
0 E 1 + 6 id 5
0E1+6F3
0E1+6T9
0E1
Jorge Morais
Entrada
+id$
+id$
id$
$
$
$
$
Acção
Reduce E  T
Shift
Shift
Reduce F  id
Reduce T  F
Reduce EE+T
Aceita
LFA 1999/2000 - 11