[antlr-interest] Examples of using treeparsers to reduce a ruleset
Ken Allan
k.allan-antlr at au.darkbluesea.com
Wed May 11 23:46:32 PDT 2005
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!
More information about the antlr-interest
mailing list