Skip to content
Tutorials Center
My learning

Topics

Lesson 25 of 61 ยท Parsing

Canonical LR(1) Parsers and Conflict Resolution

Build canonical LR(1) item sets with lookaheads, compare them with SLR and LALR on three grammars, and see how state merging creates reduce/reduce conflicts.

The LR parsing lesson built an SLR parser and explained in words that LR(1) and LALR(1) are stronger. This lesson shows how they are stronger. You will construct the canonical LR(1) collection of item sets, with a lookahead token inside every item, and let a program compare it with SLR and LALR on three grammars. The comparison produces three different stories: a grammar where SLR fails and the other two succeed, one where LR(1) is the only method that works, and one where the LR(1) table is large but harmless.

Everything here is about reduce decisions. The shift side of the table is the same in all of the methods. What differs is how much information a parser uses before it commits to a reduction.

From LR(0) items to LR(1) items

An LR(0) item is a rule with a dot, such as A -> a . b. An LR(1) item is the same pair plus one lookahead terminal: [A -> a . b, t]. The extra component has a precise meaning: if the parser eventually completes this item and reduces by A -> a b, the next input token will be t. Only then is the reduction legal.

For an item with the dot at the end, [A -> a b ., t], the parser reduces only when the next token is exactly t. SLR reduces on every token in FOLLOW(A) and LALR reduces on a merged set. LR(1) reduces on the tokens that can follow A in this very situation, no more.

Closure and goto with lookaheads

The construction needs one change in the closure step. Suppose a state contains [A -> a . B b, t]. The parser may soon start recognizing B, so for every rule B -> g, the closure adds [B -> . g, u] for each u in FIRST(b t). In words: after B comes whatever follows it in this item, which is b and, if b can vanish, the lookahead t.

goto(I, X) is unchanged: move the dot over X in every item that allows it, keep the lookahead, and take the closure.

The start state is the closure of [S' -> . S, $], with the end marker $ as lookahead.

flowchart LR
    I["Item: A -> a . B b with lookahead t"] --> C["Closure adds B -> . g"]
    C --> L["with lookahead FIRST of (b t)"]
    L --> G["goto on a symbol moves the dot, keeps the lookahead"]

Lookaheads are created by closure and then travel unchanged through goto.

Because two states with the same rules but different lookaheads are different states, the canonical LR(1) collection is larger than the LR(0) one. For the usual expression grammar, you will see that it grows from 13 to 23 states below.

Three machines, one program

The program below does the following:

  • It computes FIRST and FOLLOW for a grammar and builds the canonical LR(1) collection.
  • It merges states that have the same core (the same dotted rules, ignoring lookaheads), taking the union of their lookaheads. That gives the LALR(1) machine, which has exactly the states of the LR(0) automaton.
  • For SLR(1), it uses the same merged states, but a completed item reduces on FOLLOW of its left-hand side.
  • It reports every cell that gets two actions, for each method.
Python LR(1), LALR(1) and SLR(1) side by side

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Reading the results

The pointer grammar (S -> L = R | R, L -> * R | id, R -> L) fails SLR(1) with a shift/reduce conflict on =, but both LALR(1) and LR(1) handle it. The state that contains S -> L . = R and R -> L . is the culprit. SLR reduces R -> L whenever the next token is in FOLLOW(R), and = is in that set because R can end up on the left side of = through L -> * R. But in this particular state, the R you would produce is the whole right-hand side of an assignment, which is followed only by $. The LR(1) lookahead knows this, so the reduce cell for = stays empty and the shift wins cleanly.

The reduce/reduce grammar shows the strongest property of LR(1). After a c the parser has two possible reductions, A -> c and B -> c. The right one depends on the token that comes after: in a c d the c is an A, in a c e it is a B. After b c the roles flip: b c d needs B and b c e needs A. Canonical LR(1) keeps the two situations in two separate states, with lookaheads {A on d, B on e} and {A on e, B on d}. They have the same core, so LALR merges them, and the union of the lookaheads gives A on {d, e} and B on {d, e}: every cell is now a reduce/reduce conflict. SLR also fails, because FOLLOW(A) and FOLLOW(B) are both {d, e}.

The expression grammar has no conflict in any method. The only difference is size: 23 states for canonical LR(1) against 13 for the LALR automaton.

What merging can and cannot break

LALR(1) merges states with identical cores, so it never has more states than LR(0). The consequences, in order of importance:

  1. No new shift/reduce conflicts. The shift actions depend only on the core, and the merged lookaheads of a reduction can only collide with a shift if some member state already had that collision. So merging cannot create a shift/reduce conflict that LR(1) lacked.
  2. It can create reduce/reduce conflicts. The second grammar is the textbook example. Real programming-language grammars rarely trigger it, which is why Yacc and Bison use LALR.
  3. Error detection arrives a little later. A merged state may do a reduction on a bad token that LR(1) would have rejected immediately, but the error is still caught before any more input is shifted.

Practical tools improve on plain LALR. Minimal LR(1) (Pager's algorithm) merges two LR(1) states only when doing so cannot create a conflict, so you get tables nearly as small as LALR with the full power of LR(1). Bison offers it as %define lr.type ielr or canonical-lr.

Resolving conflicts that remain

When a grammar produces a conflict that no amount of lookahead can fix, usually because it is ambiguous, the generator needs a rule for choosing:

  • Shift/reduce: the default is to shift. That attaches a dangling else to the nearest if, which is what most languages want. Precedence and associativity declarations (%left '+', %right '^') override the default by comparing the precedence of the rule with that of the lookahead token, as in operator-precedence parsing.
  • Reduce/reduce: the default is to reduce by the rule that appears earlier in the grammar file. This usually signals a real grammar bug and deserves a rewrite rather than a lucky default.
  • Rewrite the grammar: often the cleanest cure, as shown in ambiguity and precedence and grammar transformations.

When Bison says "state 17 conflicts", ask the tool for its report with --report=all, find that state, and read the items: you now know exactly what the two competing actions mean.

Method States Reduces on Fails when
SLR(1) LR(0) count FOLLOW(A) FOLLOW is too coarse (pointer grammar)
LALR(1) LR(0) count Merged context lookaheads Merging creates a reduce/reduce conflict
Canonical LR(1) Often several times larger Exact context lookaheads Only for ambiguous or non-LR(1) grammars

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does the lookahead in an LR(1) item [A -> a b ., t] mean?

    The lookahead is the set of tokens that may legally follow this reduction in this exact context. LR(1) reduces only on such a token.
  2. 2. When closing an item [A -> a . B b, t], which lookaheads are given to the new items B -> . g?

    What follows B in this situation is b, and if b can vanish, the token t. That is FIRST(b t).
  3. 3. Why does LALR(1) fail on S -> a A d | b B d | a B e | b A e, A -> c, B -> c?

    Canonical LR(1) keeps the two states apart, with A on d and B on e in one and A on e and B on d in the other. Merged, both reductions apply to both tokens.
  4. 4. Which kind of conflict can LALR merging add that canonical LR(1) did not have?

    Shift actions depend only on the core, which merged states share, so no new shift/reduce conflict appears. Combined lookaheads can however make two reductions collide.
  5. 5. A Yacc or Bison grammar has an unresolved reduce/reduce conflict. What does the tool do by default?

    The default is the earlier rule. It is usually better to fix the grammar than to rely on that default.

Summary

  • An LR(1) item is a dotted rule plus a lookahead token. A completed item reduces only on its own lookahead.
  • Closure gives the new items FIRST(b t) as lookaheads. Goto moves the dot and keeps lookaheads. The start item is [S' -> . S, $].
  • States that differ only in lookaheads stay separate in canonical LR(1), so its tables are much larger: 23 states against 13 for the expression grammar.
  • LALR(1) merges states with equal cores. It keeps the LR(0) size and the full power of LR(1) on most grammars, but can introduce reduce/reduce conflicts, never shift/reduce ones.
  • SLR(1) uses the coarse FOLLOW sets and fails on grammars such as the pointer grammar.
  • Generators resolve leftover conflicts by precedence declarations, by shifting, or by the earlier rule, but a grammar rewrite is usually the better fix.

Next, learn what a parser does when the input is wrong in Parser Error Recovery.