Construction of SLR

SLR(1) stands for Simple LR with 1 token of lookahead. It is the easiest LR table-construction technique to learn and the cheapest to implement — a great starting point before tackling CLR(1) and LALR(1).

The "simple" comes from how it decides reductions: it uses FOLLOW sets computed from the grammar, rather than carrying detailed per-state lookahead information.

How SLR Differs from LR(0)

LR(0) parsers reduce as soon as they reach an item with the dot at the end (A → α ·), regardless of the next input token. That works for very few grammars — most real grammars produce shift/reduce conflicts at LR(0).

SLR(1) is one small but powerful improvement:

By restricting the reduction to FOLLOW(A), many LR(0) conflicts disappear — and any grammar where that single rule is enough is called SLR(1).

The Construction Pipeline

The first two steps are shared with every LR variant — they were covered in the LR Parsers topic. Step 4 is what makes the parser SLR.

We reuse the same expression grammar from the LR Parsers topic, so the DFA we already built carries over directly — only the reduce entries change.

It generates simple additions of identifiers: id, id + id, id + id + id, and so on. It is left-recursive (E → E + T) — which LR handles naturally — and it is genuinely LR(0). We will see that SLR(1), by consulting FOLLOW, still produces a tighter table than the blind LR(0) one.

FIRST and FOLLOW

We will need the FOLLOW sets in step 2 — they drive every reduce entry.

Keep these handy: FOLLOW(E) = FOLLOW(T) = { +, $ } and FOLLOW(E') = { $ }.

Augmenting and building the LR(0) item DFA are identical for every LR variant — SLR adds nothing here. We constructed this exact DFA state by state in the LR Parsers topic, so we only restate the result.

Starting from the kernel E' → · E and applying CLOSURE and GOTO until no new states appear gives 6 states:

The complete (reduce/accept) items live in I₁ (accept on $), I₂, I₃, and I₅. Note that both I₀ and I₄ transition to the single state I₃ on id — identical item sets share one state.

Now apply the SLR(1) rules to fill in every entry of ACTION and GOTO.

Shift Entries (ACTION)

For every transition I_s — a → I_t where a is a terminal:

From our DFA:

GOTO Entries

For every transition I_s — A → I_t where A is a non-terminal:

From our DFA:

Accept Entry

The state containing E' → E · accepts on $:

Reduce Entries — The SLR(1) Rule

This is the one rule that defines SLR.

Walk through each reduce state, using FOLLOW(E) = FOLLOW(T) = { +, $ }:

(Production numbers: 1 = E → E + T, 2 = E → T, 3 = T → id.)

SLR Is Tighter Than LR(0)

In the LR Parsers topic we built the LR(0) table for this same grammar, where every complete item reduces on every terminal — including id. SLR consults FOLLOW instead, and since id ∉ FOLLOW(E) and id ∉ FOLLOW(T), the id column for states 2, 3, and 5 becomes error rather than reduce:

Same DFA, same shifts and gotos — SLR just rejects bad input one step sooner.

Putting all the entries together:

Reading conventions:

• s3 — shift, then go to state 3.
• r2 — reduce by production (2): E → T.
• acc — accept.
• Empty cells — syntax error.

Every cell has at most one entry. That confirms the grammar is SLR(1) — no conflicts. Compare with the LR(0) table from the LR Parsers topic: there the id column of states 2, 3, and 5 held r2/r3/r1; here those cells are empty, because id is not in any FOLLOW set.

Quick Reading of Each Row

Let's run the SLR(1) parser on the input id + id — the same string traced in the LR Parsers topic, so you can compare the two engines directly.

The stack stores (symbol, state) pairs. We show only the state numbers for compactness — the symbols are easy to recover from context.

Notice the discipline:

• Shift pushes (token, new_state).
• Reduce by A → β pops 2·|β| entries, then pushes (A, GOTO[top][A]). The final reduction E → E + T has three symbols, so it pops 6 entries at once.

No backtracking, no guessing — every action is a direct table lookup. Reading the reductions in order (T → id, E → T, T → id, E → E + T) and reversing them recovers the rightmost derivation of id + id. That is the entire SLR(1) algorithm in action.

SLR(1) is easy but not powerful. Some unambiguous grammars cause shift/reduce conflicts in SLR even though they are perfectly parseable by stronger LR variants.

The Famous L = R Grammar

This grammar describes a tiny pointer-assignment language: *x = y, x = y, x, etc. It is unambiguous — every valid input has exactly one parse tree.

The Conflict Appears

When we build its LR(0) DFA, one state ends up with both:

To pick the right action, SLR asks: is = in FOLLOW(R)?

Walk through FOLLOW(R):

But also: R → L and S → R mean R can replace S, and L can replace R, so:

And S → L = R puts = in FOLLOW(L). Hence = ends up in FOLLOW(R) too.

So SLR concludes: on lookahead =, both reduce R → L and shift are valid:

Why SLR Was Wrong

In this context, = is the next token only when we are inside an S → L = R derivation — we definitely should shift. But SLR cannot tell that, because FOLLOW(R) is computed globally over the grammar and ignores the state the parser is in.

CLR(1) fixes this by attaching lookaheads to individual items, giving per-context precision. That is the topic of the next chapter.

Summary

Despite the limitations, most teaching examples are SLR(1) — and learning the mechanics here makes CLR and LALR almost free.