発展課題

通常回（コマ1〜15）を終えた人向けの発展課題を置く。ここが発展教材の入口である。

いずれも選択制で、1トピック = 1ディレクトリになっている。 advanced/<回ID>_<内容>/ の形で、README.md・スケルトン・check.py（および多くは golden.py）が そのディレクトリの中に閉じている（P1 のみ例外: 自動採点なしの方針資料）。資料は サイトの発展課題 にある。

回 ID の頭文字がカテゴリを表す。

全トピック一覧

どこから始めるか

共通のルール

• mycc.py と scaffold/ は書き換えない。機能はラッパー、独立したパス、またはパッチとして差し込む
• fixed17 が通り続けることを、意味を壊していないことの基準にする
• 完了条件は各トピックの README.md とサイトの資料に書いてある

fixed17 とは

workbook/final/tests/ に置いてある17本のテストのこと。 コマ1〜15 で作った機能を通しで確認する参考テストで、標準トラック完成の目安として コマ15（通常回15）で導入する。 内訳は docs/testing.md と docs/code_example.md の一覧にある。

発展課題では、これを安全網として使う。 どのトピックも既存の機能を壊さずに何かを足す／直すので、 「fixed17 が全通したままか」が「意味を壊していないか」の判定になる。

# workbook/ から。--compiler にそのトピックのラッパーを渡す
python3 scaffold/test_runner.py --compiler advanced/L1_ptrdiff/langcc.py --tests final/tests

check.py と golden.py

各トピックのテストは、目的の違う2本に分かれている。

先に check.py を全 PASS にしてから golden.py を回す、という順で使う。

golden.py が無いトピックもある。F0（コンパイラ本編と独立）、 R1・R2・R3（mycc.py の出力を変えないので回帰の対象が無い）、 P1（自動採点なし）の5本がそれで、check.py だけで完結する。

共有ツール

ラッパーの名前

mycc.py を書き換えないトピックでは、ラッパーが mycc.py を読み込んで 必要な差し替えを施す。名前はファミリごとに決まっている。

F・R・P はラッパーを使わない（F は scaffold/ の部品を自作で置き換え、 R は生成物のリンク方法を変え、P は移植そのものが課題であるため）。

環境変数の名前

土台のコンパイラと差し込むファイルの置き場所は、環境変数で差し替えられる。 名前は例外なく次の規則に従う。

接頭辞 = ラッパーのファイル名から .py を取って大文字にしたもの。 langcc.py なら LANGCC_、optcc.py なら OPTCC_。

ラッパーを持たない R 系列だけは例外で、回 ID を接頭辞にする （R1_COMPILER / R2_COMPILER / R3_COMPILER）。

注意: 2026-08-01 に、この規則へそろえる形でいくつかの名前を改名した。 環境変数名（optcc.py・foldcc.py・L3 のラッパー）とファイル名（L3 の varcc.py）が対象である。 あわせて、ファミリを移した2本（S3_ptrdiff/ → L1_ptrdiff/、L1_struct/ → S3_struct/）の ラッパーも semcc.py と langcc.py が入れ替わり、環境変数の接頭辞も入れ替わった。 旧名はエラーにならず黙って無視されるので、以前の名前を書いた手元のスクリプトやメモが あれば読み替えること。

workbook/advanced/ から実行する。

python3 ../final/mycc.py foo.c | python3 count_insns.py

F: フロントエンド

スキャフォールドでブラックボックスとして使ってきた Lexer / Parser を、自分の手で理解し、作り、置き換える。

• F0 は独立した導入回。コンパイラ本編とは無関係で、前提はコマ1 まで
• F1 以降は積み上げ式（F1 → F2 → F3 → F4）。最終目標は、自作の Lexer / Parser で final/tests（fixed17）を通すこと
• F1 は golden test で scaffold/lexer.py と完全一致することを確認する

B: 最適化入門

生成したコードを「速くする」トピックのうち、測定基盤を必要としないもの。 着手はコマ6（関数呼び出し）までで足りるので、コマ15 を待たずに始められる。 ただし完了条件のうち golden.py は fixed17（＝コマ15 の完成した final/mycc.py）を土台にするので、 やり切るにはコマ15 が要る。コマ15 前は check.py を全 PASS にするところまで進める。

各回は独立している（好きな順に取り組んでよい）。 効果は count_insns.py による静的命令数で確認する。 「実行された命令が何回減ったか」は静的命令数では分からない。 それを測る物差しは O1 が作る。

O 系列との関係

B は O の前哨である。 題材が一部重なるので、対応を先に示しておく。

どちらを先にやるか。 コマ15 がまだなら B から。 終わっているなら、O1（測る物差し）→ O3・O4 と進んだほうが、 「減った」の意味がはっきりする。

O: 最適化

生成したコードを速くする技法を、測定 → 解析 → 変換の順に積み上げる。 全部で10コマだが、各回は独立して取り組める。O1 と O2 を先に済ませておけば、 O3・O4・O7 はどれから始めてもよい。

依存関係

O1(測定)             ─→ O2(フローグラフ), O3(命令選択), O4(レジスタ割り当て)
O2(フローグラフ)     ─→ O5(生存解析), O7(ブロック整列)
O4(レジスタ割り当て) ─→ O5(生存解析)
O5(生存解析)         ─→ O6(コピー伝播 / 死コード除去)

各行は「左が、右の直接の前提である」ことを表す（矢印の向きは「前提 → そのトピック」）。 O3・O6・O7 はここから先が無いので、左側には現れない。

図にあるのは直接の前提だけで、上の一覧表の「必須の前提」は間接的なものも含めて書いてある。 たとえば O6 の O1, O2, O4 は O5 を経由した間接の前提であり、O7 の O1 は O2 を経由する。

2つの差し込み方

O4 だけコード生成器を触るのは、「どの変数の & が取られているか」が AST を見ないと分からないためである。

1ファイルだけ試すときは workbook/advanced/ から実行する。

python3 optcc.py --passes isel file.c
python3 optcc.py --regalloc --passes isel,copyprop,dce,layout file.c
python3 optcc.py --passes '' file.c        # 最適化なし(基準値)

final/tests（fixed17）全体に通したいときは workbook/ から scaffold/test_runner.py --compiler advanced/optcc.py --tests final/tests を使う （../docs/testing.md 参照）。同じ optcc.py だが、 cwd が違うのでパスの書き方が変わる。

--passes の順番を変えると効果が変わる（O6 で扱う phase ordering）。

命令数の基準は O1 に1つだけ置いてある

O 系列の資料はどれも「前 → 後」の表を出すが、その基準（素 / +isel / +regalloc / +copyprop,dce / +layout の5構成）は O1 の資料の「全構成の基準表」に一括で載せてある。 各回の表はそこからの差分である。数字が食い違って見えたら、まず基準表と突き合わせる。

全部かけるとどうなるか

基準表の両端、つまり最適化なしと --regalloc --passes isel,copyprop,dce,layout の比較。

ベンチマーク   静的:前   後    削減    動的:前      後      削減
bubble           340   233   31.5%    24023   15952   33.6%
fib_rec           77    70    9.1%    73993   68073    8.0%
loop_sum          70    43   38.6%     7840    4030   48.6%
matmul           453   308   32.0%    27958   18563   33.6%
strops           243   173   28.8%    77108   50135   35.0%
合計            1183   827   30.1%   210922  156753   25.7%

loop_sum は実行される命令が半分以下になる。 fib_rec の伸びが小さいのは、ループが無く、 局所変数をレジスタに置いても得をしない形だからである（O4 コマ2 で扱う）。

R: ランタイム

gcc とライブラリに任せていた部分を、自分の手で開ける。

R2 は R1 の syscall.s を土台にする。R3 は独立している（libc を使ってよい）。

S と L の判定基準 — 仕様の内側か、外側か

S と L は難易度でも題材でも分かれていない。分かれ目は その回で作る振る舞いの「正解」がどこに書いてあるかである。

判定は二段の問いで行う。①仕様はその構文について何か言っているか。②言っているとして、 いまの実装はそれに違反しているか。「禁止」も仕様が言っていることに数える （S3 は仕様が「不可」と定めた形を実装が受理しており、違反である）。 逆に L1 でポインタ差がバイト差になるのは仕様違反ではない——仕様がポインタ同士の減算に 何も決めていないだけである。

S のずれは向きが2通りある。実装を仕様へ合わせる回（S2）と、 仕様の側を ISO C へ寄せる回（S1・S3。S1 は仕様が例外 E3 として差分を自ら明記し、 S3 は仕様の禁止行がいずれ改訂される想定である）である。 どちらも仕様の該当行から出発する点で共通で、L のように意味を新しく決めることはしない。

この判定結果は、各トピックの位置づけ表の 仕様との関係 欄に書いてある。

2本の ID を振り直した（食い違いは解消済み）

以前は、判定基準と ID が食い違う回が2本あった。2026-08-01 に実際に移した。

2本は番号を入れ替えた形になっている。S3 も L1 も番号としては残っているが、 指す中身が入れ替わっているので、以前のメモやブックマークをそのまま読むと取り違える。

これで S1〜S3・L1〜L3 の6本すべてが、判定基準どおりの位置にある。

S: 意味論

仕様が意味を決めている構文について、いまの実装とのずれを自分で見つけて直す。 どれも「テストが通ってしまうので気づきにくい」性質を持つ。

各回は独立している。いずれも mycc.py を書き換えず、 ラッパーで生成を差し替える方式で、fixed17 が通り続けることが安全網になる。

L: 言語機能

Core プロファイルで「扱わない」と決めた機能を、意味を自分で決めてあとから足す。 どれも mycc.py と scaffold/ を書き換えず、ラッパーで差し込む。

各回は独立している。fixed17 が通り続けることが、 既存の機能を壊していないことの保証になる。

Q: 品質

「正しく動く」を作り込む。コンパイラ本体には手を入れず、独立したパスとして追加する。 「正しいプログラムを1つも拒まない」ことを、教材のテスト入力全体で確認する。

P: 移植・セルフホスト

Python 版コンパイラを C へ移植し、最終的に自分自身をコンパイルする（セルフホスト） 長期プロジェクト。他のトピックと違い1回では終わらず、自動採点もない。 大まかな進め方だけを P1_selfhost/README.md に示してある。

このセクションのページ

• 字句解析と構文解析 — CYK 法で数式を解く
• 字句解析器を作る — ブラックボックスを開ける（前編）
• 再帰下降パーサ① — 式を解析する
• 再帰下降パーサ② — 文を解析する
• 再帰下降パーサ③ — 宣言・型・プログラム全体（最終回）
• 最適化入門 — 定数畳み込みとピープホール
• レジスタ割り当て入門 — スタックマシンを卒業する
• 末尾呼び出し最適化 — 再帰をループに変える
• 最適化の測り方 — 静的と動的は別物
• 基本ブロックとフローグラフ — 最適化の地図を作る
• 命令選択 — 複数の命令を1つに畳む
• レジスタ割り当て — 変数をメモリから追い出す
• 生存変数解析 — 「この値はまだ使われるか」を解く
• コピー伝播と死コード除去 — 順番が結果を決める
• ブロック整列とループ回転 — 命令を減らさずに速くする
• libc なしで動かす — システムコールを直接呼ぶ
• 自前 printf — 数を文字に変える
• 自前 malloc — ヒープを自分で管理する
• 短絡評価 — && と || の本当の意味
• int は32ビット — 桁あふれを正しく折り返す
• 構造体の代入 — レジスタに載らないものを運ぶ
• ポインタ同士の引き算 — 差は「要素いくつ分か」
• 複合代入 — 左辺を1回しか評価しない
• 可変長引数の定義 — printf の側に立つ
• sizeof 単項式 — 答えは合っているのに、間違っている
• 構造体の値渡し・値返し — 呼び出し規約を自分で決める
• 型検査パス — 実行する前に間違いを見つける
• C 移植・セルフホスト — Python 版を C で書き直す

この資料の原稿を見る