[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