6 AnaliseSintatica Parte6 - Compiladores CEFET MG

Prévia do material em texto

Compiladores 
Prof.ª Kecia Aline Marques Ferreira 
CEFET-MG 
 
Análise Sintática 
1 
Análise Sintática – Parte 6 
 
• Recuperação de Erro em parser LR 
 
 
 
 
2 
Recuperação de Erros 
• Um analisador sintático LR detecta um erro quando consulta a 
tabela de parser na parte de ações e encontra uma entrada 
vazia. 
 
• Nesta situação, o analisador sintático pode reportar o erro ao 
usuário e encerrar a análise. 
 
• Contudo, isso pode não ser desejável para o usuário, pois o 
impossibilita identificar a maior quantidade de erros possível. 
 
 
 
 
 
 
3 
Recuperação de Erro com Símbolo ERRO 
• Este método de recuperação de erro usa um símbolo especial 
ERROR para controlar o processo de recuperação. 
 
• Nos locais em que o símbolo ERROR aparecer em uma regra 
da gramática, uma sequência de tokens errôneos na entradas 
podem ser casados. 
 
• Considere a gramática a seguir: 
exps → exp 
 | exps; exp 
exp → ID 
 |exp + exp 
 |(exps) 
 
 
4 
Recuperação de Erro com Símbolo ERRO 
• Informalmente, poderia ser definido que se um erro sintático for 
encontrado no meio de um expressão, o parser deve desviar para o 
próximo ; ou ) e retomar a análise 
 
• Os símbolos para os quais o parser deve desviar são chamados 
tokens de sincronismo. 
 
• Isso é realizado com a inserção de produções de recuperação de 
erros na gramática, tais como: 
 
exps → exp 
 | exps; exp 
 | ERROR; exp 
exp → ID 
 |exp + exp 
 |(exps) 
 |(ERROR) 
 
 
 
5 
Analisador Sintático LR(0) 
S → exps $ 
exps → exp 
 | exps; exp 
 | ERROR; exp 
exp → ID 
 |exp + exp 
 |(exps) 
 |(ERROR) 
 
6 
S → • exps $ 
exps → • exp 
exps → • exps; exp 
exps → • ERROR; exp 
exp → • ID 
exp → • exp + exp 
exp → • (exps) 
exp → • (ERROR) 
1 
exps → ERROR •; exp 
exps → ERROR; • exp 
exp → • ID 
exp → • exp + exp 
exp → • (exps) 
exp → • (ERROR) 
ERROR 
; 
2 
3 
Recuperação de Erro com Símbolo ERRO 
• O que o parser faz com símbolo ERROR? 
– ERROR é considerado um símbolo terminal da gramática 
 
– Ações shift são incluídas na tabela de parser como se ele fosse um 
token como outro qualquer 
 
– Quando um parser chega a um estado de erro, ele realiza as seguintes 
ações: 
1. Desempilha (se necessário) até chegar a um estado em que a 
ação para o token ERROR seja um shift. 
2. Realiza um shift do token ERROR 
3. Descarta tokens da entrada até encontrar um que possua uma 
ação diferente de erro no estado atual (aquele do topo da pilha) 
4. Retoma a análise 
 
 
7 
Recuperação de Erro com Símbolo ERRO 
• Deve-se tomar cuidado para que nas produções inseridas 
na gramática o símbolo ERROR seja seguido pelos tokens 
adequados. 
 
• Caso contrário, é possível que todos os tokens à frente da 
ocorrência do erro sejam descartados. 
 
• Este é o modo de recuperação de erro utilizado pelo Yacc 
e pelo CUP 
 
 
 
 
 
8 
Modo Pânico 
• O modo pânico de recuperação de erro no parser LR tenta 
eliminar a frase que contém o erro sintático 
 
– O analisador identifica que uma cadeia derivável de A contém um 
erro. 
 
– Parte dessa cadeia já foi processada e o resultado desse 
processamento é uma sequência de elementos no topo da pilha 
 
– O restante da cadeia está na entrada 
 
– O analisador tenta ignorar o restante dessa cadeia procurando um 
símbolo na entrada que possa aparecer após A. 
 
 
 
 
9 
Modo Pânico 
• Em resumo, este método: 
 
– Remove elementos do topo da pilha que deram início ao 
reconhecimento de A 
– Empilha A 
– Ignora os tokens na entrada que formariam A, buscando um token que 
possa aparecer após A. 
– Executa a ação goto referente ao estado s e A, sendo s estado do topo 
da pilha. 
 
Ou seja 
– O analisador simula que encontrou uma instância de A e prossegue a 
análise. 
 
 
 
 
10 
Modo Pânico 
• Na análise LR, o modo pânico de recuperação de erro ocorre 
da seguinte forma: 
 
– A pilha é analisada até que seja encontrado um estado s com uma 
transição sob um determinado símbolo não terminal A. 
 
– Zero ou mais símbolos da entrada são descartados até que seja 
encontrado um símbolo a que possa vir legitimamente após o símbolo 
A. 
 
– O analisador realiza a ação gn, que é dada na entrada da tabela 
referente ao estado s e ao símbolo A e prossegue a análise. 
 
 
 
 
 
11 
Modo Pânico 
– A escolha do símbolo A: 
 
• Geralmente escolhe-se um símbolo que represente uma 
construção importante no programa, por exemplo: expressão, 
comando e bloco. 
 
– A escolha do símbolo a: 
 
• Deve ser um símbolo que, em uma sequência válida, pode 
aparecer após A. 
 
• Por exemplo, se A for um comando, a poderia ser ponto e vírgula 
ou }, se esses símbolos encerrarem comando em linguagem de 
programação. 
 
 
 
 
12 
Modo Pânico 
• Exemplo : execução do parser para a entrada (x, (xx)) 
 
 
 
13 
Pilha Entrada Ação 
1 (x, (xx))$ s3 
1 (3 x, (xx))$ s2 
1 (3 x2 , (xx))$ r2 
1 (3 S7 , (xx))$ r3 
1 (3 L5 , (xx))$ s8 
1 (3 L5 ,8 (xx))$ s3 
1 (3 L5 ,8 (3 xx))$ s2 
1 (3 L5 ,8 (3 x2 x))$ r2 
1 (3 L5 ,8 (3 S7 x))$ r3 
1 (3 L5 ,8 (3 L5 x))$ ERRO 
( ) x , $ S L 
1 s3 s2 g4 
2 r2 r2 r2 r2 r2 
3 s3 s2 g7 g5 
4 a 
5 s6 s8 
6 r1 r1 r1 r1 r1 
7 r3 r3 r3 r3 r3 
8 s3 s2 g9 
9 r4 r4 r4 r4 r4 
0. S’ → S$ 
1. S → (L) | 
2. x 
3. L → S | 
4. L, S 
Modo Pânico 
• Exemplo : execução do parser para a entrada (x, (xx)) 
 
 
 
14 
Pilha Entrada Ação 
1 (3 L5 ,8 (3 L5 x))$ ERRO 
1 (3 L5 ,8 (3 L5 ))$ Desempilhar até 
estado que possua 
goto com L. 
Descartar tokens 
até encontrar ) ou , 
1 (3 L5 ,8 (3 L5 ))$ s6 
1 (3 L5 ,8 (3 L5 )6 )$ r1 
1 (3 L5 ,8 S9 )$ r4 
1 (3 L5 )$ S6 
1 (3 L5 )6 $ r1 
1 S4 $ aceita 
( ) x , $ S L 
1 s3 s2 g4 
2 r2 r2 r2 r2 r2 
3 s3 s2 g7 g5 
4 a 
5 s6 s8 
6 r1 r1 r1 r1 r1 
7 r3 r3 r3 r3 r3 
8 s3 s2 g9 
9 r4 r4 r4 r4 r4 
0. S’ → S$ 
1. S → (L) | 
2. x 
3. L → S | 
4. L, S 
Referência Bibliográfica 
Compiladores – Princípios, técnicas e ferramentas. 
Aho, A. V et al. 2ª edição 
Seção 4.8.3 
 
Modern Compiler Implementation in Java. Second Edition. 
Andrew W. Appel. 
Capítulo 3. 
 
 
 
 
 
15