design-patterns - 式 AST の操作

Question

AST を使用する際のベストプラクティスはありますか? 解析された式 AST があります。ConstantExpression、BinaryExpression など。GUI ダイアログに AST からの情報を入力したいのですが、コードがかなり乱雑になるため、ここでちょっと混乱します。

例：

expression = "Var1 > 10 AND Var2 < 20"

2 つのテキストボックスに値 10 を入力したいと考えています。ASTから20。私が今行っているのは、(.Net Is-operator を使用して) 正しい子式の型をチェックし、それに応じて動作する再帰的な方法であり、コードは本当に「臭い」です:)

Visitor など、これをやや簡単/読みやすく/保守しやすくするデザインパターンはありますか?

score 1 · Accepted Answer

AST を使用するためのベストプラクティスは次のとおりです。

ある種の文法記述から AST を構築するのに役立つ優れたパーサーを入手する
AST を調べて AST を収集/変更するのに役立つ優れたライブラリを入手する

AST を本格的に扱うには、AST を生成および操作するように設計されたパッケージを使用するのが最適です。多くの場合、このようなパッケージには、パターンマッチングやソースからソースへの変換を使用した AST 書き換えなど、多くの追加サポートが含まれています。

ここにいくつかあります：

ANTLR
DMS Software Reengineering Toolkit (私の製品)
TXL

この例では、BNF、パターン、およびソースからソースへの変換のみを使用して AST を構築および操作する方法を示します。

score 0 · Accepted Answer

ほとんどのコンパイラは、次のいずれかを使用してこの問題を解決します。

メソッドのオーバーライド
ビジター

式に現れるすべての定数値 (リテラル) を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!
  }
}

ビジター

同じプログラムですが、訪問者を使用して記述されています。

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

design-patterns - 式 AST の操作

2 に答える 2

Related

Reference