抽象構文木

抽象構文木（abstract syntax tree、AST）とは、計算機科学における有限なラベル付き有向木構造であり、節点（internal node）に演算子、葉（leaf node）にそのオペランドを対応させたものである。つまり、葉は変数や定数に対応する。抽象構文木は構文解析で構文木とデータ構造の中間的なものとして使用される。さらにコンパイラやインタプリタでのプログラムの内部表現として使われ、コンパイラ最適化やコード生成はその上で行われる。抽象構文木のとりうる構造は抽象構文で記述されている。抽象構文木は構文木とは異なり、プログラムの意味に関係ない部分を省略する。そのような省略の例としては括弧の省略があげられる。抽象構文木では木構造上、オペランドのグループ化は自明であり、グループ化のための括弧などは意味論的に不要である。

大多数のプログラミング言語のような文脈自由言語の構文解析で抽象構文木を作るのは簡単である。文法規則ごとに新たな節点を作成し、葉はその規則における記号に対応する。グループ化規則のような抽象構文木に関わらない規則は無視される。構文解析では完全な構文木を作り、その後そこから冗長な部分（プログラムの意味に関係しない部分）を除いて抽象構文木に変換する。

関連項目

• Document Object Model (DOM)
• 操車場アルゴリズム
• シンボルテーブル
• TreeDL

参考文献

この記事は2008年11月1日以前にFree On-line Dictionary of Computingから取得した項目の資料を元に、GFDL バージョン1.3以降の「RELICENSING」(再ライセンス) 条件に基づいて組み込まれている。

外部リンク

• Citations from CiteSeer
• AST View Eclipse用Javaプラグイン
• Good information about the Eclipse AST and Java Code Manipulation
• 1-5 構文解析2