9.6. SLR(1) Parsing Table

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.

1. There is an accept action in column $ provided state q contains LR(0) item S′ → S ⋅, where S′ is the new start state.

2. 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.

3. For each column labeled by a token t, the table contains action reduce n if

   1. state q contains LR(0) item N → α ⋅,
   2. production N → α is the nth production, and
   3. t is in FOLLOW(N).

4. 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.

Example

---

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:

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

Now let's add the reduce actions. Action r n requests a reduce by production number n.

Finally, we add the Goto entries.