SLR1 Conflict Analysis for the Expression Grammar | AI Research

SLR(1) Conflict Analysis for the Expression Grammar

Verified Sources

Nov 7, 2026

We analyze the grammar:

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

To determine whether it is SLR(1), we use the SLR(1) construction: build an LR(0) automaton (items and transitions), then fill the ACTION table using FOLLOW sets for reduce actions. An SLR(1) grammar must have no shift-reduce or reduce-reduce conflicts in the resulting ACTION/GOTO tables.

Key keyword concepts:

LR(0) item (the dot position)
FOLLOW set
shift-reduce conflict
reduce-reduce conflict

Claim: This grammar is SLR(1), so there are no shift-reduce or reduce-reduce conflicts.

Note: This is the standard expression grammar for precedence/associativity with parentheses, and in SLR(1) it resolves conflicts due to how FOLLOW sets restrict reduce lookaheads.

Why this grammar is usually conflict-free in SLR(1)

The only places reductions could conflict with shifts are states where an LR(0) item is “ready to reduce” (dot at the end of some production), while simultaneously a shift is possible on +, *, ) or end-of-input.

In SLR(1), a reduction $A\to \alpha$ is placed on lookaheads in $\text{FOLLOW}(A)$ . For this grammar:

Reduce of $E \to T$ is limited by what can follow an $E$ .
Reduce of $T \to F$ is limited by what can follow a $T$ .
Those FOLLOW restrictions prevent reductions on * where a shift should occur, and prevent reductions on + where a shift should occur.

To make that precise, we compute the relevant FOLLOW sets.

Compute FOLLOW sets for reduce-lookaheads

1
Step 1
Terminals are +, *, (, ), id, and end-marker $ (as input completion). Start symbol is $E$ .
2
Step 2
Add end-marker: $\$ \in \text{FOLLOW}(E)$.
3
Step 3
From $E \rightarrow E + T$ : the terminal after $E$ is +, so add + to FOLLOW( $E$ ). From $F \rightarrow (E)$ : the terminal after $E$ is ), so add ) to FOLLOW( $E$ ).
4
Step 4
Because $E \rightarrow T$ , we have FOLLOW( $T$ ) ⊆ FOLLOW( $E$ ) depending on occurrences; similarly because $T \rightarrow F$ , FOLLOW( $F$ ) ⊆ FOLLOW( $T$ ).
5
Step 5
In $E \rightarrow E + T$ , terminal after $T$ does not exist directly (since $T$ is at end), so FOLLOW( $T$ ) gets FOLLOW( $E$ ).
6
Step 6
In $T \rightarrow T * F$ , $F$ is at end, so FOLLOW( $F$ ) gets FOLLOW( $T$ ).
7
Step 7
One consistent result is:
$\text{FOLLOW}(E)=\{\$ ,,) , +} $, \$ \text{FOLLOW}(T)={$,,), +} $, \$ \text{FOLLOW}(F)={$,,), +, *}$.
These are the terminals that can legally appear immediately after each nonterminal in any sentential form.

The core SLR(1) conflict rule

For SLR(1):

Shift entries exist for transitions on terminals.
Reduce entries for an item $[A\\to\\alpha\\cdot]$ are added only for lookaheads in $\text{FOLLOW}(A)$ .
A shift-reduce conflict occurs if the ACTION table in some state has both:
- a shift on some terminal $a$ , and
- a reduce by some $A\\to\\alpha$ on the same terminal $a$ .
A reduce-reduce conflict occurs if two different reductions are both placed for the same terminal in that state.

Thus, we examine whether any reduce-ready items can share lookahead terminals with terminals that trigger shifts.

Visual intuition (not full LR(0) automaton)

In an LR(0) state where a production like:

$E\\to T\\cdot$ $E t o T c d o t$ is ready to reduce, the lookaheads must be in FOLLOW( $E$ $E$ ), i.e. among $\{\\$ ${$ , +, )}$.
- Importantly, this set does not include *, so it cannot reduce on * where a shift would be needed for $T\\to T * F$ .

Similarly:

$T\\to F\\cdot$ $T t o F c d o t$ reduces only on FOLLOW( $T$ $T$ ), i.e. $\{\\$ ${$ , +, )}$.
- Again, this avoids reducing on *.

Finally:

$F$ reductions appear on FOLLOW( $F$ ), which includes *. This is safe because the parser structure ensures that when * appears, the grammar expects to be extending a $T$ (i.e., shifting * rather than incorrectly reducing $T$ at the wrong time).

The net effect is: no terminal simultaneously belongs to both

the set of shift-triggering terminals in a state, and
the FOLLOW set that enables an incorrect reduction in that same state.

How to spot conflicts quickly

In SLR(1), if a reduce would need a lookahead that is NOT in FOLLOW(A), it will never be placed in ACTION, so the conflict cannot happen. For this grammar, FOLLOW(E) and FOLLOW(T) exclude *, preventing the most common shift-reduce conflict around precedence.

Why LR(0) alone would be insufficient

If you used only LR(0) reductions (without FOLLOW), many states would produce ambiguous reduce actions. SLR(1) resolves this by restricting reduces to FOLLOW sets, which encode what can legally follow the reduced nonterminal.

SLR(1) decision workflow for this grammar

Build LR(0) items

Compute closure/goto for dotted productions for E, T, F."

Add shift actions

For each terminal transition from a state, place shift in ACTION."

Add reduce actions via FOLLOW

For each completed item [A→α·], place reduce by A→α only on terminals in FOLLOW(A)."

Check conflicts

If a terminal gets both shift and reduce (or two reduces), grammar is not SLR(1)."

Conflict Results (explicit)

Knowledge Check

Question 1 of 4

Q1Single choice

In SLR(1), completed item [A → α ·] causes what kind of ACTION entry?

Reduce by A → α on every terminal

Reduce by A → α only on terminals in FOLLOW(A)

Shift on every terminal

Accept on every terminal in FOLLOW(A)

Explore Related Topics

Ambiguity in Context-Free Grammars and Its Link to LR Parsing Conflicts

Proving That a Grammar Is LL(1) but Not SLR(1)

Canonical Collection of LR(0) Items for an Expression Grammar

Browse all research articles