Table of Contents

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

ついに — これまで集めてきたものを全部合わせて、a + a * a を 本当にパース してみましょう。（一番楽しいところです 👀）
材料は全部そろっています: ドット・状態（どこまで・今できること）と FIRST / FOLLOW（始まり・終わりのチートシート）。この二つで作った 構文解析表（行動指針書） が、その都度 「こうしなさい」 を教えてくれます。

パーサーがやることはたった二つ — shift と reduce

パーサーはその都度、どちらか 一方 だけをやります。

  • shift（押し込む） — 次のトークンを一つ読んで スタック に積みます。
  • reduce（まとめる） — スタックの一番上のいくつかが、ある規則の 右辺 とぴったり合えば、それを 左辺の非終端記号 に まとめます。（= 木の枝が一本完成!）

🍽️ スタック は 皿の山 のようなものです — 一番上にだけ載せて（shift）、一番上からだけ取り出します（reduce）。
パーサーが 「これまで読んでまとめたもの」 をここに積んでおきます。

では いつ shift して、いつ reduce するのでしょう？ — それを 構文解析表 が決めてくれます。
「今こういう状態で、次のトークンがこれなら → shift / reduce しなさい。」（表を 作る 方法は 発展コースにあります。ここでは表が指示するとおりについていってみましょう。）

a + a * a を最後まで追いかける

a は名前なので終端記号 id です。入力の終わりは $ で表します。
一行ずつ進みましょう — アクション 欄がまさに表が指示したものです。

# スタック 残り入力 アクション
1 (空) a + a * a $ a を shift
2 a + a * a $ reduce Factor → id
3 Factor + a * a $ reduce Term → Factor
4 Term + a * a $ reduce Expr → Term
5 Expr + a * a $ + を shift
6 Expr + a * a $ a を shift
7 Expr + a * a $ reduce Factor → id
8 Expr + Factor * a $ reduce Term → Factor
9 Expr + Term * a $ * を shift
10 Expr + Term * a $ a を shift
11 Expr + Term * a $ reduce Factor → id
12 Expr + Term * Factor $ ★ reduce Term → Term '*' Factor
13 Expr + Term $ ★ reduce Expr → Expr '+' Term
14 Expr $ accept 🎉

スタックが shift で育ち、reduce でまとまって縮んでいく のが見えますね？
最後には Expr 一つだけが残りました — 入力全体が 一つの式 にまとまったのです。

見てください — a * a が + より 先に まとまりました

★ を付けた 12番 の行をもう一度見てください。
a * a が一つの Term にまとまった 後ではじめて、13番 で + がまとまりましたね。

つまり — * が + より もっと先に、もっと深く まとまったのです。掛け算の優先順位 が ひとりでに 守られたわけです!
（ひと目で見るパイプラインで約束した 「掛け算が足し算より先にまとまる」 がまさに これです。）

完成した木で見ると一目でわかります。

   Expr
   ├─ Expr
   │  └─ Term
   │     └─ Factor
   │        └─ a
   ├─ +
   └─ Term            ← a * a がここに一かたまりで!
      ├─ Term
      │  └─ Factor
      │     └─ a
      ├─ *
      └─ Factor
         └─ a

一番上の Expr は (左の a) + (右の a * a) です。a * a が右の深いところに一かたまりにまとまって いますね？ — 表がそう導いたのです。

おしまい — accept 🎉

スタックに Expr 一つだけが残り、入力が $（終わり）に到達したとき、表が最後に accept（受理） と言います。
「入力全体が文法に合った一つの Expr だ」 — パース成功!

では 間違った 入力は？（例: a + + a）
パースの途中で表の欄が 空いている ところに出くわすと — 「ここではできることがない」 → それが 文法エラー です。表が正しさと間違いまで見分けてくれるのです。

もう着きました 🎉

これが LR パースのすべて です — 読んで（shift）、合えばまとめて（reduce）、表が指示するとおりに、accept まで。

基本コースの完走、おめでとうございます! 🎊
文法の読み方 → FIRST / FOLLOW → ドット・状態 → 実際のパース まで、LR パースの大きな絵を全部つかみましたね。

🎓 表を自分で作る方法 と Janglim のコード が気になったら — 発展コース へ行けばよいです。
LR項目 → 状態 → 閉包 → GOTO → 正準集合 → 構文解析表 の順で、さっき見たものを 自分で作って みましょう。（見なくても概念はもうすべてつかんでいます。🙂）

👈 前へ: ドットと状態

Edit this page