I'm doing some very simple program analyses/transformations in Java using Soot, and I find myself needing to do some simple combinations of boolean expressions. So for example, during my analysis, I'll have an expression like (a < 25) && (b >= 10) and I want to join that expression with (a >=-10) via an OR operator to get a full expression like (a >=-10) || (a < 25) && (b >= 10). Basically, just combining two boolean expression trees into one expression. I might further desire to automatically convert the expression tree into an equivalent conjunctive normal form version of the tree.
Another requirement I have is the ability to simplify the expression (via custom code, if needed) when we have expressions that can be trivially eliminated. For example (a < 20) || (a >= 20) reduces to TRUE, since (a < 20) = (!(a >= 20)), so we can eliminate some terms as we go.
I know it's a classic introductory problem to code up a boolean expression tree, and I'm pretty sure I've implemented it before (once, long ago, for a data structures class :) ) I know I could do it again, if needed... But given that this is likely something that's been handled before, I wonder if there are any recommendations on a library I should look into to tackle the above. I hate to re-invent the wheel when there's probably a perfectly good one out there already.
So to summarize I'm looking for a Java libary that has:
- Boolean expression trees
- Combination of expressions
- Simplification of terms (this is pretty specific, so it's "nice to have")
- Conversion to CNF
Any recommendations?
(NOTE: I won't be evaluating these trees, so each of the nodes will be unresolved predicates like variable != 20 or foo >= 50, so evaluation isn't a requirement, but it doesn't hurt if it's part of the library, either.)