How do I parse boolean logic?

Question

I need to write a boolean logic parser which will translate the boolean logic language to a SQL WHERE clause.

The order of the operands will always be in the correct order (with value on the right).

Here is a relatively simple example. There could be nested parentheses and the use of NOT operators, etc.

(CACOUNT=01 OR CACOUNT=02 OR CACOUNT=03)
 AND Q4=1 AND NAME=TIMOTHY

Here is what the WHERE clause would resemble.

WHERE (
     EXISTS (
       SELECT 1 FROM MyVerticalTable b
       WHERE b.Key=a.Key AND b.Key='CACOUNT' AND b.Value='01'
     )
  OR EXISTS (
       SELECT 1 FROM MyVerticalTable b
       WHERE b.Key=a.Key AND b.Key='CACOUNT' AND b.Value='02'
  )
  OR EXISTS (
       SELECT 1 FROM MyVerticalTable b
       WHERE b.Key=a.Key AND b.Key='CACOUNT' AND b.Value='03'
  )
)
AND EXISTS (
       SELECT 1 FROM MyVerticalTable b
       WHERE b.Key=a.Key AND b.Key='Q4' AND b.Value='1'
)
AND EXISTS (
       SELECT 1 FROM MyVerticalTable b
       WHERE b.Key=a.Key AND b.Key='NAME' AND b.Value='TIMOTHY'
)

Answer 1

well, what goes after WHERE is boolean expression, so you need translation with simple replacements, not parsing. for your sample you just need to put quotations to the end: NAME='TIMOTHY'

Answer 2

Write a grammar for the language and create a recursive descent parser. This is the easiest way to parse simple "languages" such as a boolean expression.

Once you've parsed it into your AST (abstract syntax tree), then you can do whatever transformations are necessary and generate the SQL WHERE clause.

Answer 3

after edit everything changed. you still don't need rocket science. write a regular expression, something like: (\w+)=([\w\d]+), then replace each match by

EXISTS (
       SELECT 1 FROM MyVerticalTable b
       WHERE b.Key=a.Key AND b.Key='\1' AND b.Value='\2'
)