Bottom-up parsing

Top-down parsers guess, from the next token, which production will derive the coming input. Bottom-up parsers postpone that decision until they have seen everything a production derives. They read tokens from left to right, accumulating them on a stack, and whenever the top of the stack matches the right-hand side of a production in the right context, they replace it with the production's left-hand side. This replacement, called a reduction, builds the parse tree from the leaves upward, and the sequence of reductions traces a rightmost derivation in reverse. The most important family of bottom-up methods is LR parsing: Left-to-right scan, Rightmost derivation in reverse. LR parsers handle almost every grammar one would naturally write for a programming language, including left-recursive ones, which is why parser generators such as yacc and bison are built on them.

Donald Knuth introduced LR(k) parsing in 1965. His construction produced tables too large for the computers of the day, and practical use came with Frank DeRemer's simpler variants, SLR and LALR (1969 to 1971), which yacc (Stephen Johnson, Bell Labs, 1975) made universally available. The ideas in this lesson are therefore over half a century old, yet they remain the basis of tools used today, and understanding them explains the shift/reduce and reduce/reduce conflicts that parser generators report.

Shift-reduce parsing

A shift-reduce parser has a stack and the remaining input, and four actions. Shift moves the next token onto the stack. Reduce pops the right-hand side of a production from the top of the stack and pushes its left-hand side. Accept ends successfully when the stack holds just the start symbol and the input is exhausted. Error reports that no action is possible. The right-hand side that should be reduced next is called the handle. The whole difficulty of bottom-up parsing is recognizing handles: in E + T * F, the top of the stack F matches the production T → F, but reducing it would be wrong, because the correct handle is T * F. LR parsers recognize handles with a finite automaton that runs over the stack.

LR(0) items and the characteristic automaton

An LR(0) item is a production with a dot somewhere in its right-hand side, recording how much of it has been seen. The item \(E \to E + . T\) means: we have seen something derived from E, then +, and now expect something derived from T. An item with the dot at the end, such as \(T \to T * F\,.\), means the whole right-hand side is on the stack and could be reduced. The parser's states are sets of items. The closure of a set adds, for every item with the dot before a nonterminal B, all items \(B \to .\gamma\), because if we expect a B we must also expect anything a B can start with. The goto of a set on a symbol X moves the dot over X in every item where X comes next, then takes the closure. Starting from the closure of \(S' \to .E\), where S' is a new start symbol, and applying goto on every symbol until no new sets appear, produces the canonical collection of LR(0) item sets. Their transitions form a DFA, the characteristic automaton, whose states the parser keeps on its stack.

SLR(1) parse tables

From the automaton we build two tables. The ACTION table, indexed by state and terminal, says shift (and to which state), reduce (by which production), accept or error. The GOTO table, indexed by state and nonterminal, says which state to enter after a reduction. Shift entries come from the automaton's transitions on terminals. In the simplest scheme, LR(0), any state containing a completed item reduces regardless of the next token; this almost never works for real grammars. SLR(1), simple LR, reduces by \(A \to \alpha\) only when the next token is in FOLLOW(A), the set computed in lesson 3. If some table entry receives two different actions, the grammar is not SLR(1), and the clash is reported as a shift/reduce or reduce/reduce conflict.

# Building the canonical LR(0) item sets and the SLR(1) table for the
# left-recursive expression grammar (no rewriting needed for LR parsing).
G = [("S'", ("E",)),                       # 0: augmented start
     ("E", ("E", "+", "T")), ("E", ("T",)),
     ("T", ("T", "*", "F")), ("T", ("F",)),
     ("F", ("(", "E", ")")), ("F", ("id",))]
NT = {"S'", "E", "T", "F"}
TERMS = ["id", "+", "*", "(", ")", "$"]
FOLLOW = {"E": {"+", ")", "$"}, "T": {"+", "*", ")", "$"}, "F": {"+", "*", ")", "$"}}

def closure(items):                         # item = (production index, dot position)
    items = set(items); changed = True
    while changed:
        changed = False
        for p, d in list(items):
            rhs = G[p][1]
            if d < len(rhs) and rhs[d] in NT:
                for q, (lhs, _) in enumerate(G):
                    if lhs == rhs[d] and (q, 0) not in items:
                        items.add((q, 0)); changed = True
    return frozenset(items)
def goto(I, X):
    return closure({(p, d + 1) for p, d in I if d < len(G[p][1]) and G[p][1][d] == X})

states = [closure({(0, 0)})]; trans = {}
for I in states:                            # the list grows while we iterate
    for X in ["E", "T", "F", "(", "id", "+", "*", ")"]:
        J = goto(I, X)
        if not J: continue
        if J not in states: states.append(J)
        trans[states.index(I), X] = states.index(J)
print(len(states), "LR(0) states")
def show(p, d):
    lhs, rhs = G[p]; r = list(rhs); r.insert(d, "."); return f"{lhs} -> {' '.join(r)}"
for k in (0, 2, 9):
    print(f"state {k}: " + "; ".join(show(p, d) for p, d in sorted(states[k])))

ACTION, GOTO, conflicts = {}, {}, []
for i, I in enumerate(states):
    for p, d in I:
        lhs, rhs = G[p]
        if d < len(rhs) and rhs[d] not in NT:
            new = ("s", trans[i, rhs[d]])
            cell = (i, rhs[d])
        elif d == len(rhs):
            if lhs == "S'": ACTION[i, "$"] = ("acc",); continue
            for a in FOLLOW[lhs]:
                cell, new = (i, a), ("r", p)
                if cell in ACTION and ACTION[cell] != new: conflicts.append(cell)
                ACTION[cell] = new
            continue
        else: continue
        if cell in ACTION and ACTION[cell] != new: conflicts.append(cell)
        ACTION[cell] = new
    for X in ("E", "T", "F"):
        if (i, X) in trans: GOTO[i, X] = trans[i, X]
fmt = lambda a: {"s": f"s{a[-1]}", "r": f"r{a[-1]}", "acc": "acc"}[a[0]]
print("\nstate " + "".join(f"{t:>5}" for t in TERMS) + "  |" + "".join(f"{X:>4}" for X in "ETF"))
for i in range(len(states)):
    row = "".join(f"{fmt(ACTION[i, t]) if (i, t) in ACTION else '':>5}" for t in TERMS)
    gt = "".join(f"{GOTO.get((i, X), ''):>4}" for X in "ETF")
    print(f"{i:5} {row}  |{gt}")
print("conflicts:", conflicts or "none")

12 LR(0) states
state 0: S' -> . E; E -> . E + T; E -> . T; T -> . T * F; T -> . F; F -> . ( E ); F -> . id
state 2: E -> T .; T -> T . * F
state 9: E -> E + T .; T -> T . * F

state    id    +    *    (    )    $  |   E   T   F
    0    s5             s4            |   1   2   3
    1         s6                 acc  |            
    2         r2   s7        r2   r2  |            
    3         r4   r4        r4   r4  |            
    4    s5             s4            |   8   2   3
    5         r6   r6        r6   r6  |            
    6    s5             s4            |       9   3
    7    s5             s4            |          10
    8         s6            s11       |            
    9         r1   s7        r1   r1  |            
   10         r3   r3        r3   r3  |            
   11         r5   r5        r5   r5  |            
conflicts: none

The original left-recursive grammar needs no rewriting: LR parsers are happy with left recursion, which in fact keeps their stacks shallow. State 9 shows how lookahead resolves a potential clash. It contains both \(E \to E + T\,.\), complete and ready to reduce, and \(T \to T . * F\), which wants to shift *. Because * is not in FOLLOW(E), the reduction is placed only under +, ) and $, and * gets the shift: this is exactly how precedence of * over + is enforced by the table. There are twelve states and no conflicts, so the grammar is SLR(1).

The LR parsing algorithm

The driver is the same for every LR variant; only the tables differ. The stack holds states, starting with state 0. At each step the parser looks up ACTION for the state on top and the next token. To shift to state j, it pushes j and advances. To reduce by \(A \to \alpha\), it pops |α| states, looks up GOTO for the newly exposed state and A, and pushes the result; this is where a semantic action would build an AST node from the popped children. The trace shows the symbols corresponding to the stacked states, which is easier to read.

# A shift-reduce LR parse driven by the SLR(1) table above. The stack holds
# states; each reduction pops |rhs| states and follows GOTO.
G = [("S'", 1), ("E", 3), ("E", 1), ("T", 3), ("T", 1), ("F", 3), ("F", 1)]
NAMES = ["S' -> E", "E -> E + T", "E -> T", "T -> T * F", "T -> F", "F -> ( E )", "F -> id"]
A = {(0, "id"): "s5", (0, "("): "s4", (1, "+"): "s6", (1, "$"): "acc",
     (2, "+"): "r2", (2, "*"): "s7", (2, ")"): "r2", (2, "$"): "r2",
     (3, "+"): "r4", (3, "*"): "r4", (3, ")"): "r4", (3, "$"): "r4",
     (4, "id"): "s5", (4, "("): "s4", (5, "+"): "r6", (5, "*"): "r6", (5, ")"): "r6", (5, "$"): "r6",
     (6, "id"): "s5", (6, "("): "s4", (7, "id"): "s5", (7, "("): "s4",
     (8, "+"): "s6", (8, ")"): "s11", (9, "+"): "r1", (9, "*"): "s7", (9, ")"): "r1", (9, "$"): "r1",
     (10, "+"): "r3", (10, "*"): "r3", (10, ")"): "r3", (10, "$"): "r3",
     (11, "+"): "r5", (11, "*"): "r5", (11, ")"): "r5", (11, "$"): "r5"}
GOTO = {(0, "E"): 1, (0, "T"): 2, (0, "F"): 3, (4, "E"): 8, (4, "T"): 2, (4, "F"): 3,
        (6, "T"): 9, (6, "F"): 3, (7, "F"): 10}
def parse(toks):
    toks = toks + ["$"]; i = 0; st = [0]; syms = []
    print(f"{'stack (symbols)':24}{'input':16}action")
    while True:
        act = A.get((st[-1], toks[i]))
        print(f"{' '.join(syms) or '-':24}{' '.join(toks[i:]):16}", end="")
        if act is None: print(f"error in state {st[-1]} on {toks[i]!r}"); return
        if act == "acc": print("accept"); return
        if act[0] == "s":
            st.append(int(act[1:])); syms.append(toks[i]); i += 1; print("shift"); continue
        p = int(act[1:]); lhs, n = G[p]
        del st[-n:]; del syms[-n:]
        st.append(GOTO[st[-1], lhs]); syms.append(lhs)
        print(f"reduce {NAMES[p]}")
parse(["id", "+", "id", "*", "id"])

stack (symbols)         input           action
-                       id + id * id $  shift
id                      + id * id $     reduce F -> id
F                       + id * id $     reduce T -> F
T                       + id * id $     reduce E -> T
E                       + id * id $     shift
E +                     id * id $       shift
E + id                  * id $          reduce F -> id
E + F                   * id $          reduce T -> F
E + T                   * id $          shift
E + T *                 id $            shift
E + T * id              $               reduce F -> id
E + T * F               $               reduce T -> T * F
E + T                   $               reduce E -> E + T
E                       $               accept

Read the reductions from the bottom up and you get the rightmost derivation of the input in reverse. Watch the moment after the second id has been reduced to T: the stack holds E + T, and the next token is *. The parser shifts rather than reducing E + T to E, because the table, consulting FOLLOW(E), knows that a * cannot follow an E. The multiplication is therefore reduced first, inside the addition, as precedence requires. Each step does a constant amount of work, so LR parsing takes time linear in the input.

More powerful LR methods: LR(1) and LALR(1)

SLR(1) uses FOLLOW sets, which are a coarse approximation: they say which tokens can follow A anywhere in any program, not in the particular context the parser is in. Knuth's canonical LR(1) items carry a lookahead token with each item, such as \([A \to \alpha .\, , a]\), meaning reduce only if the next token is a in this context. Canonical LR(1) accepts the largest class of grammars of any deterministic one-token-lookahead method, but its automaton can have many more states, often thousands for a real language. LALR(1), lookahead LR, merges LR(1) states that have the same items apart from lookaheads. The result has exactly as many states as LR(0), with lookaheads almost as precise as LR(1). Merging can occasionally introduce a reduce/reduce conflict that canonical LR(1) avoids, but in practice LALR(1) handles virtually all programming language grammars, which is why yacc and bison use it by default. Bison also offers canonical LR(1), IELR(1), which keeps LR(1) power with LALR-sized tables, and GLR.

Every LR(1) grammar is unambiguous, and the LR(1) grammars properly include the LL(1) grammars. The extra power comes from postponing decisions: an LL parser must choose a production after seeing its first token, while an LR parser chooses after seeing its entire right-hand side and the next token. That is why LR handles left recursion and common prefixes without rewriting.

Conflicts and how to read them

When a generator reports a conflict, it is telling you the grammar is ambiguous or needs more lookahead than the method provides. A shift/reduce conflict means that in some state the parser could either shift the next token or reduce a completed item. The classic example is the dangling else: after if c if c x, with else next, the parser can reduce the inner if-statement (attaching the else to the outer if) or shift the else (attaching it to the inner if). A reduce/reduce conflict means two different completed items could both be reduced on the same token, which usually signals a real ambiguity, such as one token sequence that two different nonterminals can both derive.

# The dangling else: an SLR(1) construction reports a shift/reduce conflict,
# and yacc-style tools resolve it by shifting (else binds to the nearest if).
G = [("S'", ("S",)), ("S", ("if", "c", "S")), ("S", ("if", "c", "S", "else", "S")), ("S", ("x",))]
NT = {"S'", "S"}; FOLLOW = {"S": {"else", "$"}}
def closure(I):
    I = set(I)
    while True:
        new = {(q, 0) for p, d in I if d < len(G[p][1]) and G[p][1][d] in NT
               for q, (l, _) in enumerate(G) if l == G[p][1][d]} - I
        if not new: return frozenset(I)
        I |= new
def goto(I, X): return closure({(p, d + 1) for p, d in I if d < len(G[p][1]) and G[p][1][d] == X})
states = [closure({(0, 0)})]
for I in states:
    for X in ["if", "c", "else", "x", "S"]:
        J = goto(I, X)
        if J and J not in states: states.append(J)
for i, I in enumerate(states):
    shifts = {G[p][1][d] for p, d in I if d < len(G[p][1]) and G[p][1][d] not in NT}
    for p, d in I:
        lhs, rhs = G[p]
        if d == len(rhs) and lhs != "S'":
            for a in FOLLOW[lhs] & shifts:
                items = "; ".join(f"{G[q][0]} -> {' '.join(G[q][1][:e])} . {' '.join(G[q][1][e:])}".replace("  ", " ")
                                  for q, e in sorted(I))
                print(f"state {i}: shift/reduce conflict on {a!r}")
                print("   items:", items)
                print(f"   shift 'else' (attach to inner if)  or  reduce by {lhs} -> {' '.join(rhs)}")
print("resolution used by yacc and bison: prefer shift")

state 5: shift/reduce conflict on 'else'
   items: S -> if c S . ; S -> if c S . else S
   shift 'else' (attach to inner if)  or  reduce by S -> if c S
resolution used by yacc and bison: prefer shift

Almost every language resolves the dangling else the same way, by attaching each else to the nearest unmatched if, and yacc's default of preferring shift happens to implement exactly that. Generators also let you resolve operator ambiguities declaratively: bison's %left, %right and %nonassoc declarations assign precedence and associativity to tokens, and conflicts between items involving those tokens are resolved accordingly, so the grammar can be written with the short ambiguous expression productions. These resolutions are powerful but should be used deliberately; a conflict silently resolved in the wrong direction becomes a parser bug that no tool will report. Tern avoids the dangling else entirely by requiring braces around the branches of if, as Rust and Go do.

Semantic actions and AST building

A parser generator lets each production carry a semantic action, code that runs when the production is reduced. In bison, the action for E → E + T might be {$$ = make_binary(PLUS, $1, $3);}, where $1 and $3 refer to the values attached to the first and third symbols and $$ is the value of the left-hand side. A parallel value stack, pushed and popped in step with the state stack, holds these values. Because reductions happen bottom up, children are always built before their parents, so building an AST is natural. Actions can also implement attribute grammars (lesson 5) whose attributes are computed from children, the so-called synthesized attributes.

Error recovery in LR parsers

LR parsers detect errors at the earliest possible point, like LL parsers, when the ACTION table has an error entry. Yacc's recovery uses a special error token in productions such as stmt → error ;. On an error the parser pops states until it finds one that can shift error, shifts it, then discards input tokens until one can follow, and resumes. More sophisticated schemes search for minimal repairs, inserting, deleting or replacing a few tokens so that parsing can continue; Menhir, the LR(1) generator for OCaml, supports carefully hand-written error messages for each error state.

Which parsing method should a compiler use?

There is no single answer, and practice has shifted over time. In the 1980s and 1990s, LALR generators dominated: GCC's C and C++ front ends were bison-based until the mid-2000s. Since then, hand-written recursive descent has become the norm in major compilers, for better error messages, easier handling of context-sensitive syntax, and speed, while generators remain popular for domain-specific languages, configuration formats and research. PostgreSQL's SQL grammar is a large bison grammar; the Ruby interpreter used a bison grammar for decades before introducing a hand-written parser called Prism in 2024; ANTLR, tree-sitter (a GLR-based incremental parser used by many editors) and PEG tools are widely used in tooling. A good engineer chooses by grammar complexity, need for diagnostics, performance and team familiarity. Whatever method is used, the theory in this lesson explains what is possible: the LR(1) grammars are exactly the deterministic context-free languages' grammars that can be parsed in one left-to-right pass with one token of lookahead.

Worked examples