Parsingsimplified

Shift and Reduce, Step by Step

Two actions, one stack. Walk `1 + 2` through a bottom-up parser one move at a time and watch the tree assemble itself from the leaves upward — then see exactly what a conflict is.

The question

What do "shift" and "reduce" actually do to the stack, and when does the parser not know which to pick?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute
What the program is here

A stack of grammar symbols growing from the left, and the unconsumed input to its right. At every moment the concatenation of the two — stack contents followed by remaining input — is a *sentential form*: a valid intermediate step of a rightmost derivation of the input. The parse is the process of shrinking that form toward the start symbol, one reduction at a time, and the stack is where the shrinking happens.

What this phase may assume or do

A reduction by A -> α is legal only when α is a handle: it sits on top of the stack *and* it is the correct next reduction in the reverse rightmost derivation. Both halves matter. A substring matching a production's right-hand side may be sitting on the stack and still be the wrong thing to reduce — reducing it would produce a sentential form from which the input cannot be completed. Determining handle-hood from the stack alone is precisely what the LR automaton exists to do, and a state that cannot determine it is a conflict.

Key points

  • Only two actions exist: shift pushes the next token and advances the input; reduce pops a production's right-hand side and pushes its left-hand side without consuming input.
  • Everything else in LR parsing exists to answer "shift, or reduce by which production?" at each step.
  • Stack contents plus remaining input is always a valid sentential form; the parse shrinks it toward the start symbol.
  • Every reduce is one tree node, built by a semantic action; the root is created last, and with no actions the parser builds nothing at all.
  • Reading the action column upward gives the rightmost derivation — which is what "rightmost derivation in reverse" means in practice.
  • A handle is the substring whose reduction is the *correct* next step, not merely one that matches a production; reducing a non-handle kills a valid parse.
  • A shift/reduce conflict is a stack where a production is complete and the lookahead can also extend a different live production. Dangling else is the canonical instance.

Two actions, and that is all

A bottom-up parser has exactly two moves, plus accept and error.

Shift: take the next input token, push it onto the stack, advance the input. The parser is saying "I do not yet have enough to reduce; give me more evidence."

Reduce by A -> α: pop |α| symbols off the top of the stack — they must match α — and push A. The input does not move. The parser is saying "the top of my stack is a complete instance of a rule; I am replacing it with what the rule produces."

That is the entire machine. Everything in [[lr-parsing]] — items, states, closures, LALR merging — exists solely to answer one question at each step: shift, or reduce by which production? The stack manipulation itself is trivial.

The trace

simplifiedThe Stack column shows grammar symbols only. A real LR parser pushes a (symbol, state) pair at every step and the state is what actually selects the action — the symbols are shown here because they are what makes the derivation legible, but an implementation could discard them entirely and parse correctly using the states alone. Our stack also omits the initial state marker that a real implementation starts with.

Grammar: E -> E '+' T, E -> T, T -> NUMBER. Input: 1 + 2, with $ marking end of input. Read the table one row at a time and watch two things: the stack never contains more than three symbols, and every reduce shrinks it.

Pay particular attention to steps 2 and 3. After shifting 1, the parser reduces it to T and then immediately reduces T to E — two reductions with no shift between them, and no token consumed. That pair is where the tree's two leftmost nodes get built, and it is also where the parser commits to 1 being a complete left operand rather than the start of something longer. It can commit because the lookahead is +, and no production allows a NUMBER to be followed by + except through T and then E.

Parsing 1 + 2 with E -> E '+' T | T and T -> NUMBERsimplified
StepStackInputAction
1(empty)1 + 2 $shift 1
21+ 2 $reduce T -> NUMBER — pop 1, push T
3T+ 2 $reduce E -> T — pop T, push E
4E+ 2 $shift +
5E +2 $shift 2
6E + 2$reduce T -> NUMBER — pop 2, push T
7E + T$reduce E -> E '+' T — pop three, push E
8E$accept

Reading the trace as a tree

Every reduce builds one node. Step 2 creates a T node with the token 1 as its child; step 3 creates an E above it; step 6 creates a T over 2; step 7 creates the root E with three children. Four reductions, four nodes, and the root arrives last — which is the defining property of bottom-up parsing and the exact opposite of [[recursive-descent]], where the root node's function is entered first and returns last.

It is also why an LR parser produces nothing at all unless you tell it to. The reductions are the hooks: a generator attaches a *semantic action* to each production, run at the moment of reduction, with the popped symbols' values available as $1, $2, $3 and the result assigned to $$. Remove the actions and the parser still runs, still accepts or rejects correctly, and returns nothing — it is a recogniser, and tree construction is something bolted on top.

Now reverse the action column and read it upward: F/T -> NUMBER, then E -> T, then... that is the rightmost derivation of 1 + 2, played backwards. The trace *is* the derivation, which is what "rightmost derivation in reverse" means concretely rather than as a definition.

The same grammar with semantic actions — where the tree actually comes from
1%%
2 
3expr : expr '+' term   { $$ = mkBinary('+', $1, $3); }   /* runs at step 7 */
4     | term            { $$ = $1; }                       /* runs at step 3 */
5     ;
6 
7term : NUMBER          { $$ = mkNumber($1); }             /* runs at steps 2 and 6 */
8     ;
9 
10%%

Note $$ = $1 on the expr : term production. That reduction changes the stack — pops a T, pushes an E — and deliberately builds no node, because E and T are precedence scaffolding rather than constructs the language has. This is [[parse-tree-vs-ast]] happening at parse time: the chain rules exist in the grammar and are dropped in the action.

The handle, and why "matches a production" is not enough

At step 3 the stack held T and the parser reduced by E -> T. Why not wait? Because with + as the lookahead, T cannot be extended — no production has T followed by + on its right-hand side. Conversely, if the grammar also had T -> T '*' F and the lookahead were *, reducing E -> T at that moment would be *wrong*: the T still has a multiplication to absorb, and reducing it to E would make E * F — a form no production can complete. The parse would fail on input that is perfectly valid.

That is the content of the word handle. A handle is not "a substring matching some production". It is the substring whose reduction is the correct next step, and the reason it is a nontrivial notion is exactly the case above: two productions can match the same stack top, and only one of them keeps the parse alive. The LR automaton's states encode which, by tracking every production still in play alongside how far into it the stack has got.

The conflict, concretely

A shift/reduce conflict is a state where a completed production sits on top of the stack *and* the lookahead can legally extend a different production that is also in play. Both actions lead to a valid parse of something; the automaton cannot tell which one leads to a valid parse of *this*.

The dangling else shows it on a stack you can hold in your head. Grammar: stmt -> 'if' expr 'then' stmt | 'if' expr 'then' stmt 'else' stmt | other. Input: if a then if b then c else d. Trace it to the point where the stack is if expr then if expr then stmt and the lookahead is else.

Reduce stmt -> 'if' expr 'then' stmt now, and the inner if is complete; the else then attaches to the outer one, meaning "if a is false, do d". Shift the else instead, and the inner if continues; d runs when a is true and b is false. Both are derivations of the input under this grammar, which is the definition of an ambiguous grammar, and every language with this syntax picks one by fiat — C, C++, Java, JavaScript and Go all specify nearest-if, which corresponds to shift.

A reduce/reduce conflict is the harder sibling: two completed productions on the same stack top, and the parser has two rules it could apply. There is no defensible default. Bison picks the earlier production and warns; the honest response is almost always that the grammar means two different things by the same syntax, or that LALR merging discarded a lookahead distinction that would have separated the two states.

The dangling-else conflict, at the exact step where it appearssimplified
StepStackInputAction
…if expr thenif b then c else d $shift — parsing the inner statement
…if expr then if expr thenc else d $shift c
nif expr then if expr then stmtelse d $⚠ CONFLICT
n (a)if expr then stmtelse d $reduce first → else binds to the OUTER if
n (b)if expr then if expr then stmt elsed $shift first → else binds to the INNER if
———Yacc/Bison default: shift, i.e. (b), i.e. nearest if — which is what C, Java and Go specify

How it works

The steps, in the order the compiler takes them.

  • Initialise: empty symbol stack, input positioned at the first token, parser in the automaton's start state.
  • Consult the ACTION table with the current state and the lookahead token.
  • Shift: push the token and the target state, advance the input by one token.
  • Reduce by A -> α: pop exactly |α| symbol/state pairs, exposing an earlier state; push A and the state the GOTO table gives for (exposed state, A). The input is untouched.
  • Run the production's semantic action at the moment of reduction, with the popped values as its inputs and its result becoming the value of the newly pushed nonterminal.
  • Accept when the augmented start production is reduced with end-of-input as the lookahead.
  • Error when the ACTION cell is empty; the populated cells in that row are the legal tokens, and recovery pops states until one with an error production is exposed.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

  • A reduction fires one step too early because a lookahead distinction was lost, and a valid program is rejected with a syntax error at a token that looks entirely reasonable.
  • The dangling-else conflict is resolved by the generator's default and matches the language spec, so nobody investigates — and a later construct with the same conflict shape is resolved the same way and does not match the spec.
  • Semantic actions have side effects and the grammar is later changed so a production is reduced in a different order; the parser still accepts the same language and the actions now run against a half-built structure.
  • A reduce/reduce conflict is silenced by reordering the productions in the file, which changes which rule wins; the fix works, nobody records why the order matters, and a later alphabetical tidy-up reintroduces the bug.
  • Error recovery pops the stack to the nearest error production and discards a whole block, so a file with two independent errors reports only the first and then "syntax error at end of input".
  • A grammar author adds a production and the conflict count rises by two; because the message is only a count, the construct that broke is not the construct that was edited.

When it helps

  • Debugging a generated parser: the trace is the only representation in which a conflict is visible as a concrete situation rather than a state number.
  • Understanding why an LR grammar prefers left recursion — the trace makes it obvious, since E -> E + T reduces the accumulated left side immediately and the stack never grows.
  • Explaining a conflict to someone else, or to yourself in six months. "At this stack, with this lookahead, both of these are legal" is a complete explanation; "conflict in state 143" is not.
  • Checking a hand-written parser against a grammar: tracing the same input through both and comparing the order nodes are built in catches associativity errors that tests miss.

When it hurts

  • Reasoning about performance or memory. The trace is a model of the decisions, not of the implementation, which uses compressed tables, default reductions and no symbol stack at all.
  • Reasoning about error messages. Tracing shows where the parser stops; it does not show what the user was trying to write, which is the information the message actually needs and the parser does not have.

What it costs

Every one of these is paid by something.

  • The two-action machine buys extreme simplicity at the core — the parse loop is twenty lines regardless of grammar size — and pays by pushing all the difficulty into table construction, where it is much harder to inspect.
  • Deferring the decision until a full right-hand side is on the stack buys handle-finding and left recursion, and costs the parser any notion of which construct it is inside, so both diagnostics and recovery must be reconstructed from the stack after the fact.
  • Semantic actions at reduction points buy a clean separation between recognition and tree building, and pay with actions that are order-dependent and effectively untestable in isolation: they only run in the order the automaton chooses.
  • Resolving a conflict by generator default buys a working build today and costs a piece of the language definition that now lives in the tool rather than in the grammar file.

What else you could do

What a different compiler or language does instead, and when that is better.

  • A top-down trace — the call stack of [[recursive-descent]] — builds the root first and the leaves last. Same tree, opposite order, and a parser that always knows which construct it is inside.
  • GLR keeps both branches of a conflict alive on a graph-structured stack instead of choosing, deferring the decision until one branch dies. That is how tree-sitter parses source that does not parse.
  • Earley parsing keeps every partial derivation in a chart rather than a stack, accepting any context-free grammar with no conflicts at all, at cubic worst-case cost.
  • [[pratt-parsing]] sidesteps the expression-grammar conflicts entirely by making precedence a runtime comparison rather than a table-construction question.

See it for yourself

The flag, dump or tool that shows you this directly.

  • bison -Wcounterexamples (3.8+) prints a concrete input that triggers each conflict — effectively generating the trace above for your own grammar.
  • bison --report=all writes parser.output with every state's item set and the action taken on each lookahead; find the conflicted state number in it and the two competing items are printed side by side.
  • Enable the runtime trace: compile a Bison parser with -DYYDEBUG=1 and set yydebug = 1, and it prints every shift and reduce with the stack as it runs. This is the real version of the table above.
  • tree-sitter parse --debug file.js prints the shift/reduce actions of its GLR parser, including where it forks.
  • Our stepper at /compilers/parsing runs this trace interactively over an input you type, with the item set of the current state shown next to the stack.

Plausible wrong readings

Stated the way a confident engineer states them.

  • "Reduce means the parser removes something from the program." It replaces symbols on its own stack with the nonterminal they form. Nothing about the input changes, and reduce consumes no tokens at all.
  • "If the top of the stack matches a production, reduce." That is exactly the mistake the notion of a handle exists to prevent. A stack top can match a production and still be the wrong reduction, killing an otherwise valid parse.
  • "Shift/reduce conflicts happen because the parser is not smart enough." They happen because the grammar admits two derivations. A smarter parser (GLR) does not resolve the ambiguity, it returns both.
  • "The parser builds the tree." The parser recognises the input. Tree construction happens in semantic actions attached to reductions, and a parser with no actions produces no tree while parsing perfectly.

Misconceptions

The claim, and what is actually true.

Shift and reduce are alternatives at every step, so the parser is guessing.
In a conflict-free grammar the state and lookahead determine the action uniquely. Guessing only enters where the grammar is ambiguous, and then the generator reports it before the parser ever runs.
Reducing early is safer than reducing late.
Reducing a non-handle destroys a valid parse. The whole point of the automaton is to reduce at exactly the right moment, and "as soon as it matches" is not that moment.
The stack contains the parse tree.
It contains a viable prefix of grammar symbols — a flat sequence. Tree nodes live in the semantic values attached to those symbols, which is a separate stack in most implementations.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

The parser has a stack and two moves. Shift: push the next token. Reduce: when the top of the stack matches the right-hand side of a rule, replace those symbols with the rule's left-hand side. Keep going until the stack holds just the start symbol. Each reduce builds one node of the tree, so the tree grows from the leaves up and the root is the last thing created.

practical

When a generated parser rejects input you believe is valid, get the trace — yydebug for Bison, --debug for tree-sitter — and find the last reduce before the error. Nine times out of ten the parser reduced something that should have stayed open, and the reason is a missing lookahead distinction, which is the same information a conflict report would have given you if you had read it. For conflicts specifically, do not reason from the state number: use -Wcounterexamples to get an input that exhibits it, trace that input, and the competing actions become an ordinary situation you can think about.

advanced

The handle concept is where bottom-up parsing gets its power and its opacity in the same stroke. Deciding handle-hood from the stack alone is undecidable in general for context-free grammars; the LR construction makes it decidable by restricting to grammars where a finite automaton over viable prefixes suffices, and a conflict is precisely the automaton reporting that this grammar is outside that class. That framing explains why the fixes are what they are: rewriting the grammar moves it back inside the class, precedence declarations override the automaton at named points, and GLR abandons the requirement that the decision be made at all — keeping every handle hypothesis alive on a shared stack and letting the input kill the wrong ones. Each is a different answer to "what do we do when the finite automaton is not enough", and the choice among them is most of what distinguishes one parser generator from another.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

simplifiedOur stack shows grammar symbols; a real LR parser stacks states and can parse without the symbols at all. Real tables also use default reductions — reducing without consulting the lookahead in states where every non-error action is the same reduction — which means a real trace performs some reductions before it has detected an error that our trace would catch immediately. The accepted language is identical; the step at which an error is reported is not.
implementationThat the dangling-else conflict resolves to shift is Yacc and Bison behaviour, and it matches what C, C++, Java, JavaScript and Go specify. Menhir refuses to resolve it without an explicit declaration, and a hand-written recursive-descent parser resolves it implicitly by parsing the else in the innermost call — arriving at the same answer through a completely different mechanism.
typicalThe claim that a reduce/reduce conflict signals genuine grammar ambiguity holds for most cases in practice, but not all: LALR state merging can produce reduce/reduce conflicts in grammars that are unambiguous and are accepted by canonical LR(1). Switching the generator to LR(1) is a legitimate diagnosis step before rewriting the grammar.

If you were asked this in an interview

  • Trace 1 + 2 through a shift/reduce parser with E -> E + T | T and T -> NUMBER, showing the stack at every step.
  • At step 3 the stack holds just T and the parser reduces to E. Why is that not premature?
  • Show me a stack and a lookahead where the parser genuinely cannot decide, and tell me what the two outcomes mean to the programmer.

Connections

DSAstackn-ary-treedp-state-machine
Domains that do not exist yet
  • Programming Languages & Runtime Internals — Stack machines and their operand stacks
    The parse stack and a VM operand stack are the same shape used for different content — grammar symbols against runtime values. The runtime side is owned there; [[stack-based-vm]] is our compiler-side treatment.