先日、claude codeでlex, flex, yacc, bisonなどをいじって遊んでいて、Claudeが返してきた内容に、おもしろいものがあったので記しておく。
そのころ、私のパソコンのローカルには、chibicc, perl5, vim, などのリポジトリがあり、claude codeにそれらを読ませて、内容がどうなっているか質問したり、別言語で書かせたりして遊んでいた。その流れで、簡単な処理系（"3 + 2"を渡すと5を返してくれる、みたいな）を作ったりしていた。
peanutsjamjam
flex, lex を使用してファイルを読むプログラムを書くアプローチは、/Users/sugawara/repos/chibicc で使用されている物とは別なものですか？
Claude
はい、まったく別のアプローチです。chibicc は flex も lex も使っていません（chibicc.hとparse.cに出てくる flex は「flexible array member」という C の機能のことで、無関係です）。2つのやり方の違い
flex chibicc 書くもの 正規表現とその動作（ .lファイル）字句解析器そのものを C で手書き 解析コード flex が自動生成（数値の表 + yylex()）tokenize.c（802行）を人が書いている入力の読み方 少しずつバッファに読み込む（ yyin）ファイル全体を一度にメモリへ読み込む 判定の仕方 状態遷移表をたどる（DFA） ifとwhileで場合分けビルド flex コマンドが必要 C コンパイラだけでビルドできる chibicc のやり方
tokenize.c:644のread_file()で、ファイルの中身をまるごと1つの文字列にします。FILE *out = open_memstream(&buf, &buflen); for (;;) { char buf2[4096]; int n = fread(buf2, 1, sizeof(buf2), fp); if (n == 0) break; fwrite(buf2, 1, n, out); } fputc('\0', out); // 最後に終端の \0 を足す return buf; // ファイル全体が入った文字列を返すそして
tokenize.c:492のtokenize()が、ポインタpを先頭から末尾へ動かしながら切り分けます。char *p = file->contents; while (*p) { if (startswith(p, "//")) { ... continue; } // 行コメント if (startswith(p, "/*")) { ... continue; } // ブロックコメント if (isspace(*p)) { p++; continue; } // 空白 if (isdigit(*p) || ...) { ... continue; } // 数値 if (*p == '"') { ... continue; } // 文字列 ... }flex で
[0-9]+ { ... }と1行で書くところを、isdigit()と for ループで自分で書いている、ということです。なぜ手書きなのか
- C 言語の字句解析は、正規表現だけでは足りない部分がある
#include <stdio.h>の<stdio.h>は、#includeの後ろでだけ特別に扱う必要があります1.0e+5のような数値は、いったんゆるく読み取ってから後で解釈し直しています（convert_pp_number）- ファイル全体をメモリに持つと都合がよい
- 各トークンが「元のファイルのどこか」を指すポインタを持てます。エラーメッセージで該当行を表示するのに使います（
error_at）\r\nを\nに直す、バックスラッシュ+改行をつなげるといった前処理を、読み込んだ後にまとめてできます- 教材としてのわかりやすさ
- この本は「コンパイラの中身を全部見せる」のが目的です。自動生成された表を見せても学びになりません
- 依存を減らせる — flex が入っていない環境でもビルドできます
どちらを選ぶか
- flex が向くもの: 設定ファイルの読み取り、ログの集計、小さな言語、独自のデータ形式。規則が正規表現できれいに書けるなら、圧倒的に速く作れます。
- 手書きが向くもの: 本格的な言語の処理系、細かいエラーメッセージを出したいとき、文脈によって読み方を変えたいとき。
実は、GCC、Clang、Go など実用のコンパイラも、ほぼすべて手書きの字句解析器を使っています。理由は chibicc と同じです。flex は学習や小さなツールでは便利ですが、大きな言語では制御しにくくなります。
chibicc の
tokenize.cを flex で書くとどうなるか、比較のために一部だけ書いてみることもできます。
peanutsjamjam
chibicc の方針はわかりました。言語が異なると、flexでの扱いやすさも変わると思うのですが、Pythonはどうですか？Perlはどうですか？
Claude
言語によって難しさは大きく変わります。Python は「工夫すれば可能」、Perl は「事実上不可能」です。まず、flex が得意なのはどういう言語か
flex は正規表現＝有限オートマトンです。つまり「今までに読んだ文字の履歴を覚える」ことができません。トークンの切れ目が、その場の文字並びだけで決まる言語が得意です。
言語・形式 flex での扱いやすさ JSON、CSV、設定ファイル ◎ 数十行で書ける Lisp / Scheme ◎ 記号が単純 C ○ ほぼ書けるが、型名と変数名の区別などで苦労する Python △ 書けるが、C のコードを足す必要がある Perl ✕ 原理的に無理 Python の場合
結論: 書けますが、flex だけでは足りません。
難しい点1: インデント
Python はブロックの深さを字下げで表します。字句解析器は、字下げが深くなったら INDENT、浅くなったら DEDENT というトークンを出す必要があります。
if x: a = 1 ← ここで INDENT を1個出す b = 2 c = 3 ← ここで DEDENT を1個出す問題は、一度に何個 DEDENT を出すかは、それまでの字下げの履歴で決まることです。正規表現では表せません。そこで、flex の中にスタックを自分で持つ C のコードを書きます。
%{ int indent_stack[100] = {0}; int sp = 0; %} %x INDENT_MODE %% ^[ ]* { int width = yyleng; if (width > indent_stack[sp]) { indent_stack[++sp] = width; return INDENT; } while (width < indent_stack[sp]) { sp--; return DEDENT; } /* 複数回返す工夫が要る */ }さらに「1回の呼び出しで複数のトークンを返す」ことが flex は苦手なので、待ち行列を自分で用意することになります。
難しい点2: 行の継続
括弧の中では改行が無視されます。これも括弧の深さを数える変数が必要です。
x = [1, 2, 3] ← この改行は NEWLINE トークンにしない難しい点3: f-string
Python 3.12 以降、f-string の中に同じ引用符や入れ子の f-string が書けるようになりました。
f"{f"{x}"}"これは入れ子の深さを数える必要があり、正規表現の範囲を完全に超えています。
実際の Python はどうしているか
- CPython 本体:
Parser/lexer/lexer.cに手書きの C で書かれています。インデントのスタックも f-string の状態も、そこで管理しています。- 標準ライブラリの
tokenizeモジュール: 実は正規表現ベースです（Lib/tokenize.py）。インデント処理だけ Python のコードで補っています。つまり「正規表現 + 少しの補助コード」という方針自体は Python でも通用する、ということです。まとめ: flex で Python を扱うのは、「flex + 状態を持つ C のコード」 という組み合わせになります。
%x（排他的な開始状態）を使えば現実的に書けます。実際、flex で書かれた Python 字句解析器の例は世の中にいくつもあります。Perl の場合
結論: flex では書けません。Perl だけでなく、どんな字句解析器生成ツールでも無理です。
Perl には有名な言葉があります。
Only perl can parse Perl.（Perl を解析できるのは perl だけ）
これは冗談ではなく、理論的にそうだと示されています（2008年、Jeffrey Kegler による証明）。Perl の字句解析は、実行時の情報がないと決まらないからです。
難しい点1:
/が割り算か正規表現か決まらない$x = $a / $b; # 割り算 $x = $a =~ / $b /; # 正規表現どちらかは、直前のトークンが何だったかで決まります。Perl の内部にはこれを判断する
expectationという状態変数があります。難しい点2: 関数の定義が構文を変える
sub mylen ($) { ... } # プロトタイプを宣言 mylen $x, $y; # mylen($x), $y と解釈されるプロトタイプの宣言が先にあるかどうかで、同じ文字列の切り分け方が変わります。しかも
BEGIN { }ブロックの中で実行時にサブルーチンを定義できるので、コードを実行してみないと構文が決まりません。難しい点3: 何でも区切り文字になる
s/foo/bar/; s{foo}{bar}; s#foo#bar#; qw(a b c);
sやqの直後の任意の1文字が区切りになります。しかも括弧類は入れ子を数える必要があります。難しい点4: ヒアドキュメント
print <<"END", $x; 本文はここ END
<<"END"の位置と、本文が現れる位置が離れています。しかも1行に複数書けます。難しい点5: ソースフィルタ
use Filter::Simple;プログラム自身が、自分のソースコードを読み込み前に書き換えられます。これを許した時点で、静的な解析はあきらめるしかありません。
実際の Perl はどうしているか
- 字句解析:
toke.c（約 13,000行の手書き C）。Perl 本体で最も複雑なファイルです。- 構文解析:
perly.y（yacc）を使っています。つまり Perl は「構文解析は yacc、字句解析は手書き」という構成です。しかも
toke.cは構文解析器の状態を見ながら動くので、両者が密に絡み合っています。flex のように独立した字句解析器としては切り出せないのです。まとめ
Python Perl flex で書けるか ○ 補助コードが必要 ✕ 不可能 何が問題か インデント、f-string /の曖昧さ、プロトタイプ、ソースフィルタ必要な仕組み 字下げのスタック（有限の状態） 構文解析器の状態、さらに実行時の情報 本家の実装 手書きの C 手書きの C（13,000行） 面白いのは、flex で書きやすい言語ほど、後から書きやすい言語とは限らないことです。Python はインデントで読みやすさを取り、その代わりに字句解析が複雑になりました。Perl は書き手の自由さを取り、その代わりに解析を捨てました。
Python のインデント処理を flex で実装する例を
flex_001の隣に作ることもできます。%xと状態スタックの使い方がよく分かる題材です。作りましょうか？
