Análise Sintática - Continuação
Parte 3
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)
Um analisador preditivo tenta prever a construção seguinte da cadeia
de entrada com base em uma ou mais marcas de verificação à frente
Análise sintática Descendente
Sem Retrocesso (Preditiva)
ASD Preditiva
• ASD preditiva
– Sabe-se de antemão qual regra aplicar
• Algoritmos:
– 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.
– LL(1)Recursivo
• Ambos algoritmos exigem, em geral, a computação dos
conjuntos de verificação Primeiro (First) e de Seqüência
(Follow)
ASD Preditiva Recursiva
• Um analisador sintático recursivo é um conjunto
de procedimentos possivelmente recursivos,
um para cada não terminal a ser derivado
– Também chamado de analisador de “descida
recursiva”
– Cada regra gramatical para um A não terminal é vista
como uma definição de um procedimento, em que o
lado direito de A especifica o código para esse
procedimento
ASD preditiva recursiva
• Exemplo
ET+E|T
TF*T|F
F  a | b | (E)
procedimento E
início
T;
se (token='+‘) então
prox_token();
E;
fim
procedimento ASD
início
prox_token();
E;
fim
procedimento T
início
F;
se (token =‘*‘) então
prox_token();
T;
fim
procedimento F
início
se ( token ='(‘ ) então
prox_token();
E;
se (token =')‘) então
prox_token()
senão ERRO;
senão se (token =‘a‘)
ou (token =‘b‘)
então prox_token()
senão ERRO;
fim
ASD preditiva recursiva
• Método formal para gerar os procedimentos
– Regras de transformação: mapeamento das regras de
um não terminal em grafos sintáticos
• Também podem ser usados diagramas de transição
(Aho et al., 1995, pg82)
– Regras de tradução: mapeamento dos grafos em
procedimentos
• Exemplo
S  aAd
A cA | eB
B f | g
Grafo sintático
S:
Símbolo
terminal
a
A
Símbolo não
terminal
ASD preditiva recursiva
S  aAd
S
a
A
procedimento S
início
se (token =‘a’) então
prox_token();
A;
se (token =‘d’)
então prox_token()
senão ERRO;
senão ERRO;
fim
d
ASD preditiva recursiva
A  cA | eB
procedimento A
início
se (token =‘c’) então
prox_token();
A;
senão se (token =‘e’) então
prox_token();
B;
senão ERRO;
fim
A
c
A
e
B
ASD preditiva recursiva
Bf|g
B
procedimento B
início
se (token =‘f’) ou (token =‘g’)
então prox_token()
senão ERRO;
fim
f
g
ASD preditiva recursiva
• Programa principal
procedimento ASD
início
prox_token();
S;
se (terminou_cadeia)
então SUCESSO
senão ERRO
fim
Geralmente, concatenamos um símbolo
$ no fim da cadeia antes do seu
reconhecimento.
terminou_cadeia é a verificação da
condição token = $
ASD preditiva recursiva
•
Regras de transformação
–
Regras gramaticais  grafos sintáticos
1. Toda regra da gramática é mapeada em um
grafo
2. Toda ocorrência de um terminal x corresponde
ao seu reconhecimento na cadeia de entrada e
a leitura do próximo símbolo dessa cadeia
x
ASD preditiva recursiva
3. Toda ocorrência de um não-terminal A
corresponde a análise imediata de A
A
4. Alternativas são representadas como
A
B
C
ASD preditiva recursiva
5. Uma seqüência A B C é mapeada em
A
B
C
6. A forma A* é representada por
A
ASD preditiva recursiva
• Exercício: Faça o grafo sintático da
gramática abaixo: A
x
A  x | (B)
B  AC
C  +AC | ε
(
)
B
B
A
C
C
+
A
C
ASD preditiva recursiva
• Os grafos sintáticos podem ser
simplificados
• transformar chamadas recursivas em loops
– Os grafos simplificados devem ser
equivalentes aos grafos originais
– As simplificações nos grafos vão se refletir no
código gerado para cada grafo
ASD preditiva recursiva
• Exemplo:
• Simplifique o grafo abaixo para C  +AC | ε
C
C
+
A
C
+
A
ASD preditiva recursiva
• Regras de tradução
– Grafos sintáticos  procedimentos
1. Reduzir o número de grafos: união
de grafos para maior simplicidade
e eficiência
ASD preditiva recursiva
• Faça a união dos grafos abaixo. Se possível,
simplifique após a união.
E
T
E’
T
E
T
+
T
E’
+
E
T
+
ASD preditiva recursiva
2. Escrever um procedimento para cada grafo
•
A seqüência
A
origina o procedimento
início
A;
B;
C;
fim
B
C
ASD preditiva recursiva
•
A alternativa
A
B
C
origina o procedimento
início
se (token está em Primeiro(A)) então A
senão se (token está em Primeiro(B)) então B
senão se (token está em Primeiro(C)) então C
fim
ASD preditiva recursiva
•
Uma repetição
A
origina o procedimento
início
enquanto (token está em Primeiro(A)) faça
A;
fim
ASD preditiva recursiva
•
O terminal
x
origina
início
se (token = x)
então prox_token()
senão ERRO;
fim
ASD preditiva recursiva
•
O não terminal
A
origina
início
A;
fim
ASD preditiva recursiva
• Exercício: fazer o(s) procedimento(s) para os
grafos sintáticos
– Se possível, reduza o no de grafos
A
B
x
(
A
)
B
C
+
A
C
ASD preditiva recursiva
A
Redução dos grafos
x
A
(
B
)
x
(
B
B
A
C
+
C
+
A
A
)
ASD preditiva recursiva
Redução dos grafos
A
x
A
(
B
x
)
+
+
A
(
A
)
ASD preditiva recursiva
procedimento A
início
se (token =‘x’) então prox_token()
senão se (token =‘(‘) então
faça
prox_token();
A;
até (token <>’+’);
se (token =‘)’)
então prox_token()
senão ERRO;
A
senão ERRO;
fim
x
+
(
A
)