Análise top-down com
tabela preditiva
• Os dois métodos apresentados até agora para
fazer análise descendente usam recursividade.
Compiladores
– Cada não-terminal tem um procedimento associado;
– Chamadas com ou sem retrocesso.
• Para gramáticas LL1 não tem retrocesso.
Análise sintática (3)
• Chamadas recursivas usam uma pilha implícita
Análise LL(1) com tabela preditiva.
– A pilha das chamadas!
– Sobrecusto!
• Idéia: retirar a recursão do procedimento:
– Usa-se uma pilha para armazenar os não-terminais
encontrados;
– Usa-se uma tabela para orientar as derivações.
1
Funcionamento do parser
Reconhecedor preditivo com Pilha
• Tem um buffer em entrada;
1) Seja X o símbolo no topo da pilha
2) Seja a o símbolo de entrada a analisar
– $ marca seu fim.
• Tem um fluxo de saída;
• Uma pilha cujo fundo é marcado por $
•
• Uma tabela sintática preditiva M
*
1
0
$
a é um terminal
3) Se X = $ e a = $
– Inicializada com S (Start)
0
2
Buffer de entrada
•
Reconheceu uma sentença
•
Termina execução
4) Se X = a != $
Pilha S
Parser preditivo top-down
Saída
$
Desempilha X
•
Avança de um símbolo na entrada
5) Se X é não-terminal: Consulta a tabela M(X, a)
•
•
Tabela
3
A tabela preditiva M(X, t)
4
• Tabela Bi-dimensional:
– Dimensão 1: Não-terminal X
– Dimensão 2: Caractere da entrada (terminal) t
– A entrada (X,t) contém a regra de produção a aplicar
a
Se a entrada for vazia: ERRO
Se a entrada contém X → UVW
•
Então substitui X no topo da pilha por UVW
Exemplo de tabela M(X, t)
• Tabela Bi-dimensional:
b
c
– Dimensão 1: Não-terminal X
– Dimensão 2: Caractere da entrada (terminal) t
– A entrada (X,t) contém a regra de produção a aplicar
$
a
S
A
B
S
A
B
S → cAa
First(A) = {b, c, ε}
A → cB | B
First(B) = {b, ε}
First(S) = {c}
B → bcB | ε
•
Follow(S) = {$}
Follow(A) = {a}
Follow(B) = {a}
5
b
c
S → cAa
First(A) = {b, c, ε}
A → cB | B
First(B) = {b, ε}
First(S) = {c}
B → bcB | ε
$
S → cAa
Follow(S) = {$}
Follow(A) = {a}
Follow(B) = {a}
6
Exemplo de tabela M(X, t)
Exemplo de tabela M(X, t)
• Tabela Bi-dimensional:
• Tabela Bi-dimensional:
– Dimensão 1: Não-terminal X
– Dimensão 2: Caractere da entrada (terminal) t
– A entrada (X,t) contém a regra de produção a aplicar
a
S
A
B
b
c
– Dimensão 1: Não-terminal X
– Dimensão 2: Caractere da entrada (terminal) t
– A entrada (X,t) contém a regra de produção a aplicar
$
a
S → cAa
A→B
A→B
S → cAa
First(A) = {b, c, ε}
A → cB | B
First(B) = {b, ε}
First(S) = {c}
B → bcB | ε
S
A
B
Follow(S) = {$}
Follow(A) = {a}
Follow(B) = {a}
7
Exemplo de tabela M(X, t)
A→B
B→ε
b
c
A→B
S → cAa
A → cB
S → cAa
First(A) = {b, c, ε}
A → cB | B
First(B) = {b, ε}
First(S) = {c}
B → bcB | ε
b
ERRO
Follow(S) = {$}
Follow(A) = {a}
Follow(B) = {a}
Follow(S) = {$}
Follow(A) = {a}
Follow(B) = {a}
8
a
9
S → cAa
First(A) = {b, c, ε}
First(B) = {b, ε}
First(S) = {c}
b
A→B
B→ε
A→B
B →bcB
c
S → cAa
First(A) = {b, c, ε}
A → cB | B
First(B) = {b, ε}
First(S) = {c}
B → bcB | ε
$
S → cAa
A → cB
Follow(S) = {$}
Follow(A) = {a}
Follow(B) = {a}
10
Usando a tabela
• String: “cbca”
c
S → cAa
A → B A → cB
B →bcB ERRO
A → cB | B
B → bcB | ε
First(B) = {b, ε}
First(S) = {c}
S
A
B
– Dimensão 1: Não-terminal X
– Dimensão 2: Caractere da entrada (terminal) t
– A entrada (X,t) contém a regra de produção a aplicar
A→B
B→ε
First(A) = {b, c, ε}
A → cB | B
B → bcB | ε
$
• Tabela Bi-dimensional:
a
ERRO
S → cAa
– Dimensão 1: Não-terminal X
– Dimensão 2: Caractere da entrada (terminal) t
– A entrada (X,t) contém a regra de produção a aplicar
Exemplo de tabela M(X, t)
S
A
B
A→B
$
• Tabela Bi-dimensional:
– Dimensão 1: Não-terminal X
– Dimensão 2: Caractere da entrada (terminal) t
– A entrada (X,t) contém a regra de produção a aplicar
a
c
S → cAa
A → cB
Exemplo de tabela M(X, t)
• Tabela Bi-dimensional:
S
A
B
A→B
b
Pilha
S$
cAa$
Aa$
Ba$
bcBa$
cBa$
Ba$
a$
$
$
ERRO
ERRO
ERRO
Follow(S) = {$}
Follow(A) = {a}
Follow(B) = {a}
11
Entrada
Ação
cbca$
cbca$
bca$
bca$
bca$
ca$
a$
a$
$
S->cAa
casar c
A->B
B->bcB
casar b
casar c
B-> ε
casar a
casar $, sucesso
12
Algoritmo para construir a tabela
– Re-escrever a gramática para satisfazer
condições de LL(1)
– Calcular os conjuntos First e Follow
– Para cada produção A → 1. Para cada a ∈First()
– incluir a produção A → em M[A,a]
2. Se ε ∈ First()
– incluir a produção A → em M[A,b] para
cada b em Follow(A)
3. Se ε ∈ First() e $ ∈ Follow(A)
– incluir A → to M[A,$]
– Todas entradas não definidas são erros
Mais um exemplo...
E → TE’
E’ → +TE’| ε
T → FT’
T’ → *FT’ | ε
F → (E)| Id
E → TE’
T → FT’
T’ → *FT’ | ε
F → (E)| Id
*
id
F
E
First
Follow
E
E’
T
T’
F
{(, id}
{+, ε}
{(, id}
{*, ε}
{(, id}
{$, )}
{$, )}
{+, $, )}
{+, $, )}
{*, +, $, )}
(
F → (E)
E → TE’
T → FT’
T → FT’
E’
T
T’
+
)
{$, )}
{$, )}
{+, $, )}
{+, $, )}
{*, +, $, )}
13
14
Para: G = (T,N,P,S)
T = {a,b,c,d,e,f}
N = {S,X,Y,Z}
E’ →ε
E’ →ε
T’ →ε
T’ →ε
T’ →ε
P: S → XYZ
X → aXb | ε
Y → cYZcX | d
Z → eZYe | f
Construir Tabela e Analisar a string: abcdfcf
$
E’ → +TE’
T’ → *FT’
Follow
{(, id}
{+, ε}
{(, id}
{*, ε}
{(, id}
Exercício LL(1)
Símbolo
F → id
E → TE’
First
E
E’
T
T’
F
Construir Tabela
Mais um exemplo...
E’ → +TE’| ε
Símbolo
15
First(X) = {a, ε}
Follow(X) = {c, d, b, e, f}
First(Y) = {c, d}
Follow(Y) = {e, f}
First(Z) = {e, f}
Follow(Z) = {$, c, d}
First(S) = {a, c, d}
Follow(S) = {$}
Observação sobre a Tabela
16
Gerenciamento de Erros
• A tabela indica se há ambigüidade!
• Relatar erros & recuperar
– Mais de uma regra numa entrada!
–
–
–
–
• Soluções?
– Tornar a gramática LL(1)
• Eliminar ambiguidade, recursividade...
– Usar uma heurística para desempatar as regras
Relatar erros assim que possível
Mensagens de erro adequadas
Continua após o erro
Evitar a cascata de erros
• Nível-Frase (local) x Modo-Pânico
• Qual?
– Nível frase: tenta-se alterar UM símbolo para
recuperar.
– Modo pânico: pula x tokens de entrada até poder
voltar a fazer a análise.
– Usar outros algoritmos do que os top-down!
• Exemplo total: if... Then... Else:
S→iEtS|iEtSeS|a
• = até encontrar um token de sincronização.
E→b
17
18
Recuperação em Modo Pânico
Sumário
• Análise top-down possibilita o reconhecimento
eficiente e simples de gramáticas LL(1):
• Pula tokens até que um “conjunto de
sincronização” é encontrado
– Implementação preditiva com tabela.
– Baseada nos cálculos dos conjuntos First/Follow
– Follow(A) (A sendo no topo da pilha)
– Símbolos de alta hierarquia na gramática
• Obs: têm casos que não foram tratados (e.g. o ‘+’)
• { , for, while, if…
• Limitação:
– First(A)
– Epsilon produção
– Pop/Insert um terminal no topo da pilha.
– Quando a gramática não é LL(1) !
• Por isso: usa-se também análise ascendente
(bottom-up).
• Adicione ações de sincronia para a tabela
19
20
Bibliografia
Exercícios
Leituras:
• A. M. A. Price, S. S. Toscani. Implementação de
Linguagens de Programação: Compiladores. 3ª ed. Porto
Alegre: Sagra-Luzzatto. 2005. Cap 3, Seção 3.2.3.
A. M. A. Price, S. S. Toscani. Implementação de
Linguagens de Programação: Compiladores. 3ª ed. Porto
Alegre: Sagra-Luzzatto. 2005. Cap 3.
– 1a7
• A. V. Aho, R. Sethi, J. D. Ullman. Compilers: Principles,
Techniques and Tools. Reading: Addison-Wesley. 1985.
Seção 4.4 (parser não recursivo, preditivo).
21
22