抽象構文木

抽象構文木( AST )は、コンピュータ サイエンスでプログラムまたはコード スニペットの構造を表すために使用されるデータ構造です。これは、形式言語で記述されたテキスト (多くの場合、ソース コード)の抽象的な構文構造をツリーで表現したものです。ツリーの各ノードは、テキスト内に出現する構成要素を表します。単に構文木と呼ばれることもあります。

構文は、実際の構文に現れるすべての詳細を表すのではなく、構造またはコンテンツ関連の詳細だけを表すという意味で「抽象的」です。たとえば、グループ化括弧はツリー構造に暗黙的に含まれているため、これらを個別のノードとして表す必要はありません。同様に、if-condition-then ステートメントのような構文構造は、3 つのブランチを持つ単一のノードによって表される場合があります。

これは、抽象構文木を、従来は構文解析木と呼ばれていた具体的な構文木と区別するものです。構文解析木は通常、ソース コードの変換およびコンパイルプロセス中にパーサーによって構築されます。構築されると、後続の処理 (コンテキスト分析など) によって AST に追加情報が追加されます。

抽象構文木は、プログラム分析やプログラム変換システムでも使用されます。

抽象構文木は、プログラム コードの構造を表すためにコンパイラで広く使用されているデータ構造です。AST は通常、コンパイラの構文解析フェーズの結果です。多くの場合、コンパイラが必要とするいくつかの段階を経るプログラムの中間表現として機能し、コンパイラの最終出力に大きな影響を与えます。

AST には、コンパイル プロセスの以降の手順を支援するいくつかのプロパティがあります。

• AST は、含まれるすべての要素のプロパティや注釈などの情報を使用して編集および拡張できます。このような編集や注釈は、プログラムのソース コードを変更することになるため、不可能です。
• ソース コードと比較すると、AST には不必要な句読点や区切り文字 (中括弧、セミコロン、括弧など) が含まれません。
• AST には通常、コンパイラによる連続的な分析段階のため、プログラムに関する追加情報が含まれます。たとえば、ソース コード内の各要素の位置を保存して、コンパイラが有用なエラー メッセージを出力できるようにします。

言語は、その性質上、曖昧であることが多いです。この曖昧さを避けるために、プログラミング言語は文脈自由文法(CFG) として指定されることが多いです。しかし、プログラミング言語には、CFG では表現できないものの、言語の一部であり、仕様で文書化されている側面がしばしばあります。これらは、その妥当性と動作を決定するためにコンテキストを必要とする詳細です。たとえば、言語で新しい型の宣言が許可されている場合、CFG はそのような型の名前も使用方法も予測できません。言語に定義済みの型のセットがある場合でも、適切な使用法を強制するには通常、何らかのコンテキストが必要です。別の例としては、要素の型がコンテキストに応じて変化するダックタイピングがあります。演算子のオーバーロードは、正しい使用法と最終的な機能がコンテキストに依存するもう 1 つの例です。

AST の設計は、多くの場合、コンパイラの設計やその期待される機能と密接に関連しています。

コア要件は次のとおりです。

• 変数の型と、ソース コード内の各宣言の場所を保持する必要があります。
• 実行可能ステートメントの順序は明示的に表現され、適切に定義されている必要があります。
• バイナリ演算の左と右のコンポーネントを保存し、正しく識別する必要があります。
• 識別子とそれに割り当てられた値は、代入ステートメント用に保存する必要があります。

これらの要件は、AST のデータ構造を設計するために使用できます。

一部の演算では、加算の 2 つの項など、常に 2 つの要素が必要になります。ただし、コマンド シェルからプログラムに渡される引数リストなど、一部の言語構造では、任意の数の子が必要になります。その結果、そのような言語で記述されたコードを表すために使用される AST は、不明な数の子をすばやく追加できるように十分に柔軟である必要があります。

コンパイラ検証をサポートするには、AST をソース コード形式に解析解除できる必要があります。生成されたソース コードは、再コンパイル時に、外観が元のコードと十分に類似し、実行が同一である必要があります。AST は、コンパイラがプログラムと言語の要素の正しい使用方法をチェックするセマンティック解析中に頻繁に使用されます。コンパイラは、セマンティック解析中に AST に基づいてシンボル テーブルも生成します。ツリーを完全にトラバースすることで、プログラムの正しさを検証できます。

正確さを検証した後、AST はコード生成のベースとして機能します。AST は、コード生成用の 中間表現 (IR) (中間言語と呼ばれることもあります) を生成するためによく使用されます。

AST差分、または略してツリー差分は、2つのAST間の差異のリストを計算することから成ります。^[1]この差異のリストは通常​​、編集スクリプトと呼ばれます。編集スクリプトはコードのASTを直接参照します。たとえば、編集アクションによって、関数を表す新しいASTノードが追加されることがあります。

ASTはコードクローン検出を実行するための強力な抽象化です。^[2]

• 抽象意味グラフ（ASG）、用語グラフとも呼ばれる
• 複合パターン
• 制御フローグラフ
• 有向非巡回グラフ(DAG)
• ドキュメント オブジェクト モデル(DOM)
• 式ツリー
• 拡張バッカス・ナウア形式
• Lisp は、コードツリーを操作するマクロを備えたツリーで記述された言語ファミリーです。
• 構文木、または具象構文木とも呼ばれる
• セマンティック解決ツリー(SRT)
• 操車場アルゴリズム
• シンボルテーブル
• ツリーDL
• 抽象構文木インタープリタ

• ジョーンズ、ジョエル。「抽象構文ツリー実装イディオム」(PDF)。(さまざまな言語ファミリーにおける AST 実装の概要)
• Neamtiu, Iulian; Foster, Jeffrey S.; Hicks, Michael (2005 年 5 月 17 日)。抽象構文木マッチングを使用したソース コード進化の理解。MSR'05。ミズーリ州セントルイス: ACM。CiteSeerX  10.1.1.88.5815。
• Würsch, Michael. 抽象構文木に基づくソースコード変更検出の改善 (卒業論文)。
• Lucas, Jason (2006 年 8 月 16 日)。「Visual C++ 抽象構文ツリー (AST) に関する考察」。

ウィキメディア・コモンズには、抽象構文木に関連するメディアがあります。

• AST View: Java抽象構文木を視覚化するEclipseプラグイン
• 「Eclipse IDE での抽象構文ツリーと Java コード操作」。eclipse.org。
• 「CAST 表現」。cs.utah.edu。
• eli プロジェクト: 抽象構文木の解析
• 「アーキテクチャ主導のモダナイゼーション - ADM: 抽象構文ツリー メタモデリング - ASTM」。( OMG標準)。
• JavaParser: JavaParser ライブラリは、Java コードの抽象構文ツリーを提供します。AST 構造により、Java コードを簡単にプログラムで操作できるようになります。
• Spoon: Java ソース コードを分析、変換、書き換え、トランスパイルするライブラリ。ソース ファイルを解析して、強力な分析および変換 API を備えた適切に設計された AST を構築します。
• AST Explorer: Go、Python、Java、JavaScript などのいくつかの一般的な言語で AST を視覚化するのに役立つ Web サイト。