RIPAL: Responsive and Intuitive Parsing for the Analysis of Language

Background

We've seen a couple of LR(0) production closure examples.

In this section, we will illustrate a closure calculation that involves an ε production.

Motivating example

Example

Observe the following grammar:

S → A
A → ε

This grammar has the following augmented grammar:

S' → S $
S → A
A → ε

Recall that is has the following parse table:

	$	S	A	S'
state₁	reduce₃	goto₃	goto₂
state₂	reduce₂
state₃	accept

Recall the following parse of input string ε:

Input queue	Parse stack	Action
	1	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 2	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 3	Accept, since this action corresponds to state₃ and $ in our parse table

The fundamental question

Given a qualified production as follows:

N → sym_pre₁ sym_pre₂ ... sym_{pre_{n_pre}} · N_next sym_post₁ sym_post₂ ... sym_{post_{n_post}}

The fundamental question to assess in this context is:

How far can we progress through our productions without processing any input symbols OR with shifting and reducing input symbols such that we arrive back in the initial parse state?

The fundamental answer

Starting with the qualified production:

S' → · S $

we see the typical chaining of reduce and goto actions through the following sequence of parse stack states:

1
1 A
1 A 2
1 S
1 S 3

This chaining is fairly typical, with the exception of the transition from stack state 1 to state 1 A.

In this transition, we don't need to shift any symbol onto the parse stack before reducing according to production:

A → ε

Since ε is the empty string and not an input symbol, we can remain in state₁ in the processing of its corresponding production. We don't need to shift into an additional state because there is no terminal to shift.

As a result, the closure of the qualified production set:

{S' → · S $}

is:

{S' → · S $, S → · A, A → · ε, A → ε ·}

Conclusion

We've seen many examples of qualified production closure calculations.

Next, we will introduce the formal definition of this closure calculation.