SLR(1) Parsing Table for the Expression Grammar $E \rightarrow E+T \mid T,\; T \rightarrow T*F \mid F,\; F \rightarrow (E)\mid id$

We build an SLR(1) parsing table for the grammar:

$$\begin{aligned} E &\rightarrow E + T \mid T\\ T &\rightarrow T * F \mid F\\ F &\rightarrow (E)\mid id \end{aligned}$$

using the standard SLR(1) method:

• construct LR(0) item sets via closure and goto;
• compute FOLLOW sets using FOLLOW;
• add reduce actions only on terminals in FOLLOW of the reduced nonterminal, using SLR(1) rule.

Key symbols/terminals: \{id,+,*,(,),\}$where$$ $ is end-marker.

Note (Augmented grammar). For LR parsing we first add a new start production: $S' \rightarrow E.$ We then compute item sets for this augmented grammar.

Important keyword definitions (used throughout)

• LR(0) item
• closure
• goto
• FOLLOW
• SLR(1) parsing table

FOLLOW sets (final)

Let \ $ be end-marker.

$$\begin{aligned} FOLLOW(E) &= \{\, +,\; ),\; \$ \,\}\\ FOLLOW(T) &= \{\, +,\; ),\; \$ \,\}\\ FOLLOW(F) &= \{\, +,\; *\; ,\; ),\; \$ \,\} \end{aligned}$$

Check intuition.

• $+$ and $)$ naturally follow expressions inside $(E)$ or after completing $E+T$.
• $*$ follows an $F$ because $T \rightarrow T*F$.
• \ $follows$E$ at end of input (accept state).

LR(0) states (canonical set enumeration)

We use item notation like $A\rightarrow \alpha\cdot\beta$. Let the set of items for each state be:

$I_0$

$$\begin{aligned} S' &\rightarrow \cdot E\\ E &\rightarrow \cdot E + T\\ E &\rightarrow \cdot T\\ T &\rightarrow \cdot T * F\\ T &\rightarrow \cdot F\\ F &\rightarrow \cdot (E)\\ F &\rightarrow \cdot id \end{aligned}$$

Transitions from $I_0$:

• on $E$ to $I_1$
• on $T$ to $I_2$
• on $F$ to $I_3$
• on $( to$I_4$
• on $id$ to $I_5$

$I_1$

$$\begin{aligned} S' &\rightarrow E\cdot\\ E &\rightarrow E\cdot + T \end{aligned}$$

Transitions:

• on $+$ to $I_6$

$I_2$

$$\begin{aligned} E &\rightarrow T\cdot\\ T &\rightarrow T\cdot * F \end{aligned}$$

Transitions:

• on $*$ to $I_7$

$I_3$

$$\begin{aligned} T &\rightarrow F\cdot \end{aligned}$$

(no outgoing transitions)

$I_4$

$$\begin{aligned} F &\rightarrow ( \cdot E)\\ E &\rightarrow \cdot E + T\\ E &\rightarrow \cdot T\\ T &\rightarrow \cdot T * F\\ T &\rightarrow \cdot F\\ F &\rightarrow \cdot (E)\\ F &\rightarrow \cdot id \end{aligned}$$

Transitions:

• on $E$ to $I_8$
• on $T$ to $I_2$
• on $F$ to $I_3$
• on $( to$I_4$
• on $id$ to $I_5$

$I_5$

$$\begin{aligned} F &\rightarrow id\cdot \end{aligned}$$

(no outgoing transitions)

$I_6$

$$\begin{aligned} E &\rightarrow E + \cdot T\\ T &\rightarrow \cdot T * F\\ T &\rightarrow \cdot F\\ F &\rightarrow \cdot (E)\\ F &\rightarrow \cdot id \end{aligned}$$

Transitions:

• on $T$ to $I_9$
• on $F$ to $I_3$
• on $( to$I_4$
• on $id$ to $I_5$
• on $E$ none (already progressed)

$I_7$

$$\begin{aligned} T &\rightarrow T * \cdot F\\ F &\rightarrow \cdot (E)\\ F &\rightarrow \cdot id \end{aligned}$$

Transitions:

• on $F$ to $I_{10}$
• on $( to$I_4$
• on $id$ to $I_5$

$I_8$

$$\begin{aligned} F &\rightarrow (E\cdot )\\ E &\rightarrow E\cdot + T \end{aligned}$$

Transitions:

• on $)$ to $I_{11}$
• on $+$ to $I_6$

$I_9$

$$\begin{aligned} E &\rightarrow E + T\cdot\\ T &\rightarrow T\cdot * F \end{aligned}$$

Transitions:

• on $*$ to $I_7$

$I_{10}$

$$\begin{aligned} T &\rightarrow T * F\cdot \end{aligned}$$

(no outgoing transitions)

$I_{11}$

$$\begin{aligned} F &\rightarrow (E)\cdot \end{aligned}$$

(no outgoing transitions)

Fill ACTION and GOTO tables

We use the standard mapping:

• If an item $[a\rightarrow \alpha\cdot a\beta]$ exists and $goto(I_i,a)=I_j$ (terminal $a$), then ACTION[i,a] = shift j.
• If an item $[A\rightarrow \alpha\cdot]$ exists and $A\neq S'$, then ACTION[i,a] = reduce $A\rightarrow\alpha$ for all $a\in FOLLOW(A)$.
• If an item $[S'\rightarrow E\cdot]$ exists, then ACTION[i,$$$]=accept.

Production numbering (for reduce actions):

1. $E\rightarrow E+T$
2. $E\rightarrow T$
3. $T\rightarrow T*F$
4. $T\rightarrow F$
5. $F\rightarrow (E)$
6. $F\rightarrow id$

ACTION table (entries: shift s, reduce r# , accept acc)

Terminals order: id,\; +,\; *,\; (,\; ),\; \.

How to read rows (example).

• In state $I_1$: item $S'\rightarrow E\cdot$ gives accept on \ $. Also$E\rightarrow E\cdot + T$gives shift on$+$to$I_6$.
• In state $I_2$: item $E\rightarrow T\cdot$ implies reduce by (2) on terminals in $FOLLOW(E)$; plus we also have $T\rightarrow T\cdot * F$ so shift on $*$.

GOTO table (nonterminals $E,T,F$)