7 TraduçãoDirigidaSintaxe Parte2 - Compiladores CEFET MG

Prévia do material em texto

Compiladores 
Prof.ª Kecia Aline Marques Ferreira 
CEFET-MG 
 
Tradução Dirigida por Sintaxe 
1 
Tradução Dirigida por Sintaxe – Parte 2 
• Tradução Dirigida por Sintaxe 
 
– Esquemas de Tradução Dirigidos por Sintaxe (SDT) 
• Conceito 
• SDT pós-fixado 
• SDT para definições L-atribuídas 
• Ordem de execução das ações semânticas 
• Tradução na Análise Descendente Recursiva 
 
 
 
 
 
 
2 
Esquemas de Tradução Dirigidos por Sintaxe 
• Os esquemas de tradução dirigidos por sintaxe são uma notação 
complementar para as definições dirigidas por sintaxe 
 
• As definições dirigidas por sintaxe são implementadas usando 
esquemas de tradução 
 
• Um esquema de tradução dirigido por sintaxe (SDT) é uma 
gramática livre de contexto com fragmentos de programa inseridos 
no corpo das produções 
 
• Os fragmentos de programa são denominados ações semânticas 
 
 
 
 
3 
Esquemas de Tradução Dirigidos por Sintaxe 
• Por convenção, as ações semânticas aparecem entre chaves 
 
• Se as chaves fazem parte dos símbolos terminais da gramática, 
então elas devem ser colocadas entre aspas (‘’) para diferenciá-las. 
 
 
 
 
 
 
 
 
 
 
 
4 
Esquemas de Tradução Pós-fixados 
• SDT com todas as ações nos extremos direitos do corpo da 
produção são denominados SDT pós-fixados. 
 
• Esse tipo de SDT é aplicável quando os atributos são sintetizados, 
ou seja, a SDD é S-atribuída 
 
• Exemplo: SDT pós-fixado implementando uma calculadora de mesa: 
 
 
 
 
 
 
 
 
5 
L → E $ { print(E.val) } 
E → E1 + T { E.val = E1 .val + T.val } 
E → T { E.val = T.val } 
T → T1 * F { T.val =T1.val * F.val } 
T → F { T.val = F.val } 
F → (E) { F .val = E.val } 
F → digit { F.val = digit.lexval } 
Esquemas de Tradução para SDD L-atribuída 
• O caso mais geral de SDD é a L-atribuída 
 
• Com qualquer gramática (LR ou LL), as regras para transformar uma SDD L-
atribuída em um SDT são: 
 
– Atributo herdado: 
Incorpore a ação que avalia o atributo herdado de A imediatamente antes da 
ocorrência de A no corpo da produção 
 
Se vários atributos herdados de A dependerem um do outro, ordene a avaliação 
de atributos de modo que aqueles que são necessários primeiro sejam os 
primeiros a serem calculados. 
 
– Atributo sintetizado: 
Incorpore as ações que avaliam o atributo sintetizado da cabeça de uma produção 
no fim do corpo dessa produção 
 
 
 
6 
Ordem de Execução das Ações Semânticas 
• Uma ação pode ser inserida em qualquer posição dentro do corpo 
de uma produção 
 
• A ação é executada imediatamente após todos os símbolos à sua 
esquerda serem processados 
 
• Em uma produção B → X {ação} Y: 
 
– Se X é um símbolo terminal, a ação é executada após X ser reconhecido 
 
– Se X é um símbolo não terminal, a ação é realizada após todos os terminais 
derivados de X serem reconhecidos 
 
 
 
 
7 
Ordem de Execução das Ações Semânticas 
• Ou seja: 
 
– Se a análise for ascendente, a ação na produção B → X {ação} Y é 
executada assim que houver uma redução para X (X for inserido no 
topo da pilha) 
 
– Se a análise for descendente, a ação é executada imediatamente após 
a expansão de X e antes de tentar expandir Y 
 
 
 
 
 
 
 
8 
Tradução em Parser Recursivo Descendente 
• A implementação de um tradutor a partir de um parser se dá 
com a inclusão de comandos adequados nos locais referentes 
às ações semânticas. 
 
• Exemplo: um tradutor dirigido por sintaxe que traduz 
expressões aritméticas para a notação pós-fixada 
 
E → E1 + T { print ( ‘+’ ) } 
 | E1 - T { print ( ‘-’ ) } 
 | T 
T → digit {print (digit.lexval)} 
 
 9 
Tradução em Parser Recursivo Descendente 
• A eliminação da recursão à esquerda no esquema de tradução 
resulta em: 
 
 E → T R 
R → + T { print ( ‘+’ ) } R 
 |- T { print ( ‘-’ ) } R 
 | λ 
T → digit {print (digit.lexval)} 
 
 
10 
Tradução em Parser Recursivo Descendente 
class Token{ 
 int kind; //tipo do token 
 Object val; //representa o valor do token 
 
 Token(int k, Object v){ 
 kind = k; 
 val = v; 
 } 
} 
 
 
 
 
 
 
 
11 
Tradução em Parser Recursivo Descendente 
final int EOF=0, NUM=1, PLUS=2, MINUS =3; 
 
Token tok = getToken(); 
 
void advance() {tok = getToken();} 
 
void eat(int t) { 
 if (tok.kind == t) advance(); 
 else error(); 
} 
 
 
 
 
 
 
12 
Tradução em Parser Recursivo Descendente 
void E(){ 
 
 // E → T R 
 
 if (tok.kind == NUM){ 
 T(); R(); 
 } 
 else error(); 
} 
 
 
 
 
 
 
 
13 
Tradução em Parser Recursivo Descendente 
void T(){ 
 
 // T → digit { print (digit.lexval) } 
 
 if (tok.kind == NUM){ 
 print(tok.val); 
 eat(NUM); 
 } 
 else error(); 
} 
 
 
 
 
 
 
14 
Tradução em Parser Recursivo Descendente 
void R(){ 
 
 switch(tok.kind){ 
 
 // R → + T { print ( ‘+’ ) } R 
 case PLUS: eat(PLUS); T(); print (‘+’); R(); break; 
 
 // R → - T { print ( ‘-’ ) } R 
 case MINUS: eat(MINUS); T(); print (‘-’); R(); 
 break; 
 } 
} 
 
 
 
 
 
15 
Referência Bibliográfica 
Compiladores – Princípios, técnicas e ferramentas. 
Aho, A. V et al. 2ª edição 
Seções 5.4.1, 5.4.3, 5.4.4, 5.4.5, 5.5, 5.5.1 
 
Modern Compiler Implementation in Java. Second Edition. 
Andrew W. Appel. 
Capítulo 4. 
 
 
 
 
 
16