構文解析表 · SLR と見かけの衝突

前の章で衝突に出会いました。そして最後にこんなことをそっと漏らしておきましたね —

衝突には本物もあるけれど、表を精密でなく埋めて生じた偽物もある。

この章でその**「精度」の話を始めます。ところが不思議なことに — これがすべてたった一つの問い**から分かれて出てきます。

すべてはこの一つの問いから

衝突はほとんどいつも完了項目のせいで生じます。状態の中に A → α • のようにドットが末尾まで行った項目があると*「もう reduce しろ」*という意味ですね。ところが —

「A → α • に出会ったとき、どんな次の文字で reduce を書くべきか？」

まさにこの問いです。
この答えをどれだけ精密にするかが — 衝突が出るか出ないかを分け、これから出てくる SLR · CLR · LALR という名前たちが、実は全部この一つの問いに対する互いに違う答えなのです。

🔖 lookahead（先読み） — パーサーがいま決定を下そうとしてちらっと見る次の文字一つ。（閉包の章で一度かすめたあの言葉です。）

さあ、精度を一段ずつ上げていきましょう。

① 最も粗い答え — 「どんな文字でも」（LR(0)）

いちばん単純な答え。
A → α • なら、次の文字が何であっても reduce。

これが私たちが正準集合まで作った LR(0) 状態そのままの答えです — その状態たちには次の文字についての情報がそもそもないからです。

問題はわかりきっています。reduce をあまりに無造作に書くので、同じ状態に shift 項目が少しでもあるとたちまちぶつかります。たいていの実際の文法は、この段階で衝突だらけになります。
→ もっと精密でなければなりません。

② 一段上 — 「FOLLOW でだけ」（SLR）

賢い第一歩。
A → α • をどこでもではなく — A の後ろに来られる文字でだけ reduce するのです。その*「A の後ろに来られる文字たち」*がまさに FOLLOW(A) でしたね。

これが作り方ページで私たちが実際に使った方式で、名前が SLR です。

🔖 SLR (Simple LR) — LR(0) 状態はそのままにして、reduce は FOLLOW(A) に入った文字でだけ書く方式。（"Simple" = 最も手軽な一段の改善という意味。）

ただ通り過ぎずに、目で一度見てみましょう。 私たちの Expr 文法で状態を作っていくと — Term を読んだ直後にこんな状態が一つ出てきます。

Expr → Term •              ← 完了。Expr→Term にまとめようか？
Term → Term • '*' Factor    ← 進行中。'*' を見たら shift

この状態で次の文字が * のとき — 決めることはたった一つです。
上の Expr → Term • をいままとめるか（reduce）、やめるか？

二つの方式がこの問いに違うふうに答えます。

LR(0) の答え — 「無条件にまとめろ。」
完了項目（Expr → Term •）は次の文字をまったく見ません。どんな文字が来てもただ「まとめろ」です。
だから * でも「Expr→Term にまとめろ」と書いてしまいますね。ところがすぐ下の項目（Term → Term • '*' Factor）は * でshiftしろと言います。
→ 一つのマスに「まとめろ」と「もっと読め」が一緒に → 衝突！ ⚠️

SLR の答え — 「Expr の後ろに来られる文字のときだけまとめろ。」

ところが — なぜよりによって「来られる文字のときだけ」なのでしょう？ここに論理があります。

Expr → Term • をまとめるということは、いま作った Term を Expr 一塊にまとめてスタックに載せるという意味です。そうしたらパーサーはその Expr のすぐ後ろに入力の次の文字を続けて見ることになりますね。

だからまとめてもよいためには — その次の文字が、Expr の後ろに本当に来られる文字でなければなりません。
もし Expr の後ろに絶対に来られない文字なら？それをまとめた瞬間、**「Expr の次にその文字」*という — 文法のどこにもない形を作ってしまうのです。それはつまり「ここでまとめると間違う」*という意味ですね。

そして**「Expr の後ろに来られる文字」** — これがまさに FOLLOW の定義でした。

🔖 FOLLOW(Expr) = Expr のすぐ後ろに来られる終端記号の集合。（定義そのまま。）

だから SLR のルールは定義からまっすぐ従って出てきます — 次の文字が FOLLOW(Expr) の中にあるときだけまとめる。

さて、では * は？ 定義どおり FOLLOW(Expr) を直接求めてみましょう。
FOLLOW を求める方法は — 文法で**Expr が登場する場所ごとに、そのすぐ後ろに何が来るか**を集めることでしたね。Expr が右辺に出てくる規則をもれなく探してみると:

`Expr` が出てくる規則	`Expr` のすぐ後ろに来るもの
`Expr → Expr '+' Term`	`+`
`Factor → '(' Expr ')'`	`)`
`Accept → Expr`（増補規則）	入力の終わり `$`

これがすべてです。だから — FOLLOW(Expr) = { + ) $ } です。
（{ } は集合を表す記号にすぎず、中に入った + · ) · $ が実際の要素です。）

ここで決定的な一つが見えます — どの規則でも Expr の後ろに * が来ません。
そうならざるをえません。* は文法で唯一 Term → Term '*' Factor の一か所だけに出てくるからです。つまり * はいつも*Term のすぐ後ろの場所で、Expr の後ろ*の場所ではありません。

これで論理が閉じます:

* は FOLLOW(Expr) にない（= Expr の後ろには * が来られない）。
だから * で Expr → Term • をまとめると*「Expr の次に *」*という文法にない形になる。
したがって SLR は * ではまとめない。

reduce を書かないのでそのマスにはshift 一つだけが残り → 衝突が消えます。 ✅

方式	`*` ですること
LR(0)	次の文字を見ずに無条件にまとめる + shift → ⚠️ 衝突
SLR	`` は Expr の後ろに来られないのでまとめない* → shift だけ → ✅ きれい

一行の直観: a * … を読んでいる途中なら — 当然掛け算をもっと受け取るべきで、そこでまるごと Expr にまとめてはいけませんよね？SLR は*「* は Expr の後ろに来られない文字」という事実一つで、まさにその*「ここではまとめるな」**を正確に見抜いたのです。

このように — *「この文字が Expr の後ろに来られるか」*だけを一度問うたおかげで、私たちの Expr 文法は SLR で衝突が0になります。作り方の表があんなにきれいだったのは、まさにこのおかげです。
SLR だけでもかなり多くの文法がうまく解けます。ところが —

③ SLR の弱点 — 見かけの衝突

FOLLOW(A) が何だったか、もう一度思い出してみましょう。
それは文法全体を探って、A がどこに現れようとその後ろに来られる文字をことごとく集めた集合です。いまこの状態とは関係なく。

まさにここに落とし穴があります。

いまパーサーが立っているこの状態は、文法の中の特定の一つの場所です。
その場所で A の後ろに実際に来られる文字は — FOLLOW(A) 全体ではなく、そのうちの一部であることが多いのです。

ところが SLR は全体の FOLLOW(A) を持ってきて reduce を書きます。そうしているうちに —
この状態では絶対に来ない文字にまで reduce を書いてしまい、それが隣にあった shift とぶつかります。
文法が本当にあいまいなわけではないのに、ただ広く書きすぎて生じた衝突 — これを**見かけの衝突（spurious conflict）**と呼びます。

🔖 見かけの衝突（spurious conflict） — 文法が実際にあいまいなのではなく、reduce を必要以上に広い文字に書いて生じた偽物の衝突。

少し抽象的ですね。小さな例題で直接見てみましょう。

S → a A c
S → a B d
S → e A d
A → b
B → b

A も b に、B も b に広がる — わざと少し紛らわしく作った文法です。（それでもあいまいではありません。前後の文字で十分に分かれますから。）

まず FOLLOW(A) を求めます。A は二か所出てきます — a A c（後ろに c）と e A d（後ろに d）。だから FOLLOW(A) = { c d } です。（B は a B d の一か所だけなので FOLLOW(B) = { d }。）

では、パーサーが a b まで読んだ状態を見ましょう。この状態には完了項目が二つ入っています。

A → b •      ← 完了
B → b •      ← 完了

SLR で reduce のマスを埋めると:

A → b • は FOLLOW(A) = { c d } で reduce
B → b • は FOLLOW(B) = { d } で reduce
→ d で両方とも reduce！ reduce/reduce 衝突 ⚠️

ところがこれは本当の衝突でしょうか？ a b の次を考えてみましょう。
私たちは a で始めたので — 行ける道は a A c か a B d、二つだけです。

次が c なら → a A c の道 → A にまとめるのが正しく
次が d なら → a B d の道 → B にまとめるのが正しいです

つまり d では必ず B です。ここで A にまとめることは絶対にありません。

では SLR はなぜ d のマスに A → b reduce を書いたのでしょう？
A → b の reduce を FOLLOW(A) = { c d } 全体で書いたからです。そしてその d は — いまこの a の道ではなく、はるか遠くの e A d 規則から流れ込んだものです。e A d では A の後ろに d が来ますが、いま私たちが立っている a の道では A の後ろには c だけが来るのですから。

これがまさに見かけの衝突です。 文法があいまいなのではなく — まったく別の場所（e A d）の事情まで FOLLOW にひとまとめにして詰め込んだせいで、いまの場所にはなくてもよい reduce が書かれたのですね。

これは衝突とは？の章の本物の reduce/reduce とは違います。あちらは文法が本当にあいまいでしたが（同じ a を A とも B とも見られましたね）、こちらはあいまいでないのに SLR が偽物を見たのです。 — まさにはしごの上の段（CLR）が正確に直す地点です。（CLR の章でまさにこの文法をもう一度広げてお見せします。）

たとえでもう一度 —
FOLLOW(A) は*「A という人が生きてきて一度でも出会ったすべての人の名簿」のようなものです。
ところがいまこの状態は「今日、この部屋」です。
今日この部屋に来る人はその名簿の一部だけなのに — 名簿全体を見て「この人も来るかもしれないから席を空けておけ」とやるので、来もしない人の席のせいで見当違いにぶつかる*のです。

それで — 次へ

この見かけの衝突は — FOLLOW 全体ではなく**「まさにこの状態に本当に到達する文字」*にだけ reduce すれば消えます。その「この場所にぴったり合う文字」*がまさに次の章の lookahead で — それを状態に最初から埋め込むのが CLR、まとめて縮めたのが LALR です。一歩ずつ上っていきます。

その前に — いま学んだ SLR がエンジンのコードではどんな姿をしているか、たった一ページだけ見ていきましょう。（言葉で説明した定義がコードにそのまま埋まっているので、一度見るとさらにくっきりします。）

👉 構文解析表 · SLR — 実装