7 TraduçãoDirigidaSintaxe Parte1 - 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 1 
• Tradução Dirigida por Sintaxe 
 
– Conceitos: atributo, regra semântica e ação semântica 
 
– Definição Dirigida por Sintaxe 
• Conceito 
• Atributos Sintetizados 
• Atributos Herdados 
• Grafos de Dependência 
• Definições S-atribuídas 
• Definições L-atribuídas 
 
 
 
2 
Tradução Dirigida por Sintaxe 
• A tradução dirigida por sintaxe é feita anexando-se regras ou 
fragmentos de código às produções de uma gramática 
 
• Exemplo: considere uma expressão gerada pela produção a 
seguir: 
expr → expr1 + term 
 
– Neste contexto, expr é dado pela soma de expr1 e term 
 
– expr pode ser traduzida conforme o pseudocódigo: 
• Traduza expr1; 
• Traduza term 
• Trate + 
 
 
3 
Atributo 
• Atributo: 
 
– É qualquer valor associado a uma construção de programação. 
 
– São exemplos de atributos: tipos de dados de expressões, número de 
parâmetros de um procedimento, número de instruções no código 
gerado, o endereço da primeira instrução do código gerado, etc. 
 
– Exemplo: 
 
Produção: F → digit 
 
digit.lexval : lexval é um atributo de digit ; ele representa o valor 
numérico de digit. 
 
F.val: val é o atributo de F que representa o seu valor numérico. 
 
 
 
 
4 
Regras Semânticas 
• Regras Semânticas 
 
– São regras incluídas na gramática que servem para avaliar 
o valor de um atributo 
 
– Exemplos: 
Produção: F → digit 
Regra semântica: F.val = digit.lexval 
 
Produção: expr → expr1 + term 
Regra semântica: expr.val = expr1.val + term.val 
 
 
5 
Ações Semânticas 
• Ações (ou Rotinas) Semânticas 
 
– São fragmentos de código incluídos na gramática 
– Por convenção, as ações semânticas são delimitadas por 
chaves. 
 
– Exemplo: 
Produção: expr → expr1 + term 
Ação semântica: {print ‘+’} 
 
– A posição de uma ação semântica na produção indica a 
ordem em que ela será executada. 
 
 
6 
Ações Semânticas 
– Analisador Sintático Descendente 
 
R → ABC {ação} 
A ação semântica é executada após a expansão de C 
 
 
– Analisador Sintático Ascendente 
 
R → ABC {ação} 
A ação semântica é executada quando ABC é reduzido para R 
 
 
 
7 
Definições Dirigidas por Sintaxe 
• Definição Dirigida por Sintaxe (SDD – Sintax-Directed 
Definition) é uma gramática livre de contexto acrescida de 
atributos e regras semânticas 
 
• Atributos são associados aos símbolos da gramática 
 
• Regras semânticas são associadas às produções 
 
• Se X é um símbolo da gramática e a é um de seus atributos, 
escreve-se X.a 
 
• Atributos podem ser sintetizados ou herdados 
 
 
8 
Atributos Sintetizados 
• Um atributo sintetizado para um não-terminal A em um nó N 
da árvore de derivação é definido por uma regra semântica 
associada à produção naquele nó 
 
• A produção precisa ter A como sua cabeça 
 
• Um atributo sintetizado no nó N é definido apenas em termos 
dos valores dos atributos dos filhos de N e do próprio N 
 
• Exemplo: 
E → E1 + T 
E.val = E1.val + T.val 
 
 
9 
E 
E1 + T 
Atributos Sintetizados 
• Exemplo: definição dirigida por sintaxe para a gramática de 
expressões. 
 
 
 
 
 
 
 
 
– O atributo val é sintetizado 
 
 
 
10 
Produção Regra Semântica 
L → E $ L.val = 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 
Atributos Sintetizados 
• Uma SDD que envolve apenas atributos sintetizados é 
denominada definição S-atribuída. 
 
• A gramática do exemplo anterior possui esta propriedade. 
 
• Em uma SDD assim, cada regra semântica calcula o atributo 
para o não-terminal do lado esquerdo da produção a partir 
dos atributos do corpo desta produção. 
 
 
 
 
 
 
11 
Árvore de Derivação Anotada 
• Uma árvore de derivação que mostra os valores dos atributos 
de seus nós é denominada árvore de derivação anotada. 
 
• Ordem de avaliação dos atributos: 
 
– Antes de avaliar um atributo de um nó de uma árvore, é necessário 
avaliar todos os atributos dos quais depende seu valor. 
 
– Se os atributos são sintetizados, então é necessário avaliar os 
atributos dos filhos de um nó para, então, avaliar o atributo do próprio 
nó. 
 
 
 
 
12 
Atributos Sintetizados 
• Exemplo: árvore de derivação anotada para 3*5+4 $ 
 
 
 
 
 
 
 
 
 
 
 
 
 
13 
L.val =19 
E.val =19 
E.val =15 + T.val = 4 
T.val =15 F.val =4 
T.val =3 * F.val =5 
F.val = 3 
digit.lexval =3 
digit.lexval =5 
digit.lexval =4 
$ 
Atributos Herdados 
• Um atributo herdado para um não-terminal B em um nó N da 
árvore de derivação é definido por uma regra semântica 
associada à produção no pai de N 
 
• A produção precisa ter B em seu corpo 
 
• Um atributo herdado no nó N é definido apenas em termos 
dos valores dos atributos dos pai de N, do próprio N e dos 
irmãos de N 
 
Um nó herda atributos de seu pai ou de seus irmãos 
 
 
 
14 
Atributos Herdados 
• Exemplo: considere a gramática para declarações de variáveis 
a seguir: 
 
D → TL 
T → int 
 | real 
L → L, id 
 | id 
 
Como são definidos os atributos que representam tipos de dados 
para as variáveis? 
 
 
 
15 
Atributos Herdados 
• Exemplo: em declarações de variáveis, o tipo é um atributo 
herdado 
 
 
 
 
 
 
 
 
– O atributo type é herdado 
 
 
 
16 
Produção Regra Semântica 
D → TL L.type = T.type 
T → int T.type = integer 
T → real T.type = real 
L → L1, id L1.type = L.type 
addType(id.entry, L.type) 
L → id addType(id.entry, L.type) 
Atributos Herdados 
• Exemplo: árvore de derivação anotada para 
 real id1, id2, id3 
 
 
 
 
 
 
 
 
 
 
 
 
17 
T.type = real 
D 
L.type = real 
L.type = real 
L.type = real 
real id3 , 
id2 , 
id1 
Grafos de Dependência 
• As árvores de derivação anotadas mostram os valores dos 
atributos. 
 
• O grafo de dependência mostra a ordem de avaliação dos 
valores dos atributos 
 
• Um grafo de dependência representa o fluxo de informações 
entre as instâncias dos atributos em uma árvore de derivação 
em particular 
 
 
 
 
 
18 
Grafos de Dependência 
• Uma aresta de uma instância A de um atributo para outra B 
representa que o valor de A é necessário para calcular o valor 
de B. 
 
• Para cada nó X da árvore de derivação (X é um símbolo da 
gramática), o grafo possui um nó para cada atributo associado 
a X. 
 
• As arestas no grafo representam as restrições definidas nas 
regras semânticas. 
 
 
 
 
19 
Grafos de Dependência 
• Exemplo: atributo sintetizado. 
E → E1 + T E.val = E1.val + T.val 
 
 
 
 
 
 
 
 
 
 
 
 
20 
E 
E1 + T 
val 
val val 
Grafos de Dependência 
• Exemplo: atributo herdado 
 real id1, id2, id3 
 
 
 
 
 
 
 
 
 
 
 
 
21 
T 
D 
L 
L 
L 
real id3 , 
id2 , 
id1 
type real type real 
type real type real 
type real 
type real 
type real 
type real 
Definições S-atribuídas 
• Uma SDD é S-atribuída se todo atributo é sintetizado. 
 
• Em uma SDD S-atribuída,os atributos podem ser avaliados em 
qualquer ordem a partir das folhas da árvore em direção à raiz 
 
 
– São avaliados os atributos dos filhos de um nó, e só depois é avaliado 
o atributo do próprio nó. 
22 
Definições L-atribuídas 
• Em uma SDD L-atribuída (L = left), entre os atributos associados ao corpo 
de uma produção, as arestas podem ser direcionadas da esquerda para a 
direita, mas não da direita para a esquerda 
 
• Em uma SDD L-atribuída, cada atributo precisa ser: 
– Sintetizado ou 
– Herdado, com a seguinte restrição: 
• Seja a produção A → X1X2...Xn em que haja um atributo herdado 
Xi.a. 
• Xi.a pode ser calculado usando apenas os atributos 
– Herdados associados a A 
– Herdados associados aos símbolos X1,X2 ...Xi-1 
– Herdados ou sintetizados associados à ocorrência do próprio 
Xi 
23 
Referência Bibliográfica 
Compiladores – Princípios, técnicas e ferramentas. 
Aho, A. V et al. 2ª edição 
Seções 2.3, 5.1, 5.2 
 
Modern Compiler Implementation in Java. Second Edition. 
Andrew W. Appel. 
Capítulo 4. 
 
 
 
 
 
24