# [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

```