05 traducao dirigida por sintaxe Edjan Sobral Verissimo Michiles

Prévia do material em texto

IF688 – Tradução dirigida por 
sintaxe
Resumo desta aula
• Tradução dirigida por sintaxe
• Conceitos
– Árvore sintática decorada com atributos
– Atributos herdados e sintetizados
Tradução dirigida por sintaxe
• O que faz?
– Forma simples de definição semântica
• Como funciona? 
– Associa ações a produções de uma gramática
• Para que serve?
– Construir árvore sintática
– Checagem de tipos
– Traduzir entrada
– etc. 
Estamos 
interessados 
em todas estas 
aplicações!
Exemplo em yacc
…
line : expr '\n'{ printf("%d\n", $1); }
;
expr : expr '+' term { $$ = $1 + $3; }
| term
;
term : term '*' factor { $$ = $1 * $3; }
| factor
;
factor : '(' expr ')' { $$ = $2; }
| DIGIT
;
…
Ação é útil para definir 
comportamento! Aqui, 
calcula-se valor de uma 
expressão a partir das 
sub-expressões.
Ações e Atributos
• Conceitualmente, ações criam e associam 
atributos aos nós da árvore sintática
– Na prática, árvore não precisa ser criada 
(ver exemplo anterior)
Uma ação também é cha-
mada de regra semântica.
Ações e Atributos
• Conceitualmente, ações criam e associam 
atributos aos nós da árvore sintática
– Na prática, árvore não precisa ser criada 
(ver exemplo anterior)
O processo de avaliação dos 
atributos é chamado “anotação” ou 
“decoração” da parse tree.
Exemplo
L g E ‘\n’
E g E1 + T
E g T
T g T1 * F
T g F
F g ( E )
F g digit
Produção Regra semântica
print (E.val) 
E.val = E1.val + T.val
E.val = T.val
T.val = T1.val * F.val
T.val = F.val
F.val = E.val
F.val = digit.lexval
Árvore de “3 * 5 + 4” decorada
digit.lexval = 3
* F.val = 4
+
digit.lexval = 5
E.val = 19
T.val = 15
T.val = 4
T.val = 3
F.val = 3
F.val = 5
digit.lexval = 4
E.val = 15
Note a direção da 
avaliação dos atributos
Dois tipos de atributo
• Sintetizados (dependem dos nós filho)
• Herdados (dependem de nós pai e irmão)
herdadossintetizados
Direção da seta 
indica direção em 
que o valor do 
atributo é calculado
Atributos sintetizados
• Implementação simples: anota-se parse tree
com busca bottom-up (pós-ordem)
Muito usada na prática!
Uma definição S-attributed usa 
apenas atributos sintetizados
Atributos herdados
• Úteis para especificar contexto
– Por exemplo se um identificador usado em uma 
expressão é definido no contexto de uso
• É sempre possível trabalhar apenas com 
atributos sintetizados
– Porém, definições tornam-se mais elaboradas
Exemplo
D g T L 
T g int
T g real
L g L1 , id 
L g id
Produção Regra semântica
L.in = T.type
T.type = integer
T.type = real
L1.in = L.in
addtype(id.entry, L.in)
Atributo type é sintetizado e 
atribuite in é herdado
Árvore de “real id1, id2, id3” decorada
id3
D
L.in = real
L.in = real
real
T.type = real
,
id2L.in = real ,
id1
Direção da 
avaliação do 
atributo in
Direção da 
avaliação do 
atributo type
Exercício
• Adicione ações na gramática abaixo para 
construção de árvore sintáticas
mknode(op, left, right)
mkleaf(id, entry)
mkleaf(num, val)
E g E1 + T
E g T
T g ( E )
T g id
T g num
• Funções auxiliares:
Exercício
E g E1 + T
E g T
T g ( E )
T g id
T g num
Produção Regra semântica
E.nptr = mknode(‘+’, E1.nptr, T.nptr)
E.nptr = T.nptr
T.nptr = E.nptr
T.nptr = mkleaf(id, id.entry)
T.nptr = mkleaf(num, num.val)
Exercício
• Considerando programas com apenas uma 
função, como você faria para capturar 
declarações de variáveis sem uso e uso de 
variáveis sem declarações?