We've now seen the method an LR(0) parses uses to recognize a string as a part of a single-terminal language.
In this section, we will extend that example to include multiple terminals.
Example
Observe the following grammar:
S → ab
This grammar has the following augmented grammar:
S' → S $
S → ab
It has the following LR(0) parse table:
| a | b | $ | S | S' | |
| state1 | shift2 | goto4 | |||
| state2 | shift3 | ||||
| state3 | reduce2 | reduce2 | reduce2 | ||
| state4 | accept |
Example
Parsing input string ab:
| Input queue | Parse stack | Action |
|---|---|---|
| ab | 1 | Apply action of shift2 which corresponds to state1 and a in our parse table |
| b | 1 a 2 | Apply action of shift3 which corresponds to state2 and b in our parse table |
| 1 a 2 b 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, observe how two terminals, a and b, are shifted onto the parse stack before a reduce action is applied. The table's parse states facilitate this so that we can perform a reduction that requires two terminals, a and b, to be reduced to nonterminal S once state3 has been reached. Here, the intermediate state of state2 represents a time in the parsing procedure when the terminal a has been encountered and the parser is waiting on terminal b.
Once all symbols has been processed via a reduction, we can revert to state1 and wrap up our parsing procedure.
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 | Reject, since no action corresponds to state2 and a in our parse table |
We've now seen an LR(0) parsing procedure for a grammar containing a production with multiple terminals. Next, we will examine the parsing procedure for a grammar that accepts the empty string.
GitHub Repository: https://github.com/bprollinson/ripal
Copyright © 2017 Brendan Rollinson-Lorimer