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

E E1 + T E.code E1.code || T.code || ‘+’

E E1 + T { print ‘+’; }

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

parse treegrafo de

dependênciaPrograma

fonte

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 Regra semântica

L E ‘\n’ 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

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 ;…

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

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 = 5digit.lexval = 4

E.val = 15

Atributos Herdados

• Definidos a partir dos nós-pai e/ou dos nós-irmã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 Regra semântica

D T L L.inh = T.type

T int T.type = integer

T real T.type = real

L L1 , id L1.inh = L.inh addtype(id.entry, L.inh)

L id addtype(id.entry, L.inh)

Exemplo – atributos herdados

id3

D

L.inh = real

L.inh = real

real

T.type = real

,

id2L.inh = real ,

id1

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

S2B S1

while

B S1

+

* 4

53

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:

• Node(op,left,right)

• Leaf(id, entry)

• Leaf(num, val)

Construindo uma árvore sintática para expressões - exemplo

• Contruir a árvore para a expressão:a – 4 + c

• p1 = new Leaf(id, entry_a);p2 = new Leaf(num, 4);p3 = new Node(‘-’,p1,p2);p4 = new Leaf(id, entry_c);p5 = new Node(‘+’, p3, p4);

Definição dirigida por sintaxe – construindo uma árvore

Produção Regra semânticaE E1 + T E.node = new Node(‘+’, E1.node,T.node)

E E1 - T E.node = new Node(‘-’, E1.node,T.node)

E T E.node = T.node

T ( E ) T.node = E.node

T id T.node = new Leaf(id,id.entry)

T num T.node = new Leaf(num,num.val)