Skip to content
Tutorials Center
My learning

Topics

Lesson 24 of 61 ยท Parsing

LR(0), SLR and LALR Parsers

Build LR parsers step by step: items, closure and goto, the canonical collection, action and goto tables, conflicts, and how SLR, LALR and LR(1) differ.

In the previous lesson a shift-reduce parser kept a stack and had to decide, at every step, whether to shift or to reduce. We solved that with hand-written decisions. An LR parser solves it mechanically. It is a shift-reduce parser whose decisions come from a table, and the table is computed from the grammar by an algorithm you can run in a few dozen lines of Python.

The name means: read the input Left to right, produce a Rightmost derivation in reverse. The families you meet in compiler courses (LR(0), SLR(1), LALR(1), LR(1)) all share the same driver program. They differ only in how much information they use when filling in the table, and therefore in how many grammars they can handle and how big the tables get.

Items: where are we in a rule?

An LR(0) item is a production with a dot in the right-hand side. The dot marks how much of the rule the parser has already seen. For the rule E -> E + T there are four items:

TEXT
E -> . E + T     nothing seen yet
E -> E . + T     an E has been recognized
E -> E + . T     E and + recognized
E -> E + T .     the whole right-hand side is on the stack: ready to reduce

A set of items describes everything the parser might be in the middle of at one moment. Such a set will become one state of the parser. To build the states we need two operations.

Closure. If the dot sits in front of a nonterminal, say E -> E + . T, the parser may soon start recognizing any rule for T. So the closure adds T -> . T * F and T -> . F, and repeats until nothing new appears (a fixed-point loop, like the one in FIRST and FOLLOW).

Goto. goto(I, X) takes a state I, moves the dot over the symbol X in every item where X follows the dot, and takes the closure of the result. It is the transition of the automaton on symbol X.

To start, we augment the grammar with a new start rule E' -> E. When the parser reduces by that rule (or rather, has E' -> E . and sees $), it accepts.

Starting with closure({E' -> . E}) and applying goto to every symbol until no new sets appear gives the canonical collection of item sets. Connected by the goto transitions, they form a deterministic automaton that recognizes the viable prefixes of the grammar.

flowchart LR
    I0["I0<br/>E' -> . E<br/>E -> . E + T<br/>..."] -- "E" --> I2["I2<br/>E' -> E .<br/>E -> E . + T"]
    I2 -- "+" --> I7["I7<br/>E -> E + . T<br/>T -> . T * F<br/>..."]
    I0 -- "id" --> I5["I5<br/>F -> id ."]
    I7 -- "T" --> I10["I10<br/>E -> E + T .<br/>T -> T . * F"]

A small part of the automaton for the expression grammar. A state with a dot at the end of an item allows a reduce.

From states to tables

The LR driver uses two tables built from the automaton:

  • ACTION[state, terminal] is one of shift s (go to state s), reduce r (use rule r), accept or blank (error).
  • GOTO[state, nonterminal] is the state to enter after a reduction produces that nonterminal.

The filling rules are short:

  1. If state i contains A -> a . t b for a terminal t, and goto(i, t) = j, then ACTION[i, t] = shift j.
  2. If state i contains A -> a . (dot at the end), then ACTION[i, t] = reduce A -> a for every t in a chosen lookahead set.
  3. If state i contains E' -> E ., then ACTION[i, $] = accept.
  4. If goto(i, N) = j for a nonterminal N, then GOTO[i, N] = j.

Rule 2 is the only place where the families differ, because "a chosen lookahead set" can be defined differently:

Parser Lookahead set for reduce A -> a
LR(0) every terminal (no lookahead at all)
SLR(1) FOLLOW(A)
LALR(1) the exact set of tokens that can follow A in this context, merged across states that have the same core
LR(1) the exact set for each state, with states kept separate

The driver loop is always the same: look at the state on top of the stack and the next token, read ACTION, and either push the new state (shift), pop as many states as the rule's right-hand side has symbols and then push GOTO[exposed state, A] (reduce), accept, or report an error.

An SLR table builder you can run

The code below implements everything above: grammar parsing, FIRST and FOLLOW, closure, goto, the canonical collection, the ACTION and GOTO tables with conflict detection, and the driver. It builds the table for the expression grammar, prints a few states, the table, and then parses id + id * id while showing the stacks.

Python Building an SLR table and parsing with it

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.

You should see 12 states and no conflicts. The table shows the pattern of an SLR table: in state 4, the cell under * holds s8 (shift) while the cells under ), + and $ hold r2 (reduce E -> T). That one row is the lookahead decision from the last lesson, now computed instead of guessed. When the parse starts, the stack of states 0, then 0 5 after shifting id, and so on, shows how a single number on top of the stack summarizes everything the parser needs to know about the symbols below it.

Note that the stack holds states, not symbols. The symbols are implied: every state has exactly one incoming symbol, so keeping the states is enough to know the whole viable prefix.

Conflicts and the limits of each family

If a cell would receive two different actions, the grammar is not suitable for that kind of parser. The same table builder can show the differences. LR(0) reduces on every terminal, so any state that contains both a completed item and a shift item has a conflict. SLR(1) narrows reductions to FOLLOW(A), which resolves many of those. Still, FOLLOW is a global property of the nonterminal, not a property of the situation, and some grammars need the finer information that LR(1) and LALR(1) keep.

Python Comparing LR(0), SLR and ambiguity

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.

Three different stories appear in the output:

  • The expression grammar is not LR(0) (state 4 wants to both shift * and reduce E -> T), but it is SLR(1), because FOLLOW(E) does not contain *.
  • The pointer grammar (S -> L = R | R, L -> * R | id, R -> L) is the textbook example of a grammar that is not SLR(1) even though it is not ambiguous. In the state containing S -> L . = R and R -> L ., the token = belongs to FOLLOW(R) globally, but in that state a reduction to R cannot actually be followed by =. LR(1) and LALR(1) know this, because they track the exact lookahead for each situation.
  • The ambiguous grammar E -> E + E | id has a shift/reduce conflict in every family. No amount of lookahead can fix ambiguity. Real tools pick a winner by precedence declarations (see parser generators), or you rewrite the grammar as in ambiguity and precedence.

SLR, LR(1) and LALR(1) in practice

Canonical LR(1) items carry a lookahead token, written [A -> a . b, t]. Two states with the same items but different lookaheads stay separate. That makes LR(1) the most powerful of the family, but the tables for a real language can have thousands of states, which is why it was long considered impractical.

LALR(1) is the compromise. It builds the LR(1) states and then merges those with identical cores (same items ignoring lookaheads), taking the union of the lookaheads. The tables then have exactly as many states as the LR(0) automaton, like SLR. The merging can introduce reduce/reduce conflicts that canonical LR(1) did not have, but almost never shift/reduce ones, and in practice most programming-language grammars work. This is the algorithm inside Yacc and Bison.

Parser States Power Typical use
LR(0) few weakest teaching
SLR(1) same as LR(0) handles most expression grammars teaching, small tools
LALR(1) same as LR(0) handles nearly all practical grammars Yacc, Bison
LR(1) many strongest of the four theory, tools with state merging

The hierarchy of grammars is strictly nested: LR(0) is inside SLR(1), which is inside LALR(1), which is inside LR(1). Every LL(1) grammar is also LR(1), but not the other way around, which is why bottom-up parsing handles a larger set of languages than LL(1) parsing.

You will almost never write an LR table by hand. The exercise is to understand what a generator is doing, so that when Bison reports "shift/reduce conflict in state 17", you can read the item set of that state and see exactly which two actions collided.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does the item E -> E + . T mean?

    The dot shows how much of the right-hand side has been seen. Here E and + are on the stack and the parser now needs to recognize T.
  2. 2. Which family reduces A -> a only on tokens in FOLLOW(A)?

    SLR(1) fills reduce actions using the global FOLLOW set of the left-hand side. LR(0) uses no lookahead, and LR(1) and LALR(1) use more precise, context-specific lookaheads.
  3. 3. Why is LALR(1) popular in tools such as Yacc and Bison?

    LALR merges LR(1) states that share a core, giving small tables like SLR with better lookahead information. The merging can add reduce/reduce conflicts, but rarely for practical grammars.
  4. 4. What does an ACTION cell with two different entries tell you?

    Two possible actions in one cell is a shift/reduce or reduce/reduce conflict. Either the grammar is ambiguous, or the parser class does not use enough lookahead to decide.
  5. 5. During a reduce by a rule with three symbols on the right-hand side, what does the LR driver do with the state stack?

    One state sits on the stack for each symbol of the handle. After popping them, the state underneath and the rule's left-hand side select the next state through the GOTO table.

Summary

  • An LR item is a rule with a dot; closure and goto build the canonical collection of item sets, which is a DFA over viable prefixes.
  • ACTION and GOTO tables are filled from the automaton: shifts from terminal transitions, reduces from completed items, accept from the augmented rule.
  • LR(0) reduces without lookahead, SLR(1) uses FOLLOW sets, LR(1) tracks exact lookaheads, and LALR(1) merges LR(1) states with equal cores.
  • The same driver loop works for all of them; only the table-filling rule for reductions changes.
  • A multiply-defined cell is a conflict, caused by ambiguity or by too little lookahead.
  • LALR(1) is what Yacc and Bison use, because it is nearly as strong as LR(1) with the small tables of SLR.

Next: Syntax Errors and Error Recovery