6.1 Shift-Reduce Parsing

Top-down parsers begin with the start symbol and predict how it might expand. A bottom-up parser begins with the input tokens and repeatedly recognizes pieces that match the right side of grammar productions. Its central operation is a reduction: replace a recognized right-hand side, called a handle, with its production's left-hand nonterminal. If all reductions eventually produce the augmented start symbol, the input is syntactically valid.

For E -> E + E | id, the input id + id can be reduced in reverse:

id + id  =>  E + id  =>  E + E  =>  E

The parser cannot reduce whenever it sees id; it must know whether the current stack suffix is a complete handle and whether lookahead permits the reduction. LR parsing supplies that knowledge with states and tables. Shift-reduce parsing is the operational foundation underneath it.

A Stack of Symbols and States

A table-driven shift-reduce parser maintains an input cursor and a stack. Conceptually it holds grammar symbols; in an LR implementation it interleaves symbols with automaton states. At each step the parser consults ACTION[topState, lookahead]:

• shift s: push the lookahead token and state s, then consume one token.

• reduce A -> beta: pop the symbols/states for beta, consult GOTO[newTop, A], and push A and that destination state.

• accept: recognize a complete start production at EOF.

• error: no viable continuation exists in this state for this lookahead.

Reduction consumes no input. That detail matters: several reductions may occur before another shift, because a completed inner phrase can immediately make an enclosing phrase complete.

A Concrete Parse Table

An abstract description is less convincing than a real table. Applying the four actions to the minimal grammar E -> E + T | T and T -> id produces this LR parse table (states are numbers, s5 means shift and enter state 5, r(A->β) means reduce by that production, acc means accept, and a blank means error):

The two rightmost columns (E, T) are GOTO: after reducing to a nonterminal, the state left on the stack top selects the next state from these columns. The table fully determines every step, so the parser never needs to re-read past input.

Tracing id + id With the Table

Tracing id + id with the table above, writing the state beside each symbol, shows how the stack grows and shrinks:

Notice steps 2-3: two reductions in a row with no shift between them. The id reduces to T, and T immediately reduces to E. This is exactly what "a reduce consumes no input" means — a completed inner phrase instantly completes the enclosing one. The stack is longest at step 6, the intermediate state for recognizing E + id; reducing E -> E + T then shrinks it back to 0 E 1 in one step.

Handles, Viable Prefixes, and the Need for State

A handle is not merely any substring matching a production right side. It is the substring that should be reduced next in a rightmost derivation reversed. In id * id + id, the first id might match Factor -> id, but an expression grammar and current lookahead determine whether reducing it now is safe. The parser's stack is a viable prefix: a prefix that can occur on the stack of some valid right-sentential form without passing the next handle.

This is why simple “find a matching suffix and reduce it” is insufficient. Consider dangling else, precedence, and productions that share suffixes. A parser needs to remember a finite summary of what has been recognized, not scan the entire past or guess future input. LR automaton states are precisely that summary.

A useful mental model:

shift  = "I have seen one more token; keep possibilities open."
reduce = "This stack suffix is now certainly one grammar phrase."
goto   = "After recognizing that phrase in this context, resume this state."

Bottom-Up Parse Trees and AST Actions

Each shift usually carries a token's semantic value. Each reduction runs a semantic action that combines the values for the popped right-hand side into a new value for the left-hand side. For example:

Expr -> Expr + Term  { $$ = Binary($1, plusToken, $3); }
Term -> NUMBER       { $$ = Number($1); }

The grammar may contain precedence helpers or punctuation that do not belong in the AST. Semantic actions are where a parser turns a concrete parse into an abstract syntax tree. They should be side-effect disciplined: a parser generator may execute an action during a reduction, and error recovery can make execution order relevant.

Bottom-up parsing is especially valuable when a natural grammar is left-recursive. The grammar Expr -> Expr + Term | Term is inconvenient for recursive descent but exactly matches a left-associative reduction story. That does not make LR automatically better for every language. It trades direct handwritten control flow for a more powerful, table-driven machine.

Top-Down vs Bottom-Up at a Glance

The two families are often compared side by side. This table collects the key differences:

A useful intuition: a top-down parser must bet on which rule applies before the phrase is finished, so it is sensitive to shared prefixes and left recursion; a bottom-up parser keeps accumulating until the stack top forms a complete phrase, which is why it handles left association naturally at the cost of building a state machine and tables.

A Complete Small Trace

Use the unambiguous grammar E -> E + T | T and T -> id. Reading id + id EOF, a bottom-up parser first shifts id. It can reduce T -> id, then reduce E -> T; it shifts +, shifts the second id, reduces it to T, and finally reduces E + T to E. The important observation is that the parser did not guess a tree shape. Each reduction replaced a completed phrase on top of the stack with the category that phrase represents.

In an implementation, the stack might look like 0 id 5 after a shift, where 0 and 5 are LR states. Reducing T -> id pops both id and state 5; the remaining state chooses GOTO(0, T). Keeping states beside symbols is what lets the same grammar symbol mean different things in different contexts.

A Safe Trace Checklist

• After a shift, exactly one input token must have been consumed.

• After a reduce, input position must be unchanged, but the stack must be shorter unless the rule is epsilon.

• A reduce action must use the production's right-hand-side length, not the textual length of its token names.

• Acceptance requires both the augmented start condition and EOF. Reducing a Program while trailing tokens remain is not acceptance.