|
It is not necessary to keep the LR(0) finite-state machine around. Instead, the information contained in the finite-state machine can be stored in a table.
The conventional way to store that information is in table with rows labeled by states and columns labeled by: tokens, the special symbol $ and nonterminals, excluding the new start symbol E′.
The columns labeled by tokens are called the action columns. The columns labeled by nonterminals are called goto columns.
Consider a row labeled by state q.
There is an accept action in column $ provided state q contains LR(0) item S′ → S ⋅, where S′ is the new start state.
For each column labeled by a token t, the table contains shift n if there is a transition from state q to state n that is labeled by token t.
For each column labeled by a token t, the table contains action reduce n if
For each column labeled by a nonterminal N, the table contains the state q' so that there is a transition from state q to state q' labeled by nonterminal N.
Let's build the parsing table for the grammar whose finite-state machine is shown earlier for our augmented expression grammar.
The FIRST and FOLLOW sets are:
N | FIRST(N) | FOLLOW(N) |
---|---|---|
E′ | {n, (} | {$} |
E | {n, (} | {), +, $} |
T | {n, (} | {), *, +, $} |
F | {n, (, *, +} | {), *, +, $} |
Now, to get started on the parsing table, let's just install the shift and accept actions. A shift action that goes to state q is written s q
Action | Goto | ||||||||
---|---|---|---|---|---|---|---|---|---|
n | + | * | ( | ) | $ | E | T | F | |
0 | s 5 | s 4 | |||||||
1 | s 6 | accept | |||||||
2 | s 7 | ||||||||
3 | |||||||||
4 | s 5 | s 4 | |||||||
5 | |||||||||
6 | s 5 | s 4 | |||||||
7 | s 5 | s 4 | |||||||
8 | s 6 | s 11 | |||||||
9 | s 7 | ||||||||
10 | |||||||||
11 |
Now let's add the reduce actions. Action r n requests a reduce by production number n.
Action | Goto | ||||||||
---|---|---|---|---|---|---|---|---|---|
n | + | * | ( | ) | $ | E | T | F | |
0 | s 5 | s 4 | |||||||
1 | s 6 | accept | |||||||
2 | r 2 | s 7 | r 2 | r 2 | |||||
3 | r 4 | r 4 | r 4 | r 4 | |||||
4 | s 5 | s 4 | |||||||
5 | r 6 | r 6 | r 6 | r 6 | |||||
6 | s 5 | s 4 | |||||||
7 | s 5 | s 4 | |||||||
8 | s 6 | s 11 | |||||||
9 | r 3 | s 7 | r 3 | r 3 | |||||
10 | r 5 | r 5 | r 5 | r 5 | |||||
11 | r 7 | r 7 | r 7 | r 7 |
Finally, we add the Goto entries.
Action | Goto | ||||||||
---|---|---|---|---|---|---|---|---|---|
n | + | * | ( | ) | $ | E | T | F | |
0 | s 5 | s 4 | 1 | 2 | 3 | ||||
1 | s 6 | accept | |||||||
2 | r 2 | s 7 | r 2 | r 2 | |||||
3 | r 4 | r 4 | r 4 | r 4 | |||||
4 | s 5 | s 4 | 8 | 2 | 3 | ||||
5 | r 6 | r 6 | r 6 | r 6 | |||||
6 | s 5 | s 4 | 9 | 3 | |||||
7 | s 5 | s 4 | 10 | ||||||
8 | s 6 | s 11 | |||||||
9 | r 3 | s 7 | r 3 | r 3 | |||||
10 | r 5 | r 5 | r 5 | r 5 | |||||
11 | r 7 | r 7 | r 7 | r 7 |
|