Newsgroup: it.comp.lang.c
Titolo: notazione polacca booleana

In questo periodo mi trovo nella situazione di dover sviluppare una
sottospecie di parser SQL.
La prima cosa che mi e' venuta in mente e' stata quella di adottare un
surrogato della ben nota notazione polacca inversa da applicare ai
singoli statement SQL, in modo da ricostruire passo passo il risultato.
Sostanzialmente:
foo = 5 AND ( bar < 2 OR bar > 7 )
diverrebbe
( foo = 5 ) ( bar < 2 ) ( bar > 7 ) OR AND
Poiche' le mie doti di analisi e progettazione sono assai carenti ( :-P
) mi e' difficoltoso immaginare a priori se questa soluzione possa
risultare efficiente o se, al contrario, gli operatori booleani hanno
qualche implicazione che si scontra con tale procedura: non vorrei
trovarmi al solito a scrivere codice su codice per poi rendermi conto,
tre giorni dopo, che questo metodo non funziona in particolari
condizioni :-P.
Qualche suggerimento? Sia su questo approccio, sia su altri che al
momento non mi sovvengono?
Grazie :-)


nno mi sembra che gli operatori logici hanno particolarita' tra l'altro 
la RPN non ha neanche problemi di associativita'
devi semplicemente separare l'espressione in token
per ogni token devi:
se e' una costante od una variabile
pushare in uno stack il valore ottenuto
se e' un operatore applicarlo agli elementi della cima dello stack.
mi sembra che gli operatori unari debbono essere distinti da eventuali 
operatori binari omonimi ( caso tipico e' negazione (aritmetica) e 
sottrazione )
anche se la tua espressione andrebbe scritta cosi:
foo 5 =  bar 2 <  bar 7 >  OR AND
visto che in RPN le parentesi non esistono
se ti fosse possibile prova ad usare qualche strumento specifico per la 
realizzazione di parser come la coppia yacc e lex ( bison e flex nella 
versione GNU quindi free e disponibile per molte piattaforme ) o antlr.
con questo genere di programmi e' possibile realizzare parser ed 
interpreti con costi di sviluppo relativamente ridotti.
un esempio tipico fornito con questi tool e' il parser ed evalutatore di 
espressioni in forma standard invece che espressioni RPN.

 momento non mi sovvengono?
A meno che tu non abbia un motivo speciale per usare altri sistemi (come 
  l'RPN che hai citato) io ti consiglio di restare nel solco della 
tradizione: descrivi la grammatica del linguaggio (magari in BNF) ed usa 
uno dei tanti tool per la generazione di scanner e parser.
Visto che qui' si parla di C, ti consiglio di dare un'occhiata a RDP se 
la tua grammatica è LL(1) e puo' essere analizzata con un parser a 
discesa ricorsiva. Io l'ho trovato estremamente semplice da usare (in 
confronto ad altri).
Lex/yacc (o flex/bison) sono delle ovvie alternative ma Google ti darà 
una lista piu' completa (cerca: compiler generator tools).
Remo D.

Roberto -MadBob- Guido ha scritto in it.comp.lang.c:

L' RPN è molto simpatico, e per certi casi penso sia meglio della notazione
infissa, che è più familiare solo perché viene insegnata fino dalle scuole
elementari, ma è intrinsecamente anche più complicata.
Se però vuoi passare all' RPN è meglio farlo in modo completo, cioè evitare
di mescolare notazione infissa e notazione RPN. Inoltre nell' RPN le
parentesi non sono necessarie, anzi non devono nemmeno essere previste,
altrimenti ti perdi tutta la semplificazione nel parser.
La tua esperssione dovrebbe quindi diventare :
foo 5 = bar 2 < bar 7 > OR AND
che è ovviamente incmprensibile, ma se inviti l'utente a scrivere il codice
usando indentazioni oppurtune risulta tutto molto più elegante:
    foo 5 =
        bar 2 <
        bar 7 >
    OR
AND
ovviamente tutto questo ha poco a che fare con il c


D'accordo sul fatto che la RPN non accetta parentesi, ma questo e'
valido nel momento in cui gli elementi che compongono l'espressione
sono semplici numeri, identificati ciascuno da un set di cifre che
quello e' e quello rimane.
Ma nel mio caso non ho a che fare con numeri, ma con insiemi: "tutti
gli elementi dove foo == 5", "tutti gli elementi ove bar < 7"... Non
vedo dunque quale beneficio possa avere nell'usare la forma "foo 5 ="
considerando che foo, 5 e = non sono costrutti da contemplare nello
stack RPN per il parser booleano, al contrario di OR, AND e "foo = 5".

 stack RPN per il parser booleano, al contrario di OR, AND e "foo = 5".
Nel tuo caso dovresti fare due parser diversi, uno RPN per lo stack di
operazioni booleane e uno classico-infisso per valutare le condizione di
appartenenza ad un insieme.
Se invece fai tutto con RPN non hai solamente un parser per RPN limitato al
calcolo di operazioni boolenane, ma uno virtualmente estendibile a tutte le
altre operazioni che devi fare.