How do I parse boolean logic?

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 CA开发者_JS百科COUNT=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'
)

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'

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.

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'
)