Grammatiche con attributi

Grammatica ad attributi per il calcolo del valore di un'espressione

T F T' → ε

F T' | / F T' | → F NUM | (E)

Associamo ai simboli non terminali i seguenti attributi:

• S: double
• E: valIn ES double
• E': ris S double
• T: valIn ES double
• T': ris S double
• F: double

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 attributi ereditati e restituisce gli attributi 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;}}

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

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

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

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 (string 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:

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 → ε | -5/15-
• E → 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
• val S int
• nCifre S int
• segno S int
• nCifreIn ES int
• valIn ES int

R S c N D E.val → S.segno * (N.val + D.val * 10^N.nCifre) * 10^E.val

N.valIn = c.val

N.nCifreIn = 1

S + {S.segno = 1;}

S - {S.segno = -1;}

S {S.segno = 1;}

N c N {N.nCifre = N.nCifre; N.val = N.val; N.nCifreIn = N.nCifreIn + 1; N.valIn = N.valIn * 10 + c.val;}

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

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-

L'analizzatore lessicale viene modificato nel seguente modo:

Class Lex {

private double val = 0;

double currVal ()

{return val;}
boolean riconosciReale ( char [] st, int n ) {
    boolean errore = false;
    int q = 0;
    int i = 0;
    val=0;
    int valI, valD=0, valE=1, segno;
    for (int i=0; i<n && !errore; i++)
        switch (q) {
            0: if ( st[i] == ''+' || st[i] == ''-' ) {
                   q=2; segno = (st[i]== ''+' )?1: -1;
               }
               else if ("0" <= st[i] <= "9") {
                   q=1; valI=(int) st[i];
               }
               else errore=true;
               break;
            1: if ("0" <= st[i] <= "9") {
                   q=1; valI=valI*10+ ((int) st[i]);
               }
               else if ( st[i] == ".")
                   q=3;
               else if (st[i] == "e")
                   q=5;
               else errore=true;
               break;
            2: if ("0" <= st[i] <= "9") {
                   q=1; valI= segno *((int) st[i]);-7/15-
               }
               else errore=true;
               break;
            3: if ("0" <= st[i] <= "9") {
                   q=4; valD= ((int) st[i]) / 10;
               }
               else errore=true;
               break;
            4: if ("0" <= st[i] <= "9") {
                   q=4; valD=valD/10 + ((int) st[i]);
               }
               else if (st[i] == "e")
                   q=5;
               else errore=true;