Table of Contents

ドットと状態 — パーサーが「いまどのあたり」かを覚えておく方法

前の FIRST / FOLLOW では — パーサーが 「始まり/終わり」 を判断するために作っておく チートシート を 見ましたね。
今度は、パーサーが入力を読み進めながら 「自分はいまどのあたりまで来たんだろう？」 をどうやって覚えておくのかを見ていきましょう。
（ここでも公式・コードなしで、感覚 だけで進みます。😀）

読んでいくと — 「どこまで読んだか」の印が必要になります

パーサーはトークンを 左から1つずつ 読みます。
そうしているうちに、ある規則を 始めはしたけれど、まだ終わっていない 状況がしょっちゅう出てきます。

たとえば規則 Expr : Expr '+' Term をたどっている途中だとしてみましょう。
Expr までは読んでいて、いまは '+' が来るのを待っているところです。
この 「どこまで来たか」 をどうやって書き留めておきましょうか？

とても単純な方法があります — 規則の真ん中にドット（•）を1つ打つ のです。

   Expr → Expr • '+' Term

ドットの 前 は すでに読んだもの、ドットの 後ろ は まだ読むもの です。
上のドットは 「Expr まで読んでいて、次は '+'」 を意味しますね。

📖 こうやって ドットを打った規則 を LR項目（item） と呼びます。
名前は大げさですが、たった今見た 「規則 + どこまで」 がすべてです。これからは単に 「項目」 と呼ぶことにします。

ドットはトークンを1つ読むたびに 1マスずつ右へ 進みます。

   Expr → • Expr '+' Term      (まだ何も読んでいない)
   Expr → Expr • '+' Term      (Expr まで読んだ)
   Expr → Expr '+' • Term      ('+' まで読んだ)
   Expr → Expr '+' Term •      (すべて読んだ — さあ1つのかたまりにまとめる番！)

ドットが いちばん後ろ に届いたら、その規則を 読み切った ということです。
このときがまさに 還元（reduce）する番 なのです。（FIRST / FOLLOW で 「終わったらまとめる」 と言っていた、その 瞬間です。）

ところで — 可能性はたいてい 複数 あります

ここからもう一歩だけ進みます。
パーサーがある地点に立っているとき、進行中の規則 が必ず1つだけとは限りません。

a + a * a を読んでいて、最初の a を Term まで見たとしてみましょう。（a は名前なので Factor、その Factor は Term ですね。）
まさにその瞬間、2つのことが同時に 可能になります。

  • 「この Term 1つで1つのかたまりが終わり」 かもしれないし → Expr → Term •
  • 「後ろに * なにか がもっと付く」 かもしれません → Term → Term • '*' Factor
   Expr → Term •                 ← ここで終わりかも
   Term → Term • '*' Factor      ← '*' がさらに付くかも

こうやって 「いま可能な項目たち」 を1つのまとまりに集めたもの — それがパーサーの 状態（state） です。

🧭 たとえるなら、状態は 分かれ道に立ったときのナビ画面 のようなものです。
「ここから行ける道はこれら」 を一目で見せてくれるわけですね。
そして 次のトークン が、そのうちの1本の道を選んでくれます — * ならさらに進み、+ や入力の終わりならまとめます。
（「まとめてよい次のトークン」 を FOLLOW が教えてくれると言っていたのが、まさにここで使われます。）

読むたびに — 状態から状態へ

パーサーはトークンを1つ読むたびに ある状態から別の状態へ移っていきます。
まるで 駅から駅へ 進むようにです。

   (開始状態) ──読む──▶ (次の状態) ──読む──▶ (次の状態) ──▶ …

ですからLRパーサーは、じつは 「状態と状態のあいだを移動して回る機械」 なのです。
どの状態にいるか + 次のトークンが何か — その2つがあれば、次の行動（さらに読む / まとめる）が決まりますね。

📦 この状態が正確に何個あって、どのように作られるのか には、決まった 組み立て手順 があります（ドットを動かし、 抜けている可能性を埋めて…）。少し機械的な作業なので、気になるなら 発展コース の LR項目 から 一段階ずつ見ていけば大丈夫です。
基本トラックはここまでで十分です — 「状態 = いま可能なものたちのまとまり、読めば隣の状態へ移る」 という 感覚さえつかめれば。🙂

次の章

これで材料がすべて揃いました — ドット（どこまで読んだか）、状態（いま可能なものたち）、そして FIRST / FOLLOW（始まり/終わりのチートシート）。

この3つを合わせると — パーサーの 行動指針書、つまり 構文解析表 ができあがります。
そしてその表で a + a * a を 本当にパース してみます。（いちばんおもしろい部分ですよ 👀）

👉 表で実際にパースしてみる

👈 前へ: FIRST / FOLLOW

Edit this page