Role of Shift-Reduce Parsing (with a Worked Example)

shift-reduce parsing is a bottom-up technique that recognizes strings by repeatedly applying two operations: shift and reduce. The parser maintains a stack and an input pointer; it continues until it reaches an accept state or a reject/error.

In practical parser families, shift-reduce parsing is often implemented as LR parsing (e.g., SLR/LALR/Canonical LR). In that setting, a parsing table chooses an action for the current state and current lookahead token: typically “shift to a new state,” “reduce by production $A \rightarrow \beta$,” or “accept.” Even when the table is not shown explicitly, the conceptual role is the same: shift builds candidate “handles,” and reduce collapses them into higher-level constructs.

Why shift-reduce matters

• It performs parsing without recursion and in a single left-to-right pass over the input (with stack-based backtracking-free construction).
• It directly follows the grammar’s bottom-up structure: start from terminals, then reduce to nonterminals, until the start symbol is formed.

Key terms (role-focused):

• handle
• viable prefix
• lookahead

Important: The parser’s correctness hinges on using the right reduce rules (and when to reduce). In LR parsing, this decision is guided by the automaton state and lookahead, preventing incorrect premature reductions.

Example: Shift-Reduce Parsing for a Small Expression Grammar

We’ll illustrate the mechanics of shift-reduce parsing using a simple grammar for expressions without operator precedence complications:

Grammar $G$:

1. $E \rightarrow E + T$
2. $E \rightarrow T$
3. $T \rightarrow id$

Goal: parse the token sequence:
$$(id)\ +\ (id)\ $In symbols:$id + id$.

Assumption about actions (how a trace is possible)

To produce a concrete shift/reduce trace, we must know (or assume) the parser’s decision policy (typically from an LR parsing table). For instructional clarity, we’ll show a valid shift-reduce sequence consistent with bottom-up parsing:

• reduce each $id$ to $T$,
• then reduce $T$ to $E$ where appropriate,
• and finally reduce $E + T$ to $E$.

This demonstrates the role of shift and reduce, even if we do not display the full LR table.

Notation for the trace

• Stack shown as a sequence of grammar symbols (left to right).
• Input shown as unread tokens.
• Actions:
  • Shift: move next token from input to stack
  • Reduce: replace RHS symbols on top of stack with LHS nonterminal

What this trace teaches about the role of shift-reduce

• Shift postpones commitment: the parser collects enough symbols on the stack to potentially form a right-hand side (a handle).
• Reduce performs commitment: once the handle matches a production, it collapses the recognized structure into a nonterminal. This is how the parser builds larger syntactic constituents from smaller ones.
• The alternation continues until there is nothing left to read and the stack represents the whole sentence as the start symbol.

Mermaid summary of the role:

Action/State viewpoint (how LR connects to shift-reduce)

In an LR parser, the “role” of shift-reduce is realized by a deterministic choice:

• Shift occurs when the parsing table says to shift for the current (state, lookahead).
• Reduce occurs when it says to reduce by a specific production for that (state, lookahead).
• Accept occurs when it indicates the completed parse of the start symbol.

This makes shift-reduce parsing scalable: instead of guessing reductions, the parser uses precomputed automaton logic (parsing table plus states).