When a generated bottom-up parser reads a schema file, what do its shift and reduce actions each do to the parse stack?

middlemust knowfreq 68%

answer

two actions, one stack
input goes on, rules come off
a complete right-hand side on top
pop the right-hand side, push the nonterminal
reductions reversed give a rightmost derivation

basics

~20 s

Shift pushes the next input token onto the parse stack; reduce recognises a handle, a complete right-hand side sitting on top, pops those symbols and pushes the rule's left-hand nonterminal. The generated table decides which, per state and lookahead.

solid answer

~50 s

A bottom-up parser keeps a stack of grammar symbols (paired with table states) and one lookahead token. On shift it pushes the lookahead onto the stack and pulls the next token from the scanner. On reduce A -> beta it has recognised a handle: the top |beta| symbols are exactly that rule's right-hand side, so it pops them and pushes A instead, building one tree node; the lookahead is untouched, so several reductions can happen back to back. Two more actions finish the job: accept when the start symbol is on the stack with input exhausted, and error when the table has no entry. The choice is never made by hand-written logic — it is a table lookup on the current state plus lookahead, which is why the same driver loop runs every generated grammar.

A bottom-up parser keeps a stack of grammar symbols (paired with table states) and one lookahead token. On `shift` it pushes the lookahead onto the stack and pulls the next token from the scanner. On `reduce A -> beta` it has recognised a **handle**: the top `|beta|` symbols are exactly that rule's right-hand side, so it pops them and pushes `A` instead, building one tree node; the lookahead is untouched, so several reductions can happen back to back. Two more actions finish the job: `accept` when the start symbol is on the stack with input exhausted, and `error` when the table has no entry. The choice is never made by hand-written logic — it is a table lookup on the current state plus lookahead, which is why the same driver loop runs every generated grammar.

code

pseudocode · 21 lines

pseudocode

loop:
    s = top of state stack
    a = ACTION[s, lookahead]

    if a = shift(s2):
        push lookahead onto symbol stack
        push s2 onto state stack
        lookahead = next token from scanner

    else if a = reduce(A -> beta):
        pop |beta| symbols and |beta| states
        t = top of state stack
        push A onto symbol stack
        push GOTO[t, A] onto state stack
        -- lookahead is deliberately NOT consumed here

    else if a = accept:
        return the tree built by the reductions

    else:
        report error at lookahead

go deeper

for a junior

Recall the two moves: push the next token, or replace a finished rule's symbols with the name of that rule. Everything else in bottom-up parsing is bookkeeping around those two.

for a middle

Explain the stack of symbols plus states, what a handle is, that a reduction does not consume input, and that the action comes from a table lookup on state and lookahead rather than from hand-written code.

for a senior

Show that you can read a real trace: given a stack and a lookahead, say which action fires and why, and explain what it means when a stack you did not expect reaches a state.

for a principal

Frame the trade-off: a generated driver is uniform and fast but the parse is only as readable as the table, so investment goes into diagnostics and grammar shape rather than into parser code.

What the parse stack actually holds

A shift-reduce parser reads the input left to right and builds the tree from the leaves upward. Its working memory is a stack that holds grammar symbols — terminals it has shifted and nonterminals it has already built — in the order they appeared. A table-driven implementation pushes a parallel stack of states, one per symbol, because the action to take depends on where the recognizer is, not just on what the top symbol is.

At any moment the stack contents followed by the unread input form a sentential form: a string derivable from the start symbol. The parser's whole job is to keep that true while shrinking the stack toward the start symbol.

The four actions

shift — push the lookahead token onto the symbol stack, push the table's target state, and ask the scanner for the next token. This is the only action that consumes input.
reduce A -> beta — pop |beta| symbols and |beta| states, then push A and the state that GOTO gives for A from the newly exposed state. One tree node is built. The lookahead is not consumed, so a run of reductions can fire before the next shift.
accept — the stack holds the start symbol and the input is exhausted.
error — the state has no entry for this lookahead; the input is not in the language.

Handles: the part that may be reduced

A handle is not merely "some right-hand side that matches the top of the stack". It is a match whose reduction is the correct next step — the one that undoes the last step of a rightmost derivation of the input. This distinction is what the table buys you: a bare pattern match on the stack top would often be wrong, but the state encodes which rules are still viable given everything to the left, and the lookahead narrows it further.

A worked trace

Take a tiny data-definition grammar:

list -> list field
list -> field
field -> name colon type semi
type -> name

On the input name colon name semi:

Shift name. Stack: name.
Shift colon. Stack: name colon.
Shift name. Stack: name colon name.
Lookahead is semi; the top name is the handle for type -> name. Reduce. Stack: name colon type.
Shift semi. Stack: name colon type semi.
Reduce field -> name colon type semi. Stack: field.
Reduce list -> field. Stack: list. Input exhausted: accept.

Notice step 4: the second name was not shifted-then-forgotten, and it was not reduced the moment it landed — the table waited for the lookahead that made the reduction safe.

Why the reductions are a derivation read backwards

Write the reductions in reverse order — list -> field, then field -> name colon type semi, then type -> name — and you get exactly:

list => field => name colon type semi => name colon name semi

Each step expands the rightmost nonterminal, so a shift-reduce parse is a rightmost derivation traced backwards. That is why the family is called bottom-up: the derivation is discovered from its last step to its first.

Aspect	Shift	Reduce
Input consumed	one token	none
Stack effect	one symbol pushed	`\|beta\|` popped, one nonterminal pushed
Tree effect	a leaf is placed	an interior node is built
Driven by	`ACTION[state, lookahead]`	`ACTION[state, lookahead]` then `GOTO[state, A]`

Where people go wrong

Thinking the parser scans the whole remaining input to decide. It sees the stack's state and a fixed lookahead, nothing more.
Thinking a reduction consumes the lookahead. It does not, which is why consecutive reductions are normal.
Thinking the stack holds tokens only. After the first reduction it holds nonterminals too, and those are what later rules match.
Reducing on any right-hand-side match. Only the action table says whether this match is the handle.
Confusing the direction with top-down parsing, which starts from the start symbol and expands rules downward.

## What the parse stack actually holds A shift-reduce parser reads the input **left to right** and builds the tree **from the leaves upward**. Its working memory is a stack that holds grammar symbols — terminals it has shifted and nonterminals it has already built — in the order they appeared. A table-driven implementation pushes a parallel stack of **states**, one per symbol, because the action to take depends on where the recognizer is, not just on what the top symbol is. At any moment the stack contents followed by the unread input form a **sentential form**: a string derivable from the start symbol. The parser's whole job is to keep that true while shrinking the stack toward the start symbol. ## The four actions - **shift** — push the lookahead token onto the symbol stack, push the table's target state, and ask the scanner for the next token. This is the only action that consumes input. - **reduce `A -> beta`** — pop `|beta|` symbols and `|beta|` states, then push `A` and the state that `GOTO` gives for `A` from the newly exposed state. One tree node is built. **The lookahead is not consumed**, so a run of reductions can fire before the next shift. - **accept** — the stack holds the start symbol and the input is exhausted. - **error** — the state has no entry for this lookahead; the input is not in the language. ## Handles: the part that may be reduced A **handle** is not merely "some right-hand side that matches the top of the stack". It is a match whose reduction is the correct next step — the one that undoes the last step of a rightmost derivation of the input. This distinction is what the table buys you: a bare pattern match on the stack top would often be wrong, but the state encodes which rules are still viable given everything to the left, and the lookahead narrows it further. ## A worked trace Take a tiny data-definition grammar: - `list -> list field` - `list -> field` - `field -> name colon type semi` - `type -> name` On the input `name colon name semi`: 1. Shift `name`. Stack: `name`. 2. Shift `colon`. Stack: `name colon`. 3. Shift `name`. Stack: `name colon name`. 4. Lookahead is `semi`; the top `name` is the handle for `type -> name`. Reduce. Stack: `name colon type`. 5. Shift `semi`. Stack: `name colon type semi`. 6. Reduce `field -> name colon type semi`. Stack: `field`. 7. Reduce `list -> field`. Stack: `list`. Input exhausted: accept. Notice step 4: the second `name` was **not** shifted-then-forgotten, and it was **not** reduced the moment it landed — the table waited for the lookahead that made the reduction safe. ## Why the reductions are a derivation read backwards Write the reductions in reverse order — `list -> field`, then `field -> name colon type semi`, then `type -> name` — and you get exactly: `list => field => name colon type semi => name colon name semi` Each step expands the **rightmost** nonterminal, so a shift-reduce parse is a rightmost derivation traced backwards. That is why the family is called bottom-up: the derivation is discovered from its last step to its first. | Aspect | Shift | Reduce | |---|---|---| | Input consumed | one token | none | | Stack effect | one symbol pushed | `\|beta\|` popped, one nonterminal pushed | | Tree effect | a leaf is placed | an interior node is built | | Driven by | `ACTION[state, lookahead]` | `ACTION[state, lookahead]` then `GOTO[state, A]` | ## Where people go wrong - Thinking the parser scans the whole remaining input to decide. It sees the stack's state and a fixed lookahead, nothing more. - Thinking a reduction consumes the lookahead. It does not, which is why consecutive reductions are normal. - Thinking the stack holds tokens only. After the first reduction it holds nonterminals too, and those are what later rules match. - Reducing on any right-hand-side match. Only the action table says whether this match is the handle. - Confusing the direction with top-down parsing, which starts from the start symbol and expands rules downward.

Why does a reduce action leave the lookahead token untouched?
Because the reduction is about material already on the stack, not about the token ahead. The lookahead only selected the action. Leaving it in place lets several reductions fire in sequence — closing an inner construct, then the outer one — before the parser shifts again.
What happens to the state stack during a reduction?
It is popped in lockstep with the symbols, one state per symbol of the right-hand side. That exposes the state the parser was in before it started recognising the rule, and the new state comes from the goto entry for the rule's left-hand nonterminal from there.
Where does the parse tree come from if the stack only holds symbols?
Each reduction is the moment a node is created: the popped symbols' subtrees become its children and the pushed nonterminal carries the new node. Shifts create leaves. A parser that needs no tree just runs an action per reduction instead.

Assembling a flat-pack from a pile of parts: you lay pieces out in order (shift), and the moment a full sub-assembly is complete in front of you, you clip it together and treat it as one part (reduce).

saying these in an interview costs you the question

Says a reduce action also consumes the lookahead token
Thinks the stack only ever holds input tokens, never nonterminals
Describes it as expanding the start rule downward into the input
Believes the parser inspects the whole remaining input to choose
Reduces on any right-hand-side match without consulting the action table
Cannot say what a handle is beyond 'something that matches'

When a generated bottom-up parser reads a schema file, what do its shift and reduce actions each do to the parse stack?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

What the parse stack actually holds

The four actions

Handles: the part that may be reduced

A worked trace

Why the reductions are a derivation read backwards

Where people go wrong

▾common follow-ups3 questions

▾analogy~20 s

▾red flags6 flags

What the parse stack actually holds

The four actions

Handles: the part that may be reduced

A worked trace

Why the reductions are a derivation read backwards

Where people go wrong

answer

go deeper