PDA

Visualizza la versione completa : [C++] Alberi e parsing di espressioni


JamesC++
16-04-2008, 21:22
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
17-04-2008, 18:28
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++
17-04-2008, 20:06
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
18-04-2008, 00:04
io devo fare la tua stesa identica cosa :D :D :D

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

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

Relisys
19-04-2008, 12:07
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
19-04-2008, 16:18
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
20-04-2008, 11:17
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 ? :D :D :D

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
20-04-2008, 11:59
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
20-04-2008, 12:33
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... :D

Relisys
20-04-2008, 17:41
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...

Loading