LR Parsing

LR parsing reads tokens from left to right and constructs the reverse of a rightmost derivation via shift and reduce operations. It first accumulates the structures it has seen, then decides which production rule these symbols belong to. Unlike naive recursive descent, deterministic LR can directly handle many left-recursive grammars.

The runtime is typically just a state stack plus a table-lookup loop; the complex parts lie in generating the tables, understanding conflicts, and designing semantic actions. Small grammars can be constructed by hand, but in engineering, they are usually generated by tools.

Shift, Reduce, and the State Stack

Consider the grammar E → E + n | n and the input n + n: first shift n, then reduce it to E; subsequently shift the + and the second n, and finally reduce E + n to E. AST nodes can be constructed simultaneously during reduction.

If the state stack and semantic value stack are maintained separately, reducing a right-hand side of length r pops r items from each; the state stack bottom still retains the start state. If states and grammar symbols are interleaved, the description of the number of popped items differs. An empty production pops 0 items but still requires entering the post-reduction state via GOTO.

Items: A dot indicates how far a production has been recognized

The item E → E · + n indicates that an E has been recognized, and the next expected tokens are + and n; E → E + n · indicates that the right-hand side is complete, so a reduction can be considered.

A state often contains multiple items, representing that the current prefix might be in various syntactic contexts. It records information about viable prefixes, not just a single source code token.

For LR(0) item sets, when the closure encounters A → α · B β, it adds all productions B → · γ for B and recursively expands them. goto(I, X) first moves the items in I where the dot precedes X one position to the right, then takes the closure. Continuously executing goto on new sets constructs the item set automaton.

Edges on terminals form shift actions, while edges on non-terminals form GOTO actions. The key difference among LR variants lies in which lookahead symbols trigger reductions for completed items.

Running n+n through five states: After reduction, return to the old state, then check GOTO

Number the rules for the initial grammar: Rule 1 is E→E+n, Rule 2 is E→n. Use the following state numbers, which are manually specified for this example and do not need to match generator output.

The closure of state 0 contains E→·E+n and E→·n; after recognizing E, it goes to state 1, expecting + or end-of-input; after recognizing n, it goes to state 2, where it can reduce E→n. State 3 represents E→E+·n, and state 4 completes E→E+n·. Since FOLLOW(E)={+, $}, the corresponding reductions are filled in for these two lookaheads.

ACTION = {
    (0, "n"): ("shift", 2), (1, "+"): ("shift", 3),
    (1, "$"): ("accept", 0), (2, "+"): ("reduce", 2),
    (2, "$"): ("reduce", 2), (3, "n"): ("shift", 4),
    (4, "+"): ("reduce", 1), (4, "$"): ("reduce", 1),
}
GOTO = {(0, "E"): 1}


def parse(tokens):
    if any(t not in ("n", "+") for t in tokens):
        raise SyntaxError("invalid token")
    source = list(tokens) + ["$"]
    states, values, pos, trace = [0], [], 0, []
    while True:
        action = ACTION.get((states[-1], source[pos]))
        if action is None:
            raise SyntaxError(f"unexpected {source[pos]} at token {pos}")
        kind, number = action
        trace.append((tuple(states), pos, kind))
        if kind == "shift":
            states.append(number)
            values.append(("n",) if source[pos] == "n" else "+")
            pos += 1
        elif kind == "reduce":
            length = 3 if number == 1 else 1
            rhs = values[-length:]
            value = ("+", rhs[0], rhs[2]) if number == 1 else rhs[0]
            del values[-length:]
            del states[-length:]
            states.append(GOTO[(states[-1], "E")])
            values.append(value)
        else:
            assert len(values) == 1 and pos == len(tokens)
            return values[0], trace


node, trace = parse(["n", "+", "n"])
assert node == ("+", ("n",), ("n",))
assert [p for stack, p, action in trace] == [0, 1, 1, 2, 3, 3]
assert parse(["n", "+", "n", "+", "n"])[0] == ("+", node, ("n",))
assert parse(["n"])[0] == ("n",)
for tokens in ([], ["+", "n"], ["n", "n"], ["n", "+"], ["n", "$"]):
    try:
        parse(tokens)
    except SyntaxError:
        pass
    else:
        raise AssertionError("invalid input accepted")

After reading the second n, the stack is [0,1,3,4]. Reducing length 3 pops back to [0], then checks GOTO(0,E)=1. The lookahead is still $, and the accept action happens in the next step. You cannot check GOTO using the pre-reduction stack top 4, nor can you consume $ just because a reduction was executed.

This example has no empty rules, so length in the code is always greater than zero. When extending to ε, you must specifically handle zero length; in Python, del stack[-0:] is equivalent to clearing the entire stack, not "popping nothing." This is a boundary condition easily missed when copying algorithm descriptions directly into slice code.

Why does reduction change the stack without consuming lookahead?

Inspect reduction with both pre-pop and post-pop stacks visible. Lookahead has its own position: shift moves it; reduce removes the RHS and uses the remaining top for GOTO. Select any action or play the trace. Invalid input follows the same table and stops at a missing entry rather than skipping errors for a tidy demonstration.

How Much Context Do SLR, LR(1), and LALR Preserve?

The closure of an LR(1) item [A → α · B β, a] uses terminals from FIRST(βa) as the lookahead for productions of B. a represents what is allowed to follow after A completes; it cannot be simply understood as the character immediately to be read after the dot.

Canonical LR(1) can handle more grammars than LALR(1), but still not all context-free grammars. Ambiguous grammars cannot yield a unique analysis by deterministic LR tables without disambiguation rules.

An Example That Is LR(1) But Not LALR(1)

S → a A d | b A e | a B e | b B d
A → c
B → c

This grammar only generates four strings: acd, bce, ace, bcd, each with a unique derivation. After reading ac, if followed by d, c should be reduced to A; if followed by e, it should be reduced to B; after reading bc, it is exactly the opposite.

This shows that conflicts may arise from the compression of context in table construction; seeing a reduce/reduce conflict does not immediately imply the original grammar is ambiguous. SLR's global FOLLOW also suffers from similar precision issues. The Bison manual specifically discusses conflicts caused by LALR limitations and methods such as IELR or canonical LR to address them. Mysterious Conflicts

Distinguishing "Grammar Conflicts" from "Merge-Induced Conflicts" Using a Generator

Write the above four-string grammar as conflict.y, using single quotes for character terminals:

%start S
%%
S: 'a' A 'd' | 'b' A 'e' | 'a' B 'e' | 'b' B 'd';
A: 'c';
B: 'c';
%%

bison -Dlr.type=lalr --report=states,lookaheads -o lalr.c conflict.y
bison -Dlr.type=canonical-lr --report=states,lookaheads -o canonical.c conflict.y

This step only generates tables and reports; no lexer is needed, and it is not yet a runnable program. LALR should show two reduce/reduce conflicts, while canonical LR can preserve the different contexts after ac and bc without such conflicts. When checking the reports, locate the lookaheads for the completed items A→c· and B→c·; do not just compare the total number of states.

If you continue using the default LALR with conflicts, some strings may take the wrong reduction path; therefore, "the tool still generated a C file" does not mean the language has been correctly implemented. In engineering, you should explicitly choose an appropriate construction method or rewrite the grammar, rather than ignoring warnings. Algorithm Description in Bison Manual Source

Which correspondence is lost when states merge?

Before merging, each origin preserves a prefix/item/lookahead correspondence. After unioning lookaheads, A and B no longer retain which prefix supplied d. Both original rows stay visible to expose the lost information. Each of the four strings still has one derivation in the original grammar; a table conflict is not proof of ambiguity.

Distinguishing Two Types of Conflicts and Resolution Basis

A shift/reduce conflict means that under the same state and lookahead, both shifting and reducing are possible. For example, E → E + E | E * E | n does not express precedence, so n + n * n can have different tree structures. You can rewrite it as a layered grammar or use the tool's precedence and associativity declarations to express language rules.

A reduce/reduce conflict means there are multiple candidate reductions at the same position. It could be true ambiguity or the result of context merging mentioned above. You should examine the items, lookaheads, shortest triggering input, and counterexamples, rather than simply suppressing warnings.

Precedence declarations are semantic choices, not proofs of correctness for arbitrary conflicts. Especially when two reductions perform different semantic actions, defaulting to one rule may change the AST or side effects.

Bison and LALRPOP: Names Do Not Equal Algorithms

Bison supports configurations such as LALR, IELR, canonical LR, and GLR. Although LALRPOP's name contains LALR, the default algorithm in its project documentation is LR(1). You cannot uniformly label all tools as "default LALR," nor can you stipulate a fixed ratio for the number of states between canonical LR and LALR. Bison Grammar and Parsing Capabilities, LALRPOP Project Documentation

GLR can preserve multiple analysis branches at conflict points, later pruning or merging them, but ambiguous semantics still need to be defined, and the worst-case cost differs from deterministic LR. Delayed semantic actions, shared tree representations, and error handling all require additional design.

Error Recovery: error is a Special Mechanism

In Bison, you can write such a recovery production:

statement: error ';' { yyerrok; };

error is a special symbol for the parser, not a rule for "any character" returned by the lexer. During recovery, the parser can pop the stack until a state can shift error, then discard input as needed to find a token that allows continuation. Synchronizing to a semicolon is just an exit provided by this rule; not all errors naturally stop at a semicolon.

Resources for discarded symbols must be properly released; semantic values after recovery should also have clear representations to avoid subsequent stages treating error structures as normal nodes. Some recoveries temporarily suppress cascading diagnostics; do not treat "parser return" as proof that the source code is completely correct. Bison Error Recovery

Engineering Judgment

The table-lookup process of deterministic LR is typically linear with respect to input length, provided there is a fixed grammar, no cyclic empty reductions, and controlled semantic actions; the costs of table construction and error recovery are separate. Incremental editing support also depends on tree structure, reuse strategies, and lexical context; you cannot judge solely based on LL/LR labels.

When understanding conflicts, first reconstruct "read prefix, current item, one lookahead, candidate actions," then determine whether it is a language rule, grammar expression, or algorithm precision issue. Continue reading AST Design and Error Recovery.

Keywords: LR, item, closure, goto, shift reduce, SLR, LALR, canonical LR, IELR, GLR, lookahead, conflict, Bison, LALRPOP