抽象構文木は、コンパイラでプログラムコードの構造を表現するために広く使われているデータ構造である。 AST は通常、 コンパイラの構文解析フェーズの結果である。 AST はコンパイラが必要とするいくつかの段階を経て、プログラムの中間表現として機能することが多く、コンパイラの最終出力に強い影響を与える。 ソースコードと比較して、AST には不要な句読点や区切り記号 (中括弧、セミコロン、括弧など) が含まれない。
AST は、プログラミング言語とそのドキュメントの固有の性質のために必要とされるものである。 言語は本質的にあいまいなことが多い。 この曖昧さを避けるために、プログラミング言語はしばしば文脈自由文法 (CFG) として指定される。 しかし、プログラミング言語には、CFGでは表現できないが、言語の一部であり、その仕様に文書化されている側面がしばしば存在する。 これらは、その妥当性や振る舞いを決定するために文脈を必要とする詳細である。 例えば、ある言語が新しい型を宣言できるようにした場合、CFGはその型の名前や使い方を予測することはできません。 たとえ言語があらかじめ定義された型の集合を持っていたとしても、適切な使い方を強制するためには、通常、何らかの文脈が必要となる。 また、ダックタイピングのように、文脈によって要素の型が変化することもある。 演算子のオーバーロードも、正しい使い方と最終的な機能が文脈に基づいて決定されるケースである。 Java は優れた例を提供しており、’+’ 演算子は数値の加算と文字列の連結の両方を行います。
コンパイラの内部動作には他のデータ構造もありますが、AST は独自の機能を実行します。 最初の段階である構文解析の段階で、コンパイラは解析木を生成する。 この構文木を使って、構文指向翻訳により、コンパイラのほぼすべての機能を実現することができる。 この方法は、より効率的なコンパイラにつながるが、プログラムを書き、維持するというソフトウェア工学の原則に反するものである。 AST がパースツリーに対して持つもうひとつの利点はサイズ、特に AST の高さが小さく、要素の数が少ないことである。
DesignEdit
AST の設計は、しばしばコンパイラの設計や期待する機能と密接に結びついている。
コア要件には以下のものがある：
- 変数タイプはソースコードにおけるそれぞれの宣言のロケーションと同様に保存されなくてはならない。
- 実行可能なステートメントの順序は明示的に表現され、明確に定義されなければならない。
- バイナリ演算の左および右コンポーネントは保存され、正しく識別されなければならない。
- 識別子とその割り当て値は、割り当てステートメント用に保存されなければならない。
これらの要件は AST 用データ構造の設計に使用できる。 しかし、コマンドシェルからプログラムに渡される引数リストのように、恣意的に多数の子を必要とする言語構成もある。 その結果、そのような言語で書かれたコードを表現するために使われるASTは、未知の数の子を素早く追加できるような柔軟性も持たなければならない。
コンパイラ検証をサポートするには、ASTをソースコード形式にアンパースできることが望ましい。
UsageEdit
ASTは意味解析で集中的に使われ、コンパイラがプログラムと言語の要素の正しい使い方をチェックする。 また、コンパイラは意味解析の際に AST に基づいてシンボルテーブルを生成する。 ツリーの完全な横断によってプログラムの正しさを検証できる。
正しさを検証した後、ASTはコード生成のベースとして機能する。 ASTはしばしばコード生成のための中間表現（IR）、時には中間言語と呼ばれるものを生成するのに使われる。