[C++] Alberi e parsing di espressioni

[JamesC++]

Devo costruire un parser perciò devo creare un albero sintattico a discesa ricorsiva.
Ho deciso di creare una classe C++ per il riconoscimento dei comandi con classi derivate (classe IF,classe WHILE,classe ASSEGNAMENTO,classe BLOCCO {} ,classe RETURN) e una classe per il riconoscimento delle espressioni.

A livello concettuale non capisco come devo fare per costruire l'albero sintattico
Io penso ke debba creare anche una classe tree ma non ho chiaro come faccio ad aggiungerci nodi in modo corretto.

Premetto che conosco come scorrere la lista dei token e riconoscere gli idiomi del linguaggio .

C'è qualcuno ke può illuminarmi???

[mondobimbi]

non è una impresa semplice, già il parser per le espressioni è abbastanza complicato

Hai una classe base

class ItrNodo
{

protected:

    ItrNodo() ;

public:

...

    virtual ~ItrNodo() ;
    virtual RES eval() = 0;
}; 

da cui per esempio derivi

// operatore unario
class TUNOP : public ItrNodo
{

protected:

    ItrNodo *operand;

    TUNOP (ItrNodo *o) ;
    ~TUNOP() ;
};

// operatore binario
class TBINOP : public ItrNodo
{
protected:

    ItrNodo *left, *right;

    TBINOP (ItrNodo *l, ItrNodo *r) ;
    ~TBINOP() ;

}; 

il + binario ti risulta

class TPLUS : public TBINOP
{
public:

    TPLUS(ItrNodo *l, ItrNodo *r) ;

    RES eval () ;

    void print_op() ;
}; 

dove la eval (virtuale) in questo caso

RES TPLUS::eval ()
{
    return left->eval() + right->eval();
} 

prova a buttare giù qualcosa.
L'interprete lo affronti dopo che è ancora più complicato.
ciao
sergio

[JamesC++]

Grazie Sergio per aver cercato di aiutarmi.

Ripensandoci un po' ho pensato di fare una cosa :

Creare una classe ESPRESSIONE e conosco il metodo per rilevarle e questo vale anke per i comandi.

Creare una classe Comandi da cui derivo : classe while,classe assegnamento, classe if, classe return, classe blocco. (IL Compilatore ke devo fare contiene una grammatica semplice).

Ogni volta ke trovo un comando e una espressione mi creo l'albero relativo AD ESSA (gestendo gli errori) e poi lo vorrei passare ad un altra classe ALBERO alla quale aggancio i sottoalberi
che ho creato in modo da farne uno principale.

La classe albero la metto sotto un template <class LabelType>

Può essere un ragionamento corretto????

Attendo risposta

[Relisys]

io devo fare la tua stesa identica cosa

se vuoi possiamo scambiarci qualche idea anche tramite MSN o quello che vuoi...

fammi sapere...il mio lo trovi nel mio profilo...

[Relisys]

scusa mondobimbi...

quella è una classe base per un albero sintattico giusto??

quindi io prima di fare quello dovrei avere un riconoscitore delle espressioni???

oppure lo fa quello???

[mondobimbi]

breve esempio ma funzionante

#include <iostream>
using namespace std;

typedef float RES ;

class ItrNodo
{

protected:

    ItrNodo() {};

public:

    virtual ~ItrNodo() {};
    virtual RES eval() = 0;
};

// operatore binario
class TBINOP : public ItrNodo
{
protected:

    ItrNodo *left, *right;

    TBINOP (ItrNodo *l, ItrNodo *r) :
    left(l), right(r) {}

    ~TBINOP() {
    delete left;
    delete right;
    }

};

class TPLUS : public TBINOP
{
public:

    // implementazione della classe TPLUS
    TPLUS (ItrNodo *l, ItrNodo *r) :
        TBINOP(l, r) {}

    RES eval () {
        return left->eval() + right->eval();
    }

};

class TVALUE : public ItrNodo
{
protected:

    RES value;
public:

    TVALUE (RES val) :
        value(val)
    {
    }    

    RES eval ()
    {
           return value;
    }
};

int main (int argc, const char * argv[]) {

    ItrNodo *op1 = new TVALUE(2);
    ItrNodo *op2  = new TVALUE(3);

    ItrNodo *plus = new TPLUS(op1, op2);

    cout << "resultato=" << plus->eval() << "\n";

    delete plus;

    return (0);
} 

presuppone che tu conosca le funzioni virtuali
ciao
sergio

[Relisys]

guarda sergio sei stato davvero gentillismo...permettimi di farti due domande esplicative sul codice che mi hai postato così per vedere se l'ho bene inteso...

nel momento in cui io dichiaro

ItrNodo *op1 = new TVALUE(2);

mi viene inizializzata la variabile privata "value" della classe TVALUE a 2 (esempio preso dal tuo codice).

nel momento in cui creo il puntatore (a cui passo i due nodi con i due valori),

ItrNodo *plus = new TPLUS(op1, op2)

per lista di inizializzazione mi vengono inizializzati i due nodi(left e right...che ora sono foglie) della classe TBINOP con i due value "op1" e "op2"

a questo punto la chiamata al cout di

plus->eval()

poichè virtuale nella radice mi chiama il RES eval() della classe TPLUS e mi ritorna la somma dei due numeri....

è tuto giusto ?

poi...un altra domandina...nel momento in cui io mi appoggi ad una tavola dei simboli e ad un analizzatore lessicale già sviluppati...dovrei fare quella cosa che tu fai nel main in una classe madre della tua classe ItrNodo giusto???

ma facendo così...avrei tanie alberi quante sono le operazioni oppure avrei un albero che binario non risulterebbe + ???

io penso + la prima dato che poi devo andare a tradurre il tutto in bytecode java...quindi un albero non binario non mi aiuterebbe...

gentilissimo ancora....ciao sergio

[mondobimbi]

quello che abbiamo visto è un albero sintattico. Se vuoi aggiungere un nodo che faccia la moltiplicazione devi scrivere

class TTIMES : public TBINOP   
{
   public:         
      TTIMES (ItrNodo *l, ItrNodo *r) :           TBINOP(l, r) {}  
       RES eval () { return left->eval() * right->eval();       }     
}; 

per eseguire
3 * (2+4)
(new TTIMES(new TVALUE(3), new TPLUS(new TVALUE(2), new TVALUE(4)))->eval();

evidentemente non potresti scrivere espressioni complesse in questa maniera, hai bisogno di un analizzatore lessicale che in funzione della grammatica data ti generi per te l'albero sintattico in modo che tu debba solamente scrivere
Risolvi("3*(2+4)");

Lo scheletro di questa classe potrebbe essere

class TESPRESSIONE  {  
// tabella per la memorizzazione dei nodi degli alberi sintattici 
    HashClass *SinTreeTbl;   
    char *lexeme;  
    int token;             // token corrente     
     const char *esp ;    // l'espressione da esaminare        
   char * start_str ;    // l'indirizzo della espressione copiata 
  char *str;            // lo scanning lungo la espressione      
   int  scan();
      ItrNodo *root;
      ItrNodo *E();
     ItrNodo *F();
     ItrNodo *T();

      ItrNodo *MakeTree(); 
  public:
      TESPRESSIONE (const char * str);     
           TESPRESSIONE ();
     ~TESPRESSIONE() ;
      // risolve la espressione e disalloca l'albero sintattico 
    RES Risolvi(const char *); 
 } ; 

ti faccio vedere poi i singoli metodi cosa fanno, anche se è intuibile.
ciao
sergio

[Relisys]

Originariamente inviato da mondobimbi

evidentemente non potresti scrivere espressioni complesse in questa maniera, hai bisogno di un analizzatore lessicale che in funzione della grammatica data ti generi per te l'albero sintattico in modo che tu debba solamente scrivere
Risolvi("3*(2+4)");

sisi è proprio questo che devo fare....io l'analizzatore lessicale l'ho già creato e funziona alla perfezione con lexer...

io tramite l'analisi dei token e dei simboli dovrei riuscire a richiamare l'espressione adatta per la mia operazione...ricorsiva proprio perchè come dicevi tu io potrei dover risolvere espressioni complicate tipo 3*(4+5) / (7-3)

e questo tramite chiamate ricorsive alle espressioni....individuate dall'analizzatore lessicale in funzioni dei simboli...


mmmmm...la cosa si complica...anche perchè tutto questo deve essere sviluppato parametricamente...

[Relisys]

ho chiesto da un mod se cambia il titolo della discussione da Alberi a "Progettazione compilatore : parser" almeno forse attirerà + gente e la discussione potrebbe ampliarsi...

e perchè no potrebbe venire fuori un bel wiki appena finisco il progetto...