抽象構文木(AST)と中間表現(IR)の設計

なぜ「木」と「中間表現」を分けるのか

ソースコードを機械語へ落とす過程は、一足飛びには行えません。コンパイラは目的の異なる複数の内部表現を経由します。最初に作られるのが**抽象構文木（AST）で、プログラムの文法構造を木として持ちます。続いて、最適化やコード生成に都合のよい中間表現（IR）**へと「下げて（lowering）」いきます。

なぜ分けるのか。理由は、解析に向く形と最適化・実行に向く形が違うからです。ASTは入れ子構造をそのまま表すので型検査やスコープ解決はやりやすい一方、ループや分岐をまたいだ最適化は木のままだと扱いにくい。逆に三番地コードのような線形なIRは制御フローを明示でき、データフロー解析に向きます。1つの表現で全工程を賄おうとすると、どの工程も中途半端になります。

ソース → [字句解析] → トークン列 → [構文解析] → AST
      → [意味解析] → 注釈付きAST → [lowering] → IR(三番地/SSA/バイトコード)
      → [最適化] → IR → [コード生成] → 機械語

この段階の全体像はコンパイルとインタプリタの枠組みの内側にあたります。本稿では、その「内側」で起きる変換を構造から見ていきます。

字句・構文解析からASTへ

最初の工程は字句解析（lexing）です。文字の並びを、意味の最小単位であるトークンへ切り分けます。a = b + 1 は識別子a、代入=、識別子b、演算子+、数値1という列になります。空白やコメントはここで捨てられます。

次の構文解析（parsing）で、トークン列を文法規則に照らして木に組み上げます。重要なのは、AST が具象構文木（CST／parse tree）とは別物だという点です。CST は括弧やセミコロンなど文法上の全記号を残しますが、AST は意味に効かない記号を落とし、構造だけを残します。a = b + 1 の AST は次のようになります。

Assign
├─ target: Var(a)
└─ value: BinOp(+)
         ├─ Var(b)
         └─ Int(1)

演算子の優先順位や結合規則は、この木の形そのものとして表現されます。a + b * c なら*が+より深い位置に来るので、評価順序が木構造に焼き込まれ、後段はもう優先順位を気にしなくてよくなります。式評価の順序がどう決まるかは制御フローの仕組みとも地続きです。

意味解析では、この木に注釈を付けます。各識別子がどの宣言を指すか（名前解決）、各式の型は何か（型推論・型検査）、といった情報を木のノードに結び付けます。型の検査がここで効く点は型システムの話と重なります。

三番地コードへの lowering

注釈付き AST は、まだ入れ子の式を持っています。これを平坦な命令列へ落とすのが**三番地コード（three-address code, TAC）**です。名前の通り、1命令が最大3つのアドレス（2つの入力と1つの出力）しか持たない形に正規化します。

# a = b + c * d を三番地コードへ
t1 = c * d
t2 = b + t1
a  = t2

入れ子の式が、一時変数（t1, t2）を介した直列の命令に分解されました。各命令が単純な代入か二項演算になるので、後段の解析が一様に書けます。制御フローもgotoと条件分岐へ落とします。

# while (i < n) { sum = sum + i; i = i + 1; }
L1: if i < n goto L2
    goto L3
L2: t1  = sum + i
    sum = t1
    t2  = i + 1
    i   = t2
    goto L1
L3:

この命令列を、分岐をまたがない最大の連続区間（基本ブロック）に区切り、ブロック間のジャンプを辺とした有向グラフにしたものが**制御フローグラフ（CFG）**です。CFG はデータフロー解析の土台になります。「この変数はここで定義され、どこで使われるか」を辺に沿って追えるからです。

SSA形式 — 「一度だけ定義」という制約

三番地コードのままでも解析はできますが、同じ変数が何度も上書きされると「いま参照しているのはどの定義か」を毎回たどる必要があり、解析が重くなります。これを根本から解くのが**静的単一代入形式（SSA, Static Single Assignment）**です。

SSA の規則は単純です。各変数は、プログラム全体で正確に一度だけ代入される。 上書きが必要なら、新しい版（x1, x2, ...）を作ります。

# 元のコード
x = 1
x = x + 2
y = x * 3

# SSA形式
x1 = 1
x2 = x1 + 2
y1 = x2 * 3

こうすると、各変数名が「ただ一つの定義」と一対一に対応します。y1の右辺のx2が指す定義は、探さなくても名前から確定します。これが SSA の威力で、定義と使用の対応（use-def 鎖）がグラフを歩かずに引けるようになります。

問題は分岐の合流点です。条件によって異なる定義が流れ込む場合、どちらの版を使うか名前だけでは決められません。これを解くのが**phi関数（φ）**です。

        if cond
        ├─ then: x1 = 10
        └─ else: x2 = 20
合流点:  x3 = φ(x1, x2)   # 直前に通った経路に応じて x1 か x2 を選ぶ
        use x3

phi 関数は「直前にどの辺から合流点へ来たか」に応じて値を選ぶ、概念上の命令です。実コードには現れず、SSA から抜ける際（out-of-SSA）に、各前駆ブロックの末尾へのコピーへ展開されます。phi をどこに最小限で置くかは**支配辺境（dominance frontier）**という概念で決まり、Cytron らのアルゴリズムが標準的に使われます。

三番地コード・SSA・バイトコードの使い分け

IR は1種類ではありません。同じコンパイラが、目的に応じて複数の表現を行き来します。代表的な3形式の性格は次の通りです。

バイトコードは、仮想マシン（VM）が実行する命令列です。多くはスタックマシンを前提とし、a + bは「a を push、b を push、add（2つを pop して和を push）」という列になります。三番地コードが解析の中間生成物なのに対し、バイトコードは配布・実行のための成果物である点が性格の違いです。JVM の class ファイルや Python の .pyc がこれにあたります。

# a + b のスタックマシン向けバイトコード
load  a    # スタックに a を積む
load  b    # スタックに b を積む
add        # 上位2要素を pop し、和を push

実務の処理系では、これらが直線的に並ぶわけではありません。たとえば LLVM は SSA ベースの IR を中核に据え、フロントエンドが各言語の AST からそこへ下げ、最適化パスを SSA 上で回し、最後にバックエンドが対象 CPU の機械語を生成します。一方、JVM は javac が AST からバイトコードを吐き、実行時に JIT がそのバイトコードを再び SSA 風の内部 IR へ持ち上げて最適化します。「上げる（raise）」も「下げる（lower）」も双方向に起こりうるわけです。

まとめ

コンパイラは、解析に向く木（AST）と最適化・実行に向く線形表現（IR）を意図的に分け、ソースを段階的に下げていきます。字句・構文解析でASTを作り、意味解析で型と名前を注釈し、三番地コードへ平坦化して CFG を構築し、SSA で各変数を単一定義に正規化して最適化を高速・正確にし、最終的にバイトコードや機械語を生成します。各段で「何を解析し、何を捨てるか」が決まっており、抽象度を下げるほど高水準の意図は失われます。だからこそ最適化はそれを要する抽象度で行う必要があります。IR を1つに統一せず目的別に使い分けることこそが、現代の処理系が高い最適化品質と可搬性を両立できている理由です。