We've now seen the method an LR(0) parser uses to recognize a language containing a multi-terminal production.
In this section, we will illustrate the parsing procedure for a language that contains no terminals and instead contains only the empty string.
Example
Observe the following grammar:
S → ε
This grammar has the following augmented grammar:
S' → S $
S → ε
It has the following LR(0) parse table:
| $ | S | S' | |
| state1 | reduce2 | goto2 | |
| state2 | accept |
Example
Parsing the empty input string ε:
| Input queue | Parse stack | Action |
|---|---|---|
| 1 | Apply action of reduce2 which corresponds to state1 and $ in our parse table | |
| 1 S | Apply action of goto2 which corresponds to state1 and S in our parse table | |
| 1 S 2 | Accept, since this action corresponds to state2 and $ in our parse table |
This parsing procedure corresponds to the following derivation of the empty string (ε):
In this example, we can apply the reduce action without first shifting any symbols onto the parse stack. This is permissible because ε represents an empty set of input symbols. As a result, we can immediately use the reduce and goto actions to reach state2 and then accept.
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.
We've seen parse examples for LR(0) languages that contain a finite string and also the language that contains the empty string. Next, we will examine the parsing procedure for a grammar that can derive a string indirectly via a production chain.
GitHub Repository: https://github.com/bprollinson/ripal
Copyright © 2017 Brendan Rollinson-Lorimer