69
1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

Embed Size (px)

Citation preview

Page 1: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

1

Esquemas de Tradução

Prof. Alexandre Monteiro

Baseado em material cedido pelo Prof. Euclides Arcoverde

Recife

Page 2: 1 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

Page 3: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

3

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

Page 4: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

4

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...

Page 5: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

5

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...

Page 6: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

6

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

Page 7: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

Definição Dirigida por Sintaxe

Page 8: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

8

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)

Page 9: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

9

Exemplo 1

Considere a seguinte gramática:

L → E ;E → T + E1

E → TT → F * T1

T → FF → digit

Page 10: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

10

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

Page 11: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

11

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

Page 12: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

12

Exemplo 2

Considere a seguinte gramática:

E → E1 + TE → E1 - TE → TT → ( E )T → numT → identifier

Page 13: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

13

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ão-terminal

Page 14: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

14

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)

Page 15: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

15

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

Page 16: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

Esquema de Tradução

Page 17: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

17

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

Page 18: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

18

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

Page 19: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

19

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

Page 20: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

Usando Esquemas de Tradução

Page 21: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

21

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

Page 22: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

22

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

Page 23: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

23

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

Page 24: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

Esquemas de Tradução no CUP

Page 25: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

25

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 ::= ...

Page 26: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

26

Tradução Usando o CUP

Em alguns casos, é possível colocar a ação semântica em meio aos símbolos

• 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 ação deve ser executada

comand ::= expr {: System.out.println("Expressão!"); :} PT_VIRG ;

Page 27: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

27

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

Page 28: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

28

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

• 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

terminal String NUMERO; non terminal Integer expr;

Page 29: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

29

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”

• Ok, pois yytext() retorna uma String

[0-9]+ { return new Symbol(sym.NUMERO, yytext());}

Page 30: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

30

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

• É como se val fosse o atributo de expr

comand ::= expr:val PT_VIRG {: System.out.println("Valor: " + val); :} ;

Page 31: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

31

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

• O RESULT é como um atributo sintetizado (que depende apenas dos filhos) de expr

expr ::= expr:e1 MAIS expr:e2 {: int soma = e1.intValue() + e2.intValue(); RESULT = new Integer(soma); :}

Page 32: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

32

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

Page 33: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

Esquemas de Tradução em Parsers Descendentes

Page 34: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

34

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?

Page 35: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

35

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!"); }

Page 36: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

36

Tradução em Parsers de Descida Recursiva

...o método parseComando() ficaria assim

void parseComand() { parseExpr(); acceptToken(PT_VIRG); System.out.println("Expressão!"); }

Page 37: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

37

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!"); } ";"

Page 38: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

38

Tradução em Parsers de Descida Recursiva

...o resultado é este

void parseComand() { parseExpr(); System.out.println("Expressão!"); PT_VIRG }

Page 39: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

39

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 ");" | ...

Page 40: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

40

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!"); ... } }

Page 41: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

41

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

Page 42: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

42

Tradução em Parsers de Descida Recursiva Como trabalhar com atributos para os

símbolos?• Por exemplo, implementar a tradução abaixo

Primeiro veremos como associar um objeto a um símbolo (representando o atributo val)

expr ::= termo + expr1 {expr.val = termo.val + expr1.val} | termo {expr.val = termo.val}

Page 43: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

43

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

Para os terminais, é só retornar um atributo da classe desejada junto com o Token

Integer parseExpr() { ... }

Page 44: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

44

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

Page 45: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

45

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

Page 46: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

46

Tradução em Parsers de Descida Recursiva Gramática original

• Seria fácil criar uma tradução para calcular o valor de expressões aqui...

expr ::= expr “*” termo | termo

termo ::= NUMBER

Page 47: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

47

Tradução em Parsers de Descida Recursiva

Gramática sem recursão

• É preciso passar o valor do “termo” do lado esquerdo para o “restoExpr” fazer a multiplicação

expr ::= termo restoExpr

restoExpr ::= “*” termo restoExpr | ε

termo ::= NUMBER

Page 48: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

48

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

Page 49: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

Construção da Árvore

Page 50: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

50

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

Page 51: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

51

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ão-terminal

• Classes diferentes para cada produção

Page 52: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

52

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

- Criar classe Atribuicao com o atributo identificador (do tipo String) e o atributo expressao (do tipo que for associado a esse não-terminal)

atrib ::= IDENTIFIER EQ expr

Page 53: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

53

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); :}

Page 54: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

54

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

Page 55: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

55

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

Page 56: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

56

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); :}

Page 57: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

57

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...”

Page 58: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

Esquemas de Tradução na Árvore de Derivação

Page 59: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

59

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

Page 60: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

60

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

Page 61: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

61

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

Page 62: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

62

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

Page 63: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

63

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

Vamos supor que a árvore tenha sido criada com as classes Soma, Produto e ExprNum, todas filhas de Expr

expr → { print("+"); } expr + expr

| { print("*"); } expr * expr

| NUM { print(NUM.lexval); }

Page 64: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

64

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

}

}

Page 65: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

65

Exemplo 1: Tradução para a Forma Pré-fixada

E assim

• Fazer análogo na classe Produto

class Soma extends Expr {

private Expr expr1, expr2;

public void toPrefixed() {

print("+");

expr1.toPrefixed();

expr2.toPrefixed();

}

}

Page 66: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

66

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 verificarSemantica() de cada objeto Declaracao

E assim sucessivamente...

Page 67: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

67

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

Page 68: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

68

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

Page 69: 1 Esquemas de Tradução Prof. Alexandre Monteiro Baseado em material cedido pelo Prof. Euclides Arcoverde Recife

69

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)