[antlr-interest] Examples of using treeparsers to reduce a ruleset

[Ken Allan]

Hi,

I was just wondering if there were any websites that you guys could 
point me to with respect to using treeparser code to reduce (optimize) 
an AST.

I currently have grammer to produce from input:
"a b c d ( e f ) g OR h (NOT i NOT j) AND k OR l"

AST trees of the form:
( AND a b c d ( AND e f ) ( OR g h ) ( OR ( AND ( AND ( NOT i ) ( NOT j 
) ) k ) l ) )

I would like to reduce this to:
( AND a b c d e f ( OR g h ) ( OR k ( AND l ( NOT ( OR i j ) )

The essential steps I wish to take are:
   flatten nested ANDs
   flatten nested ORs
   move ORs within ANDs  as far right as possible
   move ANDs within ORs as far right as possible
   move NOTs within ANDs and ORs as far right as  possible
   convert multiple sequential NOTs in an AND tree into a single NOT of 
the OR of the subnodes
   convert multiple sequential NOTs in an OR tree into a single NOT of 
the AND of the subnodes

eg for the last 2:

( AND ( NOT a ) ( NOT b ) )  => ( NOT ( OR a b ) )
( OR ( NOT a ) ( NOT b ) )  => ( NOT ( AND a b ) )

I realize what I am trying to do is very complicated and understand that 
I may have to do it by hand, but I was wondering if it can be done 
nevertheless...

Thanks!