Grammatiche con attributi

Università 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:

• 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).
• 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 parte sintattica contestuale.

Attributi nelle grammatiche

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.

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, ed 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

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' {E1.valIn=E1.valIn+T.ris; E1.ris=E1.ris;} | - T E' {E1.valIn=E1.valIn-T.ris; E1.ris=E1.ris;} | {E1.ris=E1.valIn;}
→ T F T' {T'.valIn=F.ris; T.ris=T'.ris;}
→ T' * F T' {T1.valIn=T1.valIn*F.ris; T1.ris=T1.ris;} | / F T' {T1.valIn=T1.valIn/F.ris; T1.ris=T1.ris;} | {T1.ris=T1.valIn;}
→ F NUM {F.ris=NUM.val;} | (E) {F.ris=E.ris;}

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

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