Table of Contents

閉包 · 定義

🎓 発展コース です。
前の 状態 の章で — 状態とは LR項目の集合 Iₓ だと見ましたね。
ところが状態を きちんと 作るには、項目たちを 閉包 でふくらませる必要があるんです。
閉包も FIRST/FOLLOW と同じように 定義 · 計算規則 · 実装 に分けて見ていきましょう — このページは その第一歩、定義 です。

📍 ある場所 · Analyzer.Closure · …/Parsers/Analyzer.cs

閉包は 状態 — 前の 状態 の章で見た、LR項目の集合 Iₓ — の上で動く 演算です。正確には、状態を 完全に埋める 仕事をします。どういうことか見てみましょう。

なぜ「ふくらませる」のか

ある状態が、項目 Expr → • Term を1つだけ抱えているとしましょう。
ドットのすぐ後ろが 非終端記号 Term ですね。つまり、いままさに Term を読もうとしているところです。

ところで Term を読むということは — 結局 Term の 生成規則のうちの1つ を始めるという意味です。
Term → Term '*' Factor かもしれないし、Term → Factor かもしれませんね。
だから それらの生成規則も「いますぐ始められる」状態 として、この状態に一緒に入っていなければなりません。

Expr → • Term 1つだけがぽつんとあるだけだと — Term をどう始めるか が抜けた、不完全な状態 です。
この空いた箇所を埋めて 完全な状態 にするのが 閉包（closure） です。

定義 — 閉包とは

FIRST を一文で 「そのシンボルが導けるもののうち、先頭に来られる 終端記号たち」 と捉えましたね。閉包も、ちょうどそのように一文で捉えられます。

閉包（I） = その状態で 「いままさに始まりうる」 生成規則を 1つも漏らさず引き集めた 項目の集合。

「まさに始まりうる」 — これが核心です。ある項目のドットのすぐ後ろに非終端記号があるということは、「もうすぐその 非終端記号を始める」 という意味なんです。すると、その非終端記号を作る生成規則たちが まさに始まる候補 なので、（ドットを 先頭に置いたまま）すべて引いてこなければなりませんね。

もう少しはっきりと、2つの規則 で書くとこうなります。

① I にもともとあった項目はそのまま残します — 捨てるものは1つもありません。
② ある項目の ドットのすぐ後ろに非終端記号 があれば、その非終端記号の生成規則たちを（ドットを先頭に打って）足します。

②が実際にどんな様子なのか、私たちの文法から一かけら だけ取り出して見てみましょう — 前の 「なぜふくらませるか」 で挙げたあの Expr → • Term の 空いた箇所 を、今度は②がどう埋めるかをです。（これは、これから作る開始状態 I₀ の中で 実際に起きることの 一部 でもあります。）文法はこれです。

   Expr   → Expr '+' Term   |  Term
   Term   → Term '*' Factor  |  Factor
   Factor → '(' Expr ')'     |  id

集合の中に、その Expr → • Term が入っています。

   Expr → • Term

ドットのすぐ後ろが非終端記号 Term ですね。だから②が働きます — 文法から Term の生成規則を2つ見つけて、
まだ何も読んでいないので ドットを先頭に打って集合に足します。

   Expr → • Term
   Term → • Term '*' Factor      ← ②で引き込まれる
   Term → • Factor               ← ②で引き込まれる

ドットの後ろの非終端記号 をたどって、その生成規則が引き込まれてくること — これが ②一回 です。
そして、いま入ってきたばかりの Term → • Factor のドットの後ろ（Factor）にも②がまた適用されて… こうして これ以上引き込まれるものが なくなるまで 続いていきます。

（ここでは I₀ の 一かけら だけ見ました。Accept → • Expr から始めて 最初から最後まで 回して I₀ を 完成させる過程は、次の 計算規則で一段ずつゆっくり見ていきましょう。）

先ほどの 2つの規則（①②） を記号で短く書くと、こうなります。（A → α • B β は LR項目 の章で見た表記そのままです — α·β はドットの前後の記号たち、B はドットのすぐ後ろの非終端記号、γ は B の規則の 右辺です。）

CLOSURE(I) = 下の①②に 閉じている、最も小さい 項目集合

① I のすべての項目を含む。
② A → α • B β があれば（ドットの後ろが非終端記号 B）、B のすべての生成規則 B → • γ も含む。

ここで 「閉じている」 と 「最も小さい」、この2語だけ押さえれば大丈夫です。

  • 閉じている（closed） — 「もう足すものがない」 状態です。②をいくら再適用しても新しく出てくるものがなければ 閉じている、というわけですね。
    { Expr → • Term } 1つだけだと、ドットの後ろ Term の規則が抜けているので まだ 閉じていません。Term のものを入れ、 そこからさらに呼び出される Factor のものまで全部入れて はじめて 閉じます。（だから名前も 閉じる = 閉包。）
  • 最も小さい — 「ちょうど必要なぶんだけ」 です。②が 命じた 項目だけ入れて、命じてもいないものを余計に入れたりは しません。

📎 参考 — これは「LR(0)」閉包です。 ここの項目たちは 生成規則 + ドット だけなので、「次にどんなトークンが 来なければならない」 といった 先読み（lookahead） 情報がありません。だから非終端記号も 名前だけ見て 一度ずつだけ 展開すればよいのです（同じ非終端記号を二度展開することはありません）。
「では、どのトークンでまとめるか（reduce）」 は — 閉包ではなく 後の段階 で決めます。SLR は FOLLOW で、LALR は別途計算した先読みでです。閉包の段階では、そこまでは気に しません。

次へ

定義は 「②に閉じた最も小さい集合」 と言いました。
では、それを 実際にどう求めるのか — 一段ずつ自分で回してみるのが次です。

👉 閉包 · 計算規則

👈 前へ: 状態

Edit this page