抽象構文木

抽象構文木（abstract syntax tree、AST）とは、通常の構文木（具象構文木、あるいはparse treeとも言う）から、言語の意味に関係ない情報を取り除き、意味に関係ある情報のみを取り出した（抽象した）木構造のデータ構造である。

理論的には、有限なラベル付き有向木であり、分岐点（internal node）に演算子、葉（leaf node）にそのオペランドを対応させたものである。つまり、葉は変数や定数に対応する。

抽象構文木は構文解析で構文木とデータ構造の中間的なものとして使用される。さらにコンパイラやインタプリタなど（プログラミング言語処理系）でのプログラムの中間表現として使われ、コンパイラ最適化やコード生成はその上で行われる。抽象構文木のとりうる構造は抽象構文で記述されている。

抽象構文木は(具象)構文木とは異なり、プログラムの意味に関係ない部分を省略する。そのような省略の例としては括弧の省略があげられる。抽象構文木では、オペランドのグループ化が自明な木構造とするのが普通であり、グループ化のための括弧などは意味的に不要である。

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

理論的な観点からは、たとえばソースコード上の位置（何行目の何カラム目、etc）といった具象の情報は言語処理系には不要であり、抽象構文木には無くてもよいのだが、実践的には、エラーを見つけた時にプログラマに親切なエラーメッセージを出力するためなど、重要な情報であり、時には処理系のフロントエンドではなくバックエンドでも必要なこともある。

関連項目

• Document Object Model (DOM)
• 操車場アルゴリズム
• シンボルテーブル
• TreeDL
• 形式文法
• 句構造規則

参考文献

この記述は GNU Free Documentation License のもとに公開されているコンピュータ用語辞典『 Free On-line Dictionary of Computing (FOLDOC) 』に基づいています。

外部リンク

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