Shift-Reduce Parsing

Shift-reduce parsing is the engine that powers every bottom-up parser. It uses a stack and just two basic operations — shift and reduce — to walk through the input and reduce it back to the start symbol.

Operator-precedence parsing, SLR, LALR, and CLR all share this exact engine. They differ only in how they decide which action to take.

The Two Core Operations

Plus two terminal states:

That's it. The entire LR family — yacc, bison, GNU Bison, all of them — is built on these four cases.

The Setup

A shift-reduce parser maintains:

1. A stack that holds grammar symbols (and, in LR, also state numbers).
2. An input buffer that contains the remaining tokens, terminated by an end-marker $.

Initially: stack is empty (or just $), input is the full token stream.

The parser repeatedly chooses shift or reduce until the stack holds the start symbol and the input is empty.

Let's trace a full parse of id + id * id using the classic expression grammar:

The format is Stack | Input | Action. The top of the stack is on the right.

Walk through it slowly. Some takeaways:

• Every id was shifted onto the stack, then immediately reduced through F → T → E or F → T.
• After seeing E + T the parser did not reduce immediately — it shifted * first. That choice (shift over reduce) is precisely how precedence is enforced.
• A correct shift-reduce parser always picks the right action. The tables tell it how.

Why the Stack?

The stack holds everything we have committed to so far — i.e. the rightmost prefix of a right-sentential form. Reducing always works on the top of the stack, because that is where the handle lives. The rest of the stack stays untouched.

This is why bottom-up parsing is so efficient: the parser only ever looks at the top few elements of the stack and one lookahead token — never at the full history of the parse.

The question that defines every shift-reduce parser variant is: when should we reduce, and when should we keep shifting?

Naïve Approach — Try Both

We could try a reduction at every step and back out if it leads to failure. This works but is exponential in the worst case — useless for real compilers.

Operator-Precedence Approach

Use a precedence table over pairs of terminals. If the top-of-stack terminal has higher precedence than the lookahead, reduce; otherwise shift.

Simple, but only works on operator grammars.

LR Approach — States and Items

Every shift-reduce parser in the LR family uses a precomputed DFA of LR items. The parser is always in some state. The state plus the lookahead uniquely determine the action:

The DFA is computed offline (the "table construction" of the previous topic). At runtime, the parser just does table lookups.

Visualizing the Decision

This compact mechanism is the entire core of every LR parser. The tables are different from grammar to grammar, but the driver is universal.

Sometimes the table says both "shift" and "reduce" for the same (state, lookahead) pair. That is a shift/reduce conflict.

A Classic — The Dangling Else

The ambiguity in this grammar shows up directly as a shift/reduce conflict:

While parsing if E then if E then S else S, after we have:

we can:

• Shift the else — attach it to the inner if. (This is what most languages do.)
• Reduce if E then S — attach the else to the outer if.

Both are grammatically valid. The parser must pick one.

How Tools Resolve It

Bison's default — prefer shift — happens to produce the correct dangling-else behaviour. That is why the conflict is famously printed as a warning in bison rather than an error.

Another Common Source — Operator Precedence

Without precedence information, the grammar:

produces shift/reduce conflicts at the + and *. Tools like bison let you declare:

and they break the conflict automatically using these precedences.

How to Tell If a Conflict Is Real

Real production grammars almost always have a few shift/reduce conflicts that are resolved with directives. That is normal — and not a bug.

When the table says two different reductions apply at the same (state, lookahead), it's a reduce/reduce conflict. These are harder to fix than shift/reduce conflicts — they almost always indicate a genuine grammar problem.

A Small Example

After parsing the single token a, the parser has A → a · AND B → a · both ready to fire. With lookahead b it can't tell which reduction to apply.

Why It Is Hard

In a shift/reduce conflict, choosing "shift" is often a reasonable default. But choosing "the wrong reduction" produces a wrong parse tree and the error is usually deep in semantic analysis (or never caught at all).

Typical Causes

How to Fix Them

The first option is the most common and the cleanest. Real languages tend to put distinguishing tokens up front (var, function, let, class) for exactly this reason — they make parsing trivial.

When the parser hits an empty cell in the ACTION table, it has a syntax error: neither shift nor reduce is legal. What happens next is up to the implementation — but a few patterns are universal.

Panic-Mode Recovery

The most common technique: skip input tokens until a designated synchronising token (often ;, }, or else) is found, then resume parsing.

The user gets one decent error message, the parser keeps going, and the next error can also be reported. This is what gcc and clang do by default.

Phrase-Level Recovery

Tools like bison let you write error productions in the grammar:

The token error is bison's built-in placeholder. When parsing fails inside a statement, the parser tries to reduce by the error rule — consuming input up to a ; — and then resumes.

This pattern lets the grammar designer hand-craft recovery for the most common mistakes (missing ;, missing )).

Limitations of LR Errors

Compared to a top-down recursive-descent parser, LR error messages tend to be:

• Reactive — the parser only knows what it has already seen, not what it expected.
• Less specific — "syntax error near then" rather than "missing ) before then".

This is why some modern compilers (Clang in particular) have moved back to handwritten predictive parsers for the front end — they trade engineering effort for much better error messages.

When Shift-Reduce Is Worth It

Despite the error-message disadvantage, shift-reduce parsing remains the workhorse of language tooling because:

1. Tables are generated automatically from a grammar file — no hand-coding 500 mutually-recursive functions.
2. Performance is excellent — pure table lookups, O(n) in the input.
3. Grammar changes are cheap — modify the .y file, rerun the tool, done.
4. Almost every CFG is LALR(1) — the class is enormous in practice.

If you ever build a language with bison, ANTLR (in LR mode), or Menhir, you are using a shift-reduce parser.