[LUNGO] Come organizzereste un interprete per espressioni?

[f@bio80]

Salve a tutti, sto lavorando ad un componentino un pò cazzutello: devo realizzare un interprete per espressioni, espressioni che possono essere composte da parti di testo concatenate insieme, operazioni matematiche, operazioni sulle date ecc...

fondamentalmente entrano in gioco due entità: operandi e operatori.
gli operandi possono essere "costanti" ossia prelevati così come sona da una fonte dati, oppure "variabili" in quanto definiti run time dall'utente
gli operatori invece sono i classici operatori relativi alle operazioni su stringhe, numeri, date ecc...

requisito fondamentale è lasciare massima libertà all'operatore di scrivere la sua bella espressione (tanto poi a interpretarla ci devo pensare io ), quindi bisogna scrivere a manetta dentro una text area.

all'inizio avevo pensato di lavorare con la notazione polacca, minima spesa per l'operatore - massima resa per me che devo interpretare, peccato che come idea non è piaciuta, la scrittura dell'espressione deve essere quanto più naturale possibile... ari

quindi adesso chiedo a voi: come lo pensereste questo sistema?

per intenderci le espressioni che vanno valutate sono del tipo:

(valore1 * valore 2) & " " & Left(Stringa1, 3) & " " & "Ciao Mamma"

Considerazione 0)
Lo stringone da interpretare arriva all'interprete con i parametri già valorizzati, ma forse quì ci posso lavorare sopra per evitare ambiguità potrei fare le sostituzioni all'ultimo (mumble mumble...)

Considerazione 1)
Tutta la sleppa che ho scritto sopra finisce chiaramente in una stringa...ergo non posso permettere all'operatore di scrivere & " " & altrimenti quando assegno il valore s'incazza non poco...o sbaglio? quindi penso che le stringhe vadano trattate in una maniera particolare, con un tag magari...

(valore1 * valore 2) & String( ) & Left(Stringa1, 3) & String( ) & String(Ciao Mamma)

Considerazione 2)
Questa non mi fà dormire: come faccio a individuare i blocchi su cui devo fare qualcosa? intendo come divido lo stringone per interpretarlo...nel caso precedente potrei splittare tutto usando la & come parametro, ma se poi la & capita pure dentro una stringa che invece non và divisa?

insomma il problema credo che l'avete capito, please
p.s. lavoro in vb.net

[71104]

io tempo fa ho realizzato un parser per espressioni matematiche in Pascal (lavorarvo ancora con quella porcheria di Delphi... ) e posso dire che il lavoro alla fine è stato molto più semplice di come me lo aspettavo: in un paio di pomeriggi l'ho realizzato completamente, e aggiungiamocene anche un altro per la correzione di alcuni errori.
purtroppo il codice non ho più idea di dove sia (risale ad almeno 3-4 anni fa e nel frattempo ho cambiato computer 2 volte forse l'ho conservato sul disco di backup), ma funzionava benone ed era organizzato nel seguente modo: le espressioni sono costituite da un'alternanza di operandi e operatori binari e dovevano necessariamente iniziare e terminare con un operando; un operatore binario è semplicemente una stringa costituita da uno, due o più simboli (volendo anche alfanumerici), mentre un operando è costituito da zero o più operatori unari seguiti da qualcosa che rappresenti il valore: una costante numerica (volendo anche con il punto) oppure una variabile, cioè una sequenza di caratteri alfanumerici e/o underscores che *non* inizia con un carattere numerico; inoltre al posto del valore poteva anche trovarsi un'altra espressione inclusa tra parentesi tonde.
tra operatori (sia binari che unari) e valori (costanti o identificatori di variabili) devono esserci uno o più blanks, cioè spazi, tabulazioni, newlines, o carriage returns; può anche non esserci nessun blank quando la situazione non è ambigua.
la routine di parsing principale era costituita da un gigantesco loop che analizzava un carattere alla volta e settava determinate variabili/condizioni in base a quello che si aspettava di trovare; se non lo trovava interrompeva, restituiva False e memorizzava in un membro pubblico (era una classe) un messaggio di errore.
lo scopo principale della routine di parsing era di costruire un albero logico in cui rappresentare l'espressione analizzata; i nodi di quest'albero erano struct (in Pascal: record ) che rappresentavano i vari tokens e contenevano membri tipo la stringa che rappresentava il token, l'eventuale interpretazione numerica, la sua posizione (offset) a partire dall'inizio dello stream analizzato, un eventuale index in un array di operatori unari o binari se si trattava di un operatore, e così via.
una volta fatto il parsing (costruito l'albero), si poteva richiamare una o più volte una routine Run che eseguiva le espressioni analizzate (potevano essere più d'una, separate da punti e virgola) e restituiva un array contenente il risultato di ciascuna di esse.

[71104]

dimeticavo: quando il parser trovava una parentesi tonda (ammesso che fosse ammessa una parentesi tonda in quel contesto, cioè ammesso che si aspettasse di analizzare il valore di un operando), la routine si comportava in maniera ricorsiva: chiamava se stessa per analizzare la sotto-espressione contenuta tra le parentesi.
inoltre se ben ricordo, il programmatore che usava la classe poteva anche aggiungere una lista di funzioni speciali da poter usare nelle espressioni, tipo la funzione sqrt (radice quadrata), pow (potenza) e così via; per fare questo il programmatore doveva chiamare una funzione (una procedura per l'esattezza ) per aggiungere ad un array interno l'identificatore (il nome) della funzione, ed una sua callback ad essa associata, che veniva richiamata dalla Run se nell'espressione veniva incontrata quella funzione.

mi sembra anche di ricordare che in una versione fatta successivamente avevo aggiunto la possibilità di ottimizzare l'espressione in fase di parsing eseguendo una sorta di Run già in parse-time che si limitava ad operare sui valori costanti ma non sulle variabili e sulle funzioni.
se ad esempio l'espressione era 1+1, l'unico token che veniva aggiunto all'albero era un token numerico di valore 2.0, mentre nella versione precedente c'erano 3 tokens: il valore 1, operatore binario "+", e un altro valore 1.