[antlr-interest] Walking AST, and rule dilemma

Bryan Ewbank ewbank at gmail.com
Sun Jun 26 17:12:30 PDT 2005


There's a big difference between *processing* trees, and doing
*precedence* in the tree world.  If you want to do precedence in the
tree world, your parser just slurps expressions something like

   expr: ((operator)+ atom )* ;

Which gives you something that looks like a sequence of tokens under
an EXPR node; you are now left with the question of how to parse the
treenode chain that you didn't parse as tokens - it's the same
problem, but in the tree world.  You still need to write the
precedence rules, and rebuild the tree for later processing.

In either case, you will end up with something like
    add_expression : mult_expression ( ( PLUS^ | MINUS^ ) mult_expression )* ;
    mult_expression : atom ( ( MULT^ | DIV^ | MOD^ ) atom )* ;
that rebuilds the trees.  The only question is whether you build the
tree to reflect expression precedence as you process the input (rules
in parser) or defer that until your first tree pass (rules in tree
parser).  It's the same problem, just in a difference context.

Once you have the order of evaluation built into the tree (said
another way, the expression is fully parenthesized), then you simple
walk the trees and process them - no more need to remember precedence,
as it's irrelevant.

- Bryan


More information about the antlr-interest mailing list