抽象構文木

ユークリッドの互除法の次のコードの抽象構文木:

b != 0の場合: a > bの場合: a := a - bそれ以外の場合: b := b - a aを返す

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

構文が「抽象的」であるのは、実際の構文に現れるすべての詳細を表すのではなく、構造的または内容に関連する詳細のみを表すという意味です。例えば、グループ化括弧はツリー構造に暗黙的に含まれているため、個別のノードとして表現する必要はありません。同様に、if-condition-then文のような構文構造は、3つの枝を持つ単一のノードで表すことができます。

これは、抽象構文木と、伝統的に構文解析木と呼ばれる具象構文木を区別するものです。構文解析木は通常、ソースコードの翻訳およびコンパイルプロセス中にパーサーによって構築されます。構築された後、文脈解析などの後続処理によって、ASTに追加情報が追加されます。

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

コンパイラへの応用

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

モチベーション

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

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

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

デザイン

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

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

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

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

加算の2つの項のように、一部の演算は常に2つの要素を必要とします。しかし、コマンドシェルからプログラムに渡される引数リストのように、一部の言語構造は任意の数の子要素を必要とします。そのため、そのような言語で記述されたコードを表すASTは、未知の数の子要素を迅速に加算できる柔軟性も備えていなければなりません。

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

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

その他の用途

AST差分

AST差分（略してツリー差分とも呼ばれる）は、2つのAST間の差分リストを計算することで実現されます。^{[ 1 ]}この差分リストは通常​​、編集スクリプトと呼ばれます。編集スクリプトはコードのASTを直接参照します。例えば、編集操作によって関数を表す新しいASTノードが追加されることがあります。

クローン検出

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

意味

アリティーズ

を種類の集合とすると、アリティはタプル （ ）であり、はとも表記されます。より正確には、 です。 ${\displaystyle S}$ ${\displaystyle (s_{1},\dots ,s_{n},s)}$ ${\displaystyle s1,\dots ,s_{n},s\in S}$ ${\displaystyle (s_{1},\dots ,s_{n})s}$ ${\displaystyle \mathrm {Arity} (S):=\coprod _{n\in \mathbb {N} }S^{n+1}}$

を演算子の素集合の -添字付き族とします。が演算子アリティである場合、はソートを持ち、 はソートの引数を持つと言います。 ${\displaystyle {\mathcal {O}}=\{{\mathcal {O_{\alpha }}}\}_{\alpha \in \mathrm {Arity} (S)}}$ ${\displaystyle \mathrm {アリティ} (S)}$ ${\displaystyle o}$ ${\displaystyle (s_{1},\dots ,s_{n})s}$ ${\displaystyle o}$ ${\displaystyle s}$ ${\displaystyle n}$ ${\displaystyle s_{1},\dots ,s_{n}}$

AST

を有限の種類の集合とし、演算子の素集合の -添字族とする。変数の素集合の -添字族とする。抽象構文木（AST ）の族は、以下の条件を満たす最小の-添字族の素集合である。 ${\displaystyle S}$ ${\displaystyle {\mathcal {O}}}$ ${\displaystyle \mathrm {アリティ} (S)}$ ${\displaystyle {\mathcal {X}}=\{{\mathcal {X}}_{s}\}_{s\in S}}$ ${\displaystyle S}$ ${\displaystyle {\mathcal {A}}[{\mathcal {X}}]=\{{\mathcal {A}}[{\mathcal {X}}]_{s}\}_{s\in S}}$ ${\displaystyle S}$

1. 変数は AST です: if 、 then 。${\displaystyle x\in {\mathcal {X}}_{s}}$ ${\displaystyle x\in {\mathcal {A}}[{\mathcal {X}}]_{s}}$
2. 演算子は AST を結合します。が 個の引数を持つ演算子である場合、すべての に対して となります。${\displaystyle o}$ ${\displaystyle (s_{1},\dots ,s_{n})s}$ ${\displaystyle a_{i}\in {\mathcal {A}}[{\mathcal {X}}]_{s_{i}}}$ ${\displaystyle 1\leq i\leq n}$ ${\displaystyle o(a_{1};\dots ;a_{n})\in {\mathcal {A}}[{\mathcal {X}}]_{s}}$

参照

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

参考文献

1. Fluri, Beat; Wursch, Michael; PInzger, Martin; Gall, Harald (2007). 「Change Distilling: Tree Differencing for Fine-Grained Source Code Change Extraction」 . IEEE Transactions on Software Engineering . 33 (11): 725– 743. doi : 10.1109/tse.2007.70731 . ISSN  0098-5589 . S2CID  13659557 .
2. Koschke, Rainer; Falke, Raimar; Frenzel, Pierre (2006). 「抽象構文接尾辞木を用いたクローン検出」 . 2006 第13回リバースエンジニアリングワーキングカンファレンス. IEEE. pp.  253– 262. doi : 10.1109/wcre.2006.18 . ISBN 0-7695-2719-1. S2CID  6985484 .

さらに読む

• ジョーンズ、ジョエル. 「抽象構文木実装イディオム」(PDF) .オリジナル(PDF)から2024年7月21日時点のアーカイブ。 2011年11月9日閲覧。（さまざまな言語ファミリーにおける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) に関する考察」 .
• ロバート・ハーパー（2016年）『プログラミング言語の実践的基礎（第2版）』ケンブリッジ大学出版局。

外部リンク

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