|
An LR parser finds the handle (or decides to do a shift) by reading the stack from bottom to top using a finite-state machine. The state in which the machine stops tells the parser what to do.
For an LR(0) parser, each state of the finite-state machine is labeled by a set of LR(0) items.
Suppose that S′ is the start state of an augmented grammar, and the sole production for S′ is S′ → S.
The start state is labeled by the closure of set {S′ → ⋅ S}. Here is the start state for our augmented expression grammar.
_____________ | E′ → ⋅ E | | E → ⋅ T | | E → ⋅ E + T | | T → ⋅ F | | T → ⋅ T * F | | F → ⋅ n | | F → ⋅ ( E ) | |_____________|
Remark. This start state happens to include all of the productions. That does not always happen. You only get the LR(0) items that come from the closure process.
Now find all of the symbols that immediately follow a dot in the start state. There is a transition coming out of the start state for each of those symbols.
In the state shown above, there are 5 symbols that follow a dot: E, T, F, n and (.
For each of those symbols σ, find all of the LR(0) items in the current state where σ immediately follows the dot.
Make a new state qσ, and put into qσ all of those items with the dot moved to just after σ.
Now take a closure in that state. The transition labeled σ goes to state qσ.
An example makes that much more clear. In the start state shown above, there are two LR(0) items with E immediately after the dot.
| E′ → ⋅ E |
| E → ⋅ E + T |
Moving the dot across E in those items yields
| E′ → E ⋅ |
| E → E ⋅ + T |
Forming the closure of that set of LR(0) items does not change it because neither of the two items has a dot followed by a nonterminal.
Here is a slightly larger part of the finite state machine.
_____________ _____________ | E′ → ⋅ E | | | | E → ⋅ T |--E-->| E′ → E ⋅ | | E → ⋅ E + T | | E → E ⋅ + T | | T → ⋅ F | |_____________| | T → ⋅ T * F | | F → ⋅ n | | F → ⋅ ( E ) | |_____________|
The transition labeled '(' coming out of the start state goes to a state initially labeled by set
Taking the closure yields
| F → ( ⋅ E ) |
| E → ⋅ T |
| E → ⋅ E + T |
| T → ⋅ F |
| T → ⋅ T * F |
| F → ⋅ n |
| F → ⋅ ( E ) |
You must do the same thing for every state q, providing it with transitions labeled by each symbol that occurs immediately after a dot in q.
It is important to have only one copy of each state. No two states should contain exactly the same set of LR(0) items.
If you find that you have built a new state that has exactly the same items in it as an existing state, make the transition go to that existing state instead.
Here is the complete machine for our augmented expression grammar.
It is too awkward to show the whole thing as a diagram, so states are numbered, and transitions show the state by number.
This finite state machine is shown on page 244 of the Dragon Book.
_____________ | 0 | | E′ → ⋅ E | | E → ⋅ T |---E---> 1 | E → ⋅ E + T |---T---> 2 | T → ⋅ F |---F---> 3 | T → ⋅ T * F |---(---> 4 | F → ⋅ n |---n---> 5 | F → ⋅ ( E ) | |_____________| _____________ | 1 | | E′ → E ⋅ |---+---> 6 | E → E ⋅ + T | |_____________| _____________ | 2 | | E → T ⋅ |---*---> 7 | T → T ⋅ * F | |_____________| _____________ | 3 | | T → F ⋅ | |_____________| _____________ | 4 | | F → ( ⋅ E ) |---E---> 8 | E → ⋅ T |---T---> 2 | E → ⋅ E + T |---F---> 3 | T → ⋅ F |---(---> 4 | T → ⋅ T * F |---n---> 5 | F → ⋅ n | | F → ⋅ ( E ) | |_____________| _____________ | 5 | | F → n ⋅ | |_____________| _____________ | 6 | | E → E + ⋅ T |---T---> 9 | T → ⋅ F |---F---> 3 | T → ⋅ T * F |---(---> 4 | F → ⋅ n |---n---> 5 | F → ⋅ ( E ) | |_____________| _____________ | 7 | | T → T * ⋅ F |---F---> 10 | F → ⋅ n |---(---> 4 | F → ⋅ ( E ) |---n---> 5 |_____________| _____________ | 8 | | E → E ⋅ + T |---+---> 6 | F → ( E ⋅ ) |---)---> 11 |_____________| _____________ | 9 | | E → E + T ⋅ |---*---> 7 | T → T ⋅ * F | |_____________| _____________ | 10 | | T → T * F ⋅ | |_____________| _____________ | 11 | | F → ( E ) ⋅ | |_____________|
|