構文解析表 · 衝突とは？
前のページで私たちは Expr 文法を使って構文解析表を完成させました。その表をちょっとだけ思い出してみましょう。
一マス一マスに行動がちょうど一つずつ入っていましたね — s5、r2、goto 3、acc … だからパーサーはその都度迷わずにマスを一つ見つけ、そのとおりに従うだけでよかったのです。
ところが作り方ページの最後で、私はそっと一つの問いを置いておきました。
「もし一つのマスに行動が二つ入ったらどうしましょう？」
このページがまさにその話です。ゆっくり進んでいきましょう。
まず — 表はなぜ「詰まることなく」回ったのか
構文解析表のすることを一行にまとめると、これでした。
いまの状態 + 次に来る文字 → どんな行動をするか、それを一マス一マスに書いておいたもの。
パーサーはその都度いまの状態と次の文字で表からマスを一つ選び、そこに書かれたとおりにだけ動きます。
マスごとに書かれた答えが一つだから — パーサーは一度も悩みません。このように悩みなくスイスイ回る性質を**決定的（deterministic）**と呼びます。
🔖 決定的（deterministic） — その都度すべき行動がちょうど一つに定まっていて、パーサーが迷うことがないこと。
さて、この**「マスごとに一つ」**という約束が破れると、何が起きるのでしょうか？
衝突 — 一つのマスに行動が二つ
ある文法では — 表を埋めていくと一つのマスに行動が二つ入ってしまいます。
そのマスに着いたパーサーはその瞬間ためらいます。「えっ… 二つのうちどっちをしろってこと？」
このように一つのマスに入る行動が二つ以上で、パーサーが何をすべきか決められない状況を**衝突（conflict）**と呼びます。
🔖 衝突（conflict） — 構文解析表の一つのマスに行動が二つ以上入って、パーサーが決定できなくなったこと。
私たちの Expr 文法は運よく — 実はよく設計されていたので — 衝突が一つもありませんでした。だから表があんなにきれいだったのです。
でも世の中の多くの文法はそうではありません。衝突がどうやって生まれるのか、その二つの種類を一つずつ見てみましょう。
種類① — shift / reduce 衝突
衝突をわざと見せるために、私たちの Expr ではなく、とても小さな文法を一つ持ってきます。
S → S '+' S S → a
「S は S 足す S、または単に a」 — 足し算を表すちっぽけな文法です。
この文法で状態たちを作っていくと、ある一つの状態の中にこの二つの項目が一緒に入ります。（項目・状態がうろ覚えなら LR項目・状態の章を思い出してください。）
S → S '+' S • ← ドットが末尾。完了項目 → '+' を見たら reduce（S+S を S にまとめる） S → S • '+' S ← ドットの後ろが '+'。進行中項目 → '+' を見たら shift（'+' を読んでさらに進む）
同じ状態、同じ次の文字 + なのに —
**上の項目は「reduce しろ」**と、**下の項目は「shift しろ」**と、互いに違う行動を叫びます。
ですからこの状態の + のマスには行動が二つ入ってしまいます。
| 状態 | … | + |
… |
|---|---|---|---|
| （この状態） | shift / reduce ⚠️ |
片方は shift、片方は reduce なのでぶつかるこの衝突を — そのまま shift/reduce 衝突と呼びます。
💡 なぜ生じたのか —
a + a + aを思い浮かべてみてください。真ん中まで読んだパーサーは、左のa + aを先に一塊にまとめるか（reduce）、それともひとまず+をさらに受け取って後で決めるか（shift）を決めなければなりません。ところがこの文法は(a+a)+aも、a+(a+a)もどちらも正しいと言います。答えが二つだからパーサーが選べないのです。このように一つの文を二通りに解釈できる文法をあいまいな（ambiguous）文法と呼びます。（ただし衝突が即あいまいさというわけではありません — あいまいでないのに衝突が見える場合があり、そのうちのかなりが、表をもっと精密に埋めれば消える見かけの衝突です。まさに次の話ですね。）
種類② — reduce / reduce 衝突
今度はまた別の小さな文法。
S → A S → B A → a B → a
「a 一つが A にもなれるし B にもなれる」文法です。
表を作っていくと、a を読んだ直後の状態にこの二つの項目が一緒に入ります。
A → a • ← 完了。reduce A→a B → a • ← 完了。reduce B→a
今度は両方とも reduce です。ところが — どの規則でまとめろと言うのでしょう？A→a で？B→a で？
どちらも「まとめろ」なのにまとめる対象が違うのでぶつかります。これを reduce/reduce 衝突と呼びます。
二つの種類を並べてみると:
| 衝突の種類 | 一つのマスでぶつかるもの | パーサーの悩み |
|---|---|---|
| shift / reduce | shift 一つ + reduce 一つ | 「もっと読むか、いままとめるか？」 |
| reduce / reduce | reduce 二つ（規則が違う） | 「どの規則でまとめる？」 |
[状態]の章で植えておいた種
覚えていますか？状態の章で — 一つの状態の中には完了項目（ドットが末尾にあってまとめようとする）と進行中項目（ドットの後ろに記号が残っていて読もうとする）が混ざっていることがあると言って、それを🌱衝突の種と呼んでおきました。
いま、その種が育って実になったのです。
- 一つの状態で完了項目と進行中項目が同じ文字をめぐってぶつかれば → shift/reduce 衝突
- 一つの状態で完了項目が二つぶつかれば → reduce/reduce 衝突
状態を学ぶときに「これが後で衝突になります」と先送りしておいたあの話を、いまようやく全部返した格好です。
それで — 衝突が出るとどうなるのか
文法に衝突があると、その表は**「マスごとに答えが一つ」**という約束が破れます。
= その文法はそのままでは決定的に構文解析できません。パーサーがそのマスで止まってしまうからです。
抜け出す道は二つです。
- 文法を直す — あいまいさを取り除いて、衝突がそもそも出ないように書き直す。
（私たちの Expr 文法がまさにそうやってよく整えられた文法です。だから表がきれいだったのですね。） - 表をもっと賢く埋める — 驚くことに、衝突のように見えるもののうち一部は本当の衝突ではなく、表を精密でなく埋めたせいで生じた見かけの衝突です。もっと精密に埋めるとするりと消えます。
その**「もっと精密に埋める」**へ向かう旅が — まさに次のページ（SLR）から始まります。
作り方ページで reduce のマスを FOLLOW で決めたあの方式（名前は SLR でしたね？）がなぜ見かけの衝突を生むのかから見て — そこから lookahead → CLR → LALR と精度のはしごを一段ずつ上りながら、その見かけの衝突をどうやってなくすかを見ます。
次へ
- 衝突 = 一つのマスに行動が二つ。shift/reduce と reduce/reduce、二つの種類。
- ある衝突は本物で、ある衝突は表を精密でなく埋めて生じた見かけだ — 次の章の核心。