Working with expression AST:s

Question

Hi,

Is there any best practice when working with AST:s? I have a parsed expression AST. ConstantExpression, BinaryExpression etc. I want to populate a GUI-dialog with information from the AST, and it's here where I get kinda confused because my code gets pretty messy.

Example:

expression = "Var1 > 10 AND Var2 < 20"

I want to populate two textboxes with value 10 resp. 20 from the AST. What I'm doing now is a recursive method that checks for correct child expression-types (with .Net Is-operator) and acts accordingly and the code is really "smelly" :)

Is there any design pattern, like Visitor or such, that makes this somewhat easier/more readable/maintainable ?

Answer 1

Most compilers solve this problem by using either

• Method overriding
• Visitor

Here are is how you'd go about collecting all constant value (literals) that appears in your expression into a List of integers. Calling code can then populate textboxes with values from this list.

Method overriding

The top-most AST class defines an abstract method which is overridden at subclasses.

class AstNode {
  .. // Some stuff
  public abstract void collectValues(List<Integer> ints);
}

class ConstantExpression : AstNode {
  private int value;
  .. // Some stuff
  public override void collectValues(List<Integer> ints) { ints.Add(value); }
}

 class BinaryExpression : AstNode {
   private AstNode left;
   private AstNode right;
   .. // Some stuff
   public override void collectValues(List<Integer> ints) { 
      left.collectValues(ints); 
      right.collectValues(ints); 
   }
}

class Identifier : AstNode {
  .. // Some stuff
  public override void collectValues(List<Integer> ints) { 
     // do nothing!
  }
}

Visitor

Same program but written using Visitors.

class Visitor {
   public abstract void visit(ConstantExpression e);
   public abstract void visit(BinaryExpression e);
   public abstract void visit(Identifier e);
}

class AstNode {
  .. // Some stuff
  public abstract void accept(Visitor v);
}

class ConstantExpression : AstNode {
  public int value;
  .. // Some stuff
  public override void accept(Visitor v) { v.visit(this); }
}

 class BinaryExpression : AstNode {
   private AstNode left;
   private AstNode right;
   .. // Some stuff
  public override void accept(Visitor v) { 
     left.accept(v); 
     right.accept(v); 
     v.visit(this); 
  }
}

class Identifier : AstNode {
  .. // Some stuff
  public override void accept(Visitor v) { v.visit(this); }
}


class ValueCollector : Visitor {
  public List<Integer> ints = ...;

   public void visit(ConstantExpression e) { ints.Add(e.value); }
   public void visit(BinaryExpression e) { }
   public void visit(Identifier e) { }
}