使用表达式 AST

Question

使用 AST 时是否有最佳实践？ 我有一个已解析的表达式 AST。常量表达式、二进制表达式等 我想用来自 AST 的信息填充 GUI 对话框，但在这里我有点困惑，因为我的代码变得非常混乱。

示例：

expression = "Var1 > 10 AND Var2 < 20"

我想分别填充两个文本框的值 10。 20 来自 AST。 我现在正在做的是一种递归方法，它检查正确的子表达式类型（使用.Net Is-operator）并进行相应的操作，代码真的很“臭”:)

是否有任何设计模式，例如 Visitor 等，这使得这更容易/更具可读性/可维护性？

Answer 1

使用 AST 的最佳实践是：

• 获得好的解析器来帮助您根据某种语法描述构建 AST
• 获得一个好的库来帮助您遍历 AST 来收集/修改 AST

对于认真使用 AST 的工作，最好通过以下方式完成使用旨在生成和操作 AST 的包。通常，此类包包含许多附加支持，例如使用源到源转换的模式匹配和/或 AST 重写。

以下是几个：

• ANTLR
• DMS 软件再工程工具包（我的产品）
• TXL

此示例展示了如何仅使用 BNF、模式和源到- 来构建和操作 AST。源转换。

Answer 2

大多数编译器通过使用

• 重写
• Visitor 的

方法来解决此问题。以下是如何将表达式中出现的所有常量值（文字）收集到整数的 List 中。然后，调用代码可以使用该列表中的值填充文本框。

方法重写

最顶层的 AST 类定义了一个抽象方法，该方法在子类中被重写。

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

相同的程序，但使用 Visitor 编写。

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) { }
}