Esquemas de Tradução
Prof. Alexandre Monteiro
Baseado em material cedido pelo Prof. Euclides Arcoverde
Recife
‹#›
Contatos

Prof. Guilherme Alexandre Monteiro Reinaldo

Apelido: Alexandre Cordel

E-mail/gtalk: [email protected]
[email protected]

Site: http://www.alexandrecordel.com.br/fbv

Celular: (81) 9801-1878
Traduções Dirigidas por Sintaxe



As produções de uma gramática são suas
“regras sintáticas” e definem construções
relevantes da linguagem
Traduções Dirigidas por Sintaxe associam
regras semânticas a cada uma dessas regras
sintáticas, com algum objetivo
As regras semânticas definem a saída
correspondente a cada produção
3
Traduções Dirigidas por Sintaxe

Possíveis aplicações
•Criação da árvore sintática em memória
•Verificação de tipos
•Geração de código intermediário
•Etc.

Enfim, ela pode ser usada em todo o restante das etapas do
front-end...
4
Traduções Dirigidas por Sintaxe

Existem dois tipos
• Definição Dirigida por Sintaxe – assumindo que
cada nó da árvore possui atributos, define os
valores que eles devem receber
• Esquemas de Tradução – associam código qualquer
a cada produção, para ser executado durante a
análise sintática (parsing)

A distinção é um pouco confusa...
5
Traduções Dirigidas por Sintaxe

“Definição Dirigida por Sintaxe” é uma
descrição mais abstrata e formal de uma
tradução
• Especifica a tradução

Já um “Esquema de Tradução” é a descrição
concreta do código que vai ser executado para
cada produção
• Implementa uma definição dirigida por sintaxe
• Usa trechos de código
6
Definição Dirigida por Sintaxe
Definição Dirigida por Sintaxe

É a gramática livre de contexto da linguagem
acrescida de
• Descrição dos atributos que cada símbolo (terminal
ou não-terminal) possui
• Regras semânticas, associadas a cada produção,
para definir os valores dos atributos

Chamaremos SDD (Syntax-Directed Definition)
8
Exemplo 1

Considere a seguinte gramática:
L
E
E
T
T
F
→
→
→
→
→
→
E ;
T + E1
T
F * T1
F
digit
9
Exemplo 1

Com base em uma gramática de expressões, o objetivo do
exemplo é avaliar o valor numérico das expressões
•Para os não-terminais L, E, T e F, vamos
considerar que possuem o atributo “val”
•O símbolo terminal digit terá um atributo
“lexval”, com o seu valor numérico
•O símbolo terminal ; (ponto-e-vírgula) não
tem importância nesta tradução
10
Exemplo 1
Produção
Regra Semântica
L→E;
L.val = E.val
E → T + E1
E.val = T.val + E1.val
E→T
E.val = T.val
T → F * T1
T.val = F.val * T1.val
T→F
T.val = F.val
F → digit
F.val = digit.lexval
11
Exemplo 2

Considere a seguinte gramática:
E
E
E
T
T
T
→
→
→
→
→
→
E1 + T
E1 - T
T
( E )
num
identifier
12
Exemplo 2


Este exemplo usa uma gramática de expressões com soma
e subtração apenas
O objetivo da SDD neste exemplo é construir a árvore
sintática
•Cada não-terminal tem um atributo “node”
que representa o nó da árvore que
representa aquela ocorrência do nãoterminal
13
Exemplo 2
Produção
Regra Semântica
E → E1 + T
E.node = new Op(‘+’, E1.node, T.node)
E → E1 - T
E.node = new Op(‘-’, E1.node, T.node)
E→T
E.node = T.node
T→(E)
T.node = E.node
T → num
T.node = new Leaf(num)
T → identifier
T.node = new Leaf(identifier)
14
Definição Dirigida por Sintaxe


Não se preocupa com detalhes, como a ordem de definição
dos atributos
Sua principal aplicação é para especificar traduções mais
simples
•Mais abstrata
15
Esquema de Tradução
Esquema de Tradução

É uma extensão do conceito de SDD
• Possui trechos de código como regras semânticas
(que passam a ser chamadas ações semânticas)
• Controla a ordem de execução das ações
semânticas

Implementação da tradução (ou da SDD)
• Mais concreta
17
Esquema de Tradução

Assim, um Esquema de Tradução é uma
gramática livre acrescida de
• Descrição dos atributos que cada símbolo (terminal
ou não-terminal) possui
• Ações semânticas, associadas a cada produção
- Descritas na forma de trechos de código de uma linguagem
de programação real
- Posicionadas dentro da produção como se fossem um
símbolo, para indicar o momento exato de executar a ação
18
Esquema de Tradução

Um Esquema de Tradução pode ser
implementado junto com a análise sintática
• Ações semânticas disparadas sempre que o parser
identifica uma produção

Ou percorrendo a árvore de derivação
• Primeiro, a árvore é construída por um Esquema de
Tradução realizado durante a análise sintática
• Depois, a árvore é percorrida, disparando as ações
semânticas no momento adequado
19
Usando Esquemas de Tradução
Introdução

Esquemas de Tradução são um tipo de Tradução Dirigida
por Sintaxe
•Ações semânticas (trechos de código)
associados às produções

Pode ser realizada de duas maneiras
•Junto com a análise sintática
- Veremos no CUP e em parsers descendentes
•Percorrendo a árvore de derivação
21
Sumário

Esquemas de Tradução no CUP

Esquemas de Tradução em Parsers Descendentes

Construção da Árvore

Esquemas de Tradução na Árvore Sintática
22
Tradução na Análise Sintática


As ações semânticas são disparadas sempre que o parser
identifica uma produção
Veremos como é feita em dois casos
•Esquema de tradução em parsers ascedentes
(como o CUP)
•Esquema de tradução em parsers de descida
recursiva
23
Esquemas de Tradução no CUP
Tradução Usando o CUP

Em geral, basta colocar um trechos de código em meio às
produções delimitando-os por {: e :}
comand ::= expr PT_VIRG
{: System.out.println("Expressão!"); :}
;
expr ::= ...
25
Tradução Usando o CUP

Em alguns casos, é possível colocar a ação
semântica em meio aos símbolos
comand ::= expr
{: System.out.println("Expressão!"); :}
PT_VIRG
;
• Ação executada antes de reconhecer o PT_VIRG

Em outros casos, o CUP pode indicar que é
incapaz de identificar o momento em que a
26
ação deve ser executada
Tradução Usando o CUP


O CUP permite associar classes aos símbolos
(terminais ou não-terminais)
Pensando no conceito de Definição Dirigida por
Sintaxe, é como se
• Cada símbolo tivesse um único atributo
• O tipo desse atributo é a classe em questão

Funcionam como atributos sintetizados
• Não permite atributos herdados
27
Tradução Usando o CUP

Para associar classes aos símbolos terminais e
não-terminais, basta indicá-las na seção de
declaração de símbolos
terminal String NUMERO;
non terminal Integer expr;
• Ocorrências do símbolo terminal NUMERO serão
representadas por objetos da classe String
• Ocorrências do não-terminal expr representadas
pela classe Integer
28
Integração Lexer/CUP

Atenção: o tipo com que você declara um
símbolo terminal deve ser o mesmo tipo
retornado pelo lexer no segundo parâmetro do
construtor de “Symbol”
[0-9]+ {
return new Symbol(sym.NUMERO, yytext());
}
• Ok, pois yytext() retorna uma String
29
Tradução Usando o CUP

Para ter acesso aos objetos que representam
os atributos dos símbolos filhos, basta colocar
dois pontos seguido de um nome qualquer
• A ação poderá usar esse nome como uma variável
daquele tipo
comand ::= expr:val PT_VIRG
{: System.out.println("Valor: " + val); :}
;
• É como se val fosse o atributo de expr
30
Tradução Usando o CUP

Para atribuir valor ao objeto que representa o
não-terminal pai (lado esquerdo), é preciso
usar a variável RESULT
expr ::= expr:e1 MAIS expr:e2
{: int soma = e1.intValue() + e2.intValue();
RESULT = new Integer(soma);
:}
• O RESULT é como um atributo sintetizado (que
depende apenas dos filhos) de expr 31
Tradução Usando o CUP

Para um exemplo completo de uso do CUP
junto com ações semânticas será
disponibilizado no oro-aro
• Implementa um Esquema de Tradução para
interpretar expressões, retornando seus valores

Veremos agora como usar um Esquema de
Tradução com um parser de descida recursiva
32
Esquemas de Tradução em Parsers
Descendentes
Tradução em Parsers de Descida
Recursiva

Relembrando a técnica
• O reconhecimento de cada não-terminal X está
associado a um procedimento parseX()
• Dentro de parseX() é feita a discriminação entre as
diferentes produções de X

Como fazer para associar ações semânticas a
cada produção?
34
Tradução em Parsers de Descida
Recursiva


O caso mais simples é se o não-terminal tem uma só
produção e a ação deve ser executada no final da produção
Por exemplo, para essa tradução...
comand ::= expr ";" { System.out.println("Expressão!"); }
35
Tradução em Parsers de Descida
Recursiva

...o método parseComando() ficaria assim
void parseComand() {
parseExpr();
acceptToken(PT_VIRG);
System.out.println("Expressão!");
}
36
Tradução em Parsers de Descida
Recursiva

Se o não-terminal tem apenas uma produção e a ação tiver
que ser executada no meio da produção...
comand ::= expr {System.out.println("Expressão!"); } ";"
37
Tradução em Parsers de Descida
Recursiva

...o resultado é este
void parseComand() {
parseExpr();
System.out.println("Expressão!");
PT_VIRG
}
38
Tradução em Parsers de Descida
Recursiva

Se tiver mais de uma produção...
comand ::= "while" {System.out.println("While!");}
"(" expr ")" comand
| "do" comand {System.out.println(“Do-While!");}
"while (" expr ");"
| ...
39
Tradução em Parsers de Descida
Recursiva

...basta posicionar a ação semântica dentro do
bloco que trata a produção desejada
void parseLoopComand() {
if (token.getType() == WHILE) {
acceptToken();
System.out.println(“While!");
...
} else if (token.getType() == DO) {
acceptToken();
parseComand();
System.out.println(“Do-While!");
...
}
}
40
Tradução em Parsers de Descida
Recursiva



Em alguns casos, pode não ser possível posicionar a ação
adequadamente, pois ainda não se sabe qual é a produção
Por exemplo: se tiver mais de uma produção e a ação de
alguma delas acontece antes do primeiro símbolo
Mesma limitação do CUP
41
Tradução em Parsers de Descida
Recursiva

Como trabalhar com atributos para os
símbolos?
• Por exemplo, implementar a tradução abaixo
expr ::= termo + expr1 {expr.val = termo.val + expr1.val}
| termo
{expr.val = termo.val}

Primeiro veremos como associar um objeto a
um símbolo (representando o atributo val)
42
Tradução em Parsers de Descida
Recursiva

Para associar uma classe ao não-terminal X,
basta fazer o método parseX() retornar a
classe
Integer parseExpr() {
...
}

Para os terminais, é só retornar um atributo da
classe desejada junto com o Token
43
Tradução em Parsers de Descida
Recursiva

Para acessar os valores dos filhos basta
receber (e guardar) os valores de retorno
• Atributos sintetizados
Integer parseExpr() {
Integer termoVal = parseTermo();
if (token.getType() == MAIS) {
acceptToken();
Integer expr1Val = parseExpr();
return termoVal + expr1Val;
}
}
44
Tradução em Parsers de Descida
Recursiva

Em alguns casos, pode ser necessário passar valores por
parâmetro
•Atributos herdados

Isso acontece, por exemplo, em uma gramática recursiva à
esquerda, após transformá-la em uma sem a recursão
45
Tradução em Parsers de Descida
Recursiva

Gramática original
expr ::= expr “*” termo
| termo
termo ::= NUMBER
• Seria fácil criar uma tradução para calcular o valor
de expressões aqui...
46
Tradução em Parsers de Descida
Recursiva

Gramática sem recursão
expr ::= termo restoExpr
restoExpr ::= “*” termo restoExpr
| ε
termo ::= NUMBER
• É preciso passar o valor do “termo” do lado
esquerdo para o “restoExpr” fazer a multiplicação
47
Tradução em Parsers de Descida
Recursiva

A tradução ficaria assim
Integer parseExpr() {
Integer termoVal = parseTermo();
parseRestoExpr(termoVal);
}
Integer parseRestoExpr(Integer esq) {
if (token.getType() == VEZES) {
Integer dir = parseTermo();
Integer produto = esq * dir;
return parseRestoExpr(produto);
} else {
return esq;
}
}
48
Construção da Árvore
Construção da Árvore

Relembrando...
• Árvore de derivação – guarda todos os símbolos,
inclusive sinais especiais, de cada produção
- Feita com base na gramática concreta
• Árvore sintática – guarda só o que é importante de
cada produção
- Feita com base na gramática abstrata

É mais adequado construir a árvore sintática
50
Construção da Árvore


Não são árvores homogêneas, como as que são vistas nas
disciplinas de estruturas de dados
Cada nó dessa árvore pode ser de um tipo diferente
•Classes diferentes para cada símbolo nãoterminal
•Classes diferentes para cada produção
51
Construção da Árvore

Se o não-terminal tiver uma só produção
• Usar uma só classe e colocar como atributos dela os
símbolos importantes que aparecem no lado direito
• Exemplo de produção no CUP
atrib ::= IDENTIFIER EQ expr
- Criar classe Atribuicao com o atributo identificador (do
tipo String) e o atributo expressao (do tipo que for
associado a esse não-terminal)
52
Construção da Árvore

Se o não-terminal tiver uma só produção (cont.)
•Por fim, colocar a ação no CUP para
instanciar esse objeto
atrib ::= IDENTIFIER:id EQ expr:e
{: RESULT = new Atribuicao(id,e); :}
53
Construção da Árvore

Não-terminal com mais de uma produção
• Criar uma classe abstrata ou interface para
representar o não-terminal
• Criar uma classe (herdada) para cada produção
• Exemplos de produções no CUP
expr ::= expr MAIS expr
| expr VEZES expr
| NUM
54
Construção da Árvore

Não-terminal com mais de uma produção (cont.)
•Criar interface Expr
•Criar classes filhas Soma, Produto e
ExprNum
Expr
Soma
Produto
ExprNum
55
Construção da Árvore

Não-terminal com mais de uma produção
(cont.)
• Colocar as ações no CUP para instanciar as classes
expr ::= expr:e1 MAIS expr:e2
{: RESULT = new Soma(e1,e2); :}
| expr:e1 VEZES expr:e2
{: RESULT = new Produto(e1,e2); :}
| NUM:n
{: RESULT = new ExprNum(n); :}
56
Construção da Árvore

Em alguns casos, uma mesma classe pode ser
usada para mais de uma produção
• Uma só classe para "if" sem "else" e para "if" com
"else"
• Uma só classe para todas as expressões binárias
• Uma só classe para todas as expressões unárias
• “Usar o bom senso...”
57
Esquemas de Tradução na Árvore
de Derivação
Tradução na Análise Sintática


Já vimos como usar Esquemas de Tradução
junto com a análise sintática
Esquemas desse tipo têm algumas limitações
• Parsers ascendentes (como o CUP) permitem apenas
atributos sintetizados
• Parser descendentes permitem atributos
sintetizados e herdados, mas com algumas
restrições
59
Tradução na Árvore


Outra maneira de se usar Esquemas de Tradução é usando a
árvore
Essa estratégia é mais geral do que traduções que
acontecem durante a análise sintática
•Permite implementar qualquer tradução,
mesmo com atributos herdados
60
Esquema de Tradução na Árvore de
Derivação

A primeira etapa é construir a árvore sintática
•Acabamos de ver como fazer isso durante a
análise sintática...

Em seguida, basta percorrer a árvore, executando as ações
semânticas no momento desejado
61
Esquema de Tradução na Árvore de
Derivação

Uma maneira simples de implementar uma tradução é criar
métodos em cada classe da árvore que representar uma
produção (ou um não-terminal)
•Tudo inicia chamando o método do nó raiz
•No momento adequado, cada nó chama os
métodos equivalentes dos filhos
62
Exemplo 1: Tradução para a Forma
Pré-fixada

Este é o Esquema de Tradução desejado
• Visa passar a expressão para a forma prefixada
expr →
{ print("+"); } expr + expr
| { print("*"); } expr * expr
| NUM { print(NUM.lexval); }

Vamos supor que a árvore tenha sido criada
com as classes Soma, Produto e ExprNum,
todas filhas de Expr
63
Exemplo 1: Tradução para a Forma
Pré-fixada

A tradução é feita assim
class ExprNum extends Expr {
int lexval;
public void toPrefixed() {
print(lexval);
}
}
64
Exemplo 1: Tradução para a Forma
Pré-fixada

E assim
class Soma extends Expr {
private Expr expr1, expr2;
public void toPrefixed() {
print("+");
expr1.toPrefixed();
expr2.toPrefixed();
}
}
•Fazer análogo na classe Produto
65
Exemplo 2: Verificação Semântica




Criar um método verificaSemantica() em cada classe
da árvore
O início seria no método verificarSemantica() da
classe Program
Esse método iria chamar o método
verificarSemantica() da classe ListaDecl e, depois, o
da classe Bloco
O método da classe ListaDecl iria chamar o método
66
verificarSemantica() de cada objeto Declaracao
Esquema de Tradução na Árvore de
Derivação




Outra maneira de percorrer a árvore é usando
o design pattern "Visitor"
A árvore implementa apenas as chamadas a
métodos de um Visitor genérico
Classes Visitor de próposito específico podem
ser criadas para implementar uma tradução
Ver
http://en.wikipedia.org/wiki/Visitor_pattern
67
Visitor


Visitor é um padrão de projeto catalogado
pelos “quatro” mosqueteiros da engenharia de
software, Gamma, Helm, Johnson e Vlissides
(Gang of Four - GoF), como um padrão de
projeto comportamental
Seu objetivo principal é permitir que sejam
adicionadas novas funcionalidades a classes
existentes, de maneira plugável, sem que haja
a necessidade de se alterar a hierarquia dessas
classes
68
Bibliografia

AHO, A., LAM, M. S., SETHI, R., ULLMAN, J. D.,
Compiladores: princípios, técnicas e ferramentas. Ed.
Addison Wesley. 2a Edição, 2008 (Capítulo 4)
69