抽象構文木
プログラムの構造を表す木。 AST。 構文解析の出力であり、 以降の処理の共通の土台になる。
具象構文木との違い#
具象構文木（解析木）は文法規則をそのまま反映するので、 括弧や区切り記号のノードまで含む。
AST は意味に必要な情報だけを残す。
(1 + 2) * 3
↓ AST
*
/ + 3
/ 1 2括弧は木の形として表現されるので、ノードとしては消える。
なぜ木なのか#
プログラムの構造が再帰的だから。
- 式の中に式がある
- 文の中にブロックがあり、ブロックの中に文がある
再帰的なデータには再帰的な処理が自然に書ける。 AST を辿る処理は Visitor パターンや パターンマッチで簡潔に書ける。
何に使うか#
| 用途 | 例 |
|---|---|
| 意味解析 | 型検査、変数の解決 |
| 最適化 | 定数畳み込み、不要コード削除 |
| コード生成 | 木を辿って命令を出す |
| フォーマッタ | AST から整形して出力（Prettier） |
| リンタ | 特定のパターンを検出（ESLint） |
| トランスパイラ | 別の言語の AST に変換（Babel、TypeScript） |
ソースコードを機械的に扱う道具は、ほぼすべて AST を経由する。 文字列の正規表現でコードを書き換えるのが脆いのは、 構造を無視しているため。
中間表現へ#
最適化を本格的に行う段階では、 AST よりさらに単純化した中間表現に落とす （LLVM IR、SSA 形式など）。 木より制御フローグラフの方が解析しやすいため。
参考文献#
- Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools, 2nd ed. Pearson, 2006.
- Robert Nystrom. Crafting Interpreters. Genever Benning, 2021.（全文公開） https://craftinginterpreters.com/
- Daniel P. Friedman, Mitchell Wand. Essentials of Programming Languages, 3rd ed. MIT Press, 2008.