|
An SLR(1) parser is supposed to use the finite-state machine to read what is on the stack, from bottom to top, at each step. But the cost of doing that can be avoided.
Instead of storing tokens and nonterminals on the stack, we store states. The state tells the state that the finite-state machine would be in.
Each time a symbol is (conceptually) pushed onto the stack,
When a shift q action is performed, the parser just pushes state q onto the stack and removes one token from the input.
Suppose that action reduce n is performed, where production n is N → α and α has i symbols.
The parser pops the stack i times, to get rid of the states on the stack corresponding to the symbols in α. Then, if the top state is q, the parser pushes goto(q, N).
Let's carry out a parse of n+n*n using those ideas.
| Stack | Input | Action |
|---|---|---|
| $ 0 | n + n * n $ | Shift 5 |
| $ 0 5 | + n * n $ | Reduce 6 (F → n) [goto(0, F) = 3] |
| $ 0 3 | + n * n $ | Reduce 4 (T → F) [goto(0, T) = 2] |
| $ 0 2 | + n * n $ | Reduce 2 (E → T) [goto(0, E) = 1] |
| $ 0 1 | + n * n $ | Shift 6 |
| $ 0 1 6 | n * n $ | Shift 5 |
| $ 0 1 6 5 | * n $ | Reduce 6 (F → n) [goto(6, F) = 3] |
| $ 0 1 6 3 | * n $ | Reduce 4 (T → F) [goto(6, T) = 9] |
| $ 0 1 6 9 | * n $ | Shift 7 |
| $ 0 1 6 9 7 | n $ | Shift 5 |
| $ 0 1 6 9 7 5 | $ | Reduce 6 (F → n) [goto(7, F) = 10] |
| $ 0 1 6 9 7 10 | $ | Reduce 5 (T → T * F) [goto(6, T) = 9] |
| $ 0 1 6 9 | $ | Reduce 3 (E → E + T) [goto(0, E) = 1] |
| $ 0 1 | $ | Accept |
|