Table of Contents

Closure Β· How to Compute

πŸŽ“ This is an advanced track chapter.
In the previous Closure Β· Definition β€” we said CLOSURE(I) is "the smallest set closed under β‘‘."
The definition only tells us "which set it is." This page shows how you actually compute it β€” and we'll do it by building, by hand, the real start state Iβ‚€ of our example grammar, one step at a time.

The method

The method itself is simple.

Start from some item set I, and apply rule β‘‘ one step at a time until there's nothing left to add.

The key is "until there's nothing left to add." The set grows one step at a time, and at some moment nothing new comes in β€” that's when it's closed, and you stop.
It's exactly the same flavor as the fixed point (repeat until nothing changes) we saw in FIRST/FOLLOW.

Before that β€” where do we start? (the augmented grammar)

Closure starts from a single start item. Where does that one item come from?

Here a small device shows up. An LR parser tacks exactly one start rule onto the very top of the original grammar β€” Accept β†’ Expr. (Expr is the original start symbol of our grammar.)
A grammar with one extra start rule laid on top like this is called an augmented grammar.

Why tack on such a thing? β€” so the parser can cleanly tell that "now the whole input is done."
The original start symbol Expr shows up all over the inside of expressions (the Expr in Expr '+' Term, the Expr in '(' Expr ')', and so on). So finishing a single Expr doesn't mean the whole input is done β€” it might just be part of a bigger expression.
But if you lay on a single Accept that isn't used anywhere else β€” then the very moment you finish Accept β†’ Expr is exactly "the whole thing is done (accept)", and you know it at a glance. (How this "done signal" actually gets used is something we'll tie up in the parse table chapter. For now we just use it as a starting point.)

In plain terms β€” picture a shipping box. A box can have yet another smaller box inside it (just as our Expr has another Expr inside, like in '(' Expr ')'). Then it gets confusing "which one is the outermost box."
So you put one more outer box wrapping the whole thing and write on it "this is the final outer wrapping."
That outer box is exactly Accept β†’ Expr β€” once even the outer box is closed (completed), you know at a glance that "it's all done (accept)!"

So the starting item is just one β€” Accept β†’ β€’ Expr.
The result of running closure on it is precisely the start state Iβ‚€. Let's watch it grow with our own eyes.

One step at a time β€” watching Iβ‚€ grow

Before we follow along, let me lay the augmented grammar out here. (So that at each step we can pin down right away which production comes in.)

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

Start β€” 1 item. We begin from a single virtual start item.

   Accept β†’ β€’ Expr

Step 1. After the dot in Accept β†’ β€’ Expr comes Expr.
Looking at the Expr line in the grammar, its productions are the two Expr β†’ Expr '+' Term and Expr β†’ Term.
We add these two to the set β€” with the dot at the very front, since we haven't read anything yet.

   Accept β†’ β€’ Expr
   Expr   β†’ β€’ Expr '+' Term       ← new
   Expr   β†’ β€’ Term                ← new

β†’ 3 items.

Step 2. Let's look at what comes after the dot in the two that just came in.

  • After the dot in Expr β†’ β€’ Term comes Term. In the grammar, Term's productions are the two Term β†’ Term '*' Factor and Term β†’ Factor. We add these two (with the dot at the very front).
  • After the dot in Expr β†’ β€’ Expr '+' Term comes Expr too β€” but Expr was already expanded in Step 1 (those two rules are already in the set). So there's nothing new to add.
   Accept β†’ β€’ Expr
   Expr   β†’ β€’ Expr '+' Term
   Expr   β†’ β€’ Term
   Term   β†’ β€’ Term '*' Factor     ← new
   Term   β†’ β€’ Factor              ← new

β†’ 5 items.

Step 3. Again, let's look at what comes after the dot in the two that just came in.

  • After the dot in Term β†’ β€’ Factor comes Factor. In the grammar, Factor's productions are the two Factor β†’ '(' Expr ')' and Factor β†’ id. We add these two.
  • After the dot in Term β†’ β€’ Term '*' Factor comes Term β†’ already expanded, so nothing new.
   Accept β†’ β€’ Expr
   Expr   β†’ β€’ Expr '+' Term
   Expr   β†’ β€’ Term
   Term   β†’ β€’ Term '*' Factor
   Term   β†’ β€’ Factor
   Factor β†’ β€’ '(' Expr ')'        ← new
   Factor β†’ β€’ id                  ← new

β†’ 7 items.

Step 4. Let's look at the remaining dots. After the dot in Factor β†’ β€’ '(' Expr ')' comes '(', and after the dot in Factor β†’ β€’ id comes id β€” both are terminals.
A terminal has no production to start from, so there's nothing to expand. And nothing left to add either β†’ it's closed. Done!

Wrapping up β€” this is Iβ‚€

The set grew 1 β†’ 3 β†’ 5 β†’ 7, and then stopped, because there was nothing left to grow.
This final 7-item closed set is precisely the start state Iβ‚€ of our grammar.

   Iβ‚€ = CLOSURE( { Accept β†’ β€’Expr } )
      = the 7 items where the productions of AcceptΒ·ExprΒ·TermΒ·Factor all gather with the dot at the very front

"Everything that can come at the very front" is what's gathered into Iβ‚€ β€” the ( and id after the dot in Factor β†’ β€’'(' Expr ')' and Factor β†’ β€’id are exactly the terminals you can read first. (Hey, that's the same as FIRST(Expr) = { '(', id }! That's no coincidence.)

One more step β€” the author writes this process as 'recursion'

Just now we watched the set grow sideways one step at a time. The author's design notes write the same computation in a slightly more compact form β€” a recursive shape where Closure contains another Closure inside it.

Once you know how to read it, it isn't hard.

  • Closure({ … }) is a mark meaning "these items still need more expanding."
  • The red symbol is the symbol after the dot we're currently expanding (the marker).
  • Each time we go down one line, the productions of that red nonterminal get pulled in as a new Closure({ … }). (Items already sorted out on an earlier line are omitted, and all gathered on the very last line.)
Closure({ Accept β†’ β€’ Expr })
 = { Accept β†’ β€’ Expr,   Closure({ Expr β†’ β€’ Expr '+' Term,  Expr β†’ β€’ Term }) }
 = { Expr β†’ β€’ Expr '+' Term,  Expr β†’ β€’ Term,   Closure({ Term β†’ β€’ Term '*' Factor,  Term β†’ β€’ Factor }) }
 = { Term β†’ β€’ Term '*' Factor,  Term β†’ β€’ Factor,   Closure({ Factor β†’ β€’ '(' Expr ')',  Factor β†’ β€’ id }) }
 = { Factor β†’ β€’ '(' Expr ')',  Factor β†’ β€’ id }      (after the dot is '(' Β· id β€” terminals, so it stops)
 = { Accept→‒Expr, Expr→‒Expr'+'Term, Expr→‒Term, Term→‒Term'*'Factor, Term→‒Factor, Factor→‒'('Expr')', Factor→‒id }   = I₀

At the very end the Closure({ … }) disappeared, didn't it? That means there's nothing left to expand β€” that is, it's closed. And that's Iβ‚€.
(The promise that "a nonterminal already expanded won't be expanded again" holds here too β€” which is why the Expr in Expr β†’ β€’Expr '+' Term and the Term in Term β†’ β€’Term '*' Factor don't get caught as markers. Otherwise it would loop forever.)

And this recursive shape of Closure calling Closure is the spitting image of the code in the next implementation, result.UnionWith(Closure( … )). It's just what we wrote by hand, moved straight into code.
(The author's original notes are drawn with their own test grammar S' β†’ G, G β†’ E = E | f, …, but the expansion principle is exactly the same.)

Next

This "one step at a time until it closes" that we ran by hand β€” how did the code do it?

πŸ‘‰ Closure Β· Implementation

πŸ‘ˆ Previously: Closure Β· Definition

Edit this page