RIPAL: Responsive and Intuitive Parsing for the Analysis of Language

Pages

LR(0) parse example - ε production chain

Background

We've seen a method for parsing a production chain that derives a fixed string.

Now, we will illustrate a method for parsing a production chain that derives the empty string ε.

Setup

Example

Observe the following grammar:

S → A
A → ε

This grammar has the following augmented grammar:

S' → S $
S → A
A → ε

It has the following LR(0) parse table:

$ S A S'
state1 reduce3 goto3 goto2
state2 reduce2
state3 accept

Parse example

Example

Parsing input string ε:

Input queue Parse stack Action
1 Apply action of reduce3 which corresponds to state1 and $ in our parse table
1 A Apply action of goto2 which corresponds to state1 and A in our parse table
1 A 2 Apply action of reduce2 which corresponds to state2 and $ in our parse table
1 S Apply action of goto3 which corresponds to state1 and S in our parse table
1 S 3 Accept, since this action corresponds to state3 and $ in our parse table

This parsing procedure corresponds to the following derivation of the empty string (ε):

S → A → ε

The general flow of this parse is similar to our previous example of handling production chains that derive a terminal symbol. However, since there are not input symbols, we do not need to shift any symbols onto the parse stack and can immediately apply our reduce actions in bottom-up order.

Here, state2 represents a point in our parse when our first reduction (to nonternal A) has occurred while state3 represents a point when our reduction to the start symbol S has been subsequently applied.

Example

Failing to parse input string a:

Input queue Parse stack Action
a 1 Reject, since no action corresponds to state1 and a in our parse table

Note

This example is a bit of a cheat because Σ = {}. However, the illustration is still relevant.

Conclusion

We've now seen some examples of parsing input strings beloning to context-free languages with production chains in their grammars. We have essentially gone deep with productions. Next, we will go wide and look at parsing techniques and analysis related to multi-nonterminal productions.

GitHub Repository: https://github.com/bprollinson/ripal

Copyright © 2017 Brendan Rollinson-Lorimer