SLR(1) Parsing for the Grammar (E \to E+T \mid T,; T \to T*F \mid F,; F \to t,d)

We are given the grammar:

[ E \to E + T \mid T,\quad T \to T * F \mid F,\quad F \to t, d ]

The goal is to construct:

1. the SLR state transition diagram (based on LR(0) item sets and GOTO transitions), and
2. the SLR parse table (actions based on LR(0) items, with reductions restricted by FOLLOW sets).

Key definitions used throughout:

• LR(0) item
• closure
• GOTO
• FOLLOW set

Note: This section performs the construction mechanically from the grammar, using standard SLR(1) methodology: build LR(0) canonical item sets, compute FOLLOW sets, then fill ACTION/GOTO using the SLR rule for reductions.

Step 1: Augment the grammar, then compute FOLLOW sets

Augment with a new start symbol:

[ S' \to E ]

We use end-marker ($).

FIRST/LR(0) mechanics are not strictly needed for SLR reductions; only FOLLOW sets are required.

Compute FOLLOW sets:

• (\text{FOLLOW}(E)):
  In (E \to E + T), the symbol after the (E) is terminal (+), so (+\in\text{FOLLOW}(E)).
  Also, since (S' \to E), ($\in\text{FOLLOW}(E)).
  Hence: [ \text{FOLLOW}(E)={+, $} ]

• (\text{FOLLOW}(T)):
  In (E \to E + T), (T) is followed by (+), so (+\in\text{FOLLOW}(T)).
  In (E \to T), (T) appears at the end of RHS, so (\text{FOLLOW}(T)) includes (\text{FOLLOW}(E)).
  Thus: [ \text{FOLLOW}(T)={+, $} ]

• (\text{FOLLOW}(F)):
  In (T \to T * F), (F) is followed by (), so (\in\text{FOLLOW}(F)).
  In (T \to F), (F) appears at the end, so (\text{FOLLOW}(F)) includes (\text{FOLLOW}(T)).
  Hence: [ \text{FOLLOW}(F)={*, +, $} ]

These FOLLOW sets will control where reductions occur in the SLR table.

Step 2: Build LR(0) item sets (the basis of the SLR automaton)

We write each LR(0) item as (A \to \alpha \cdot \beta).

Productions:

1. (S' \to E)
2. (E \to E + T)
3. (E \to T)
4. (T \to T * F)
5. (T \to F)
6. (F \to t, d)

Start with the closure of ([S' \to \cdot E]).

• I0
  • (S' \to \cdot E)
  • (E \to \cdot E + T)
  • (E \to \cdot T)
  • (T \to \cdot T * F)
  • (T \to \cdot F)
  • (F \to \cdot t, d)

Compute transitions with GOTO on grammar symbols. The resulting canonical LR(0) collection is:

• I0

  • (S' \to \cdot E)
  • (E \to \cdot E + T)
  • (E \to \cdot T)
  • (T \to \cdot T * F)
  • (T \to \cdot F)
  • (F \to \cdot t, d)

• I1 = GOTO(I0, E)

  • (S' \to E \cdot)
  • (E \to E \cdot + T)

• I2 = GOTO(I0, T)

  • (E \to T \cdot)
  • (T \to T \cdot * F)

• I3 = GOTO(I0, F)

  • (T \to F \cdot)

• I4 = GOTO(I0, t)

  • (F \to t \cdot d)

• I5 = GOTO(I0, d) does not exist (no item has dot before (d) from I0).

Continuing from each relevant item set:

• I6 = GOTO(I1, '+')

  • from (E \to E \cdot + T): (E \to E + \cdot T)
  • closure adds:
    • (T \to \cdot T * F)
    • (T \to \cdot F)
    • (F \to \cdot t, d)
  • so:
  • I6
    • (E \to E + \cdot T)
    • (T \to \cdot T * F)
    • (T \to \cdot F)
    • (F \to \cdot t, d)

• I7 = GOTO(I2, '*')

  • from (T \to T \cdot * F): (T \to T * \cdot F)
  • closure adds:
    • (F \to \cdot t, d)
  • so:
  • I7
    • (T \to T * \cdot F)
    • (F \to \cdot t, d)

• I8 = GOTO(I4, d)

  • from (F \to t \cdot d): (F \to t d \cdot)
  • so:
  • I8
    • (F \to t d \cdot)

• I9 = GOTO(I6, T)

  • from (E \to E + \cdot T): (E \to E + T \cdot)
  • also from (T \to \cdot T * F) via GOTO on (T):
    • (T \to T \cdot * F)
  • so:
  • I9
    • (E \to E + T \cdot)
    • (T \to T \cdot * F)

• I10 = GOTO(I6, F)

  • from (T \to \cdot F): (T \to F \cdot)
  • I10
    • (T \to F \cdot)
  • (This is equivalent in content to I3; in canonical construction it would unify if identical. Here, we keep a consistent set; you can merge if you detect equality.)

• I11 = GOTO(I7, F)

  • from (T \to T * \cdot F): (T \to T * F \cdot)
  • I11
    • (T \to T * F \cdot)

To keep the diagram unambiguous, we’ll use the unique sets as follows (merging identical ones like (T \to F \cdot)):

Unique canonical LR(0) item sets:

• I0, I1, I2, I3(=I10), I4, I6, I7, I8, I9, I11

Step 3: SLR State transition diagram (from LR(0) item sets)

We add transitions labeled by grammar symbols using GOTO.

Transitions:

• From I0

  • on (E) → I1
  • on (T) → I2
  • on (F) → I3
  • on (t) → I4

• From I1

  • on (+) → I6

• From I6

  • on (T) → I9
  • on (F) → I3
  • on (t) → I4

• From I2

  • on (*) → I7

• From I7

  • on (F) → I11
  • on (t) → I4

• From I4

  • on (d) → I8

And accepting is when state contains (S' \to E\cdot).

Step 4: Label productions for reduce numbers

Assign production numbers:

1. (E \to E + T)
2. (E \to T)
3. (T \to T * F)
4. (T \to F)
5. (F \to t, d)

We will write reduces as “r1”, “r2”, etc.

Step 5: Construct the SLR parse table

We use:

• (\text{FOLLOW}(E)={+, $})
• (\text{FOLLOW}(T)={+, $})
• (\text{FOLLOW}(F)={*, +, $})

Now fill ACTION/GOTO by the rules.

ACTION table columns: (t, d, +, *, $)
GOTO table columns: (E, T, F)

ACTION

• State I0
  • items include (F \to \cdot t d) so on (t): shift I4.
• State I1
  • (S' \to E\cdot) so on ($): accept.
• State I2
  • (E \to T\cdot) so reduce by production 2 on FOLLOW(E)=({+, $})
  • (T \to T \cdot * F) so on (*): shift I7
• State I3
  • (T \to F\cdot) so reduce by production 4 on FOLLOW(T)=({+, $})
• State I4
  • (F \to t \cdot d) so on (d): shift I8
• State I6
  • items include (F \to \cdot t d), so on (t): shift I4
• State I7
  • (F \to \cdot t d) so on (t): shift I4
  • (no terminal after dot besides (t))
• State I8
  • (F \to t d\cdot) reduce by production 5 on FOLLOW(F)=({*, +, $})
• State I9
  • (E \to E + T\cdot) reduce by production 1 on FOLLOW(E)=({+, $})
  • (T \to T \cdot * F) so on (*): shift I7
• State I11
  • (T \to T * F\cdot) reduce by production 3 on FOLLOW(T)=({+, $})

GOTO

From the transition diagram:

• I0: GOTO(I0,E)=I1, GOTO(I0,T)=I2, GOTO(I0,F)=I3
• I1: (no nonterminal goto besides via + which is shift, so none)
• I2: none besides shifts
• I6: GOTO(I6,T)=I9, GOTO(I6,F)=I3
• I7: GOTO(I7,F)=I11
• others: as applicable from transitions