字句解析と構文解析

字句解析器はソースをトークンに分け、構文解析器は後続のコンパイラー段階で使う構造を作る。12 + 3 * 4 は元の順序の五トークンになり、12 + (3 * 4) と解析されて 24 になる。左から順に計算するだけなら 60 だ。

字句解析は切り分けと分類、構文解析は階層を担当する。乗算の優先は * トークンを前へ動かすのではなく、解析呼び出しの構成で決まる。

字句解析と構文解析の仕組み

字句解析器は左から走査する。数字が数値の字句を始め、隣接する数字も同じ字句に加えるので、12 は一つの NUMBER(12) になる。+、*、(、) は各一トークン。空白は位置を進めるだけで出力しない。@ のように受け付ける種類がない文字で停止する。

パーサーはトークンの種類を読み、空白や元の文字オフセットは扱わない。本レッスンは三つの再帰下降規則を使う。primary() は NUMBER または括弧式、term() は STAR のループ、expr() は PLUS のループを担当する。term が乗算を終えてから待機中の expr へ戻るため、優先順位が生まれる。

数値は AST の葉になる。演算子を読んだ瞬間には親を作らず、左部分木と演算子を保持し、右側の解析を待って Mul または Add にまとめる。括弧は制御フローを変え、効果は木に残るので、本モデルの AST ノードにはならない。

字句解析と構文解析のステップ

既定のソースは 12 + 3 * 4。

1. 1 を読み、続く 2 を同じ範囲に加えて NUMBER(12) を出す。
2. 最初の空白を飛ばし、トークン列に空の枠は作らない。
3. PLUS(+) を出し、次の空白を飛ばして NUMBER(3) を出す。
4. 三つ目の空白の後で STAR(*)、四つ目の後で NUMBER(4) を出す。五トークンと別の EOF マーカーになる。
5. PLUS は STAR より前のまま。まだ階層がないので、この順序だけではグループ化は決まらない。
6. expr() が term()、さらに primary() を呼び、NUMBER(12) を消費して葉 12 を作る。
7. term は STAR ではなく PLUS を見て 12 を返す。外側 expr は PLUS を消費し、left = 12 を保って右辺の term を呼ぶ。
8. 右の term は NUMBER(3) を読み、STAR で left = 3 を保ち、primary を呼んで NUMBER(4) を得る。
9. term が 3 * 4 を Mul にまとめる。戻ってから待機中の expr が 12 + Mul を根 Add にする。
10. 全トークンを消費し、木の値は 12 + (3 * 4) = 24 になる。

トークン列を並べ替えることはない。呼び出しパネルでは expr が term の STAR 処理を待ち、AST の親は Mul、Add の順に作られる。

制御フローが木の階層になる

文法が PLUS の各オペランドを term に任せ、term が乗算を先に終えるので、Add(12, Mul(3, 4)) になる。同じループで PLUS と STAR を左から扱うと、同じ列でも Mul(Add(12, 3), 4) となり 60 を返す。変わったのは演算子ではなく解析の制御フローだ。

AST はグループ化を記録し、後続の生成、最適化、評価はトークンの優先順位を調べ直さずに済む。(12 + 3) * 4 も同じ規則を使う。primary が括弧内で expr を呼び、内側 Add が終わってから外側 term が Mul を作るため、この場合は 60 が正しい。

時間計算量と空間計算量

文字数を c、トークン数を t、最大括弧深さを d とする。

この小さな決定的文法の上界であり、任意の文法や解析方式が線形という保証ではない。

境界ケース

• 空または空白だけの入力は空トークン列になり、primary が必要な位置の EOF で構文解析が拒否する。
• 12+3*4 は空白付きと同じトークンと AST になる。空白は字句解析の責任だ。
• 12 + @ 4 は字句解析で止まり、@ を捏造せず、構文解析も始めない。
• 12 + * 4 は字句として有効でも構文は無効。primary が数値か左括弧を期待して STAR を拒否する。
• (12 + 3 * 4 は内部部分木を作っても、take("RPAREN") が EOF で失敗する。

よくある間違い

• 一桁ごとに NUMBER を作る。12 を分けると、演算子のない第二オペランドが残る。
• トークン化できれば構文も有効だと思う。12 + * 4 はその反例だ。
• 演算子を読んですぐ親を作る。右部分木がまだないため待つ必要がある。
• 加算と乗算を同じ解析ループへ入れ、既定値を 24 から 60 に変えてしまう。
• AST が優先順位を作ると言う。制御フローが選び、AST は記録する。
• 本モデルの AST に括弧ノードを残す。効果は既に階層で表される。

モデルの範囲と拡張

非負整数、加算、乗算、一段の括弧を受け付ける。識別子、単項演算、減除算、文字列、コメント、位置情報、型検査、エラー回復は省く。実用パーサーは最初の誤りで止まるだけでなく、複数の診断を示すことが多い。

同じ構成は問い合わせ言語、設定式、テンプレート、DSL、コンパイラー、リンターに使える。同じ優先度の演算子は既存ループへ、別の優先度は新規則と呼び出し境界へ加えることが多い。各規則の責任を明確にする理由だ。