[antlr-interest] simplification of logic formula
Michel Metzger
metzgerm at iro.umontreal.ca
Thu Mar 31 09:39:50 PST 2005
Hi,
I have a question for you !
I have a logic formula: logic operators (&&, ||, !), atomic proposition
(a, b, c, d, ...), and litterals (true, false)
What I want is to simplify those formulae : for instance translate (a &&
!a) into false
I also want to push the not operator in front of atomic propositions
only. ie, transform !(a && b) in !a || !b
To do that, I thought that using tree parser to transform my syntax tree
would be a good idea. I wrote the following tree transformation rules:
|! (#(OP_NOT OP_OR)) => #(OP_NOT #(OP_OR leftNO:expr rightNO:expr))
{
#expr = #([OP_AND, "&&"], #([12, "!"], leftNO), #([12, "!"],
rightNO));
}
|! (#(OP_NOT OP_AND)) => #(OP_NOT #(OP_AND leftNA:expr
rightNA:expr))
{
#expr = #([OP_OR, "||"], #([12, "!"], leftNA), #([12, "!"],
rightNA));
}
But I have a problem :
take the formula !((a && b) || c). The result should be : ((!a || !b) &&
!c). But with the rules I wrote, the result is :
(!(a && b) && !c. I understand why, but is there a way to call again my
transformation rule on the subtree that I build in my action bloc ?
I hope that my question is clear, and sorry for my english :)
Michel
More information about the antlr-interest
mailing list