III – Análise sintáctica
• Parsers predictivos não recursivos
• FIRST e FOLLOW
• Bibliografia aconselhada:
– Aho, Sethi e Ullman – secção 4.4
– Crespo – secção 4.3
Jorge Morais
LFA 1999/2000 - 1
Parser descendente não recursivo
Jorge Morais
LFA 1999/2000 - 2
Função FIRST
• Se x é um símbolo terminal FIRST(x) = {x}
• Se X  , adicionar  a FIRST(X)
• Se X  Y1 Y2 ... Yi-1 Yi ... Yk , onde  está
em FIRST(Y1), FIRST(Y2), ..., FIRST(Yi-1),
adicionar o conteúdo de FIRST(Yi) a
FIRST(X); se todos os FIRST(Yj ), com
j=1,2, ..., k, contiverem  então adicionar  a
FIRST(X)
Jorge Morais
LFA 1999/2000 - 3
Função FIRST
• FIRST(X1 X2 ... Xk) contém:
– FIRST(X1)\{};
– se  está em FIRST(X1) também contém
FIRST(X2)\{};
– ...
– se  está em FIRST(Xk-1) também contém
FIRST(Xk)\{};
– se  está em FIRST(Xk) também contém ;
Jorge Morais
LFA 1999/2000 - 4
Função FOLLOW
• $ pertence a FOLLOW(S), onde $ é o fim
de sequência e S o símbolo inicial
• Se A  B, então FIRST()\{} é
adicionado a FOLLOW(B)
• Se A  B ou A  B (onde FIRST()
contém ), adicionar FOLLOW(A) a
FOLLOW(B)
Jorge Morais
LFA 1999/2000 - 5
Exemplo
• E  T E’
E’  + T E’ | - T E’ | 
T  F T’
T’  * F T’ | / F T’ | 
F  ( E ) | id
Jorge Morais
LFA 1999/2000 - 6
Exemplo - FIRST
•
•
•
•
•
FIRST(E) = {(, id}
FIRST(E’) = {+, -, }
FIRST(T) = {(, id}
FIRST(T’) = {*, /, }
FIRST(T) = {(, id}
Jorge Morais
LFA 1999/2000 - 7
Exemplo - FOLLOW
•
•
•
•
•
FOLLOW(E) = {), $}
FOLLOW(E’) = {), $}
FOLLOW(T) = {+, -, ), $}
FOLLOW(T’) = {+, -, ), $}
FOLLOW(F) = {*, /, +, -, ), $}
Jorge Morais
LFA 1999/2000 - 8
Tabela de derivação
• Para cada produção A  
– Para cada terminal a em FIRST()
• Adicionar A   a M(A,a)
– Se  está em FIRST()
• Adicionar A   a M(A,b), para todos os b em
FOLLOW(A)
– Se  está em FIRST() e $ em FOLLOW(A)
• Adicionar A   a M(A,$)
Jorge Morais
LFA 1999/2000 - 9
Exemplo - Tabela de derivação

id
E
E
TE’
*
/
Jorge Morais
)
$
E’ 

E’ 

T’ 

T’ 

T
FT’
T’ 

F
id
(
E’ 
-TE’
T
FT’
T’
F
-
E
TE’
E’ 
+TE’
E’
T
+
T’ 

T’ 
*FT’
T’ 
/FT’
F
(E)
LFA 1999/2000 - 10
Parser descendente não recursivo
• A pilha é iniciada com o símbolo inicial S sobre o
símbolo $
• Sendo X o símbolo no topo da pilha e a o símbolo
de entrada actual:
– Se X = a = $, terminar com sucesso
– Se X = a  $, retirar X da pilha e prosseguir com o
símbolo de entrada seguinte
– Se X é uma variável (não terminal) consultar a tabela.
Se existir uma produção colocar o lado direito na pilha
(por ordem, o primeiro no topo). Senão entrada de erro.
Jorge Morais
LFA 1999/2000 - 11
Exemplo - Parser
Pilha
$E
$E’T
$E’T’F
$E’T’id
$E’T’
$E’
$E’T+
Jorge Morais
Entrada
id+id*id$
id+id*id$
id+id*id$
id+id*id$
+id*id$
+id*id$
+id*id$
Saída
E TE’
T FT’
F id
T’  
E’ +TE’
LFA 1999/2000 - 12
Exemplo - Parser (cont.)
Pilha
$E’T
$E’T’F
$E’T’id
$E’T’
$E’T’F *
$E’T’F
$E’T’id
Jorge Morais
Entrada
id*id$
id*id$
id*id$
*id$
*id$
id$
Id$
Saída
T FT’
F id
T’ *FT’
F id
LFA 1999/2000 - 13
Exemplo - Parser (cont.)
Pilha
$E’T
$E’
$
Entrada
Saída
$ $ T’  
$ E’  
• A sequência é reconhecida
• A uso da tabela evita a recursividade
Jorge Morais
LFA 1999/2000 - 14
Recuperação de erros
• Na variável A, adicionar tokens de sincronização
em FOLLOW(A)
• Adicionar tokens de sincronização de variáveis
hierarquicamente anteriores
• Adicionar tokens de FIRST(A)
• Se a produção gerar a palavra vazia, usar essa por
defeito
• Retirar um símbolo terminal do topo da pilha
Jorge Morais
LFA 1999/2000 - 15
Gramáticas LL(1)
• Gramáticas não ambíguas, sem recursividade à
esquerda
• Uma gramática diz-se LL(1) se, e só se, para 2
produções distintas A  | :
– para qualquer terminal a,  e  não derivam,
simultaneamente, palavras começadas por a
– apenas um (de  ou ) pode derivar 
– se  * , então  não deriva nenhuma palavra
começando por um terminal em FOLLOW(A)
Jorge Morais
LFA 1999/2000 - 16