Parsing: Bottom-Up

A shift-reduce parser maintains two data structures: a stack of grammar symbols (terminals and non-terminals) and an input buffer of remaining tokens. At each step it makes one of four decisions:

• Shift: move the next input token onto the stack.
• Reduce: the top n symbols of the stack match the right-hand side of some production A → α; pop them and push A.
• Accept: the stack contains only the start symbol and input is empty.
• Error: no valid action exists.

The key insight is that a rightmost derivation in reverse is exactly a sequence of reductions. If the original program was derived by the sequence S ⇒ ... ⇒ αAβ ⇒ αγβ (substituting A → γ last), then the parser will eventually see γ on the stack and reduce it back to A. The parse proceeds right-to-left through the rightmost derivation, which is why these are called LR parsers.

Handles: At any point in a rightmost-derivation-in-reverse, the sequence of symbols on the stack that should be reduced next is called the handle. The entire challenge of bottom-up parsing is identifying the handle efficiently — doing it in O(1) time per token, without backtracking. The LR automaton encodes exactly this ability.

# Trace of shift-reduce parsing for: id + id * id
# Grammar: E → E+T | T,  T → T*F | F,  F → id

Stack          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

The LR machinery needs to track not just which production it might be in the middle of, but how far along that production it has gotten. This is formalized as an LR(0) item: a production with a dot (•) marking the parser's current position.

For the production E → E + T, the possible LR(0) items are:

• E → • E + T (nothing shifted yet)
• E → E • + T (E is on the stack, + is next)
• E → E + • T (E and + are on the stack)
• E → E + T • (complete; reduce now)

A dot at the end means the right-hand side is fully matched — this is a complete item and signals a reduction.

Closure: When the dot is immediately before a non-terminal B, the parser might be about to parse any production of B. The closure of an item set I adds all items B → • γ for every B that appears after a dot in some item in I. This is exactly the epsilon-closure from NFA construction.

Goto: goto(I, X) computes the item set reachable by shifting symbol X: move the dot past X in every item where the dot precedes X, then take closure.

The canonical LR(0) collection is the set of all item sets reachable from the initial item S' → • S $ by repeated application of closure and goto. This collection is the state set of a finite automaton (the LR(0) automaton) whose language is the set of viable prefixes — stack contents that could appear in a valid parse.

# Building LR(0) items for: S' → S,  S → a S b | ε

# Augmented grammar adds: S' → S $

# I0 = closure({S' → • S $})
#   = { S' → • S $,
#         S → • a S b,
#         S → •          }   ← S has an ε-production

# goto(I0, a) = closure({S → a • S b})
#             = { S → a • S b,
#                 S → • a S b,
#                 S → •        }

# goto(I0, S) = closure({S' → S • $}) = { S' → S • $ }
# goto(I1, a) = I1  (loop: same set, a is recursive)
# goto(I1, S) = closure({S → a S • b}) = { S → a S • b }
# goto(I2, b) = closure({S → a S b •}) = { S → a S b • }

The canonical LR(0) collection maps directly to a parsing table with two parts:

• ACTION[state, terminal]: what to do when the parser is in state and sees terminal a.
  • shift s: push token a and go to state s.
  • reduce A → α: pop |α| symbols, push A.
  • accept: done.
  • error: syntax error.
• GOTO[state, nonterminal]: after reducing to non-terminal A in state, go to GOTO[state, A].

The table construction rule for LR(0):

1. If [A → α • a β] is in state i and goto(Ii, a) = Ij, then ACTION[i, a] = shift j.
2. If [A → α •] is in state i (a complete item), then ACTION[i, a] = reduce A → α for all terminals a (and $).
3. If [S' → S •] is in the initial + goto state, ACTION[i, $] = accept.
4. GOTO[i, A] = j whenever goto(Ii, A) = Ij.

An LR(0) conflict arises when a cell would receive two different entries:

• Shift-reduce conflict: a state has both a shift action (from a non-complete item) and a reduce action (from a complete item) on the same terminal.
• Reduce-reduce conflict: two different complete items in the same state, both wanting to reduce on the same terminal.

Most real grammars have LR(0) conflicts. SLR and LALR(1) resolve them using lookahead.

# Partial ACTION/GOTO table for: E → E+T | T,  T → T*F | F,  F → (E) | id
# States 0–11 (abbreviated)

#        ACTION                      GOTO
# 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|
# sN = shift to state N; rN = reduce by production N

LR(0) is too weak for most grammars because it fills reduce entries for all terminals. SLR(1) (Simple LR with 1 lookahead) restricts reductions: only fill ACTION[i, a] = reduce A → α if a ∈ FOLLOW(A).

FOLLOW(A) is the set of terminals that can appear immediately after A in any sentential form. For example, if A only ever appears before + or ), then a reduce on * is never valid — it would be a false alarm.

This resolves many LR(0) conflicts. The classic example is the dangling-else: stmt → if expr then stmt | if expr then stmt else stmt. An SLR-aware grammar designer recognizes that else is in FOLLOW(stmt) from the second production, which would create an SLR conflict, necessitating either a grammar rewrite or an explicit conflict resolution rule.

SLR(1) table construction:

• Same item sets as LR(0).
• Complete item [A → α •] in state i → ACTION[i, a] = reduce A → α only if a ∈ FOLLOW(A).

SLR(1) is stronger than LR(0) but still fails on some unambiguous grammars. The weakness: FOLLOW is a global property of the grammar, not specific to the parsing context (which state we reached A from). Two uses of A in different contexts may have different valid lookaheads, but FOLLOW merges them all.

# SLR conflict resolution example
# Grammar: S → L = R | R,  L → * R | id,  R → L
# FOLLOW(R) = {=, $}  FOLLOW(L) = {=, $}

# State: { R → L •,  S → L • = R }
#   - Complete item: reduce R → L  (for a ∈ FOLLOW(R) = {=, $})
#   - Non-complete: shift on '='
# Both apply to '=' → SHIFT-REDUCE CONFLICT.
# SLR cannot resolve this; need LALR(1) or LR(1).

# BUT: semantically R → L should NOT reduce when '=' follows
# because L = R is the only production that uses '=' after L.
# LR(1) items track this precisely.

The key to resolving SLR's weakness is to make lookahead context-sensitive. Instead of consulting the global FOLLOW set, each item carries its own lookahead: the set of terminals that are valid in this specific context.

An LR(1) item is a pair [A → α • β, a] where a is a terminal (or $) — the lookahead. The meaning: "we are in the middle of production A → α β, and after we finish reducing to A, the next token will be a".

LR(1) closure: When the dot is before non-terminal B in item [A → α • B β, a], add items [B → • γ, b] for every production B → γ and every b ∈ FIRST(βa). This is the lookahead refinement: the context after B in this production is β, followed by whatever a expects.

LR(1) table: Complete item [A → α •, a] in state i → ACTION[i, a] = reduce A → α. The lookahead is already baked in; no global FOLLOW lookup needed.

The canonical LR(1) parser (CLR(1) or just LR(1)) is the most powerful deterministic parser for context-free grammars. It can parse any unambiguous grammar that admits a deterministic PDA. The cost: the number of states can be quadratic in the LR(0) state count, making the tables very large in practice. This is why LALR(1) exists.

# LR(1) item example for: S → L = R | R,  L → * R | id,  R → L
# In state reached after shifting L from the initial state:

# [ R → L •,    = ]  ← reduce R→L only when lookahead is '='
# [ S → L • = R, $ ]  ← shift '=' when lookahead after S is '$'

# Now '=' has ONE action in this state: shift (from S → L • = R)
# Reduce only fires if lookahead = '=' AND item is R→L•,
# but that item has lookahead '=' NOT '$'.
# Wait — lookahead for R→L• here is actually '$' (not '=')
# because R appears in S → R, and FOLLOW(S)={$}.
# So ACTION[state, =] = shift (from S→L•=R, lookahead $)
# ACTION[state, $] = reduce R→L (from R→L•, lookahead $)
# No conflict! LR(1) resolves what SLR cannot.

Canonical LR(1) is powerful but produces enormous tables. Consider C: the LR(1) automaton might have thousands of states. LALR(1) (Look-Ahead LR) achieves nearly the same power with dramatically fewer states by merging LR(1) states that share the same core — the LR(0) items, ignoring lookaheads.

Merging procedure:

1. Build the canonical LR(1) collection.
2. Find all pairs of states whose LR(0) cores are identical.
3. Merge them: union their lookahead sets.
4. If any merged state has a reduce-reduce conflict (two complete items with overlapping lookaheads), the grammar is not LALR(1).

The beautiful fact: merging LR(1) states with identical cores never introduces shift-reduce conflicts (if the LR(1) grammar had none). It can only introduce reduce-reduce conflicts. So LALR(1) is strictly between SLR(1) and LR(1) in power, but has the same number of states as SLR(1).

Practically, yacc and bison generate LALR(1) parsers. The vast majority of programming language grammars — C, C++, Java, Go — are LALR(1). The few that are LR(1) but not LALR(1) are exotic constructs that language designers typically avoid.

Efficient construction: Modern tools (like De Remer's algorithm) construct LALR(1) tables without ever building the full LR(1) collection — they propagate lookaheads through the LR(0) automaton, saving significant time and memory.

# Illustrating state merging in LALR(1)
# Two LR(1) states with the same LR(0) core:

# State I4 (LR(1)):
#   [A → b •, c]
#   [B → b •, d]

# State I7 (LR(1)):
#   [A → b •, d]
#   [B → b •, c]

# Same LR(0) core: {A → b •, B → b •}
# LALR merge → new state I47:
#   [A → b •, c/d]
#   [B → b •, c/d]

# Now on 'c': reduce A→b AND reduce B→b → REDUCE-REDUCE CONFLICT.
# Grammar is LR(1) but NOT LALR(1).
# (This is a known pathological case; real grammars avoid it.)

All LR variants share one driver algorithm. The parser's entire state is the stack — not a stack of grammar symbols, but a stack of state numbers (integers indexing the parsing table). Grammar symbols are implicit in transitions.

The driver loop:

1. Let s = top of stack, a = current lookahead token.
2. Look up ACTION[s, a]:
   • shift t: push state t onto stack; advance input.
   • reduce A → α (length n): pop n states off stack; let s' = new top; push GOTO[s', A].
   • accept: success.
   • error: call error recovery.

Notice: the grammar symbols themselves are never explicitly on the stack — the state encodes all needed information. This is the elegance of the LR encoding.

Stack invariant: The sequence of states on the stack, read bottom to top, corresponds to the sequence of transitions in the LR automaton following the current viable prefix. Each state summarizes the entire history of parsing up to that point.

Error recovery: When ACTION[s, a] = error, the parser needs to resynchronize. The most common technique is panic-mode recovery: pop states until finding one with a designated error token in its action set, shift the error token, then skip input tokens until a synchronizing token (;, }) appears.

def lr_driver(action, goto, tokens):
    stack = [0]          # stack of state numbers
    tokens = tokens + ['$']
    pos = 0
    
    while True:
        s = stack[-1]
        a = tokens[pos]
        entry = action[s].get(a)
        
        if entry is None:
            raise SyntaxError(f"Unexpected {a!r} in state {s}")
        
        kind = entry[0]
        
        if kind == 'shift':
            t = entry[1]
            stack.append(t)
            pos += 1
        
        elif kind == 'reduce':
            lhs, rhs_len = entry[1], entry[2]
            for _ in range(rhs_len):
                stack.pop()
            top = stack[-1]
            stack.append(goto[top][lhs])
        
        elif kind == 'accept':
            return  # success
        
        else:
            raise SyntaxError(f"Parse error at {a!r}")

Hand-constructing LR tables for a real language grammar (hundreds of productions) is infeasible. yacc (Yet Another Compiler-Compiler, 1975, Stephen Johnson at Bell Labs) and its GNU successor bison automate the entire process from a grammar specification file.

A bison .y file has three sections separated by %%:

1. Declarations: %token names, %left/%right/%nonassoc precedence, %type for semantic types, C preamble in %{ %} blocks.
2. Rules: productions in BNF with embedded C actions in { } using $$ (left-hand side value) and $1, $2, ... (right-hand side values).
3. User code: C functions like yylex() (lexer) and yyerror().

bison reads the grammar, builds the LALR(1) automaton, and emits a C file containing the table arrays and the driver loop. The generated parser calls yylex() to get tokens and returns 0 on success.

Semantic actions execute at reduction time — when the production fires. This is when you typically construct AST nodes. Because LR parsing is bottom-up, by the time you reduce E → E + T, both sub-trees are already built.

Error productions: bison allows error as a terminal in productions (e.g., stmt: error ';') to designate error-recovery points, similar to catch blocks in exception handling.

/* simple_calc.y -- arithmetic expression evaluator */
%{
#include <stdio.h>
int yylex(void);
void yyerror(const char *s);
%}

%token NUMBER
%left  '+' '-'
%left  '*' '/'
%right UMINUS          /* unary minus, highest precedence */

%%

program:
    expr '\n'  { printf("= %d\n", $1); }
  ;

expr:
    expr '+' expr   { $$ = $1 + $3; }
  | expr '-' expr   { $$ = $1 - $3; }
  | expr '*' expr   { $$ = $1 * $3; }
  | expr '/' expr   { $$ = $1 / $3; }
  | '-' expr %prec UMINUS  { $$ = -$2; }
  | '(' expr ')'   { $$ = $2; }
  | NUMBER          { $$ = $1; }
  ;
%%

void yyerror(const char *s) { fprintf(stderr, "error: %s\n", s); }

Real-world grammars are often ambiguous — the expression a + b * c can parse as (a+b)*c or a+(b*c) depending on precedence. An unambiguous grammar for arithmetic requires rewriting into multiple levels (expr → expr + term | term, term → term * factor | factor, etc.), which is verbose but correct.

bison provides a pragmatic shortcut: precedence and associativity declarations that resolve shift-reduce conflicts without rewriting the grammar.

The mechanism:

• %left '+' %left '*': assigns left associativity and a precedence level (later declarations have higher precedence).
• When a shift-reduce conflict arises between a pending reduction (say E → E + E) and a shift (say *), bison compares the precedence of the production (taken from its rightmost terminal, +) against the precedence of the lookahead token (*).
• If the token has higher precedence → shift (correct for + vs *).
• If the production has higher precedence → reduce.
• If equal precedence: associativity decides (left → reduce, right → shift, nonassoc → error).

%prec override: A production can be explicitly assigned a precedence with %prec TOKEN. The classic use is unary minus: expr: '-' expr %prec UMINUS where UMINUS is declared with higher precedence than binary minus.

This mechanism is elegant but dangerous if misapplied. It silently resolves conflicts that might indicate a genuine grammar design error. Always check bison's conflict summary (-v flag produces parser.output) and understand each resolved conflict.

/* Precedence ladder in bison (low to high, top to bottom) */
%nonassoc LOWER_THAN_ELSE   /* for dangling-else resolution */
%nonassoc ELSE
%left  OR
%left  AND
%nonassoc EQ NEQ
%nonassoc '<' '>' LE GE
%left  '+' '-'
%left  '*' '/' '%'
%right UMINUS '!' '~'  /* unary; highest precedence */

/* Dangling-else: shift-reduce conflict between:
   stmt: IF expr THEN stmt •        (reduce)
   stmt: IF expr THEN stmt • ELSE stmt (shift ELSE)
   Resolution: ELSE has higher prec than LOWER_THAN_ELSE
   → shift ELSE → inner if gets the else → correct C semantics */
stmt:
    IF expr THEN stmt           %prec LOWER_THAN_ELSE
  | IF expr THEN stmt ELSE stmt
  ;

The four LR variants form a strict containment hierarchy based on which grammars they can handle without conflict:

LR(0) ⊂ SLR(1) ⊂ LALR(1) ⊂ LR(1)

Every LR(0) grammar is SLR(1), every SLR(1) grammar is LALR(1), and every LALR(1) grammar is LR(1). The inclusions are strict — there exist grammars in each class that are not in the smaller class.

LR(0): No lookahead at all. Every complete item reduces on every terminal. Useful only for simple grammars (e.g., unambiguous grammars where every state has at most one complete item and no shift items on the same terminal).

SLR(1): LR(0) states + FOLLOW sets. Resolves many practical conflicts cheaply. Fails for grammars where FOLLOW is too permissive (different syntactic contexts for the same non-terminal).

LALR(1): The industrial sweet spot. Same state count as LR(0)/SLR(1), but with precise per-context lookaheads. Used by yacc, bison, most parser generators. Fails only for exotic grammars (LR(1)-but-not-LALR(1) grammars require contrived constructs).

LR(1): Maximum power for deterministic CFGs. Resolves all conflicts that are theoretically resolvable. Rarely needed in practice; used in some research compilers.

GLR (Generalized LR, Tomita 1987): Extends LR to handle all CFGs including ambiguous ones, by splitting the parser into multiple parallel stacks at conflicts. Used in modern tools like Tree-sitter (editors, syntax highlighting) and some NLP parsers.

# Grammar that is LALR(1) but NOT SLR(1):
# S → a E c | a F d | b F c | b E d
# E → e
# F → e

# FOLLOW(E) = {c, d},  FOLLOW(F) = {c, d}  (identical!)
# State containing [E → e •] and [F → e •]:
#   SLR: reduce E on {c,d} AND reduce F on {c,d} → reduce-reduce conflict
#   LALR(1): E is only reached via 'a', so lookahead(E→e•) = {c}
#            F is only reached via context, so lookahead(F→e•) = {d}
#            No conflict! Different contexts, different lookaheads.

# Grammar that is LR(1) but NOT LALR(1) (pathological):
# S → a E a | b E b | a F b | b F a
# E → e
# F → e
# (merging LR(1) states creates reduce-reduce conflict)