Análise Sintática - Continuação
Parte 4
Profa. Heloise Manica Paris Teixeira
Slides cedidos pela Prof. Valéria Feltrin (DIN-UEM)
Análise sintática
Analisadores Sintáticos
Do símbolo de partida para
a sentença
Descendente
(Top-down)
Com retrocesso
(back track)
Da sentença para o
simbolo de partida
Ascendente
(Bottom-up)
Sem retrocesso
(preditive)
•Recursiva
•Não Recursiva LL(1)
Um analisador preditivo tenta prever a construção seguinte da cadeia
de entrada com base em uma ou mais marcas de verificação à frente
ASD Preditiva
• Algoritmos:
– Recursivo
– LL(1)
• Gramáticas LL(1)
• O primeiro “L” se refere ao fato de o
processamento ocorrer da esquerda para a direita
(Left)
• O segundo “L” se refere ao fato de o analisador
acompanhar uma derivação à esquerda para a
cadeia de entrada.
• O número (1) significa que é usado um símbolo da
entrada para prever a direção da análise.
ASD preditiva não recursiva
• Idéia geral
– A recursão é substituída pelo uso de uma pilha onde os
símbolos sendo expandidos são armazenados
– Para determinar qual regra gramatical aplicar, consulta-se
uma tabela sintática
Cadeia de entrada
Pilha
X
a
+
Analisador sintático
Y
Z
$
b
Tabela sintática
$
Saída
ASD preditiva não recursiva
• Funcionamento
– Um símbolo não terminal a ser expandido é
empilhado
E  T E’
E’  + E | ε
Ta|b
Pilha
E
$
topo
ASD preditiva não recursiva
– Ao expandir um não terminal no topo da pilha, ele é
desempilhado e seu lado direito da regra gramatical é
empilhado (em sentido inverso) para expansão
•
O sentido inverso garante a ordem natural de expansão da
esquerda para a direita
Cadeia: a+b
E  T E’
E’  + E | ε
Ta|b
Cadeia: a+b
Pilha
Pilha
T
E
$
topo
E’
$
topo
ASD preditiva não recursiva
– Quando um símbolo terminal estiver no topo da pilha e esse
mesmo símbolo estiver no início da cadeia sendo reconhecida, o
terminal é desempilhado e o símbolo inicial da cadeia consumido
E  T E’
E’  + E | ε
Ta|b
Cadeia: a+b
Cadeia: +b
Pilha
Pilha
T
E’
$
topo
Pilha
a
topo
E’
E’
$
$
topo
ASD preditiva não recursiva
E  T E’
E’  + E | ε
Ta|b
Cadeia: +b
Pilha
Cadeia: +b
Cadeia: b
Pilha
Pilha
Cadeia: b
Pilha
+
E’
E
E
$
$
$
Cadeia: b
Pilha
T
b
E´
E´
$
$
ASD preditiva não recursiva
E  T E’
E’  + E | ε
Ta|b
Cadeia: b
Pilha
Cadeia: $
Cadeia: $
Pilha
Pilha
Pilha
b
E´
E´
$
$
Cadeia Aceita!
$
ASD preditiva não recursiva
•
Considere:
–
–
•
X = topo da pilha
a = símbolo inicial da cadeia de entrada
Possibilidades durante a análise:
1.
Se X = a = $, então o analisador termina a análise com sucesso
2.
Se X = a ≠ $, então o analisador desempilha X e consome o
símbolo inicial da cadeia
3.
Se X é não terminal, então o analisador procura na tabela
sintática a regra de X que produz o símbolo inicial da cadeia e
empilha seu lado direito (em sentido inverso)
4.
Se X é terminal e é diferente de ‘a’ ou se X é não terminal e não
há regra cuja derivação produza ‘a’, então ocorreu um erro!
ASD preditiva não recursiva
•
Algoritmo de análise sintática
Cadeia: 4+5$
empilhe um símbolo delimitador ($) e o símbolo inicial da gramática;
concatene ao final da cadeia um símbolo delimitador ($);
Pilha
faça ip apontar para o primeiro símbolo da cadeia;
repetir
X=símbolo no topo da pilha;
a=símbolo apontado por ip;
se (X for um terminal ou o símbolo delimitador) então
E
se X=a então
$
desempilhar X;
avançar ip;
senão ERRO;
senão /*X é um não terminal*/
se (existe na tabela sintática uma regra de X que produza a) então
desempilhar X;
empilhar em sentido inverso o lado direito da regra selecionada;
senão ERRO;
até que X=símbolo delimitador
/*pilha está vazia*/
X=topo
ASD preditiva não recursiva
• Exemplo
E  T E’
E’  + E | ε
Ta|b
topo
Tabela sintática
a
E
b
$
ETE’ ETE’
E’
T
+
E’+E E’ ε
Ta
Tb
Reconhecer a+b
Pilha
Cadeia
Regra
$E
a +b$
ETE’
$E’ T
a+b$
Ta
$E’ a
a+b$
---
$E’
+b$
E’+E
$E+
+b$
---
$E
b$
ETE’
$E’T
b$
Tb
$E’b
b$
---
$E’
$
E’ε
$
$
SUCESSO
ASD preditiva não recursiva
• Exemplo
E  T E’
E’  + E | ε
Ta|b
Pilha
Cadeia
Regra
$E
a*b$
ETE’
$E’T
a*b$
Ta
$E’a
a*b$
---
$E’
*b$
ERRO
Tabela sintática
a
E
b
$
E’+E
E’ε
ETE’ ETE’
E’
T
+
Ta
Tb
Reconhecer a*b
A cadeia não pertence à linguagem!
ASD preditiva não recursiva
• Exercício: reconheça a cadeia 01012
S  0A | 1B
A  1B | 2
B  0A | 2
Tabela sintática
S
0
1
S0A
S1B
A
B
A1B
B0A
2
A2
B2
Pilha
Cadeia
Regra
$S
01012$
S0A
$A0
01012$
---
$A
1012$
A1B
$B1
1012$
---
$B
012$
B0A
$A0
012$
---
$A
12$
A1B
$B1
12$
---
$B
2$
B2
$2
2$
---
$
$
SUCESSO
ASD preditiva não recursiva
• Como construir a tabela sintática?
S  0A | 1B
A  1B | 2
B  0A | 2
F(S)= {0, 1}
F(A)= {1,2}
F(B)= {0,2}
Tabela sintática
S
0
1
S0A
S1B
A
B
A1B
B0A
2
A2
B2
• De acordo com o exemplo, para um não terminal
X e um terminal ‘n’, a tabela indica a regra de X
cujo conjunto Primeiro (Fisrt) contém ‘n’
ASD preditiva não recursiva
• Exercício: construa a tabela sintática e reconheça a
cadeia 0aa
S  0A | B
A  aA | ε
Bb
F(S)= {0, b}
F(A)= {a, ε}
F(B)= {b}
Tabela sintática
0
S
A
B
a
S0A
b
$
SB
AaA
Aε
Bb
Pilha
Cadeia
Regra
$S
0aa$
S  0A
$A0
0aa$
---
$A
aa$
A  aA
$Aa
aa$
---
$A
a$
A  aA
$Aa
a$
---
$A
$
Aε
$
$
SUCESSO
ASD preditiva não recursiva
• Exercício: construa a tabela e reconheça a cadeia 0a1
F(S)= {0, b}
F(A)= {a, ε}
F(B)= {b}
S  0A1 | B
A  aA | ε
Bb
Tabela sintática
0
S
A
B
1
a
S0A1
b
$
SB
Aε
AaA
Aε
Bb
Pilha
Cadeia
Regra
$S
0a1$
S  0A1
$1A0
0a1$
---
$1A
a1$
A  aA
$1Aa
a1$
---
$1A
1$
ERRO
Por que aconteceu o erro?
A cadeia não faz parte da
linguagem? Ou a tabela está
errada?
Para se chegar ao terminal 1, A deve produzir ε. Portanto, a regra Aε deve ser
adicionada na tabela para a combinação de A com 1 e não em A com $
ASD preditiva não recursiva
•
Regras para construção da tabela sintática
1. Para cada produção A da gramática, execute os
passos 2 e 3 abaixo
2. Para cada terminal a em Primeiro(), adicione A
em T[A,a]
3. Se ε estiver em Primeiro(), adicione A em T[A,b]
para cada terminal b em Seguidor(A)
4. Faça cada entrada indefinida da tabela indicar erro
ASD preditiva não recursiva
• Exercício: construir a tabela sintática para a gramática abaixo
E TE’
E’ +TE’ | ε
T  FT’
T’  *FT’ | ε
F (E) | id
P(E) = { ( , id }
seguidor(E) = { ), $ }
P(E’) = { +, ε }
seguidor(E') = { ), $ }
P(T)={(, id}
seguidor(T) = { +, ), $ }
P(T’) = { *, ε }
seguidor(T’) = { +, ), $ }
P(F)={(, id}
seguidor(F) = {*, +, ), $ }
id
E
(
TFT’
$
E’ε
E’ε
T’ε
T’ε
TFT’
T’ε
Fid
)
ETE’
E’+TE’
T’
F
*
ETE’
E’
T
+
Tabela sintática
T’*FT’
F(E)
ASD preditiva não recursiva
• Exercício: reconhecer a cadeia id+id*id
E TE’
E’ +TE’ | ε
T  FT’
T’  *FT’ | ε
F (E) | id
Tabela sintática
id
E
(
TFT’
$
E’ε
E’ε
T’ε
T’ε
TFT’
T’ε
Fid
)
ETE’
E’+TE’
T’
F
*
ETE’
E’
T
+
T’*FT’
F(E)