|
Now we turn to a class of parsers known collectively as LR parsers. The L indicates that the parser reads the input from left to right, and the R indicates that it produces a rightmost derivation (and so is a bottom-up style of parsing).
For technical reasons, we do not want the start symbol to appear on the right-hand side of any production. That is easy to arrange.
If G is a grammar with start nonterminal S, form the augmented grammar G' by adding a new nonterminal S' to G and adding one production, S' → S. The start nonterminal of G' is S'.
I will describe the simplest of the LR parsers, LR(0), using an augmented version of our unambiguous expression grammar as a running example. The start nonterminal is E'.
| 1. E' | → | E |
| 2. E | → | T |
| 3. E | → | E + T |
| 4. T | → | F |
| 5. T | → | T * F |
| 6. F | → | n |
| 7. F | → | ( E ) |
|