- 抽象構文木（AST）は、プログラムの論理構造を表し、無関係な構文上の詳細を排除する。
- ASTは、アリティ関数と、どのノードと構造が有効かを定義するツリー文法を備えたアルファベットから構築されます。
- デューイ記法や「.」や「/」などの演算子を使用すると、これらの構造内のサブツリーやパスを正確に参照できます。
- コンパイラ、インタプリタ、およびコード解析ツールは、プログラムを確実に最適化、変換、および理解するためにASTに依存している。
プログラミングにおける抽象構文木は、最初は非常に理論的に聞こえる概念の一つですが、一度理解すれば、コンパイラ、インタプリタ、コード解析、リファクタリングツール、さらには構造化データクエリ言語など、あらゆる場面で使われていることに気づくでしょう。つまり、抽象構文木は、機械がプレーンテキストを超えてプログラムの構造を「理解」する方法なのです。
抽象構文木（AST）は、古典的な構文解析木と混同されることがありますが、独自のルールを持っています。抽象構文木は単なる美しい図ではなく、具体的な構文から不要なもの（括弧、カンマ、冗長なキーワードなど）をすべて排除し、どのような操作が、どのような値に対して、どのような順序で実行されるかといった本質的な要素に焦点を当てた、コンパクトで適切に設計されたデータ構造です。
抽象構文木（AST）とは一体何でしょうか？
プログラミング言語理論において、抽象構文木（AST）は、プログラムの構文を表す木構造ですが、具体的な構文解析木に比べて簡略化された形で表現されます。構文解析木と同じ重要な情報を含みますが、よりコンパクトで扱いやすい形で整理されています。
構文解析木には、文法のすべての生成規則と、括弧、コンマ、セミコロンなどの純粋に構文的な要素を含むすべての終端記号が含まれます。一方、ASTは、意味に寄与しないこれらの詳細を取り除き、式や文の論理構造のみを保持します。
実装面では、ASTは通常、それがどのような構文構造であるかを示す型（定数、識別子、関数適用、二項演算子など）を持つノードオブジェクトと、その内容を記述する追加のプロパティ（値、名前、子ノード、引数リストなど）で構成されます。
ASTの利点は、構文上のノイズのない、プログラム構造の明確なビューを提供するため、型チェック、最適化、コード生成など、コンパイラやインタプリタの後続の段階を容易にすることです。
具体的な構文木と抽象的な構文木の違い
ASTが何に貢献しているかを完全に理解するには、まず具体的な構文解析木と抽象的な構文解析木を比較すると役立ちます。 「a + 4 * 5」のような算術式を認識する単純な文法を想像してみてください。具体的な構文解析木は、非終端記号、終端記号、括弧、演算子など、各文法規則の適用を正確に反映します。
このツリーは通常、非常に深く、文法の形式的な構造を維持するためだけに存在する中間ノードが多数存在します。例えば、「式」、「項」、「因子」といったノードに加え、「+」、「*」、識別子、数値などの終端記号が存在する場合があります。各生成規則はツリーの枝となり、構造的な複雑さを増していきます。
一方、同じ式の抽象構文木は、実際の演算とオペランドを表すことに限定されます。したがって、「式」と「項」の複数のレベルの代わりに、加算を表すルートノードと、その子ノードとして、左側に識別子a、右側に乗算ノード（その子ノードは値 4 と 5）を持つことができます。純粋に文法的なノードは消え、構造の一部が再編成または圧縮されます。
これは、ASTと具体的な構文木が同じ意味情報を含んでいるものの、ASTの方がはるかに直接的かつ簡潔な形でそれを表現していることを意味します。この凝縮は、分析ツールや実行ツールでコードを効率的に扱う上で非常に重要です。
アリティ関数を持つ木構造とアルファベット
これらのツリーを数学的な観点から形式化するために、通常はアリティ関数を持つアルファベットの概念が用いられます。単なる記号の集合ではなく、各記号がツリー内で持つことができる子の数を示す数値に関連付けられたアルファベットが定義されます。
アリティ関数を持つアルファベットとは、非公式には、有限個の記号の集合と、各記号に自然数（0を含む）を割り当てる関数からなるペアのことです。この数値は記号のアリティを示します。0の場合は葉、1の場合は単項ノード、2の場合は二項ノードとして扱われます。また、演算子の引数リストとして可変アリティの記号を許容することも一般的です。
引数数が 0 のシンボルは、ツリーの葉（定数や識別子など）に対応します。引数数が 1 のシンボルは、単一の子式を含む構造に使用されます。引数数が 2 のシンボルは、加算、乗算、代入などの古典的な二項演算を表します。また、引数数が可変のシンボルを使用すると、複数の引数を持つ関数呼び出しなど、不定数のサブツリーを受け入れる構造をモデル化できます。
このアリティを持つアルファベットから、考えられるすべてのツリーの集合を定義できます。まず、空のツリー（考慮する場合）から始め、アリティが0で可変のすべてのシンボルを追加し、帰納的に拡張します。シンボルがk項である場合、既に構築されているk個のサブツリーの親ノードとして配置できます。これにより、アルファベットに関連付けられたツリー言語（または用語）が得られます。
ツリー言語とノードの概念
アルファベットとそのアリティ関数によって形成されるすべての木の集合は、この文脈では木言語または項言語と呼ばれます。これは、文字列におけるクリーネ閉包に相当するものですが、木構造に関するものです。
文字列を解析する際に、シーケンス内のアルファベット記号の出現をトークンと呼ぶのと同様に、ツリーを扱う際には通常ノードという用語を用います。ノードとは、基本的に、ツリー内の特定の位置にある、アリティを持つアルファベット記号の特定の出現のことです。
この観点から見ると、このツリー言語はノードにとって、文字列の集合がトークンの出現にとっての存在と同じである。各ツリーはアルファベットから段階的に構築された構造として解釈され、ノードはそのシンボルを物理的に具現化する個々の要素である。
この考え方は、パーサーやASTジェネレータを設計する際に非常に役立ちます。なぜなら、文字列文法に似た方法でこれらのツリーの構築規則について推論できるだけでなく、階層構造を直接扱うことができるからです。
特定の抽象構文木におけるノードのアリティ：Eggの場合
理論から実践的な例に移ると、多くの教材ではASTの構築と操作を説明するためにEgg言語が用いられています。この文脈では、いくつかの主要なノードタイプが使用され、それぞれに明確なアリティが定義されているため、非常に簡単に操作できます。
一般的な Egg AST では、 VALUEノードはリーフノードとみなされます。VALUE ノードは文字列や数値などのリテラルを表します。子ノードはなく、値のみを格納します。同様に、識別子（変数名、関数名など）に使用される WORD ノードも、名前を格納するプロパティを持つリーフノードとして扱われます。
Eggにおける重要なノードはAPPLY型であり、これは関数または演算子の適用を表します。このノード型には、概念的に2つの子ノードがあります。1つは適用される式を指すOPERATOR子ノード、もう1つはARGS子ノードです。ARGS子ノードは実際には特別なARRAYノードであり、引数ごとに1つのサブツリーのコレクションを維持する役割を担っています。
したがって、配列はASTに可変引数を導入する自然な方法です。APPLYは常に2つの要素（演算子と引数リスト）を持ちますが、その内部リストには、表現される特定の呼び出しに応じて、0個、1個、または多数のサブツリーが含まれる可能性があります。
卵におけるASTリンパ節の詳細な解剖図
実装レベルでは、EggのASTノードは通常、プロパティを持つオブジェクトとして表現され、JavaScriptなどの言語と完全に適合します。すべてのノードは共通のプロパティ`type`を共有しており、これはノードのタイプ（VALUE、WORD、APPLY、ARRAYなど）を識別し、したがって、オブジェクトの残りの部分が持つ構造を決定します。
VALUEノードは、リテラル定数に使用されます。VALUEノードには、多くの場合「value」と呼ばれるプロパティがあり、そこに表現する数値または文字列が格納されます。VALUEノードの内容はリテラルによって完全に記述されるため、子ノードは存在しません。
ワードノードは、変数名、関数名、パラメータ名などの識別子用に予約されています。通常、ワードノードには、識別子を文字列として格納する`name`プロパティがあります。VALUEノードと同様に、ワードノードはツリーの葉ノードとして機能し、その名前を提供することのみを目的としています。
適用ノードは、アプリケーションまたは呼び出しを表します。適用ノードには、適用される式（別のノード）を指す演算子プロパティと、ARRAYノードにリンクするargsプロパティが含まれます。ARRAYノードはAST内の特定のノードであり、アプリケーションの引数リストを保持することを目的としています。
ARRAYノードは、他のノードを格納する構造化されたコンテナとして理解でき、サブツリーのシーケンスを表します。引数の数という観点から見ると、メインノードタイプの定義を変更することなく、同じAPPLYステートメント内で引数なし、引数1つ、または引数複数での呼び出しを可能にするため、柔軟性が向上します。
ASTの例：1つの値を持つシンプルなアプリケーション
上記すべてを視覚化するために、単一の引数5を持つ関数Xの適用など、単純な命令の表現について考えてみましょう。パーサーによって生成されるASTは、 Eggのルールに従ってVALUE、WORD、APPLYノードで構成された項に対応します。
概念的には、ルートにAPPLYノードを配置します。そのoperatorプロパティはXという名前のWORDノードを指し、argsプロパティは単一の要素（数値5を持つVALUEノード）を含むARRAYノードを参照します。このようにして、誰に、そして何に適用されるのかが構造上明確に示されます。
すべての属性を明示的に記述したい場合は、型、演算子、引数、名前、値を示すより詳細な表記法を用いることができます。この冗長な表記法は、パーサーのデバッグや、テキスト式がインタプリタ内でどのようにツリーオブジェクトに変換されるかを理解する際に非常に役立ちます。
実際のシステム実装では、このツリーは通常、保存、送信、または検査を容易にするためにJSON形式でシリアル化されます。実際、 npmエコシステム内のevm2termパッケージなどのツールやモジュールは、これらのASTを分析や変換を容易にするためのコンパクトな表現を提供します。
ASTの例：入れ子になった加算と乗算
もう1つの典型的な例は、 "+(a, *(4, 5))"のような、やや複雑な式です。ここでは、最初の引数が識別子 a であり、2 番目の引数が 4 と 5 の乗算結果である加算演算があります。この式から得られる AST は、その入れ子構造を反映しています。
ツリーのルートには、加算演算を表すAPPLYノードが再び配置されます。その演算子は「+」という名前のWORDノードであり、引数は2つの要素を持つARRAYノードに格納されます。1つ目は「a」という名前のWORDノード、2つ目は乗算を表す別のAPPLYノードです。
その 2 番目の APPLY の演算子は "*" という名前の WORD であり、引数には 2 つの VALUE ノードを持つ ARRAY があります。1 つのノードの値は 4、もう 1 つのノードの値は 5 です。構造全体を見ると、評価の順序は 4 に 5 を掛けてから、その結果を a に加えることであることが明確にわかります。
表記法を拡張してすべての属性を含めると、すべてのノードの型、名前または具体的な値、およびノード間の関係がわかります。この明示的な記述は、 Eggインタープリタにおける実際の実装に対応しており、各ノードは前述のプロパティを持つオブジェクトです。
ツリー文法とパーサー文法
これらの抽象構文木（AST）が生成される方法は恣意的なものではなく、ツリー文法と呼ばれるものに基づいています。典型的な定式化では、このような文法は、アリティを持つアルファベット、有限個の構文変数（非終端記号）、有限個の生成規則、および開始記号からなる四つ組として定義されます。
各生成規則において、変数は、根がアリティを持つアルファベットの記号であり、子が変数または既に定義された木である木に置き換えられます。この構造は、古典的な正規文法や文脈自由文法を彷彿とさせますが、記号列ではなく木を直接生成するように調整されています。
より正式な定義に関連して、Eggのパーサーがツリーを生成するために使用する具体的な文法があります。この文法は通常、ドキュメントで非公式に説明されていますが、キーワード、演算子、括弧などのどの組み合わせが言語で受け入れられるか、そしてそれらがVALUE、WORD、APPLY、ARRAY型のノードにどのように変換されるかを正確に記述しています。
このツリー文法は、文献で「正規ツリー文法」として知られているものの特殊なケースと見なすことができます。その基本的な考え方は、入力トークンのシーケンスを、解釈またはコンパイル可能な構造化された抽象構文木（AST）に変換するための明確な規則を用意することです。
デューイ記法：ツリー内の座標
抽象構文木（AST）を取得したら、関数の2番目の引数や式の演算子など、特定のサブツリーを参照する必要が生じることがよくあります。これを実現する非常に洗練された方法が、いわゆるデューイ十進分類法です。これは、文書のセクションやサブセクションに番号を付ける際に用いられる方式を借用したものです。
この表記法では、木 t から始めて、部分木はピリオドで区切られた数字の列で表されます。各数字は子の位置（通常は 1 から始まる）を示し、このシーケンスは木を下方向に進みながら続きます。したがって、t/2.1.3 のような式は、t の 2 番目の子の最初の子の 3 番目の子を指します。
この表記法の帰納的定義は単純です。空の文字列はツリー全体を指します。文字列が数字と、ピリオドで区切られた複数の数字から構成されている場合、まず指定されたインデックスに対応する子サブツリーを取得し、次に同じロジックを文字列の残りの部分に再帰的に適用することによって解釈されます。
例えば、加算を表すルートノードAPPLY、子ノード「+」、乗算を表す別の子ノードAPPLYを持つ「+(a, *(4,5))」のような式を表すツリーtがあるとします。この場合、特定の位置を特定できます。子ノードに適切な番号を付けると、t/1は演算子「+」を持つWORDノード、t/2.1は識別子「a」、t/2.2.2.1は値4を持つVALUEノードとなります。
AST内で「座標」を指定するこの方法は、エラーを報告する際、ツリーをナビゲートする際、または特定のノードにローカル変換を曖昧さなく適用する際に、特定の場所を指摘するのに非常に役立ちます。
プログラミングとツールにおける同等の表記法
デューイの記法の背後にある考え方は、ツリー理論に限ったものではありません。実際、私たちがプログラミングや構造化データ処理で日常的に使用する多くの実用的な記法に繰り返し現れており、たとえ私たちが常にそれに気づいているわけではないとしても、その考え方は共通しています。
プログラミング言語でドット演算子を使って式を記述する場合（例えば object.property.subproperty のように）、実際には非常に似たようなことを行っています。つまり、ネストされたオブジェクトのツリーをたどり、各ステップで位置番号ではなく名前で子要素を選択するのです。ルートノードから始めて、より内部のノードへと降りていきます。
同様のパターンはUnix系ファイルシステムにも見られ、スラッシュ演算子（/）を使用してディレクトリを区切ります。/src/js/tutu.jsは、ファイルシステムのルートから特定のリソースへのパスを表し、ツリー構造の連続するレベルをたどります。
構造化文書の世界では、XPathのような言語は、XMLツリー内のノードを選択するために非常によく似た表記法を使用します。「A//B/*」のようなクエリは、現在のコンテキストに対して適切な位置にある要素Aの子孫であるすべての要素Bの最初の子（名前は問わない）を選択します。このとき、単一スラッシュと二重スラッシュを使用して深さのレベルを示します。
もう一つのよく知られたツールであるjq言語は、並列システムを使用してJSON構造をナビゲートし、複合パス、フィルタ、および式を通してサブオブジェクトを選択できるようにします。これらの表記法はすべて、ツリー内のパスを表現するさまざまな方法であり、デューイ十進分類法と非常によく似ていますが、それぞれの分野に合わせて調整されています。
言語学とプログラミングにおける構文解析木
コンパイラの世界以外にも、構文木は言語学において文の構造を表すために用いられます。言語学では、構文木は派生木または構文解析木と呼ばれ、文がどのように句、単語、文法カテゴリーに分解されるかを示します。
これらのツリーでは、プログラミングと同様に、3つの基本的なノードタイプが存在します。完全な文または全体構造を表すルートノード、親ノードとして機能し、文のサブセットをグループ化する内部ノードまたは分岐ノード、そして通常は入力文字列に現れる特定の単語に対応するリーフノードです。
ルートノードは唯一無二の存在であり、ツリー構造全体がそこから派生します。分岐ノードはルートノードまたは他の親ノードのすぐ下に位置し、文やプログラムの各部分を階層的に整理する役割を果たします。一方、リーフノードはツリーの最下層に位置し、子ノードを持たないため、分岐構造が閉じられます。
これらのツリーは、複雑な文を扱いやすい要素に分解するのに役立つため、強力な教育ツールと考えられています。プログラミングにも同じことが言えます。適切に構築された抽象構文木（AST）があれば、どの操作が連鎖しているか、どの式がネストされているか、評価の流れがどのように行われているかを一目で把握できます。
分析の目的に応じて、さまざまな種類の分析ツリーが存在します。単語や構成要素間の依存関係（例えば、文中で誰が誰に依存しているか）を重視するものもあれば、フレーズや構成要素へのグループ化に焦点を当てるものもあり、結果として大きく2つの種類に分けられます。
依存関係と構成要素による構文木
最もよく知られているタイプの1つに、依存関係に基づく構文木があります。この方式では、文中のすべての単語またはすべての関連要素が葉ノードとして扱われ、それらの間のリンクは直接的な依存関係（例えば、主動詞とその主語）を示します。その結果、他の方式よりもノード数の少ない木が生成されることがよくあります。
このシンプルさゆえに、初心者や特定の言語処理タスクにおいて特に便利です。なぜなら、この構造は中間ノードを多数導入することなく、誰が誰に依存しているかに焦点を当てているからです。プログラミングに適用すると、文法的な装飾を省き、本質的な関係性のみに絞るという考え方になります。
その対極にあるのが、構成要素に基づく構文木です。これは、ルートノード、内部分岐ノード、リーフノードを区別し、関連するすべてのグループを可視化します。これらの木は通常、より多くのノードを含み、文やプログラムの階層構造をより詳細に反映します。
一般的に見られる構成要素ツリーのテンプレートは、多数の葉ノード、複数の分岐レベル、そして明確に定義されたルートノードを持つ長い文を表示します。これらは、複雑な文や、複数の階層にネストされた構造を持つプログラムを分析する際に特に役立ちます。
依存関係ツリーと構成関係ツリーの両方において、テンプレートとして例や視覚的なリソースが用意されているため、ノードに必要な情報を入力するだけで済みます。これにより時間を節約でき、構造を図示するたびに図を一から設計する必要がなくなります。
ASTに関連する実用的なアプリケーションとツール
ASTは単なる理論上の概念ではなく、コードを扱うあらゆる人が日常的に使用する数多くのツールで実際に活用されています。コンパイラ、インタプリタ、ミニファイア、コードフォーマッタ、静的解析ツールなどは、その機能を果たすためにほぼ必ずASTに依存しています。
一般的なコンパイラは、ソースコードを受け取り、トークン化、構文解析を行い、抽象構文木を生成します。そこから、意味チェック（型、変数スコープ、構文構造の不適切な使用など）を実行し、ASTを走査および変換することでコード最適化を行い、機械語（バイトコード）を生成します。
リンターやフォーマッターなどのツールもAST（抽象構文木）に対して機能します。これらのツールは構造を分析して問題のあるパターン、不適切な慣習、または矛盾を検出し、ツリーのセマンティック構造を維持しつつコードの表現を調整する変更を提案します。
例えば、JavaScriptのエコシステムでは、ASTをJSON形式で公開するライブラリが複数存在し、他のツールがそれを利用してリファクタリングを実行したり、自動ドキュメントを生成したり、複雑なプログラムの構造を視覚化したりすることが容易になっている。
テストカバレッジを測定するための計測機器や、ソースコードを他の言語に変換するといった、やや専門的な分野においても、ASTは多くの現代的なソリューションの基盤となっています。なぜなら、ASTを用いることで、生のテキストと機械語の間で非常に快適な抽象度レベルで作業できるからです。
要約すると、抽象構文木は、言語の形式文法、コンパイラやインタプリタにおける内部表現、そしてコードを安全かつ効率的に記述、分析、変換するために使用する高度なツールを結びつける重要な要素です。構文木がどのように構築されているか、デューイ十進分類法などの概念を用いてどのようにナビゲートするか、そしてどのような種類のノード（VALUE、WORD、APPLY、固定または可変のアリティ構造など）が関わっているかを理解することで、プログラム処理時にマシンが実際に行っていることをより明確に把握することができます。
