Tradução Dirigida por Sintaxe
• Pode ser descrita de duas formas:
– Definições dirigidas por sintaxe: mais abstratas
– Esquemas de tradução: especificam ordem de
avaliação
Tradução Dirigida por Sintaxe
• Conceitualmente, realiza o parsing, constrói
parse tree, e atravessa a árvore sob
demanda para avaliar as regras semânticas
nos nós da parse tree.
• Avaliação das regras semânticas pode ser
usada para gerar código, guardar
informações na tabela de símbolos, emitir
mensagens de erro etc.
Tradução dirigida por sintaxe
Programa
fonte
parse tree
grafo de
dependência
ordem de
avaliação para
regras semânticas
Definições dirigidas por sintaxe
• Generalização de gramática livre de
contexto em que cada símbolo da gramática
é associado a um conjunto de atributos.
• Dois tipos de atributos: sintetizados e
herdados
Tipos de atributos
• Atributos sintetizados: computados a partir
dos atributos dos nós-filhos (abaixo do
próprio nó).
• Atributos herdados: computados a partir de
nós-pais ou nós-irmãos (acima ou ao lado
do próprio nó).
Parse tree anotada
• Mostra os valores dos atributos em cada nó.
• O processo de avaliação dos atributos é
chamado “anotar” ou “decorar” a parse
tree.
Definição dirigida por sintaxe exemplo
Produção
L g E ‘\n’
E g E1 + T
EgT
T g T1 * F
TgF
Fg(E)
F g digit
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
Exemplo em yacc
…
line
:
;
expr
:
|
;
term
:
|
;
factor :
|
;
…
expr '\n'{ printf("%d\n", $1); }
expr '+' term
term
{ $$ = $1 + $3; }
term '*' factor { $$ = $1 * $3; }
factor
'(' expr ')'
DIGIT
{ $$ = $2; }
Em definições dirigidas por
sintaxe
• Terminais possuem apenas atributos
sintetizados (pelo analisador léxico).
Atributos Sintetizados
• Muito usados na prática.
• Uma definição que usa apenas atributos
sintetizados é chamada de S-attributed
definition.
• Definições S-attributed podem sempre ser
anotadas através da avaliação das regras
semânticas em cada nó, atravessando a
parse tree bottom-up, a partir das folhas.
Exemplo –parse tree anotada
para 3 * 5 + 4 n
E.val = 19
E.val = 15
T.val = 15
T.val = 3
+
F.val = 5
*
T.val = 4
F.val = 4
F.val = 3
digit.lexval = 3
digit.lexval = 5
digit.lexval = 4
Atributos Herdados
• Definidos a partir dos nós-pai e/ou dos nósirmãos.
• Úteis para especificar dependência do
contexto, por exemplo se um identificador
aparece à esquerda ou direita de uma
atribuição.
• É sempre possível trabalhar apenas com
atributos sintetizados.
Atributos herdados - exemplo
Produção
DgTL
T g int
T g real
L g L1 , id
L g id
Regra semântica
L.in = T.type
T.type = integer
T.type = real
L1.in = L.in
addtype(id.entry, L.in)
addtype(id.entry, L.in)
Exemplo – atributos herdados
D
T.type = real
L.in = real
real
L.in = real
L.in = real
id1
,
,
id2
id3
Grafos de dependência
•
Úteis para determinar a ordem de
avaliação dos atributos:
1. Gerar grafo de dependência
2. fazer sort topológico – ordenação dos nós de
um grafo acíclico dirigido em que todas as
arestas vão de um nó anterior para nós
posteriores.
Construção de árvores sintáticas
•
A construção de árvores sintáticas como
representação intermediária permite
separar o processo de tradução do
processo de parsing.
Construção de árvores sintáticas
•
•
Uma gramática adequada para parsing
pode não ser adequada para refletir a
hierarquia natural das construções de uma
linguagem. Ex: sequência de statements
vs. expressões aninhadas em FORTRAN.
Alem disso, o método de parsing pode
não ser adequado para a construção de
uma parse tree.
Árvores sintáticas (abstratas)
•
•
Uma árvore sintática (abstrata) é uma
forma condensada de parse tree adequada
para representar os construtores de uma
linguagem.
Operadores e palavras chaves (que são
terminais) normalmente não aparecem
como folhas, e sim associados a um nó.
Árvores sintáticas - exemplo
If-then-else
B
S1
S2
+
while
*
B
4
S1
3
5
Construindo Árvores Sintáticas
•
•
•
•
Semelhante à tradução para notação pós-fixa:
criar sub-árvores criando um nó para cada
operando e operador.
Cada nó pode ser representado por um registro
com vários campos.
Operador: um campo identifica o tipo do
operador, e os outros campos são apontadores
para os nós dos operandos.
Podem existir campos adicionais para guardar
atributos.
Construindo uma árvore sintática
para expressões
•
•
•
•
Funções auxiliares:
mknode(op,left,right)
mkleaf(id, entry)
mkleaf(num, val)
Construindo uma árvore sintática
para expressões - exemplo
•
•
Contruir a árvore para a expressão:
a–4*c
p1 = mkleaf(id, entry_a);
p2 = mkleaf(num, 4);
p3 = mknode(‘-’,p1,p2);
p4 = mkleaf(id, entry_c);
p5 = mknode(‘+’, p3, p4);
Definição dirigida por sintaxe –
construindo uma árvore
Produção
E g E1 + T
EgT
Tg(E)
T g id
T g num
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)