Table of Contents

Closure Β· Definition

πŸŽ“ This is an Advanced track lesson.
In the previous State chapter β€” we saw that a state is a set of LR items Iβ‚“.
But to build a state properly, you have to inflate its items with a closure.
Just like FIRST/FOLLOW, let's split closure into definition Β· computation rules Β· implementation β€” this page is the first step, the definition.

πŸ“ Where it lives Β· Analyzer.Closure Β· …/Parsers/Analyzer.cs

Closure is an operation that works on a state β€” the set of LR items Iβ‚“ we saw in the previous State chapter. To be precise, its job is to fill a state out completely. Let's see what that means.

Why Do We Have to "Inflate" It

Suppose some state holds a single item, Expr β†’ β€’ Term.
Right after the dot is the nonterminal Term. In other words, we're just about to read a Term.

But reading a Term means β€” in the end, starting one of Term's productions.
It could be Term β†’ Term '*' Factor, or it could be Term β†’ Factor.
So those productions, in their "about to start" form, also have to live in this state alongside the original item.

If all you have is the lone Expr β†’ β€’ Term, then how to start a Term is missing β€” it's an incomplete state.
Filling that gap to make it a complete state is what closure does.

Definition β€” What Closure Is

We pinned FIRST down in one sentence as "of everything that symbol can derive, the terminals that can come at the very front". Closure can be pinned down in one sentence just the same way.

Closure(I) = the set of items you get by gathering, without leaving a single one out, every production in that state that "can just start now."

"Can just start now" β€” that's the heart of it. The fact that a nonterminal sits right after the dot of some item means "we're about to start that nonterminal." So the productions that build that nonterminal are candidates that may just start, and we have to pull them all in (with the dot placed at the very front).

Written out a bit more carefully, as two rules, it goes like this.

β‘  Keep every item that was already in I β€” we throw away nothing.
β‘‘ If some item has a nonterminal right after the dot, add that nonterminal's productions (with the dot marked at the very front).

To see what β‘‘ actually looks like, let's pull off just one slice of our grammar β€” how β‘‘ now fills the gap of that Expr β†’ β€’ Term from the 'why inflate it' section above. (This is also part of what really happens inside the start state Iβ‚€ we'll build soon.) Here's the grammar.

   Expr   β†’ Expr '+' Term   |  Term
   Term   β†’ Term '*' Factor  |  Factor
   Factor β†’ '(' Expr ')'     |  id

Inside the set sits that Expr β†’ β€’ Term.

   Expr β†’ β€’ Term

Right after the dot is the nonterminal Term. So β‘‘ kicks in β€” it finds Term's two productions in the grammar, and
since nothing has been read yet, marks the dot at the very front and adds them to the set.

   Expr β†’ β€’ Term
   Term β†’ β€’ Term '*' Factor      ← pulled in by β‘‘
   Term β†’ β€’ Factor               ← pulled in by β‘‘

Following the nonterminal after the dot and dragging its productions in β€” that's one application of β‘‘.
And the Term β†’ β€’ Factor that just came in has a nonterminal after its dot too (Factor), so β‘‘ applies again… and this keeps going until there's nothing left to pull in.

(Here we looked at just one slice of Iβ‚€. The process of starting from Accept β†’ β€’ Expr and running it from start to finish to complete Iβ‚€, we'll walk through one step at a time in the next chapter, Computation Rules.)

Writing the two rules (β‘ β‘‘) above in short symbolic form gives this. (A β†’ Ξ± β€’ B Ξ² is exactly the notation we saw in the LR item chapter β€” Ξ±Β·Ξ² are the symbols before and after the dot, B is the nonterminal right after the dot, and Ξ³ is the right-hand side of a B rule.)

CLOSURE(I) = the smallest item set that is closed under β‘ β‘‘ below

β‘  contains every item of I.
β‘‘ if A β†’ Ξ± β€’ B Ξ² is present (a nonterminal B after the dot), it also contains every production B β†’ β€’ Ξ³ of B.

Here you only need to grasp these two phrases, "closed" and "smallest."

  • closed β€” a state where "there's nothing left to add." No matter how many more times you apply β‘‘, if nothing new comes out, it's closed.
    If all you have is { Expr β†’ β€’ Term }, then the rules for the Term after the dot are missing, so it's not yet closed. Only once you've put in the Term items, and the Factor items that get summoned from there too, does it finally become closed. (That's why the name is closing = closure.)
  • smallest β€” "only as much as is strictly needed." You put in only the items β‘‘ told you to, never something it didn't even ask for.

πŸ“Ž Note β€” this is the "LR(0)" closure. The items here are just production + dot, so they carry no lookahead information like "which token must come next." That's why a nonterminal only needs to be expanded once each, just by its name (there's never a reason to expand the same nonterminal twice).
"And so which token to reduce on" β€” that's decided not by closure but by a later stage. SLR decides it with FOLLOW, and LALR with a separately computed lookahead. At the closure stage we don't worry about any of that.

Next

The definition said it's "the smallest set closed under β‘‘."
So next is how you actually compute it β€” running it yourself, one step at a time.

πŸ‘‰ Closure Β· Computation Rules

πŸ‘ˆ Previously: State

Edit this page