III – Análise sintáctica
• Análise sintáctica orientada à precedência
de operadores
• Bibliografia aconselhada:
– Aho, Sethi e Ullman – secção 4.6
– Crespo – secção 5.3
Jorge Morais
LFA 1999/2000 - 1
Relações de precedência
• Relações entre operadores
– 1 < 2 – operador 1 cede prioridade a 2
– 1 = 2 – 1 e 2 têm a mesma prioridade
– 1 > 2 – operador 1 ganha prioridade a 2
• Significado
– < marca o início dum ponto de apoio
– = marca o interior dum ponto de apoio
– > marca o fim dum ponto de apoio
Jorge Morais
LFA 1999/2000 - 2
Regras gerais
• Relação entre operadores iguais:
– se o operador for associado à esquerda:  > 
– se o operador for associado à direita:  < 
• Relação entre operadores e outros
($ delimita o início e fim da sequência):
$ < (
$ < id
id > $
) > $
(=)
( < (
) > )
( < id id > )
Jorge Morais
LFA 1999/2000 - 3
Tabela de operadores
• E  E + E | E * E | ( E ) | id
id
id
+
*
(
)
$
Jorge Morais
<
<
<
<
+
>
>
>
<
>
<
*
>
<
>
<
>
<
(
<
<
<
)
>
>
>
=
>
$
>
>
>
>
<
LFA 1999/2000 - 4
Exemplo
•
•
•
•
•
•
•
E  E + E | E * E | ( E ) | id
$ id + id * id $
$ < id > + < id > * < id >
Após as reduções E  id, fica:
$ < E + < E * E > $
Após as reduções E  E * E, fica:
$ < E + E > $
Jorge Morais
LFA 1999/2000 - 5
Exemplo - Parser
Pilha
$
$ < id
$E
$ < E +
$ < E + < id
$ < E + E
$ < E + < E *
Jorge Morais
Rel Entrada
Acção
< id+id*id$
+id*id$ E  id
>
+id*id$
<
id*id$
<
*id$ E  id
>
*id$
<
id$
<
LFA 1999/2000 - 6
Exemplo - Parser (cont.)
Pilha
Rel Entrada
Acção
$ E  id
$< E+< E*< id >
$ EE*E
$ < E+ < E * E >
$ EE+E
$ < E + E
>
$E
$
Jorge Morais
LFA 1999/2000 - 7
Exemplo
•
•
•
•
•
•
•
E  E + E | E * E | ( E ) | id
$ id + id + id $
$ < id > + < id > * < id >
Após as reduções E  id, fica:
$ < E + E > + E > $
Após as reduções E  E + E, fica:
$ < E + E > $
Jorge Morais
LFA 1999/2000 - 8
Exemplo - Parser
Pilha
$
$ < id
$E
$ < E +
$ < E + < id
$ < E + E
$E
Jorge Morais
Rel Entrada
< id+id+id$
+id+id$
>
+id+id$
<
id+id$
<
+id$
>
+id$
>
+id$
<
Acção
E  id
E  id
EE+E
LFA 1999/2000 - 9
Exemplo - Parser (cont.)
Pilha
$ < E +
$ < E+ < id
$ < E + E
$E
Jorge Morais
Rel Entrada
Acção
id$
<
$ E  id
>
$ EE+E
>
$
LFA 1999/2000 - 10