lookahead（LR(1) 項目）
SLR の章で私たちは、「A → α • に出会ったら、どんな次の文字で reduce するのか？」という問いを FOLLOW(A) で答えました。ところが見かけの衝突で見たように — FOLLOW(A) は文法全体をひとまとめにしたものなので、いまこの場所には広すぎたのです。
そこでもう一歩進みます — 項目の一つ一つに、その場所にぴったり合う次の文字をつけよう。 この「項目につく次の文字」がまさに lookahead です。
この章では lookahead が正確に何で、どうやって求めるのかを — もれなく解いていきます。（次に来る CLR・LALR が、すべてこの lookahead の上に立っています。）
0. 記号の約束から — 混乱しないように
公式には α · β · t のような文字が出てきます。始める前にこれが何の文字なのかをはっきりさせておきます。（これをやらないとすぐ混乱します。）
これまで例題の a b c d x y は**文法に本当に埋め込まれた文字（終端記号）でしたね。ところが公式を書くときは — 「どの規則、どの文字でも」を指す空欄（プレースホルダー）**が必要です。
| 記号 | どんな空欄か | 入りうる例 |
|---|---|---|
A B |
非終端記号一つ（規則の名前） | 例題の A · B · S … |
α β |
記号の並び — 終端記号・非終端記号が0個以上並んだもの | 空の並び · c · A c · a A … |
t |
終端記号一つ — lookahead の場所 | c · d · または入力の終わり $ |
⚠️ 表記の注意 — lookahead は
aではなくtで書きます。 教科書では lookahead の場所をふつうaで書きます。ところが私たちの例題には本物の文字a（例:S → a A c）があるので、aが本物の文字と lookahead の場所の二つの意味で重なってしまいます。
そこでこのマニュアルでは lookahead の場所をt（terminal = 終端記号）で書きます。tは特定の文字ではなく*「ここに来る次の終端記号一つ」*という空欄です — そこに実際に何が入るのかは公式で求めるものです。
要点だけ: α β t = 空欄、 a b c … = 本物の文字。
1. LR(1) 項目 — 項目に lookahead をつける
閉包の章の項目は規則 + ドットでした — 例: A → α • β（ドットの前 α はすでに読んだ、ドットの後ろ β はまだ）。
ここに **lookahead 一文字（t）**をつけたのが LR(1) 項目です。
[ A → α • β , t ]
後ろについた t の読み方はこうです:
「
A → α βを最後まで読んで **Aにまとめた直後*、すぐ次の文字がtなら** — そのまとめは正しい。」*
つまり t はこの規則をまとめてもよい次の文字です。（だから「先読み（lookahead）」と呼びます。）
さて — 「なぜ lookahead が t なのか？」 t は文字の名前ではなく、**「まとめたあとに来る次の文字が入る場所」**という空欄です。その場所に実際にどんな文字が入るのかを求めるのが — まさに次の §2 です。
💡 SLR との比較: SLR は「
Aという規則にはFOLLOW(A)」のように非終端記号の単位で lookahead をまとめていました。LR(1) 項目は項目の単位 — 同じA → b •でもどの状態にいるかによって違うtを持つことができます。この細やかさが次の章たちの核心です。
2. その lookahead、どうやって求めるのか — 閉包で FIRST から
項目は閉包で増えていきます（閉包の計算法） — ドットの後ろに非終端記号があれば、その規則たちを広げることでしたね。LR(1) では、広げながら新しい項目の lookahead まで決めてあげます。
広げる状況はこうです。すでにこんな項目があるとしましょう:
[ A → α • B β , t ]
ドットの後ろに非終端記号 B がありますね（その後ろには β、そしてこの項目の lookahead t）。閉包は B → γ の規則たちを新しく入れます:
[ B → • γ , ? ] ← この新しい項目の lookahead の場所には何を入れる？
考えてみましょう — B を全部まとめたら、そのすぐ後ろには何が来ますか？
[ A → α • B β , t ]
もとの項目で B の後ろにあった β です。だから B の lookahead は*β の最初の文字*たち（FIRST(β)）になりますね。
ところがもし β が空か、まるごと消えうる場合（つまり B の後ろに事実上何もない場合）、そのときは B の次に来るのはもとの項目の lookahead t です。
新しい lookahead = t
なぜ t になるのでしょう？ もとの項目は [ A → α • B β , t ] ですが、β が消えると実質 [ A → α • B , t ] になり、この項目どおり A を展開すると B がいちばん後ろに来ます。B をまとめると A もすぐ終わります。すると B の次に来るのは*A の次に来るもの*そのもので、それが何かはこの項目がすでに教えてくれています — lookahead t ですね。だから B はその t をそのまま引き継ぎます。
この二つの場合を一つの式にまとめたのが —
新しい lookahead =
FIRST( β t )
（FIRST(β t) = β の FIRST を集めつつ、β がすべて消えうるなら t まで含める — FIRST の定義そのままです。）
これが lookahead を求める公式のすべてです。新しい計算ではなく、すでに学んだ FIRST を「ドットの後ろの β」に適用するだけです。
3. 手で一度 — 本物の文字で
空欄（α β t）ではなく本物の文字でやってみましょう。小さな文法:
S → ( A ) A → n
（( ) n は本物の終端記号です。n は数字や名前のようなトークンだと思ってください。）
始めて ( を読むと、こんな項目があります（いちばん外側は入力の終わり $ で閉じるので lookahead が $）:
[ S → ( • A ) , $ ]
ドットの後ろが非終端記号 A ですね。広げて A → n を新しく入れる番です — 公式 FIRST(β t) に代入します:
- ドットの後ろの非終端記号
B=A Aの次に残ったβ=)- この項目の lookahead
t=$ - → 新しい lookahead =
FIRST( ) $ )— ところが先頭の)は終端記号なので消えられず、FIRST はその後ろの$までは届きません。だから$は外れてFIRST( ) )={ ) }（)は終端記号なので自分自身）
そこで新しい項目は:
[ A → • n , ) ]
n を読むとドットが進んで — [ A → n • , ) ]。
読み方: 「A → n をまとめた直後に ) が来たら正しい。」 — 当然ですね、( n ) で n の後ろには ) が来るのですから。
β が空の場合も一度見てみましょう。 もし規則が S → ( A ) ではなく単に S → A だったら？[ S → • A , $ ] で A を広げるとき — A の後ろに残ったものがありません（β が空）。すると公式が FIRST( $ ) = { $ }、つまり親の lookahead $ をそのまま引き継いで [ A → • n , $ ] になります。
🔖 一行まとめ — lookahead は*項目ごとにつく「まとめてもよい次の終端記号」*で、閉包では
FIRST(β t)で求めます。（ドットの後ろのβの FIRST、βが消えれば親tを引き継ぐ。）
次へ
これで lookahead が何で、どうやって出てくるのかが分かりました。これを状態を作るときから最初からつけて表を埋めると — それが CLR です。行ってみましょう。