ASTの目標を理解していると思います。以前にいくつかのツリー構造を構築したことがありますが、ASTは作成していません。ほとんど混乱しています。ノードは数字ではなくテキストであるため、コードを解析しているときにトークン/文字列を入力するための良い方法を考えることはできません。
たとえば、ASTの図を見ると、変数とその値は等号のリーフノードでした。これは私には完全に理にかなっていますが、これを実装するにはどうすればよいですか？ケースバイケースで実行できると思います。そのため、「=」に出くわしたときに、それをノードとして使用し、「=」の前に解析された値をリーフとして追加します。おそらく間違っているようです。構文に応じて、何トンものことを主張する必要があります。
そして、別の問題に遭遇しました。ツリーはどのようにトラバースされますか？高さをずっと下げて、一番下にぶつかったときにノードを上に戻り、その隣のノードについても同じことをしますか？
ASTでたくさんの図を見てきましたが、コード内にかなり単純な例を見つけることができなかったので、おそらく役立つでしょう。
コメント
- 重要な概念you ‘欠落しているのは再帰です。再帰は一種の直感に反するものであり、’最終的に’が学習者ごとに異なります。 div id = “509a8f6b64”>
クリック’ですが、再帰がなければ、解析（および他の多くの計算トピックも）を理解する方法はありません。 ）。
回答
簡単な答えは、スタックを使用することです。 これは良い例ですが、ASTに適用します。
参考までに、これはEdsgerDijkstraの
操車場アルゴリズム。
この場合、演算子スタックと式スタックを使用します。ほとんどの言語では数値は式と見なされるため、式スタックを使用して数値を格納します。
class ExprNode: char c ExprNode operand1 ExprNode operand2 ExprNode(char num): c = num operand1 = operand2 = nil Expr(char op, ExprNode e1, ExprNode e2): c = op operand1 = e1 operand2 = e2 # Parser ExprNode parse(string input): char c while (c = input.getNextChar()): if (c == "("): operatorStack.push(c) else if (c.isDigit()): exprStack.push(ExprNode(c)) else if (c.isOperator()): while(operatorStack.top().precedence >= c.precedence): operator = operatorStack.pop() # Careful! The second operand was pushed last. e2 = exprStack.pop() e1 = exprStack.pop() exprStack.push(ExprNode(operator, e1, e2)) operatorStack.push(c) else if (c == ")"): while (operatorStack.top() != "("): operator = operatorStack.pop() # Careful! The second operand was pushed last. e2 = exprStack.pop() e1 = exprStack.pop() exprStack.push(ExprNode(operator, e1, e2)) # Pop the "(" off the operator stack. operatorStack.pop() else: error() return nil # There should only be one item on exprStack. # It"s the root node, so we return it. return exprStack.pop()
（私のコードについては親切にしてください。堅牢ではないことはわかっています。疑似コードであるはずです。）
とにかく、コードからわかるように、任意です。式は他の式のオペランドにすることができます。次の入力がある場合：
5 * 3 + (4 + 2 % 2 * 8) 私が書いたコードはこのASTを生成します：
+ / \ / \ * + / \ / \ 5 3 4 * / \ % 8 / \ 2 2 次に、そのASTのコードを生成する場合は、ポストオーダーツリートラバーサルを実行します。リーフノード（数値付き）にアクセスすると、コンパイラがオペランド値を知る必要があるため、定数を生成します。演算子を使用してノードにアクセスすると、演算子から適切な命令を生成します。たとえば、「+」演算子は「追加」命令を出します。
コメント
- これは次のように機能します。 r右から左ではなく、左から右への結合性を持つ演算子。
- @Simon、右から左への演算子の機能を追加するのは非常に簡単です。最も簡単なのは、ルックアップテーブルを追加することです。演算子が右から左の場合は、オペランドの順序を逆にするだけです。
- @Simon両方をサポートする場合は、’ 操車場アルゴリズムを完全に調べた方がよいでしょう。アルゴリズムが進むにつれて、それは’絶対クラッカーです。
回答
ASTがテストで通常どのように表現されるか（リーフノードに数値/変数があり、内部ノードに記号があるツリー）と、実際に実装される方法には大きな違いがあります。
AST（オブジェクト指向言語）の実装では、ポリモーフィズムを多用します。 ASTのノードは通常、さまざまなクラスで実装され、すべてが共通のASTNodeクラスから派生しています。処理している言語の構文構造ごとに、ConstantNode（または42）、VariableNode（変数名の場合）、AssignmentNode（割り当て操作の場合）、ExpressionNode（一般式の場合）など。
特定の各ノードタイプは、そのノードに子があるかどうか、その数、場合によってはどのタイプかを指定します。 ConstantNodeには通常子がなく、AssignmentNodeには2つあり、ExpressionBlockNodeには子があります。子はいくつでもあります。
ASTは、解析したばかりの構成を知っているパーサーによって作成されるため、適切な種類のASTノードを作成できます。
トラバースする場合ASTでは、ノードのポリモーフィズムが実際に機能します。ベースのASTNodeは、ノードで実行できる操作を定義し、特定の各ノードタイプは、その特定の言語構造に対して特定の方法でそれらの操作を実装します。
回答
ソーステキストからASTを構築するのは”単に” 解析。それがどの程度正確に行われるかは、解析された形式言語と実装によって異なります。 menhir（Ocamlの場合）、 GNU bison とflex、または ANTLR など。多くの場合”手動で” 再帰的降下パーサーをコーディングします（この回答が理由を説明しています）。構文解析のコンテキストの側面は、他の場所（シンボルテーブル、属性など）で行われることがよくあります。
ただし、実際には、ASTはあなたが信じているよりもはるかに複雑です。たとえば、 GCC のようなコンパイラでは、ASTはソースの場所情報といくつかの入力情報を保持します。 GCCのジェネリックツリーと GIMPLE について読み、その gcc / tree.def 。 C、C ++、Fortran、Adaを処理する場合は、独自の GCCプラグインを作成することを検討してください。ところで、廃止された GCC MELT （&を実装するように設計しました）の内部も見てください。質問。 ドラゴンブックを読んでください。参考のためにこのドラフトレポート、 RefPerSys プロジェクトおよび多くのソースコードも参照してください。その他のオープンソースプロジェクト（ Ocaml または または SBCL または Jq ）例としてffb008b8ea “>
github または gitlab 。
コメント
- I ‘は、ソーステキストを解析してJSの配列に変換するLuaインタープリターを作成しています。 ASTと見なしてもいいですか？ ‘次のようなことをすることになっています：
--My comment #1 print("Hello, ".."world.")は `[{“タイプ”：”-“、” content “：”私のコメント＃1 “}、{” type “：” call “、 ” name “：” print “、”引数”：[[{” type “：” str “、”アクション”：” .. “、”コンテンツ”：”こんにちは、”}、{” type “：” str “、” content “：” world。”}]]}] `JSでは、JSよりもはるかに簡単だと思います’その他の言語！ - @TheProHandsこれは、ASTではなくトークンと見なされます。
回答
この質問は4年以上前のものですが、もっと詳細な回答を追加する必要があると思います。
抽象的な構文ツリーは他のツリーと同じように作成されます。この場合のより正確なステートメントは、構文ツリーノードには必要に応じて可変個引数のノードがあるということです。
例は、1 + 2のような単純な式です。これにより、数値に関するデータを保持する左右のノードを保持する単一のルートノードが作成されます。C言語では、「次のようになります
struct ASTNode; union SyntaxNode { int64_t llVal; uint64_t ullVal; struct { struct ASTNode *left, *right; } BinaryExpr; }; enum SyntaxNodeType { AST_IntVal, AST_Add, AST_Sub, AST_Mul, AST_Div, AST_Mod, }; struct ASTNode { union SyntaxNode *Data; enum SyntaxNodeType Type; }; 質問はトラバースの方法でもありましたか？この場合のトラバースは ノードへのアクセス 。各ノードにアクセスするには、各ノードタイプを使用して、各構文ノードのデータを評価する方法を決定する必要があります。
これは、各ノードのコンテンツを単純に出力するCの別の例です。
void AST_PrintNode(const ASTNode *node) { if( !node ) return; char *opername = NULL; switch( node->Type ) { case AST_IntVal: printf("AST Integer Literal - %lli\n", node->Data->llVal); break; case AST_Add: if( !opername ) opername = "+"; case AST_Sub: if( !opername ) opername = "-"; case AST_Mul: if( !opername ) opername = "*"; case AST_Div: if( !opername ) opername = "/"; case AST_Mod: if( !opername ) opername = "%"; printf("AST Binary Expr - Oper: \"%s\" Left:\"%p\" | Right:\"%p\"\n", opername, node->Data->BinaryExpr.left, node->Data->BinaryExpr.right); AST_PrintNode(node->Data->BinaryExpr.left); // NOTE: Recursively Visit each node. AST_PrintNode(node->Data->BinaryExpr.right); break; } } 関数が再帰的にアクセスする方法に注意してください。扱っているノードのタイプに応じて、各ノード。
より複雑な例、ifステートメント構文を追加しましょう！ifステートメントを思い出してください。オプションのelse句を含めることもできます。元のノード構造にif-elseステートメントを追加しましょう。 ifステートメント自体もifステートメントを持つことができるため、ノードシステム内で一種の再帰が発生する可能性があることに注意してください。その他のステートメントはオプションであるため、elsestmtフィールドをNULLにすることができます。これは、再帰ビジター関数が無視できます。
struct ASTNode; union SyntaxNode { int64_t llVal; uint64_t ullVal; struct { struct ASTNode *left, *right; } BinaryExpr; struct { struct ASTNode *expr, *stmt, *elsestmt; } IfStmt; }; enum SyntaxNodeType { AST_IntVal, AST_Add, AST_Sub, AST_Mul, AST_Div, AST_Mod, AST_IfStmt, AST_ElseStmt, AST_Stmt }; struct ASTNode { union SyntaxNode *Data; enum SyntaxNodeType Type; }; back AST_PrintNodeと呼ばれるノードビジターの印刷関数では、次のCコードを追加することで、ifステートメントのAST構造に対応できます。
case AST_IfStmt: puts("AST If Statement\n"); AST_PrintNode(node->Data->IfStmt.expr); AST_PrintNode(node->Data->IfStmt.stmt); AST_PrintNode(node->Data->IfStmt.elsestmt); break; それと同じくらい簡単です！結論として、構文木は、ツリーとそのデータ自体のタグ付き共用体のツリーにすぎません！