6 AnaliseSintatica Parte2 - 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 2 
• Análise Sintática Descendente 
– FIRST e FOLLOW 
– Gramáticas LL(1) 
– Fatoração à esquerda 
– Eliminação de recursão à esquerda 
– Parser LL(1) 
– Recuperação de erro 
 
 
 
2 
Analisador Sintático Descendente 
• Marcador de fim de arquivo: 
– O parser lida não só com símbolos terminais, mas também com o fim de arquivo 
– Utiliza-se $ para representar o fim de arquivo 
– Suponha que S é o símbolo inicial da gramática 
– Para indicar que $ deve seguir depois de um sentença completa de S, é introduzido na 
gramática um novo símbolo inicial S’ e uma nova produção S’ → S$ 
 
 
 
 
 
 
 
 
 
 
 
3 
E → E + T | 
 E - T | 
 T 
T → T * F | 
 T / F 
 F 
F → id | 
 num| 
 (E) 
 
 
 
 
 
S → E$ 
E → E + T | 
 E - T | 
 T 
T → T * F | 
 T / F 
 F 
F → id | 
 num| 
 (E) 
Analisador Sintático Descendente 
 
• Parser recursivo descendente (ou preditivo) não funciona para qualquer 
gramática: 
 
 Exemplo: 
S → E$ 
E → E + T | 
 E - T | 
 T 
T → T * F | 
 T / F 
 F 
F → id | 
 num| 
 (E) 
 
 
 
4 
Analisador Sintático Descendente 
void S(){ 
 E(); eat(EOF); 
} 
 
void E(){ 
 switch(tok){ 
 case ?: E(); eat(PLUS); T(); break; 
 case ?: E(); eat(MINUS); T(); break; 
 case ?: T(); break; 
 default: error(); 
 } 
} 
 
void T(){ 
 switch(tok){ 
 case ?: T(); eat(TIMES); F(); break; 
 case ?: T(); eat(DIV); F(); break; 
 case ?: F(); break; 
 default: error(); 
 } 
} 
 
5 
Analisador Sintático Descendente 
• Há conflito na implementação do parser para essa gramática: 
 
– na função E, por exemplo, não é possível definir qual cláusula será utilizada 
 
Por exemplo: 
 
 Para a entrada (1 * 2 - 3) + 4 deveria ser utilizada a produção E → E + T 
 
 Mas para a entrada (1 * 2 - 3) deveria ser utilizada a produção E → T 
 
 
 
6 
Analisador Sintático Descendente 
 
• Parser recursivo descendente (ou preditivo, ou analisador sintático 
de descida recursivo) funciona apenas em gramáticas nas quais o 
primeiro símbolo terminal de cada sub-cadeia provê informação 
suficiente para escolher a próxima produção a ser utilizada. 
 
• As características dessas gramáticas baseiam-se em dois conceitos: 
FIRST e FOLLOW 
 
7 
Analisador Sintático Descendente - FIRST 
• FIRST: 
 
– Dada uma cadeia α de símbolos terminais e não terminais, FIRST(α) é o 
conjunto de todos os símbolos terminais que podem iniciar qualquer cadeia 
derivada de α 
 
– Por exemplo: 
 
• Seja α = T * F (uma produção de T na gramática anterior). 
 
• Qualquer cadeia de símbolos terminais derivadas de α deve começar com 
id, num ou ( 
 
• FIRST(T*F) = {id, num, (} 
 
8 
Analisador Sintático Descendente - FIRST 
 
– Se duas produções diferentes X → α1 e X → α2 têm o mesmo símbolo do lado 
esquerdo (X) e os lados direitos têm FIRST sobrepostos (FIRST com algum 
elemento em comum), então não é possível utilizar um parser preditivo para a 
gramática. 
 
– Se algum símbolo terminal I estiver em FIRST(α1 ) e em FIRST(α2 ), a função X 
no parser preditivo não saberá o que fazer se o token na entrada for I. 
 
Exemplo: 
T → T * F | 
 T / F 
 F 
F → id | 
 num| 
 (E) 
9 
Analisador Sintático Descendente – FIRST 
• FIRST deve ser calculado para todos os símbolos X (terminais e não 
terminais) da gramática. 
 
• Para calcular o FIRST(X) de todos os símbolos X da gramática, aplicam-se 
as regras a seguir até que não haja mais terminais ou λ que possam ser 
inseridos em algum FIRST(X) 
 
– Ou seja, até que não seja mais possível alterar FIRST(X) algum. 
 
 
 
 
 
 
 
 
 
10 
Analisador Sintático Descendente - FIRST 
Exemplo: considere a gramática 
Z → d | XYZ 
Y → λ | c 
X → Y | a 
 
 
 
1. Se X é um símbolo terminal, então FIRST(X) = {X} 
 
FIRST(a) = {a} 
FIRST(c) = {c} 
FIRST(d) = {d} 
 
 
 
 
 
 
11 
Analisador Sintático Descendente - FIRST 
2. Se X é um símbolo não terminal 
 Seja a um dos símbolos terminais 
 Se X → Y1Y2...Yk é uma produção para algum k ≥ 1 
 Se para algum i (1 ≥ i ≥ k), a estiver em FIRST(Yi) e 
 λ estiver em todos os FIRST(Y1), ..., FIRST(Yi-1) , ou seja, Y1...Yi-1 
 puder produzir λ, então 
 
 Acrescente a a FIRST(X) 
 
 Se λ está em todos os FIRST(Y1), ..., FIRST(Yk) 
 então 
 Acrescente λ a FIRST(X) 
 
 Se Yi não derivar λ, então não se acrescenta mais nada a FIRST(X) 
 Senão, adiciona-se FIRST(Yi+1) a FIRST(X), e assim por diante. 
 
 12 
Analisador Sintático Descendente - FIRST 
Z → d | XYZ 
Y → λ | c 
X → Y | a 
 
Na gramática anterior tem-se os seguintes conjuntos FIRST: 
 
FIRST(Y): {λ, c} 
FIRST(X): {a, c, λ} 
FIRST(Z): {d, a, c } 
 
 
 
 
 
13 
Analisador Sintático Descendente - FOLLOW 
• FOLLOW: 
 
– FOLLOW(X) , onde X é um símbolo não terminal, é o conjunto de terminais 
que podem imediatamente seguir X 
 
– a Є FOLLOW(X) se existir alguma derivação que contenha αXaβ 
 
– Isso pode ocorrer se houver alguma derivação do tipo αXYaβ onde Y deriva λ 
 
– Se X for o símbolo não terminal mais à direita em alguma forma sentencial, 
então $ está em FOLLOW(X) 
 
• $ é um símbolo “marcador de fim de cadeia de entrada” ou “marcador de fim de arquivo” 
 
 
 
14 
Analisador Sintático Descendente - FOLLOW 
• Para calcular o FOLLOW para todos os não-terminais A, aplicam-se as 
seguintes regras até que nada mais possa ser acrescentado a nenhum dos 
conjuntos FOLLOW: 
 
1. Coloque $ em FOLLOW(S), onde S é o símbolo inicial da gramática e $ é o 
marcador de fim de arquivo. 
 
2. Se houver uma produção A → αBβ (onde α e β são cadeias de símbolos da 
gramática, e B é um não terminal ), então tudo em FIRST(β), exceto λ, está em 
FOLLOW(B) 
 
3. Se houver uma produção A → αB ou A → αBβ , onde o FIRST(β) contém λ, 
então inclui-se o FOLLOW(A) em FOLLOW(B) 
 
 
 
15 
Analisador Sintático Descendente - FOLLOW 
Z → d | XYZ 
Y → λ | c 
X → Y | a 
 
FIRST(Y): {λ, c} 
FIRST(X): {a, c, λ} 
FIRST(Z): {d, a, c } 
 
 
Na gramática anterior tem-se os seguintes conjuntos FOLLOW: 
 
FOLLOW(Z): {$} 
FOLLOW(Y): {d, a, c} 
FOLLOW(X): {c, d, a } 
 
 
 
 
16 
Analisador Sintático Descendente – 
FIRST e FOLLOW 
Outro exemplo: considere a gramática a seguir 
 
E → T K 
K → +T K | λ 
T → F X 
X → *F X | λ 
F → ( E ) | id 
 
 
 
17 
FIRST FOLLOW 
+ + - 
* * - 
( ( - 
) ) - 
id id - 
F (, id +, $, ), * 
X *, λ +, $, ) 
T (, id +, $, ) 
K +, λ $, ) 
E (, id $, ) 
Analisador Sintático Descendente - Tabela 
• Tabela de Parser preditivo para uma gramática: 
– Considere um parser preditivo 
 
– O procedimento para um não-terminal X tem uma cláusula para cada 
produção X 
 
– A cláusula é escolhida com base no próximo token a na entrada 
 
– Se for possível escolher a produção correta para cada par (X, a), então é 
possível escrever um parser preditivo. 
 
• Toda a informação necessária para escrevero parser preditivo pode 
ser representada em uma tabela bidimensional, indexada por não 
terminais X e terminais a 
 
– Esta tabela é chamada Tabela de Parser Preditivo 
18 
Analisador Sintático Descendente - Tabela 
• Para construir esta tabela: 
 
– entre com a produção X → β na linha X, coluna a para cada a Є FIRST(β); 
 
– Se β é anulável (pode produzir λ) , entre com a produção X → β na linha X, 
coluna a para cada a Є FOLLOW(X). 
 
Exemplo: 
Z → d | XYZ 
Y → λ | c 
X → Y | a 
 
19 
FIRST FOLLOW 
X a, c, λ a, c, d 
Y c, λ a, c, d 
Z a, c, d $ 
1 a c d 
X X → a 
X → Y 
X → Y 
 
X → Y 
 
Y 
Z 
X → a : a pertence ao FIRST(a). Logo, a 
produção X → a deve ser incluída na 
linha, X, coluna a 
X → Y : c pertence ao FIRST(Y). 
Logo, a produção X → Y deve ser 
incluída na linha, X, coluna c 
Y é anulável, logo a produção 
X → Y deve ser incluída na colunas 
pertencentes ao FOLLOW(X): a, c e d 
Analisador Sintático Descendente - Tabela 
Z → d | XYZ 
Y → λ | c 
X → Y | a 
 
20 
FIRST FOLLOW 
X a, c, λ a, c, d 
Y c, λ a, c, d 
Z a, c, d $ 
2 a c d 
X X → a 
X → Y 
X → Y 
 
X → Y 
 
Y Y → λ Y → c 
Y → λ 
Y → λ 
Z 
Y → c : c pertence ao FIRST(c). Logo, 
a produção Y → c deve ser incluída 
na linha, Y, coluna c 
Y tem uma produção Y → λ, ou seja ,é anulável. 
Logo a produção Y → λ 
deve ser incluída na colunas pertencentes ao 
FOLLOW(Y): a, c e d 
Analisador Sintático Descendente - Tabela 
Z → d | XYZ 
Y → λ | c 
X → Y | a 
 
21 
FIRST FOLLOW 
X a, c, λ a, c, d 
Y c, λ a, c, d 
Z a, c, d $ 
3 a c d 
X X → a 
X → Y 
X → Y 
 
X → Y 
 
Y Y → λ Y → c 
Y → λ 
Y → λ 
Z Z → XYZ 
 
Z → XYZ 
 
Z → d 
Z → XYZ 
Z → d : d pertence ao FIRST(d). Logo, a produção 
Z → d deve ser incluída na linha Z, coluna d 
FIRST(XYZ) é {a, c, d}. Logo a produção Z → XYZ 
deve ser incluída na linha Z, coluna a, b e c 
Analisador Sintático Descendente - Tabela 
 
Z → d | XYZ 
Y → λ | c 
X → Y | a 
 
 
 
 
• A tabela de parser preditivo para a gramática possui entradas duplicadas 
(mais de uma produção para um par de não terminal e terminal). 
 
• A presença de entradas múltiplas na tabela implica que o parser preditivo 
não funcionará para a gramática 
 
22 
a c d 
X X → a 
X → Y 
X → Y 
 
X → Y 
 
Y Y → λ Y → c 
Y → λ 
Y → λ 
Z Z → XYZ 
 
Z → XYZ 
 
Z → d 
Z → XYZ 
Analisador Sintático Descendente – 
Gramática LL(1) 
• A gramática é ambígua 
 
Z → d | XYZ 
Y → λ | c 
X → Y | a 
 
 
• Uma gramática ambígua sempre levará a entradas duplicadas na tabela de 
parser preditivo. 
 
• Para gerar um parser preditivo para essa gramática é necessário encontrar 
uma gramática não ambígua. 
 
• Uma gramática cuja tabela de parser preditivo não contém entradas 
múltiplas é denominada LL(1). 
 
23 
Z 
d 
Z 
Y d X 
Y 
λ 
λ 
Analisador Sintático Descendente – 
Gramática LL(1) 
• Analisadores sintáticos preditivos podem ser construídos para uma classe 
de gramáticas chamada LL(1): 
 
– Primeiro L indica left-to-right: significa que a cadeia da entrada é 
processada da esquerda para a direita 
 
– Segundo L indica leftmost: indica que a derivação é mais à esquerda 
 
– 1 indica que é necessário conhecer apenas 1 símbolo à frente em cada 
passo para tomar decisões quanto à ação a ser tomada (1-symbol 
lookahead). 
 
 
24 
Analisador Sintático Descendente – 
Gramática LL(1) 
• Gramáticas LL(1) são suficientemente ricas para reconhecer a maioria das 
construções presentes nas linguagens de programação 
 
• Porém, escrever uma gramática LL(1) pode não ser fácil 
 
• Felizmente, os conflitos em tabelas LL(1) em linguagens de programação 
são resultantes de duas categorias principais: prefixos comuns e recursão 
à esquerda. 
 
• Transformações simples na gramática que eliminam prefixos comuns e 
recursão à esquerda permitem transformar a maior parte das gramáticas 
de linguagens de programação em LL(1) 
 
 
 
25 
Analisador Sintático Descendente – 
Fatoração à esquerda 
• A fatoração à esquerda é uma transformação na gramática útil na 
produção de gramáticas adequadas para um reconhecedor 
sintático preditivo 
 
• Quando duas ou mais produções de um símbolo não terminal 
começam com a mesma forma sentencial (prefixo comum), não é 
claro qual das produções deve ser escolhida. 
 
• Esse problema pode ser resolvido reescrevendo-se as produções de 
forma a adiar a decisão até que se tenha lido a cadeia de entrada o 
suficiente 
 
 
26 
Analisador Sintático Descendente – 
Fatoração à esquerda 
• Exemplo: 
 
stmt → if expr then stmt | 
 if expr then stmt else stmt | 
 other 
 
– Ao ler um if na entrada, não é possível decidir qual produção será 
escolhida 
 
– Derivações para if E1 then if E2 then S1 else S2? 
 
 
 
 
 
 
27 
Analisador Sintático Descendente – 
 Fatoração à esquerda 
if E1 then if E2 then S1 else S2 
 
28 
stmt 
expr then if stmt 
expr then if stmt else stmt 
E1 
E2 S1 S2 
expr then if stmt else stmt 
E1 S2 
stmt 
expr then if stmt 
E2 S1 
Em todas as linguagens de 
programação, esta é a 
derivação preferida: casar 
o else com o then não 
casado mais próximo. 
Analisador Sintático Descendente – 
Fatoração à esquerda 
• Em geral, se 
 A → αβ1 | αβ2 (α é o prefixo comum) 
 pode-se adiar a decisão expandindo 
 A para αA’ 
 e, então, após ler a entrada derivada de α, 
 expandir A’ para β1 ou β2 . 
 
 A → αA’ 
 A’ → β1 | β2 
 
 
 
 
29 
Analisador Sintático Descendente – 
Fatoração à esquerda 
• Exemplo: 
stmt → if expr then stmt | 
 if expr then stmt else stmt | 
 other 
 
stmt → if expr then stmt stmt’ | 
 other 
stmt’ → λ | 
 else stmt 
 
 
 
 
 
 
30 
FIRST FOLLOW 
stmt if, other else 
stmt’ else, λ else 
if then other else 
stmt stmt → if expr then stmt stmt’ 
 
stmt → other 
stmt’ stmt ‘ → else stmt 
stmt’ → λ 
Analisador Sintático Descendente – 
Fatoração à esquerda 
• Embora a gramática seja ainda ambígua, ela não representa um problema 
para o parser preditivo 
 
• O problema pode ser resolvido escolhendo-se a produção 
 stmt’→ else stmt, em vez de escolher a produção λ quando houver um 
else na entrada. 
 
 
 
 
 
31 
stmt 
expr then stmt 
expr then if stmt 
else 
E1 
E2 S1 
S2 
if stmt’ 
stmt’ 
stmt 
Escolher produção 
stmt ‘ → else stmt em vez 
de escolher 
stmt’ → λ 
λ 
Analisador Sintático Descendente 
 
void stmtprime(){ 
 // stmt’ → λ | 
 // else stmt 
 if (tok == ELSE) {eat(ELSE); stmt();} 
} 
 
32 
Analisador Sintático Descendente – 
Eliminação de Recursão à Esquerda 
• Suponha que queiramos construir um parser preditivo para a 
gramática: 
 
S → E$ 
E → E + T | 
 E - T | 
 T 
T → T * F | 
 T / F 
 F 
F → id | 
 num| 
 (E) 
 
 33 
Analisador Sintático Descendente – 
Eliminação de Recursão à Esquerda 
• A tabela do parser preditivo certamente conterá entrada duplicada 
 
• Por exemplo, em E → E + T | T, FIRST(T) está em FIRST(E)• O problema é que E aparece como o primeiro termo no lado direito de 
uma produção E 
 
• Isso é denominado recursão à esquerda 
 
• Gramáticas com recursão à esquerda não podem ser LL(1) 
 
• Para eliminar a recursão à esquerda, reescreve-se a gramática utilizando-
se recursão à direita 
 
 34 
Analisador Sintático Descendente – 
Eliminação de Recursão à Esquerda 
• Considere as regras a seguir, em que nenhum w começa com o símbolo 
não terminal X. 
 
X → Xy1 | Xy2 | ... | Xyn | w1 | w2 | ... | wk 
 
• As regras X são utilizadas da seguinte forma em uma derivação mais a 
esquerda: 
 
X Xyip yip-1 ... yi1 wj yip yip-1 ... yi1 
 
• A forma sentencial wj yip yip-1 ... Yi1 pode ser obtida utilizando-se 
recursão à direita em vez de recursão à esquerda, por meio das regras: 
 
X → w1Z | w2 Z| ... | wkZ 
Z → y1 Z | y2 Z | ... | yn Z | λ 
 
 
 
35 
Analisador Sintático Descendente – 
Eliminação de Recursão à Esquerda 
S → E$ 
E → TE’ 
E’ → + TE’ 
 | - TE’ 
 | λ 
T → F T’ 
T’ → * F T’ 
 | / F T’ 
 | λ 
F → id 
 | num 
 | (E) 
 
 
36 
Analisador Sintático Descendente – 
Eliminação de Recursão à Esquerda 
S → E$ 
E → TE’ 
E’ → + TE’ | - TE’ | λ 
T → F T’ 
T’ → * F T’ | / F T’ | λ 
F → id | num | (E) 
 
 
37 
FIRST FOLLOW 
S id, num, ( $ 
E id, num, ( $,) 
E’ +, -, λ $,) 
T id, num, ( $,), +, - 
T’ *, /, λ $,), +, - 
F id, num, ( $,), +, -,*,/ 
+ - * / id num ( ) $ 
S S → E$ S → E$ S → E$ 
E E → TE’ E → TE’ E → TE’ 
E’ E’ → + TE’ E’ → - TE’ E’ →λ E’ →λ 
T T → F T’ T → F T’ T → F T’ 
T’ T’ →λ T’ →λ T’ → * F T’ T’ → / F T’ T’ →λ T’ →λ 
F F → id F → num F → (E) 
Analisador Sintático Descendente 
• A partir da tabela, é fácil escrever o parser recursivo descendente: 
 
void T(){ 
 switch(tok){ 
 case ID: 
 case NUM: 
 case LPAREN: F(); Tprime(); break; 
 default: error(); 
 } 
} 
 
38 
Analisador Sintático Descendente 
 
void Tprime(){ 
 switch(tok){ 
 case MINUS: break; 
 case PLUS: break; 
 case TIMES:eat(TIMES); F(); Tprime(); break; 
 case DIV:eat(DIV); F(); Tprime(); break; 
 case EOF: break; 
 case RPAREN: break; 
 default: error(); 
 } 
} 
 
39 
Recuperação de Erro 
• Um erro sintático ocorre quando há um token na entrada não esperado 
pelo analisador sintático. 
 
• Na ocorrência de um erro sintático, é seguro apenas emitir uma 
mensagem de erro para o usuário e abortar o processo de compilação. 
 
• Porém, o melhor é emitir a mensagem de erro e recuperar do erro, de 
forma que outros erros de compilação possam ser identificados. 
 
• Recuperação de erro pode ser realizada principalmente pela inserção ou 
exclusão de tokens na entrada. 
40 
Recuperação de Erro 
• Inserção de Tokens 
 
– A entrada de dados (arquivo fonte) não é de fato modificada 
 
– É suficiente simular que o token esperado foi encontrado, emitir uma 
mensagem de erro e retornar normalmente. 
 
void T(){ 
 switch(tok){ 
 case ID: 
 case NUM: 
 case LPAREN: F(); Tprime(); break; 
 default: print(“Expected id, num or left-paren.”); 
 } 
} 
41 
Recuperação de Erro 
• Modo Pânico 
 
– Tokens são descartados da entrada, até que um token esperado (token de 
sincronismo) seja encontrado 
 
– A eficácia do método depende da escolha do conjunto de sincronismo 
 
– Uma heurística simples para essa escolha é utilizar o conjunto FOLLOW do 
símbolo não terminal como tokens de sincronismo. 
 
 
 
42 
Recuperação de Erro 
 
int Tprime_synch[] = {PLUS, MINUS, RPAREN, EOF}; 
 
void Tprime(){ 
 switch(tok){ 
 case MINUS: break; 
 case PLUS: break; 
 case TIMES:eat(TIMES); F(); Tprime(); break; 
 case DIV:eat(DIV); F(); Tprime(); break; 
 case EOF: break; 
 case RPAREN: break; 
 default: print(“Expected +, -, *, rigth-paren or 
 end-of-file”); 
 skipto(Tprime_synch); 
 } 
} 
43 
Referência Bibliográfica 
Compiladores – Princípios, técnicas e ferramentas. 
Aho, A. V et al. 2ª edição 
Seção 4.3, Seção 4.4.1,4.4.2, 4.4.3 e 4.4.5 (somente Modo 
Pânico) 
 
Modern Compiler Implementation in Java. Second Edition. 
Andrew W. Appel. 
Capítulo 3. 
 
 
 
44