抽象構文木

抽象構文木（ちゅうしょうこうぶんぎ、英: abstract syntax tree、AST）は、通常の構文木（具象構文木あるいは解析木とも言う）から、言語の意味に関係ない情報を取り除き、意味に関係ある情報のみを取り出した（抽象した）木構造の木である。

理論的には、有限なラベル付き有向木である。また、演算子と変数や定数といったオペランドから成る数式などのようなものに対する抽象構文木を例にすると、分枝点は演算子、葉はオペランド（つまり、変数や定数）である。

抽象構文木は、構文解析によって直接得られる具象構文木と、最終的な意味表現などのデータ構造との、中間にあるものと位置付けることができる。コンパイラやインタプリタといったプログラミング言語処理系の場合は、中間表現のひとつであり、一部の最適化は抽象構文木の上の操作などによっておこなわれる。具象に対する構文がたとえばBNFによって規定されるように、抽象構文木についてもそれを規定する抽象構文というものが考えられる（が、あまり意識されることはない）。抽象構文木から例えば、バイトコードインタプリタに渡す場合にはバイトコードに、現代的なコンパイラの場合には静的単一代入形式などの、目的コードに近くより扱いやすい形式に変換（一種のコード生成）がおこなわれる。

抽象構文木は具象構文木とは異なり、プログラムの意味に関係ない部分を省略する。そのような省略の例としては括弧の省略があげられる。抽象構文木では、その自然な木構造によって結合は自明であるから、グループ化のための括弧などは意味的に不要である。変数名などの名前なども、識別できればよいので何らかのIDのようなもので構わない。ただし現実的にはエラーへの対応などが必要なので、シンボルテーブルの逆引きなどによって対応することもある。逆に理論的には、ド・ブラウン・インデックスのようにインデックス値にしてしまえることもある。

抽象構文木は、具象構文木から「抽象して」作られることもあれば、構文解析フェーズで直接いきなり作ってしまうこともある。

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

関連項目

• 操車場アルゴリズム
• シンボルテーブル
• 形式文法
• 句構造規則

参考文献

この記事は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