Re: parsing boolean queries

Hello,


> [One possibility is to parse once to find out what the names are, then
> parse again to evaluate the expression. Or parse once and build a
> data structure like a parse tree or RPN operator list, then interpret
> the data structure to evaluate the expression. -John]


I use the RPN approach in a text-search routine I wrote (it is in a
Bible concordance program I wrote). Basically, the "names" in my
application are actuall words to be found in the text, and there are
logical operators for AND, OR, and NOT, as well as parens for grouping
just like in normal algebraic notation. I parse the text pattern into
an RPN, then "execute" the RPN. During "execution" each word
(corresponding to your names) is treated as though it is the operand
of an implicit "search" operator... that word is searched for in the
text, and a true/false boolean result is obtained indicating the
presense or abscense of that word in the text. Therefore, the "word"
(like your name) really represents implicitly a boolean value (which
ends up on the evaluation stack as a result). Each logical operator,
of course, only has to deal with boolean values as operands on the
stack and result (which, in turn goes on the evaluation stack). This
works well since each word (name) is only looked up (value computed)
when it is needed in the evaluation, and the result is always a
logical (boolean). (This is not as powerful as regular-expression
pattern matching, but it works quite well in my application.)


--
Charles cbrtjr@ix.netcom.com
* http://pw2.netcom.com/~cbrtjr/wrdthing.html *

Return to the comp.compilers page.
Search the comp.compilers archives again.