We've seen the handling of terminals and the empty string in LR(0) parsing.
In this section, we will explore parsing a production chain with an LR(0) parser.
Example
Observe the following grammar:
S → A
A → a
This grammar has the following augmented grammar:
S' → S $
S → A
A → a
It has the following LR(0) parse table:
| a | $ | S | A | S' | |
| state1 | shift2 | goto4 | goto3 | ||
| state2 | reduce3 | reduce3 | |||
| state3 | reduce2 | reduce2 | |||
| state4 | accept |
Example
Parsing input string a:
| Input queue | Parse stack | Action |
|---|---|---|
| a | 1 | Apply action of shift2 which corresponds to state1 and a in our parse table |
| 1 a 2 | Apply action of reduce3 which corresponds to state2 and $ in our parse table | |
| 1 A | Apply action of goto3 which corresponds to state1 and A in our parse table | |
| 1 A 3 | Apply action of reduce2 which corresponds to state3 and $ in our parse table | |
| 1 S | Apply action of goto4 which corresponds to state1 and S in our parse table | |
| 1 S 4 | Accept, since this action corresponds to state4 and $ in our parse table |
This parsing procedure corresponds to the following derivation of string a:
In the above example, we first shift the terminal a onto the parse stack. Then, based on reaching state2, we are able to reduce the terminal a into the nonterminal A.
Then, we are able to use the goto action to transition into a parse state state3 where we are able to reduce A to S.
In this setup, the trick to understanding the setup is to observe that state2 and state3 are used as temporary states in which to apply reductions. state1 is a critical state to observe. In particular, state1 is a baseline parse state that delegates to the next phase of the parsing procedure based on which nonterminal node has been most recently derived via a reduction.
Example
Failing to parse input string aa:
| Input queue | Parse stack | Action |
|---|---|---|
| aa | 1 | Apply action of shift2 which corresponds to state1 and a in our parse table |
| a | 1 a 2 | Apply action of reduce3 which corresponds to state2 and a in our parse table |
| a | 1 A | Apply action of goto3 which corresponds to state1 and A in our parse table |
| a | 1 A 3 | Apply action of reduce2 which corresponds to state3 and a in our parse table |
| a | 1 S | Apply action of goto4 which corresponds to state1 and S in our parse table |
| a | 1 S 4 | Reject, since no action corresponds to state4 and a in our parse table |
We've now seen some examples of parsing input strings relating to a production chain within a context-free grammar. Next, we will look at a similar example that derives the empty string rather than a fixed string.
GitHub Repository: https://github.com/bprollinson/ripal
Copyright © 2017 Brendan Rollinson-Lorimer