RIPAL: Responsive and Intuitive Parsing for the Analysis of Language

Background

We've seen the motivations for using the concept of the LR(0) closure in our parser construction process. We've also seen the utility of the production dot symbol in this context.

In this section, we will begin to flesh out this closure calculation.

Motivating example

Observe the following grammar:

S → A
A → B
B → C
C → c

This grammar has the following augmented grammar:

S' → S $
S → A
A → B
B → C
C → c

Recall that it has the following parse table:

	c	$	S	A	B	C	S'
state₁	shift₂		goto₆	goto₅	goto₄	goto₃
state₂	reduce₅	reduce₅
state₃	reduce₄	reduce₄
state₄	reduce₃	reduce₃
state₅	reduce₂	reduce₂
state₆		accept

Recall the following parse of input string c:

Input queue	Parse stack	Action
c	1	Apply action of shift₂ which corresponds to state₁ and c in our parse table
	1 c 2	Apply action of reduce₅ which corresponds to state₂ and $ in our parse table
	1 C	Apply action of goto₃ which corresponds to state₁ and C in our parse table
	1 C 3	Apply action of reduce₄ which corresponds to state₃ and $ in our parse table
	1 B	Apply action of goto₄ which corresponds to state₁ and B in our parse table
	1 B 4	Apply action of reduce₃ which corresponds to state₄ and $ in our parse table
	1 A	Apply action of goto₅ which corresponds to state₁ and A in our parse table
	1 A 5	Apply action of reduce₂ which corresponds to state₅ and $ in our parse table
	1 S	Apply action of goto₆ which corresponds to state₁ and S in our parse table
	1 S 6	Accept, since this action corresponds to state₆ and $ in our parse table

Also, recall that we are chaining the processing of the following productions via the goto and reduce actions:

S → A
A → B
B → C

The fundamental question

Using the above example, let's start with a qualified version of our first production as follows:

S' → · S $

From this position, we know we need to first process the reduction to nonterminal S.

The fundamental question to assess in this context is:

How far can we progress through our productions without processing any input symbols?

Intuitive argument

Since the dot appears before the symbol S, we can ask this same question about the following production:

S → A

Adding the dot to the beginning of the right-hand side (since nothing has been processed so far from this next production), we end up with:

S → · A

Repeating this process, we can use this same argument to include all of the following qualified productions:

S' → · S $
S → · A
A → · B
B → · C

But what about the production C → c?

Thinking about the derivation of the string c, we can certainly reach the following position without processing the terminal c:

C → · c

Keep in mind that in bottom-up parsing, we derive strings in reverse. With that in mind, we can map the actions corresponding to the expansion of our closure from:

S → · S $

to:

C → · c

to the chain of goto and reduce actions related to the reduction of nonterminals S, A, B and C.

However, the shifting of terminal c onto the parse stack does not fit this pattern.

The fundamental answer

Starting with qualified production:

S' → · S $

we can chain productions and reach the following set of qualified productions as our closure:

S' → · S $
S → · A
A → · B
B → · C
C → · c

Conclusion

We've seen a basic LR(0) closure calculation.

Next, we will illustrate a more advanced closure calculation.