alberi binari

[cionci]

Originariamente inviato da /\/\@®¢Ø
Quella di cui parli dovrebbe essere la polacca inverna
(RPN: Reverse Polish Notation), quella diretta dovrebbe avere l'operatore per primo
L'espressione che hai scritto diventa

3 5 * 12 9 - 8 : 42 * + 3 25 + -

Il metodo piu' semplice per trovarla e' scriversi l'albero dalla notazione infissa e poi fare una visita in postordine

Tra l'altro è l'ordine in cui inserire quella espressione nelle mitiche calcolatrici scientifiche HP48 !!!

[/\/\@®¢Ø]

Originariamente inviato da misterx
infatti è la costruzione dell'albero con una espressione il problema; so che ai nodi vanno gli operatori matematici, meglio aritmetici ( + - * : ) e la distribuzione del calcolo tra semialbero destro o sinistro avviene in funzione della priorità di calcolo dell'espressione; ne caso sotto abbiamo ben due priorità

ma è vero che se scrivo 3 * 5 + (12 - 9) : 8 * 42 - (3 + 25) il compilatore la trasforma in notazione postfissa prima di elaborarne il risultato ?

Non e' necessario. Una volta costruito l'albero avere la notazione postfissa e' immediato (attraversamento in postordine dell'albero), ma quello e' un passo successivo. Elaborare le espressioni con operatori infissi e' decisamente piu' complicato che non per la RPN (per la quale basta una pila), sostanzialmente le tecniche sono le stesse che i compilatori usano per 'leggere' il codice sorgente e capire quello che vuole il programmatore. Domani magari faccio un paio di esempi semplici.
'notte

[misterx]

vai ...../\/\@®¢Ø ..... che ti leggo volentieri

esci gli esempi

[/\/\@®¢Ø]

ehm... attenzione: volevo scrivere una piccola introduzione per spiegare il codice ma mi e' venuto fuori un papiro ...
vabbe' se proprio non vuoi passa al post del codice

Quel che si fa in questi casi e' partire da una descrizione di come e' strutturata una espressione aritmetica o, piu' tecnicamente, la "grammatica del linguaggio" (delle esp. ar.).

Come e' fatta una delle nostre espressioni ?
Se ci accontentiamo di poco (), possiamo considerare espressioni che contengano solo numeri, in tal caso possiamo descriverle nel seguente modo

<exp> = <num>

Ovvero 'una espressione si puo' scrivere come un numero', e con <num> intendiamo una sequenza di cifre.
(Sorvoliamo per ora su alcuni aspetti come numeri negativi, o sul come si legga un numero).

Se aggiungiamo le quattro operazioni otteniamo invece:

<exp> = <num> | <num> + <num> | <num> - <num> | <num> / <num> | <num> * <num>

Dove la | non e' un simbolo terminale ma indica alternative tra regole (produzioni) diverse.Va letta "una expressione si puo' scrivere come un numero oppure come un numero seguito dal simbolo + seguito da un altro numero etc."
I nomi tra < e > sono detti simboli non-terminali, i singoli caratteri fuori invese sono i terminali.
Ma quale va scelta tra le cinque ? Informalmente, diciamo che va scelta quella "che va bene". Idealmente dovremmo scegliere delle regole tali che la scelta sia univoca.

In questo modo non possiamo pero' usare piu' di un operatore, mentre noi vogliamo usarne un numero indeterminato, e dobbiamo quindi introdurre una qualche forma di ricorsione nelle nostre definizioni:

<exp> = <num> | <exp> + <num> | <exp> - <num> | <exp> / <num> | <exp> * <num>

Per vedere se una espressione e' descritta da questa grammatica si parte da un simbolo non-terminale particolare, e si procede a sostituire un simbolo non-terminale con uno o piu' simboli (terminali e non-terminali) finche' non ci restano solo terminali.
Le regola qui sopra ad esempio dice che possiamo sostituire un <exp> con una qualsiasi delle 5 sequenze a destra dell'uguale. Ad esempio partendo da <exp> possiamo passare a <exp>'+'<num>. Sostituendo nuovamente <exp> possiamo ottenere <exp>'/'<num>+<num> e cosi' via.
Se introduciamo delle produzione per descrivere gli interi possiamo fare un esempio concreto:

<num> = <digit> | <num><digit>
<digit> = '0' | '1' | '2' | ... | '9'

L'espressione "3+4" si puo ricavare quindi con i seguenti passaggi <exp> -> <exp>+<num> -> (sostituiamo la <exp>) -> <num>+<num> -> (sostituiamo la prima <num>) -> <digit>+<num> -> 3+<num> -> 3+<digit> -> 3+4
Va notato che generalmente il riconoscimento dei numeri viene fatto a priori, e si considerano quindi non singole cifre ma i numeri nel loro complesso. Questo permette delle semplificazioni che vedremo successivamente.

Il prossimo passo e' vedere cosa centra tutto questo con gli alberi, e come fare a calcolare l'espressione, oltre che a valutarne la correttezza (chi ha detto "era ora" ? )

Notiamo innanzi tutto che le produzioni che abbiamo utilizzato sono strutturare in modo ben preciso: un non-terminale a sinistra dell'uguale, e un terminale a destra, eventualmente 'accompagnato' da altri non-terminali. Questo ci fornisce un modo per rappresentare le produzioni tramite nodi di un albero:
Per rappresentare la produzione <exp> -> <exp>+<num> possiamo infatti usare un nodo che abbia come chiave il simbolo '+' e come figli gli alberi che rappresentano a loro volta una <exp> e un <num>.

L'esempio 3+4 visto sopra si tradure quindi come l'albero

   <exp:'+'>
    /    \
 <exp>   <num>
   |       |
 <num>   <digit:4>
   |
 <digit:3>

Se ci fermiamo al livello dei <num> come detto sopra, e procedendo intuitivamente, si puo' semplificare il tutto fino a

      <exp:'+'>
       /      \
    <num:3>  <num:4>

Valutare l'espressione a questo punto e' semplice: si parte dalla radice e si valutano prima i sottorami e poi con i risultati si valuta il nodo corrente. Nell'esempio prima si valuta il valore di 3 e di 4, e poi si ritorna il valore della loro somma.

Va notato che la grammatica finora adottata, seppure perfetta per trovare gli errori, non e' precisa nel trovare l'albero. Con un paio di esempi si puo' vedere che non rispetta le precedenze tra gli operatori (ma rispetta l'associativita' a sinistra... perche' ? ):
3+4*5 :
<exp> -> <exp>*<num> -> <exp>+<num>*<num> -> ...
ci porta a

      <exp:*>
     /      \ 
  <exp:+>   <num:5>
   /   \
 ....

E' un errore perche se andiamo a valutare l'espressione, viene eseguita prima la somma e poi la moltiplicazione.

Si puo' introdurre la precedenza nella nostra grammatica imponendo semplicemente di "dover scegliere prima" tra + e - che tra * e / in modo che appaiano "piu' in alto" nell'albero:

<exp> = <exp> + <fact> | <exp> - <fact> | <fact>
<fact> = <fact> * <num> | <fact> / <num> | <num>

Infine una aggiunta per poter gestire le parentesi:

<exp> = <exp> + <fact> | <exp> - <fact> | <fact>
<fact> = <fact> * <term> | <fact> / <term> | <term>
<term> = ( <exp> ) | <num>

Col prossimo post faro' un esempio di come scrivere il codice per fare tutti questi passaggi.

[misterx]

dammi il tempo di leggerlo e capirlo; preparati alle mie domande

[/\/\@®¢Ø]

Finalmente arriva l'esempio

Come dicevo nel messaggio precedente, di solito si fa per prima la cosiddetta "analisi lessicale" cioe' si cercano di individuare da subito le 'parole' del linguaggio; nel nostro caso si tratta solo di ignorare la spaziatura inutile e di aggregare le cifre consecutive. Questo in linea di massima agevola il lavoro successivo e non e' neanche difficile ad implementare (non e' pero' la regola: linguaggi come il C e il C++ non la adottano). Il prodotto di questa analisi saranno quelli che vengono comunquemente chiamati tokens (gettoni) e saranno gli elementi base su cui lavorera' il parser vero e proprio. Noi dobbiamo distinguere due tipi di gettoni, ovvero le cifre e gli operatori.
In C++ possiamo tradurre questo con

enum token_type { INTEGER , OP };

struct token
{
    token(char c):ttype(OP),symbol(c){}
    token(int n):ttype(INTEGER),value(n){}

    token_type ttype;

    union
    {
        int value;
        char symbol;
    };
};

La nostra funzione 'lexer' fara' prendera in input una sequenza di caratteri e ritornera' una sequenza di tokens: (versione da bocciatura all'esame, ma comunque scrivibile in due secondi )

struct lexical_error
{
    lexical_error(int n):pos(n){};
    int pos;
};


vector<token> lexer( const string& s )
{
    vector<token> result;
    for ( unsigned int i=0 ; i<s.size() ; ++i )
    {
        static const string valid_ops = "+-*/()";
        if ( isspace( s[i] ) )
        {
            // Spazio, ignoriamolo
            continue;
        }
        else if ( isdigit( s[i] ) )
        {
            // Cifra, leggiamo un numero
            int n=s[i++] -'0';
            while( isdigit(s[i]) )
                n = n*10 + s[i++] - '0';
            --i;
            result.push_back( token(n) );
        }
        // Quattro operazioni e parentesi
        else if ( valid_ops.find( s[i] ) != string::npos )
        {
            result.push_back( token( s[i] ));
        }
        // Simbolo sconosciuto, lanciamo un'eccezione
        else
            throw lexical_error(i);
    }
    return result;
}

E l'analisi vera e propria ? Vista la struttura ricorsiva delle definizioni ad ogni non-terminale possiamo associare una funzione che prova a vedere quale delle produzioni si applica, e quando ne trova una che va bene costruisce l'albero opportuno consumando man mano i gettoni di ingresso. Ad esempio se in un dato momento ci troviamo a dover considerare una <term>

<term> = ( <exp> ) | <num>

Non faremo che controllare se il primo gettone e un token operatore ( oppre un numero. Nel primo caso chiameremo "consumeremo" il gettone, chiameremo la funzione associata ad exp e al suo ritorno verificheremo di avere una ')' e cosi' via. Nel caso il token non rientri nelle due categorie lanceremo un'eccezione.
Per semplificare il parser adottero' pero' un imbroglio e una astuzia (per ora). L'imbroglio sta nella definizione di <exp> (e <term>):

<exp> = <exp> + <fact>

Adottando la tecnica sopra esposta infatti entreremmo in un ciclo infinito, non possiamo sapere in anticipo infatti quante 'exp innestate' abbiamo. Una soluzione e' quella di "spiare in avanti" per vedere quando (se!) troviamo una +. Un'altra (sbagliata ma piu' semplice ) e' quella di invertire l'associativita' delle operazioni e riscrivere la precedente come:

<exp> = <fact>+<exp>

Pur se cambia il significato delle espressioni adottero' quest'ultima idea per accorciare il codice.
L'astuzia sta nel notare che non occorre affatto costruirsi l'albero: se si guarda l'ordine in cui l'algoritmo costruisce l'albero e quello in cui poi viene attraversato per trovare il risultato si scopre che e' lo stesso; possiamo quindi accorpare i due e ritornare direttamente i valori. Il risultato e' il seguente:

// <exp> = <fact>+<exp> | <fact>-<exp> | <fact>

template <class It>
int exp( It& first, It last )
{
    int n1 = fact( first , last );
    // Potremmo avere + o - e un <exp>
    if ( first->ttype == OP && first->symbol == '+' )
    {
        ++first;
        return n1 + exp(first,last);
    }
    else if ( first->ttype == OP && first->symbol == '-' )
    {
        ++first;
        return n1 - exp(first,last);
    }
    return n1;
}

// <fact> = <term>*<fact> | <term>/<fact> | <term>
template <class It>
int fact( It& first ,It last )
{
    int n1 = term(first,last);
    // c'e' rimasto qualcosa ... dovrebbe essere * o / e un <fact>
    if ( first->ttype == OP && first->symbol == '*' )
    {
        ++first;
        return n1*fact(first,last);
    }
    else if ( first->ttype == OP && first->symbol == '/' )
    {
        ++first;
        int n2 = exp(first,last);
        if ( n2 == 0 )
            throw div_by_zero();
        return n1/n2;
    }
    return n1;
}

// <term> = (<exp>) | <num>
template <class It>
int term( It& first , It last )
{
    if ( first->ttype == OP && first->symbol == '(' )
    {
        ++first;
        int n = exp(first,last);
        if ( first->ttype == OP && first->symbol == ')' )
        {
            ++first;
            return n;
        }
        throw err_not_closed();
    }
    if ( first->ttype == INTEGER )
    // e' semplicemente un numero
    {
        It old = first++;
        return old->value;
    }
    throw err_unexpected("<term>: expecting a ( or a number");
}

int parse( const vector<token>& v )
{
    typedef vector<token>::const_iterator It;
    It first=v.begin();
    It last=v.end();
    int n = exp( first,last );
    if ( first != last )
        throw err_not_empty();
    return n;
}

A meno di eventuali errori ovviamente (sembra comunque funzionare).
Il funzionamento e' veramente semplice: si parte dal non-terminale iniziale (exp) e gli si da in pasto la lista di gettoni (tramite iteratori). Questo cerca di trovare il risultato ed aggiorna gli iteratori. Le condizioni di errore capitano quando viene gettata un'eccezione oppure viene ritornato un risultato ma non siamo arrivati alla fine dei gettoni.
lexer e parser vengono messe infine assieme nel main:

int main()
{
    string s;
    while(true)
    {
        try
        {
            cout << "Inserisci l'espressione" << endl;
            getline( cin , s);
            vector<token> v = lexer(s);
            cout << "Il risultato e'" << parse(v)<<endl;
        }
        catch( lexical_error )
        {
            cout << "lexical error" << endl;
        }
        catch( err_unexpected e )
        {
            cout << "syntax error:" << e.what() << endl;
        }
        catch( div_by_zero )
        {
            cout << "divide by zero error" << endl;
        }
        catch( err_not_closed )
        {
            cout << "parenthesis error" << endl;
        }
        catch( err_not_empty )
        {
            cout << "too much data" << endl;
        }
    }

}

Per esempi piu' evoluti e' consigliabile utilizzare un qualche generatore di parser, se la grammatica e' un po' complessa comincia diventare un'impresa scriverselo a mano.
E' comunque un campo molto studiato, e c'e' si puo' trovare tanta teoria (su cui io ho decisamente sorvolato ) quanta 'pratica'.

[misterx]

ci scommetto che sei un ometto con tutti 30+

eheh, se scrivevi il codice in java

[xybercom]

x /\/\@®¢Ø
quello che hai scritto è interessante, grazie; potresti però aggiungere qualche riferimento a libri/articoli o librerie ?

[buemuschiato]

x /\/\@®¢Ø anche io...

Davvero interessante quello che hai scritto...
Anche io, come xybercom, sarei interessato a un pò di bibliografia.

ciao

[misterx]

Originariamente inviato da xybercom
x /\/\@®¢Ø
quello che hai scritto è interessante, grazie; potresti però aggiungere qualche riferimento a libri/articoli o librerie ?

lo avrà studiato all'uni

fate domande così anche gli altri leggendovi possono imparare

[xybercom]

Originariamente inviato da misterx
lo avrà studiato all'uni

fate domande così anche gli altri leggendovi possono imparare

Che vuoi dire ? ?

[/\/\@®¢Ø]

Originariamente inviato da xybercom
x /\/\@®¢Ø
quello che hai scritto è interessante, grazie; potresti però aggiungere qualche riferimento a libri/articoli o librerie ?

Faccio riferimeno ai testi che ho in possesso, prendete quindi le mie indicazioni con le pinze.
Vi interessa piu' la parte teorica o pratica ?
Per la parte teorica ho trovato il libro "Theory of computing - A gentle introduction" (Kinber - Smith), molto chiaro. Fa una panoramica dei vari tipi di linguaggi (come complessita') e delle macchine astratte per implementarli. Unico neo, il prezzo tutt'altro che "gentile" (40-50 euro! ).
Se valutate il valore del libro in base al peso troverete piu' utile "Introduction to Automata Theory, Languages and Computation", di Hopcroft, Motwani e Ullman, che a parita di prezzo offre quasi il triplo di pagine . Battute a parte, e' decisamente piu' completo ma a mio giudizio anche meno chiaro nell'esposizione.
Per l'aspetto piu' pratico potete rivolgervi verso un testo che tratta di compilatori. Se volete, da qualche parte in internet dovrebbe trovarsi un PDF liberamente scaricabile dal titolo "Compilers and compiler generators"(spiacente, al momento non ricordo autore o indirizzo). A differenza degli altri due testi (di stampo universitario) non richied conoscenze teoriche particolari e fornisce inoltre diverso codice di esempio in C++ e Modula-3.

[buemuschiato]

/\/\@®¢Ø, grazie per i riferimenti!

[xybercom]

Originariamente inviato da /\/\@®¢Ø
Faccio riferimeno ai testi che ho in possesso, prendete quindi le mie indicazioni con le pinze.
...
Vi interessa piu' la parte teorica o pratica ?

Grazie.
A me interessa scrivere programmi, il che richiede ovviamente anche delle basi di teoria (purchè non sia fine a sè stessa).
Mi domandavo però se non ci siano librerie standard (non mi sembra il caso di reinventare la ruota) per ricavare l'albero rappresentante un'espressione matematica. Cercavo qualcosa di più agile rispetto al sorgente di un compilatore.
Andando un po' off-topic so che Mathematica fa questo automaticamente.

Il link al pdf penso sia questo http://www.scifac.ru.ac.za/compilers/

[Luc@s]

Originariamente inviato da xybercom
Grazie.
A me interessa scrivere programmi, il che richiede ovviamente anche delle basi di teoria (purchè non sia fine a sè stessa).
Mi domandavo però se non ci siano librerie standard (non mi sembra il caso di reinventare la ruota) per ricavare l'albero rappresentante un'espressione matematica. Cercavo qualcosa di più agile rispetto al sorgente di un compilatore.
Andando un po' off-topic so che Mathematica fa questo automaticamente.

Guarda caso interessa anche a me questa ramo

[misterx]

io non ho capito se cercate un qualcosa tipo: scrivo un'espressione e mi viene disegnato un albero binario

[xybercom]

Originariamente inviato da misterx
io non ho capito se cercate un qualcosa tipo: scrivo un'espressione e mi viene disegnato un albero binario

no, il problema è :
data l'espressione matematica creare l'albero (rappresentazione matematica dell'espressione)
rappresentarlo/manipolarlo poi è facile.

Un esempio con Mathematica (che non uso da un po') :
x + 2 * y <=> Plus [ x , Times[2,y] ]
Cioè il programma riconosce che si tratta di una somma con il primo addendo dato da x e il secondo dato dal prodotto di 2 per y.

Questo è il primo passo per poter valutare una funzione definita da un utente.
Es. l'utente inserisce una funzione "sin(x^2)" e il programma genera l'albero e la valuta per i valori di x desiderati.

[xybercom]

Io comunque ho trovato a livello di librerie:
1) fparser http://www.students.tut.fi/~warp/FunctionParser/
che è una libreria C++ che ho provato e sembra funzionare ma non mi sembra "standard"
2) libmatheval che è una libreria GNU http://www.gnu.org/software/libmatheval/
però è in C e non ho ancora avuto tempo di provarla

[/\/\@®¢Ø]

Originariamente inviato da xybercom
Io comunque ho trovato a livello di librerie:
1) fparser http://www.students.tut.fi/~warp/FunctionParser/
che è una libreria C++ che ho provato e sembra funzionare ma non mi sembra "standard"
2) libmatheval che è una libreria GNU http://www.gnu.org/software/libmatheval/
però è in C e non ho ancora avuto tempo di provarla

Che io sappia non esistono librerie standard per quel che serve a te. Tra l'altro mi sembra che la prima libreria calcoli direttamente il risultato... a te e' sufficiente o ti interessa anche l'albero intermedio ?
Nel secondo caso puoi comunque utilizzare un generatore di parser che ti crei l'albero... non e' molto difficile.

[xybercom]

Beh, a me serve essenzialmente il risultato anche se può essere utile avere anche l'albero.
x chiarire quando parlavo di librerie "standard" mi riferivo a librerie molto diffuse, con un ampia base di utilizzatori non a librerie come la STL.
Per generare un parser ci sono strumenti esterni (come accennavi) ? Quali ?