RIPAL: Responsive and Intuitive Parsing for the Analysis of Language

Background

We've seen the process for constructing and LR(0) DFA for a grammar containing a production chain that derives terminal.

In this section, we will expand this process to handle a grammar containing a production chain that derives ε, the empty string.

Our grammar

The language we will be analzying is specified by the following grammar:

S → A
A → ε

This grammar has the following augmented grammar:

S' → S $
S → A
A → ε

Our parse table

This grammar has the following LR(0) parse table:

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

Parsing 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

Initial state

As per our standard process, we will construct our initial qualified production rule.

Our initial set of qualified productions is:

{S' → · S}

Calculating the closure set, we end up with:

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

In this case, we are able to move the dot past the ε symbol because no input symbol needs to be processed in doing so.

As a result, our initial parse state is:

DFA state 1. This state contains the following productions: S prime produces dot S $, S produces dot A, A produces dot ε, A produces ε dot.

Handing nonterminal A

Observe the following sequence of parse stack states encountered in the parsing example above:

1
1 A
1 A 2
1 S

In this language, because the production A → ε does not produce a terminal, we don't need to shift any terminals onto the stack before applying the reduction.

As a result, we can apply the actions of reduce followed by goto right away.

Starting with the following qualified production from state₁:

S → · A

we can shift the dot past nonterminal A and state state₂ with the following production set:

{S → A ·}

Since the dot is at the end of the production, this closure can't be further expanded. As a result, state₂ can be represented as:

DFA state 2. This state contains the following production: A produces A dot.

We can represent this transition into state₂ with the following DFA:

DFA containing two states. State 1 contains the following productions: S prime produces dot S $, S produces dot A, A produces dot ε, A produces ε dot. State 2 contains the following production: A produces A dot. State 1 transitions to state 2 on nonterminal symbol A.

Once state₂ is reached, nontermal A can be reduced to S, and we can return to state₁.

Handling end of string

After reducing A to S, from state₁, we want to process the end of string according to our standard approach.

Extending our DFA, we end up with a final diagram of:

DFA containing four states. State 1 contains the following productions: S prime produces dot S $, S produces dot A, A produces dot ε, A produces ε dot. State 2 contains the following production: A produces A dot. State 1 transitions to state 2 on nonterminal symbol A. State 3 contains the following production: S prime produces S dot $. State 1 transitions to state 3 on nonterminal symbol S. State 4 contains the following production: S prime produces S $ dot. State 3 transitions to state 4 on end of string symbol $. State 4 is an accepting state.

Conclusion

We've seen the LR(0) DFA construction process for a grammar that derives the empty string, ε through a production chain.

Next, we will investigate the DFA contruction for a grammar containing a production that produces multiple nonterminal symbols.