AST からコードへ

本レッスンは AST を帰りがけ順でたどり、子の後に演算子を書き、一ノードにつき一命令のスタックバイトコードを作る。1 + 2 * 3 で MUL が ADD より先になるのは、乗算が木の深い位置にあるためで、ソース文字を並べ替えたからではない。生成時間はノード数に線形だ。

スタック機械は演算前に二つの値を必要とするので、命令をオペランドの後に置く。IR パネルは生成中のプログラムで、実行時スタックではない。本レッスンは生成し、次で実行する。

AST コード生成の仕組み

構文解析は既にソースを Lit、Name、BinOp ノードへ変えている。生成器は木を読み、後の VM 用コードを追加する。リテラルは LOAD_CONST、名前は LOAD_NAME、加乗算は両部分木を出力してから ADD または MUL を書く。

1 + 2 * 3 と (1 + 2) * 3 は同じ演算と値を使っても木が違うため、異なるプログラムになる。優先順位は解析済みで、生成器は形を読むだけだ。

変換器、式の最適化、VM バックエンドは、定数畳み込みや構文の展開のように、木を変えてから生成する構成を使う。Babel や TypeScript にも木の変換と出力の段階がある。本レッスンの Fold はその分離を示す。

Fold は emit の前に動く。左右の子を折り畳み、両方がリテラルなら二項演算を Lit(eval(op, left, right)) に替える。残った木を同じ生成器へ渡す。1 + 2 * 3 は LOAD_CONST 7 になる。x + 2 * 3 は乗算だけを畳み、名前はリテラルでないため加算を残し、三命令を作る。

AST コード生成のステップ

既定の Naive は +(1, *(2, 3)) を処理し、IR は空から始める。

1. 根 +、左の 1、右の * と子 2、3 を示す。まだ命令はない。
2. 1 へ下り、演算子は待つ。
3. LOAD_CONST 1 を書く。
4. + へ戻る。左側は生成済み。
5. 右部分木 * へ下る。
6. 2 へ下り、* が待つ。
7. LOAD_CONST 2 を書く。
8. * へ戻る。
9. 3 へ下る。
10. LOAD_CONST 3 を書く。
11. * へ戻り、両子が生成済みになる。
12. MUL を書く。ソースは + が先でも、深い * が先に生成される。
13. + へ戻る。
14. ADD を書く。根が最後になる。
15. LOAD_CONST 1, LOAD_CONST 2, LOAD_CONST 3, MUL, ADD の五命令が完成する。

Fold に替えると、葉は既にリテラルなので書き換えず、2 * 3 を 6、1 + 6 を 7 にして、LOAD_CONST 7 だけを出す。x + 2 * 3 なら乗算は畳めても加算は残り、LOAD_NAME x / LOAD_CONST 6 / ADD を生成する。

コードパネルは下降時に emit(node.left)、emit(node.right) を個別に示す。リテラル生成では LOAD_CONST だけを光らせ、LOAD_NAME は同時に光らない。Fold の return Lit(...) と return BinOp(...) も実行された分岐に分けて示す。

MUL が ADD より先になる理由

(1 + 2) * 3 は + が深いため、Naive は ADD、MUL の順に書く。パーサーが別の木を作り、生成器は同じ規則でたどる。

Fold は別の生成器ではない。両方式は emit を共有し、その入力の木だけを変える。子より先に現在ノードを畳もうとすると、既定の + は右にまだ * を見て畳めず、一命令ではなく三命令を残しうる。下から上への処理が、この書き換えの必要条件だ。

時間計算量と空間計算量

n ノードの Naive は O(n) 命令を O(n) 時間で生成する。Fold は O(n) で書き換え、残る k ≤ n ノードを O(k) で出力する。x + y は畳めず k=n。名前はそれに依存する祖先をすべて阻むが、独立したリテラル部分木は畳める。x + 2 * 3 の乗算は畳めるので k<n。線形の書き換えと引き換えに、短いプログラムを得られる可能性がある。補助再帰スタックは木の高さに依存し、IR と木の保存領域は別に必要になる。

境界ケース

• 括弧は木を変え、歩き方は変えない。(1 + 2) * 3 は別のプログラムになる。
• 名前が阻むのは祖先で、他の部分木ではない。(x + 1) * 2 はどちらの二項演算も畳めず、x + 2 * 3 の乗算は畳める。
• 2 * 3 + 4 * 5 は 6 + 20、次に 26 になる。Naive なら七命令。
• 一リテラルの木は一つの LOAD_CONST を出し、待つ演算子はない。
• プリセットは全て根を持ち、空の木を扱わない。空プログラムの入力処理はパーサーの仕事だ。

よくある間違い

• ソース順で ADD を先に出す。実行時に二値がそろわず、スタックがアンダーフローする。
• ソースの整形とコード生成を同じ操作と考える。ソースは + を中間に置き、スタックコードはオペランドの後に置く。
• 上から畳み、子がリテラルになる前に親を判定して多段の定数式を逃す。
• Fold 用に別生成器を作る。emit は共通で、五命令のままなら先に書き換えたかを確認する。
• IR を実行時スタックと読む。ここで並ぶのは作成したプログラムで、実行スタックは次のレッスンだ。

モデルの範囲

IR は LOAD_CONST、LOAD_NAME、ADD、MUL などの教材用スタックコードで、if、ループ、実行時スタック表示はない。実コンパイラーは三番地コードや SSA へ下げ、定数伝播、デッドコード除去、インライン化を行い、機械命令を選んでレジスターを割り当てる場合がある。

本レッスンの対象は式木の帰りがけ順生成と、木を変えた後に生成器を再利用する段階分離だ。完全なコンパイラーは対象機械や制御フローに応じた別の順序付けや表現も使う。