Boolean Query / Expression to a Concrete syntax tree

Question

I'm creating a search form that allows boolean expressions, like: "foo AND bar" or "foo AND NOT bar".

Is there a library for PHP, Ruby or Java that can transform boolean expressions to a concrete syntax tree?

(I could write my own lexer/parser, but I rather use something tried and tested)

EDIT: To clarify, I'm not parsing arrhythmic expressions. It's going to be used for parsing full text queries that allow boolean operators.

Answer 1

I know this question is almost three years old now, but I recently put together a library in Java specifically to manipulate boolean expressions: jbool_expressions.

It includes a tool too parse expressions out of string input:

Expression<String> expr = ExprParser.parse("( ( (! C) | C) & A & B)")

You can also do some fairly simple simplification:

Expression<String> simplified = RuleSet.simplify(expr);
System.out.println(expr);

gives

(A & B)

Hope this helps.