We've seen a wide variety of LR(0) parsing techniques.
In this section, we will explore parsing productions that have multiple nonterminals on the right-hand side.
Example
Observe the following grammar:
S → A B
A → a
B → b
This grammar has the following augmented grammar:
S' → S $
S → A B
A → a
B → b
It has the LR(0) parse table:
| a | b | $ | S | A | B | S' | |
| state1 | shift5 | goto6 | goto2 | ||||
| state2 | shift3 | goto4 | |||||
| state3 | reduce4 | reduce4 | reduce4 | ||||
| state4 | reduce2 | reduce2 | reduce2 | ||||
| state5 | reduce3 | reduce3 | reduce3 | ||||
| state6 | accept |
Example input
Parsing input string ab:
| Input queue | Parse stack | Action |
|---|---|---|
| ab | 1 | Apply action of shift5, which corresponds to state1 and a in our parse table |
| b | 1 a 5 | Apply action of reduce3, which corresponds to state5 and b in our parse table |
| b | 1 A | Apply action of goto2, 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 reduce4, which corresponds to state3 and $ in our parse table | |
| 1 A 2 B | Apply action of goto4, which corresponds to state2 and B in our parse table | |
| 1 A 2 B 4 | Apply action of reduce2, which corresponds to state4 and $ in our parse table | |
| 1 S | Apply action of goto6, which corresponds to state1 and S in our parse table | |
| 1 S 6 | Accept, since this action corresponds to state6 and $ in our parse table |
This parsing procedure corresponds to the following derivation of string ab:
In this example, we first reduce terminal a to nonterminal A. We then reduce terminal b to nonterminal B. Finally, we are able to reduce nonterminals A and B to our start symbol S. Since we have reached the end of input at that point, we are able to accept the string as part of our language.
This example illustrates a key difference between LL(1) and LR(0) parsing. In an LR(0) parse, the rightmost derivation of our input string is produced. This happens because although we perform our reductions from left to right, this parse is bottom-up, so the illustration of our derivation will be in the reverse right-to-left derivation order.
Example
Failing to parse input string a:
| Input queue | Parse stack | Action |
|---|---|---|
| a | 1 | Apply action of shift5, which corresponds to state1 and a in our parse table |
| 1 a 5 | Apply action of reduce3, which corresponds to state5 and $ in our parse table | |
| 1 A | Apply action of goto2, which corresponds to state1 and A in our parse table | |
| 1 A 2 | Reject, since state2 and $ correspond to ø in our table |
We've now seen the parsing procedure for an LR(0) language containing a multi-nonterinal production. In particular, we've seen how it results in the rightmost derivation of a string within our language.
Next, we will look at the process for generating an LR(0) parse table from a context-free grammar.