7

抽象構文木の構造がよくわかりません。ASTが表すプログラムのソースで「下(前)」に行くには、一番上のノードを右に行くか、下に行くか? たとえば、サンプルプログラムは

a = 1
b = 2
c = 3
d = 4
e = 5

次のような AST が生成されます。 ここに画像の説明を入力

またはこれ： ここに画像の説明を入力

最初のものでは、「右」にmain node進むとプログラムが進みますが、2番目のものでは、next各ノードのポインターをたどるだけで同じことが行われます。

最初のノードのポインターの配列が非常に長くなる可能性がある特別なノードタイプのようなものは必要ないため、2番目の方がより正しいようです。forただし、ループやif分岐など、より複雑なものに入ると、2 番目の方が 1 番目よりも複雑になることがわかります。

4

5 に答える 5

5

最初の表現はより典型的なものですが、2 番目の表現は再帰的なデータ構造としてのツリーの構築と互換性があり、実装プラットフォームが命令的ではなく機能的である場合に使用される可能性があります。

検討：

ここに画像の説明を入力

これは、命令型プログラミング言語の一連のステートメントを含む「ブロック」の一般的な構成を反映するために、短縮され、「ブロック」というより適切な名前の「メイン」ノード (概念的なストローマン) を除いて、最初の例です。さまざまな種類のノードにはさまざまな種類の子があり、それらの子には、「ブロック」の場合のように順序が重要な補助ノードのコレクションが含まれることがあります。同じことが、たとえば配列の初期化から発生する可能性があります。

int[] arr = {1, 2}

これが構文ツリーでどのように表現されるかを考えてみましょう。

ここに画像の説明を入力

ここで、array-literal-type ノードには、順序が重要な同じタイプの子も複数あります。

于 2011-05-27T18:30:05.070 に答える
4

最初のものでは、メインノードで「右」に進むとプログラムが進みますが、2番目のものでは、各ノードの次のポインターをたどるだけで同じことが行われます.

最初のノードのポインターの配列が非常に長くなる可能性がある特別なノードタイプのようなものは必要ないため、2番目の方がより正しいようです

ほとんどの場合、最初のアプローチを好みます。次のノードへのポインターを維持する必要がない場合は、AST を構築する方がはるかに簡単だと思います。

次のように、すべてのオブジェクトを共通の基本クラスから派生させる方が一般的に簡単だと思います。

abstract class Expr { }

class Block : Expr
{
    Expr[] Statements { get; set; }
    public Block(Expr[] statements) { ... }
}

class Assign : Expr
{
    Var Variable { get; set; }
    Expr Expression { get; set; }
    public Assign(Var variable, Expr expression) { ... }
}

class Var : Expr
{
    string Name { get; set; }
    public Variable(string name) { ... }
}

class Int : Expr
{
    int Value { get; set; }
    public Int(int value) { ... }
}

結果の AST は次のとおりです。

Expr program =
    new Block(new Expr[]
        {
            new Assign(new Var("a"), new Int(1)),
            new Assign(new Var("b"), new Int(2)),
            new Assign(new Var("c"), new Int(3)),
            new Assign(new Var("d"), new Int(4)),
            new Assign(new Var("e"), new Int(5)),
        });
于 2011-05-27T18:44:17.277 に答える
1

いくつかの理由から、最初のバージョンの方が理にかなっていると思います。

第一に、最初のものはプログラムの「入れ子」をより明確に示しており、根付きツリー (ツリーの通常の概念) として明確に実装されています。

2 つ目の、より重要な理由は、"メイン ノード" が実際には "ブランチ ノード" (たとえば) であった可能性があることです。これは、より大きな AST 内の別のノードである可能性があります。このようにして、AST を再帰的な意味で見ることができます。各 AST は、子として他の AST を持つノードです。これにより、最初の設計がより単純で、より一般的で、非常に均一になります。

于 2011-05-27T18:29:51.410 に答える
1

言語によって異なります。C では、ブロックには可変スコープがあるため、最初の形式を使用してブロックの概念をキャプチャする必要があります。

{
    {
        int a = 1;
    }
    // a doesn't exist here
}

変数のスコープは、いわゆる「メイン ノード」の属性になります。

于 2011-05-27T18:21:38.010 に答える
0

提案: ツリー データ構造を扱うときは、コンパイラ関連の AST であろうと他の種類であろうと、常に単一の「ルート」ノードを使用してください。

class ASTTreeNode {
  bool isRoot() {...}

  string display() { ... }  
  // ...
}

void main ()
{
  ASTTreeNode MyRoot = new ASTTreeNode();

  // ...

  // prints the root node, plus each subnode recursively
  MyRoot.Show();
}

乾杯。

于 2011-05-27T18:24:42.667 に答える