Departamento de Estatística e Informática Universidade ... · PDF file•Regras são avaliadas quando a produção é aplicada •Gramática de atributos –Defn. dirigida por sintaxe

1

Tradução dirigida por sintaxe

André Luis Meneses Silva

[email protected]

Departamento de Estatística e Informática

Universidade Federal de Sergipe

Compiladores

2

Definições dirigidas por sintaxe

• Gramática + regras (ações) semânticas

– Cada símbolo possui um atributo

– Regras definem os valores dos atributos

– Cada produção tem sua(s) regra(s)

• Regras são avaliadas quando a produção é aplicada

• Gramática de atributos

– Defn. dirigida por sintaxe onde as regras não

têm efeitos colaterais (paradigma funcional)

3

terminal Integer NUM;

non terminal Integer expr;...

expr ::= expr:a PLUS expr:b

{: RESULT = new Integer(a.intValue() +

b.intValue()); :}

| expr:a TIMES expr:b

{: RESULT = new Integer(a.intValue() *

b.intValue()); :}

| LPAREN expr:a RPAREN

{: RESULT = a :}

| NUM : i

{: RESULT = i :} ;

Exemplo em CUP

4

Atributos sintetizados e herdados

• Considere a árvore de derivação:

– O valor de um atributo sintetizado é definido em função dos valores dos atributos dos filhos

• Exemplo anterior

– Atributos herdados dependem dos irmãos e/ou o pai

• Cup só trabalha com atributos sintetizados

D T L { L.type = T.type }

L id , L1 { L1.type = L.type; id.type=L.type }

L id { id.type = L.type }

5

N N1 D { N.v = N1.v*10 + D.v }

N D { N.v = D.v }

D 0 { D.v = 0 }

D 1 { D.v = 1 }

...

D 9 { D.v = 9 }

Exemplo: números simples

N N D

N D

N D N

N D

6

N N1 D { N.v = N1.v*10 + D.v }

N D { N.v = D.v }

D 0 { D.v = 0 }

D 1 { D.v = 1 }

...

D 9 { D.v = 9 }

S N { N.h = 0; }

N D N1 { N.s = N1.s ;

N1.h = N.h*10 + D.s }

N D { N.s = N.h*10 + D.s; }

D 0 { D.s = 0 }

D 1 { D.s = 1 }

...

D 9 { D.s = 9 }

Exemplo: números simples

N N D

N D

N D N

N D

Qual é mais adequada

para definir o valor

semântico de N

somente com atributos

sintetizados?

7

Árvore de derivação

DN

N

DN

0D

1

9

• 901 árvore

de derivação

8


DN

N

DN

0D

1

9

• 901 árvore

de derivação

N N1 D { N.v = N1.v*10+D.v }

N D { N.v = D.v }

D 0 { D.v = 0 }

D 1 { D.v = 1 }

...

D 9 { D.v = 9 }

9


DN

N

DN

0D

1

9

D.v = 9

• 901 árvore

de derivação

N N1 D { N.v = N1.v*10+D.v }

N D { N.v = D.v }

D 0 { D.v = 0 }

D 1 { D.v = 1 }

...

D 9 { D.v = 9 }

10


DN

N

DN

0D

1

9

D.v = 9

N.v = 9

• 901 árvore

de derivação

N N1 D { N.v = N1.v*10+D.v }

N D { N.v = D.v }

D 0 { D.v = 0 }

D 1 { D.v = 1 }

...

D 9 { D.v = 9 }

11


DN

N

DN

0D

1

9

D.v = 9

N.v = 9

N.v = 90

D.v = 0

• 901 árvore

de derivação

N N1 D { N.v = N1.v*10+D.v }

N D { N.v = D.v }

D 0 { D.v = 0 }

D 1 { D.v = 1 }

...

D 9 { D.v = 9 }

12


• 901 árvore

de derivação

N N1 D { N.v = N1.v*10+D.v }

N D { N.v = D.v }

D 0 { D.v = 0 }

D 1 { D.v = 1 }

...

D 9 { D.v = 9 }

DN

N

DN

0D

1

9

D.v = 9

N.v = 9

N.v = 90

D.v = 0

N.v = 901

D.v = 1

13

Implementando Atributos Sintetizados – LR

• Empilha-se o valor do atributo junto com o símbolo/estado

• Quando há redução, a respectiva regra semântica é avaliada

( , 2 + 4 * 8 $) ├ (<NUM,2>, + 4 * 8 $)

├ (<expr,2>, + 4 * 8 $)

├ ( <expr,2><PLUS>, 4 * 8 $)

├ (<expr,2><PLUS><NUM,4>, * 8 $)

├ (<expr,2><PLUS><expr,4>, * 8 $)

├ (<expr,2><PLUS><expr,4><TIMES>, 8 $)

├ (<expr,2><PLUS><expr,4><TIMES><NUM,8>, $)

├ (<expr,2><PLUS><expr,4><TIMES><expr,8>, $)

├ (<expr,2><PLUS><expr,32>, $)

├ (<expr,34>, $)

14

4+9 ; <ENTER>

13

5*(4+2); <ENTER>

30

<EOF>

Ações com efeitos colaterais

• Gramáticas de atributos são declarativas

• As vezes é interessante escrever ações com efeitos

colaterais

– Maior cuidado pois a execução das ações depende da

ordem em que as produções são reduzidas

• Ex. Uma calculadora interativa com ações imperativas

15

terminal SEMI, PLUS, TIMES, LPAREN, RPAREN;

terminal Integer NUMBER; // com atributo

non terminal Integer expr; // com atributo

non terminal expr_, calc;

precedence left PLUS;

precedence left TIMES;

Implementação com o CUP

16

calc ::= expr_ SEMI calc

| expr_ SEMI {: System.out.println("BYE"); :} ;

expr_ ::= expr:e {: System.out.println(e.toString()); :} ;

expr ::= expr:a PLUS expr:b

{: RESULT = new Integer(a.intValue() +

b.intValue()); :}

| expr:a TIMES expr:b

{: RESULT = new Integer(a.intValue() *

b.intValue()); :}

| LPAREN expr:a RPAREN

{: RESULT = a :}

| NUM : i

{: RESULT = i :} ;

17

Ações imperativas exigem cuidado

calc ::= expr:e SEMI calc

{: System.out.println(e.toString()); :}

| expr:e SEMI

{: System.out.println(e.toString());

System.out.println("BYE"); :} ;

expr ::= ...

Como se comportam os parsers das seguinte gramáticas?

18

Ações imperativas exigem cuidado

calc ::= expr:e SEMI calc


| expr:e SEMI



expr ::= ...

Como se comportam os parsers das seguinte gramáticas?

calc ::= calc expr:e SEMI


| expr:e SEMI



expr ::= ...

19

s ::= calc {: System.out.println("BYE"); :} ;

calc ::= calc expr:e SEMI


| expr:e SEMI

{: System.out.println(e.toString()); :} ;

expr ::= ...

20

Ações embutidas

calc ::= calc expr:e {: System.out.println(e.toString()); :}

SEMI

| expr:e SEMI {: System.out.println(e.toString()); :} ;

expr ::= ...

Quando são executadas as ações embutidas?

– São tratadas como não terminais (um novo para c/ação)

– Uma produção vazia é adicionada para c/ação

– Conflitos podem ser introduzidos

calc ::= calc expr:e $N_1 SEMI

| ...

$N_1 ::= {: System.out.println(e.toString()); :} ;

21

Implementação totalmente imperativa

import java.util.*;

action code {:

List pilha = new Vector();

void push(int a) { pilha.add(pilha.size(), new Integer(a)); }

int pop() { Integer i = (Integer) pilha.remove(pilha.size()-1);

return i.intValue(); }

:}

terminal PLUS, TIMES, SEMI, LPAREN, RPAREN;


non terminal expr, expr_, calc;



22

calc ::= expr_ SEMI calc

| expr_ SEMI {: System.out.println("BYE"); :}

;

expr_ ::= expr {: System.out.println(pop()); :} ;

expr ::= expr PLUS expr

{: int a = pop(); int b = pop(); push(a+b); :}

| expr TIMES expr

{: int a = pop(); int b = pop(); push(a*b); :}

| LPAREN expr RPAREN

| NUM : i {: push(i.intValue()); :} ;

23

Exemplo estendido:

Todo um interpretador em Ações semânticas

Prog → Stm

Stm → Stm ; Stm

| id := Exp

| print ( ExpList )

Exp → Exp BinOp Exp

| Stm , Exp

| ( Exp )

| id

| num

ExpList → Exp , ExpList

| Exp

BinOp → + | *

Sintaxe de

Straight-line

24


terminal String ID;

terminal PLUS, TIMES, SEMI, COMMA, LPAREN,

RPAREN, ASSIGN, PRINT ;

non terminal exp, stm, exps, prog;

precedence right SEMI;



Interprete em Estilo Imperativo

25

action code {:

List pilha = new Vector();

void push(int a) {

pilha.add(pilha.size(), new Integer(a)); }

int pop() {

Integer i = (Integer) pilha.remove(pilha.size()-1);

return i.intValue(); }

Map mem = new HashMap();

void store(int v, String id) {

mem.put(id, new Integer(v)); }

int get(String id) {

Integer v = (Integer) mem.get(id);

return v.intValue(); }

:}

26

prog ::= stm ;stm ::= stm SEMI stm

| ID:id ASSIGN exp {: store(id,pop()); :}| PRINT LPAREN exps RPAREN

{: System.out.println(); :};

exps ::= exp {: System.out.println(pop()); :} | exps COMMA exp

{: System.out.println(pop()); :} ;

exp ::= exp PLUS exp{: int a = pop(); int b = pop(); push(a+b); :}

| exp TIMES exp {: int a = pop(); int b = pop(); push(a*b); :}

| LPAREN exp RPAREN| stm COMMA exp| NUM : i {: push(i.intValue()); :}| ID : id {: push(get(id)); :};

Misturando estilos// declarações de símbolos e precedências como antes, salvo:

non terminal Integer exp ;

action code {: ... // só definições de get e store:}

prog ::= stm ;

stm ::= stm SEMI stm

| ID:id ASSIGN exp:e {: store(id,e.intValue()); :}

| PRINT LPAREN exps RPAREN

{: System.out.println(); :}

;

exps ::= exp:e {: System.out.println(e.intValue()); :}

| exps COMMA exp:e

{: System.out.println(e.intValue()); :}

;

Impressão: ações semânticas com efeitos colaterais

Avaliação de expressões: gramática de atributos

28

exp ::= exp:e1 PLUS exp:e2

{: RESULT = new Integer(e1.intValue()+

e2.intValue(); :}

| exp TIMES exp

{: RESULT = new Integer(e1.intValue()*

e2.intValue(); :}

| LPAREN exp:e RPAREN {: RESULT = e; :}

| stm COMMA exp:e {: RESULT = e; :}

| NUM : i {: RESULT = i; :}

| ID : id {: RESULT = new Integer(get(id)); :}

;

29

Ações Semânticas em LL

• Ações semânticas são misturadas com o

fluxo de controle das ações do parser

• Ordem de avaliação é fácil predizer

• Atributos sintetizados

– Valor de retorno da função

• Atributos herdados

– Através de argumentos da função

30

Atributos sintetizados em LL

E → num + E1 { E.v = num.v + E1.v }

| num { E.v = num.v }

int E() {

if (tok1.code == NUM && tok2.code == PLUS ) {

int i = tok1.value();

reconhece(NUM ); reconhece (PLUS); int j = E( ); return(i+j); }

else if (tok1.code == NUM && tok2.code == EOF) {

int i = tok1.value; reconhece(NUM); return i; }

else erro();

}

LL(2)

Atributos sintetizados são passados de filhos para pai através do retorno da função

31

Atributos herdados em LL

E → num E’

E’ → + num E1’

| - num E’

|

Se aumentarmos a operação “-”, o parser começa a complicar

Podemos fatorar à esq. para termos LL(1)

No entanto a gramáticade atributos precisa de atributos herdados

O computo do + e – associa a esq. ou a dir.?

{ E’.h = num.v ;

E.v = E’.v}

{ E1’.h = E’.h + num.v;

E’.v = E1’.v }

{ ... // similar }

{ E’.v = E’.h }

32

Atributos herdados em LL

Atributos herdados são passados

• de pai para filho através de argumentos da função

• de irmão (à esquerda) para irmão na avaliação da produção

int E() {switch(tok.code) {

case NUM: int v = tok.value(); reconhece(NUM); return E’(v);

default: erro(); } }

int E’(int h) {switch(tok.code) { // h atributo herdado

case PLUS: reconhece(PLUS); int v = reconhece(NUM);

return E’(h+v);

case MINUS: ... // similar

case EOF : return h;

default: erro(); }

33

Interprete de Expressões LL

E → T E’

E’ → + T E’ |

T → F T’

T’ → * F T’ |

F → num | ( E )

Gramática de expressões

por camadas e fatorada

Primeiro(E) = { id, num, ( }

Primeiro(E’) = { ,+, $ }

...

Seguinte(E) = { ), $ }

Seguinte(E’) = { ), $ }

....Exercício tipo prova:

• Calcular a tabela de parser LL(1)

• Dar uma gramática de atributos para

um interpretador desta gramática

• Implementar na mão

• Extra: implementar usando JavaCC

34

Ações com efeitos colaterâis

public class InterpretadorSL {

Map mem = ...;

void SimpleStm() {switch(tok.code) {

case PRINT: reconhece(PRINT); reconhece(LPAREN);

ExpList(); reconhece (RPAREN)

case ID: String id = (String) tok.value();

reconhece (ID); reconhece(ASSIGN);

int v = Exp( ); mem.store(id,v); break;

default: erro();

}

um interpretador de straight-line

Embutimos ações semânticas no parser

35

void compoundStm { ... }

void ExpList( ) {switch(tok.code) {

case ....: int v = Exp( );

System.out.print(v+" ");

reconhece(COMMA);

ExpList();

break;

case RPAREN: System.out.println(); break;

default: erro();

}

int Exp ( ) {...}

36

Ações semânticas no JavaCCvoid SimpleStm( ) :

{ Token t;

int v; }

{ “print” “(” ExpList() “)”

| t=<ID> <ASSIGN> v = Exp( ); { mem.store(t.image(),v); }

}

...

void ExpList( ) :

{ int v;

}

{ v = Exp( ) { System.out.print(v+" "); }

( <COMMA> v = Exp() { System.out.print(v+" "); } )*

{ System.out.println() }

}

...

37

Exercício opcional

• Completar o interpretador de straight-line

na mão ou usando JavaCC

38

Exercício opcional• Utilizando uma gramática de atributos escrita em JavaCC,

dar uma implementação em estilo funcional do interpretador de straight-line

– Definir o tipo memória com funções

• int get(String), Memoria store(int,String)

– Atributos herdados são necessários?

– Atributo sintetizado de Stm

• Memória e Lista de valores (impressos), ou

• Memória (aqui a impressão será imperativa)

– Atributo de Exp

• ?

– Atributo de Exps

• ?

• Qual é a dificuldade de se fazer este exercício no Cup?

Documents

Departamento de Estatística e Informática Universidade ... · PDF file•Regras são avaliadas quando a produção é aplicada •Gramática de atributos –Defn. dirigida por sintaxe