Che materia stai cercando?

Grammatiche con attributi

Dispensa di Linguaggi e traduttori sulle grammatiche con attributi, per il corso di ingegneria informatica. Si acquisiranno tutti i dettagli delle grammatiche con attribute e le loro diverse tipologie, imparando come mettere in pratica le nozioni -con esempi chiari- per la realizzazione di interpreti e traduzioni. Inoltre, si parlerà anche delle grammatiche EBNF con attributi, degli attributi... Vedi di più

Esame di Linguaggi e traduttori docente Prof. D. Saccà

Anteprima

ESTRATTO DOCUMENTO

UNIVERSITA’ DELLA CALABRIA

Corso di Laurea in Ingegneria Informatica

Corso di Linguaggi e Traduttori A

DISPENSA DIDATTICA SU

GRAMMATICHE CON ATTRIBUTI

a cura di Domenico Saccà

- Grammatiche con attributi

Abbiamo imparato ad effettuare l'analisi sintattica di linguaggi non-contestuali a partire da

grammatiche LL(1). Rimangono ancora altri compiti da svolgere:

1. un linguaggio "pratico", ad esempio Java, è contestuale (basti pensare al fatto che una

variabile può essere utilizzata solo se definita precedentemente ed in maniera adeguata

all’utilizzo previsto)

2. una volta verificata la correttezza di una frase di un linguaggio, ad esempio a, è necessario

assegnargli un significato - ad esempio ad un programma Java bisogna tradurlo in una frase

di un altro linguaggio (Byte Code) per la sua esecuzione - cioè è necessaria una analisi

semantica.

Per svolgere i due nuovi compiti non butteremo a mare le tecniche imparate fin qui: l'analisi

sintattica non-contestuale rimane come nucleo su cui inserire ulteriori azioni, chiamate semantiche,

anche se quelli di cui al punto (1), chiamate di semantica statica, sono di fatto sintattiche – è la perte

sintattica contestuale.

Per procedere associamo ad ogni simbolo non-terminale, ad esempio X, uno o più attributi che

vanno calcolati all'interno del metodo che implementa X. Un attributo ha un dominio (ad esempio

può assumere valori interi o stringhe) e può essere:

sintetizzato (S), cioè il suo valore è calcolato all'interno della procedura X e restituito dalla

• procedura alla sua terminazione;

ereditato da sinistra (ES), cioè il suo valore viene fornito in ingresso alla procedura X,

• tipicamente ricopiandolo da un attributo sintetizzato di un altro simbolo che compare a

sinistra nella regola; il valore viene poi utilizzato all'interno del metodo X, tipicamente per

calcolare il valore di un qualche attributo sintetizzato, ma non solo;

ereditato da destra (ED), la sola differenza rispetto al caso precedente è che il suo valore è

• copiato da un attributo sintetizzato di un altro simbolo che compare a destra nella regola -

ma come vedremo gli attributi ereditati da destra sono di difficile implementazione;

prodotto dall'esterno (PE) (effetto collaterale - side effect), cioè il valore è calcolato da

• procedure esterne, ad esempio dall'analizzatore lessicale oppure da una lettura da tastiera.

Attributi di tipo PE sono associabili anche ai simboli terminali (token) e sono calcolati

dall’analizzatore lessicale. -1/15-

Una grammatica ad attributi è una tripla <G, A, E> dove G è una grammatica di tipo 2, A è un

insieme di attributi associati ai simboli non-terminali e a quelli terminali di G, e E è un insieme di

equazioni per il calcolo dei valori dei vari attributi.

- Grammatiche con attributi per realizzare un interprete

Consideriamo la grammatica del nostro solito linguaggio delle espressioni aritmetiche - ma questa

volta supponiamo che non esistono variabili per cui gli operandi sono solo numeri:

E T E' | -T E' | +T E'

→ ε

E' + T E' | - T E' |

T F T'

→ ε

T' * F T' | / F T' |

F NUM | (E)

Vogliamo costruire una grammatica ad attributi che calcoli per ciascuna espressione il suo valore.

Sostanzialmente si tratta di un semplice interprete, cioè un programma che effettua l’analisi

sintattica di un programma sorgente e lo esegue direttamente senza effettuare la traduzione in un

programma oggetto.

Associamo ai simboli non terminali i seguenti attributi:

Attributo Tipo Dominio

ris S double

E valIn ES double

E' ris S double

ris S double

T valIn ES double

T' ris S double

ris S double

F

Inoltre al token NUM associamo un attributo VAL di tipo PE e dominio double, che memorizza il

valore del token - pertanto dobbiamo supporre che esiste un ulteriore metodo dell'analizzatore

lessicale, double currVal(), che restituisce il valore del corrente token (ovviamente se esso è NUM

altrimenti potrebbe restituire un errore o un valore di default come 1).

I vari attributi sono calcolati nel seguente modo - tali computazioni sono equazioni inserite come

annotazioni nella grammatica. Per distinguere le diverse occorrenze dello stesso simbolo in una

regola utilizziamo opportuni pedici.

E T E' {E'.valIn=T.ris; E.ris=E'.ris;} | -T E' {E'.valIn= -T.ris; E.ris=E'.ris;} |

+T E' {E'.valIn=T.ris; E.ris=E'.ris;}

E' + T E' {E' .valIn=E' .valIn+T.ris; E' .ris=E' .ris;} |

0 1 1 o 0 1 ε

- T E' {E' .valIn=E' .valIn-T.ris; E' .ris=E' .ris;} | {E' .ris=E' .valIn;}

1 1 o 0 1 0 0

T F T' {T'.valIn=F.ris; T.ris=T'.ris;}

T' * F T' {T' .valIn=T' .valIn*F.ris; T' .ris=T' .ris;} |

0 1 1 o 0 1 ε

{T' .valIn=T' .valIn/F.ris; T' .ris=T' .ris;} | {T' .ris=T' .valIn;}

/ F T'

1 1 o 0 1 0 0

F NUM {F.ris=NUM.val;} | (E) {F.ris=E.ris;}

-2/15-

Ora la grammatica non solo effettua l'analisi sintattica ma anche calcola il valore di una espressione,

cioè effettua azioni semantiche dando significato alla espressione.

Il parser va leggermente modificato per implementare le azioni semantiche. In particolare ogni

metodo corrispondente a un simbolo non terminale X utilizza come parametri formali di ingresso gli

attribuiti ereditati e restituisce gli attribuiti sintetizzati. Le copie degli attributi ereditati si effettuano

al momento del passaggio dei parametri attuali. Mostriamo la realizzazione per la nostra solita

grammatica:

public static boolean calcola ( ) {

costruisciLT_E(); costruisciLT_E1();

costruisciLT_T(); costruisciLT_T1(); costruisciLT_F();

ioh = new IOH();

lex=new LexE (ioh);

double risultato = E();

skipTo(LexE.FINE);

if ( !errore )

ioh.fineConRisultato(risultato);

else

ioh.fineErrata();

}

private static double E() {

double E_ris;

skipTo(LT_E);

switch (lex.currToken() ) {

case Lex.NUM: case Lex.PARTA:

double T_ris=T(); double E1_ris=E1(T_ris);

E_ris = E1_ris; return E_ris;

case Lex.PIU:

lex.nextToken();

double T_ris=T(); double E1_ris=E1(T_ris);

E_ris = E1_ris; return E_ris;

case Lex.MENO:

lex.nextToken();

double T_ris=T(); double E1_ris=E1(-T_ris);

E_ris = E1_ris; return E_ris;

case Lex.MOLT: case Lex.DIV: case Lex.FINE:

setErrore(); T(); E1(1.0);

return 1.0;

}

}

Ovviamente il codice può essere ottimizzato - ad esempio sopra potremmo scrivere:

switch (lex.currToken() ) {

case Lex.NUM: case Lex.PARTA:

return E1(T());

case Lex.PIU: case Lex.MENO:

int segno=(lex.currToken()==Lex.PIU)?1:-1;

lex.nextToken();

return E1(segno*T());

case Lex.MOLT: case Lex.DIV: case Lex.FINE:

setErrore(); T(); E1(1.0);

return 1.0;

}

Scriviamo ora gli altri metodi:

private static double E1( double valIn) {

skipTo(LT_E1); -3/15-

switch (lex.currToken() ) {

case Lex.PIU: lex.nextToken();

return E1(valIn+T());

case Lex.MENO: lex.nextToken();

return E1(valIn-T());

case Lex.NUM: case Lex.PARTA:

setErrore(); ioh.errore(2);

T(); E1(1.0);

return 1.0;

case Lex.PARTC: case Lex.FINE:

return valIn;

}

}

private static double T() {

skipTo(LT_T);

switch (lex.currToken() ) {

case Lex.NUM: case Lex.PARTA:

return T1(F());

case Lex.PIU: case Lex.MENO: case Lex.MOLT:

case Lex.DIV: case Lex.Fine:

setErrore(); F(); T1(1.0);

return 1.0;

}

}

private static double T1( double valIn ) {

skipTo(LT_T1);

switch (lex.currToken() ) {

case Lex.MOLT:

lex.nextToken();

return T1(valIn*F());

case Lex.DIV:

lex.nextToken();

return T1(valIn/F());

case Lex.NUM: case Lex.PARTA:

setErrore(); ioh.errore(2);

F(); T1(1.0);

return 1.0;

case Lex.PIU: case Lex.MENO: case Lex.PARTC: case Lex.FINE:

return valIn;

}

}

private static double F() {

skipTo(LT_F);

switch (lex.currToken() ) {

case Lex.NUM:

double NUM_val=lex.currVal();

lex.nextToken();

return NUM_val;

case Lex.PARTA:

lex.nextToken();

double E_ris=E(); accetta(Lex.PARTC);

return E_ris;

case Lex.PIU: case Lex.MENO: case Lex.MOLT:

case Lex.DIV: case Lex.FINE:

setErrore(); ioh.errore(1);

return 1.0;

}

} -4/15-

Provate ora a realizzare l'analizzatore lessicale.

Esercizio 1.

Scrivete un interprete per espressioni aritmetiche in cui gli operandi siano non solo numeri reali

(double) ma anche variabili. Associamo al token ID un attributo nome di tipo PE e dominio string

per memorizzare il nome della variabile – tale valore viene restituito dall’analizzatore lessicale con

il metodo currID().

Per la gestione delle variabili, prevedere un modulo apposito (VarHandler) realizzato tramite una

apposito oggetto che mette a disposizione il metodo:

double valID (stringi id_Nome );

che restituisce il valore della variabile con identificatore idNome. Tale metodo viene richiamato dal

metodo F ogni volta che serve conoscere il valore di una variabile:

private static double F() {

skipTo(LT_F);

switch (lex.currToken() ) {

case Lex.ID:

string ID_nome=lex.currID();

lex.nextToken();

double ID_val = varHandler.valID(ID_Nome);

return ID_val;

case Lex.NUM:

double NUM_val=lex.currVal();

lex.nextToken();

return NUM_val;

case Lex.PARTA:

lex.nextToken();

double E_ris=E(); accetta(Lex.PARTC);

return E_ris;

case Lex.PIU: case Lex.MENO: case Lex.MOLT:

case Lex.DIV: case Lex.FINE:

setErrore(); ioh.errore(1);

return 1.0;

}

}

L’attributo sintetizzato ris di F è ora calcolato anche tramite il ricorso a funzioni esterne (metodo

valID), cioè è è anche di tipo PE.

Per l’implementazione della classe VarHandler, si può procedere in questo modo:

− l’oggetto varHandler va creato dal parser all’inizio; nella inizializzazione l’oggetto dovrà

indicare che non ci sono ancora variabili definite;

− ogni volta che viene utilizzata una variabile X e lanciato il metodo varHandler.valID(X), se

è la prima volta che X viene adoperata, varHandler chiede all’esterno all’utente il valore di

tale variabile, lo memorizza per possibili utilizzi successivi e lo restituisce; altrimenti viene

semplicemente restituito il valore letto precedentemente.

- Un secondo esempio di grammatica con attributi

Consideriamo come un secondo esempio di grammatica con attributi il linguaggio dei numeri reali

in notazione a virgola mobile:

R S c N D E

→ ε

S + | - |

→ ε

N c N |

→ . ε

D c N | -5/15-

E e S c N

dove c è un token corrispondente a una cifra da 0 a 9.

Per calcolare il valore di un numero reale, costruiamo la seguente grammatica con attributi:

Attributo Tipo Dominio

val S double

R val S int

D nCifre S int

segno S int

S nCifreIn ES int

nCifre S int

valIn ES int

N val S int

val S int

E val PE int

c –D.nCifre E.val

R S c N D E {R.val = S.segno*(N.val+D.val*10 )*10 ; N.valIn=c.val; N.nCifreIn=1;}

→ ε

S + {S.segno=1;} | - {S.segno=-1;} | {S.segno=1;}

N c N {N .nCifre=N .nCifre; N .val=N .val; N .nCifreIn=N .nCifreIn+1;

0 1 0 1 0 1 1 0

N .valIn=N .valIn*10+c.val;} |

1 0

ε .nCifre=N .nCifreIn; N .val=N .valIn;}

{N

0 0 0 0

D . c N {N.valIn=c.val; N.nCifreIn=1; D.val=N.val; D.nCifre=N.nCifre;} |

ε {D.val=0.0; D.nCifre=0;}

→ ε

E e S c N {N.valIn=c.val; N.nCifreIn=1; E.val=S.segno*N.val;} | {E.val=1;}

Esercizio 2.

Implementare la grammatica ad attributi per i numeri a virgola mobile.

- Automi a stati finiti con attributi: automi traduttori

Il linguaggio dei numeri a virgola mobile è regolare per cui ricorrere all'analisi LL(1) è decisamente

sovra-dimensionato. Ovviamente è conveniente continuare ad utilizzare un automa a stati finiti. Ma

è necessario introdurre attributi che sono globali per tutti gli stati che:

- vanno inizializzati prima di avviare l’esecuzione dell’automa a stati finiti (INIZIO)

- vanno modificati tramite opportune azioni semantiche in corrispondenza delle mosse di

transizione - a tale scopo potremmo etichettare gli archi di un automa con tali azioni

- vanno eventualmente modificati a fine computazione dell’automa(FINE).

L’automa è presentato di seguito: -6/15-


PAGINE

15

PESO

303.69 KB

PUBBLICATO

+1 anno fa


DESCRIZIONE APPUNTO

Dispensa di Linguaggi e traduttori sulle grammatiche con attributi, per il corso di ingegneria informatica. Si acquisiranno tutti i dettagli delle grammatiche con attribute e le loro diverse tipologie, imparando come mettere in pratica le nozioni -con esempi chiari- per la realizzazione di interpreti e traduzioni. Inoltre, si parlerà anche delle grammatiche EBNF con attributi, degli attributi nel Type Checking e degli attributi nelle analisi ascendenti.


DETTAGLI
Corso di laurea: Corso di laurea in ingegneria informatica
SSD:
Università: Calabria - Unical
A.A.: 2007-2008

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher BalboFonseca di informazioni apprese con la frequenza delle lezioni di Linguaggi e traduttori e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Calabria - Unical o del prof Saccà Domenico.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Corso di laurea in ingegneria informatica

Analisi probabilistica e teoria delle code - esercizi
Esercitazione
Analisi probabilistica e teoria delle code - prova
Esercitazione
Analisi probabilistica e teoria delle code - prova settembre 2008
Esercitazione
Analisi probabilistica e teoria delle code - prova luglio 2007
Esercitazione