Bottom-Up Parsing

A derivation rewrites the start symbol into a string of terminals by repeatedly replacing nonterminals with production bodies. A rightmost derivation always expands the rightmost nonterminal at each step. Bottom-up parsing's central insight is that constructing a parse tree bottom-up is equivalent to finding a rightmost derivation and reading it backward — starting from the final string of terminals and undoing one rewrite step at a time until only the start symbol is left. This reversed sequence of rewrite-undos is called a rightmost derivation in reverse, and it is exactly what a shift-reduce parser computes. Each undo-step needs a target: a substring of the current sentential form that (a) matches the body of some production `A → β`, and (b) sits in a position such that replacing it with `A` yields the previous line of the rightmost derivation. Such a substring is called a handle. Crucially, a handle is not just any match of a production body — it must be the specific occurrence that a rightmost derivation would have expanded last. Finding handles reliably, without ever reducing the wrong substring or reducing too early or too late, is the whole game of bottom-up parsing. The mechanism that finds handles efficiently is a shift-reduce parser: a stack (initially empty) holding a mix of terminals and nonterminals already recognized, and a remaining input buffer of unread tokens, terminated by a special end-marker `$`. At every step the parser makes one of four possible moves:

• Shift: push the next input token onto the stack.
• Reduce: pop a handle (matching some production's right-hand side `β`) off the top of the stack and push the corresponding left-hand nonterminal `A`.
• Accept: when the stack contains exactly the start symbol and the input is exhausted, the parse succeeds.
• Error: no shift or reduce move is legal — the input is rejected.

A parser that always uses the rightmost handle available and never has to guess between two legal actions is deterministic; the LR family (foreshadowed but not built here) is the general recipe for making this determinism automatic and table-driven for a large grammar class. Without such tables, a shift-reduce parser can still be built (or simulated) directly for restricted, unambiguous grammars, and understanding that direct mechanism is the goal of this article.

The driver loop is strikingly small; all the intelligence lives in how the parser decides, at each configuration, whether to shift or to reduce, and if reducing, by which production. Call the pair (stack contents, remaining input) a configuration. The parser transitions between configurations until it reaches an accepting one or gets stuck. ``` function SHIFT-REDUCE-PARSE(grammar G, input tokens w1 w2 ... wn): stack ← [ ] # bottom-of-stack marker buffer ← [w1, w2, ..., wn, ] # input with end marker pointer ← 0 # index of next unread token in buffer loop: if stack == [$, StartSymbol] and buffer[pointer] ==$: return ACCEPT, build-tree-from(history) handle ← FIND-HANDLE(stack, buffer, pointer) # the decision oracle if handle is NONE: if buffer[pointer] == $ and stack has more than one symbol: return ERROR # stuck: no reduce, no input left

# SHIFT push(stack, buffer[pointer]) pointer ← pointer + 1 record action SHIFT else:

# REDUCE using production handle.production : A -> beta pop(stack, length(handle.beta)) push(stack, handle.production.head) # push A attach children = popped symbols under new tree node A record action REDUCE(handle.production) function FIND-HANDLE(stack, buffer, pointer):

# Try every suffix of the stack (from shortest to longest) as a

# candidate body beta of some production A -> beta. for length L = 1 upto size(stack) - 1: # never touch the $ marker candidate ← top L symbols of stack for each production (A -> beta) in G: if candidate == beta: if reducing here is consistent with a valid rightmost derivation continuation (verified via viable-prefix / precedence check): return {production: (A -> beta), beta: beta} return NONE ``` Two points deserve emphasis. First, `FIND-HANDLE` as written is a specification, not yet an efficient algorithm — checking "is this a valid handle" by brute force over all productions and all stack suffixes is what a real implementation must avoid; that avoidance, via precomputed automaton states, is exactly the subject that LR and LALR Parsing tackles. Second, the loop is a faithful shift-reduce skeleton used even by hand-built or precedence-based parsers: everything about which grammars it works correctly and efficiently for is encoded in how `FIND-HANDLE` is implemented.

Simplified decision rule (operator-precedence style). For expression grammars, a common simplified oracle compares the precedence of the terminal on top of the stack with the next input terminal: ``` function SIMPLE-ORACLE(stack_top_terminal a, next_input_terminal b): if precedence(a) < precedence(b): return SHIFT if precedence(a) > precedence(b): return REDUCE if precedence(a) == precedence(b): return SHIFT if right-associative(a) else REDUCE ``` This is enough to disambiguate `id + id id` correctly (multiply binds tighter, so we shift past `+` and reduce the ``-expression first) without ever consulting a full LR table — but it only works for the narrow class of operator-precedence grammars, a stepping stone toward the fully general table-driven approach. The diagram below shows one instant mid-parse: the stack holds a mix of already-reduced nonterminals and shifted terminals, growing to the left, while the buffer holds the unconsumed suffix of the token stream, with `$` marking true end of input.

Time complexity. For any grammar processed by a table-driven (LR-style) shift-reduce parser, each input token is shifted exactly once, and the total number of reduce actions across a whole parse is bounded by the number of internal nodes of the parse tree, which is linear in the number of tokens for any fixed grammar. Each individual action (shift or reduce) with a precomputed table takes `O(1)` time — one table lookup and, for reduce, popping a bounded number of stack symbols (bounded by the length of the longest production body, a grammar constant). This gives: ``` Total time = O(n) shifts + O(n) reduces, each O(1) ⇒ O(n) overall ``` where `n` is the number of input tokens. This linear bound is the entire reason bottom-up (LR-style) parsing displaced the exponential-worst-case general CFG parsers (like naive CYK or Earley without restriction) for compiler frontends: a compiler must parse million-line codebases, and only linear-time parsing scales. The pseudocode `FIND-HANDLE` shown above is deliberately not the efficient version — it brute-forces over stack suffixes and productions, giving `O(n^2 · |G|)` or worse in the naive rendering. The entire achievement of the LR construction (previewed, not built, here) is precomputing a deterministic finite automaton over viable prefixes so that the handle-recognition decision collapses to a single table lookup keyed on (current state, lookahead token) — turning the specification above into the `O(n)` real algorithm. That construction is the natural next step after this article.

Space complexity. The stack holds at most `O(n)` symbols in the worst case (e.g., a long chain of shifts before any reduction, as in deeply nested parentheses), so space is `O(n)` for the stack, plus `O(1)` additional working state per step if using a precomputed table (the table itself is `O(|G|)` sized, independent of input length).

Correctness argument. The correctness claim is: if the shift-reduce parser accepts, the sequence of reductions performed, read in order, is a rightmost derivation of the input in reverse — hence the constructed tree is a valid parse tree for the input under the grammar. The argument rests on an invariant maintained at every configuration: > Invariant. At every point in the parse, the string formed by concatenating the stack contents (bottom to top) with the unread portion of the input buffer equals some sentential form that occurs in a rightmost derivation of the full input string.

• Base case: initially the stack is empty and the buffer is the whole input `w`, which is trivially the last line of the rightmost derivation (the derived string itself).
• Shift step preserves the invariant: moving a terminal from the front of the buffer to the top of the stack does not change the concatenation `stack · buffer`, so the sentential form is untouched — trivially still valid.
• Reduce step preserves the invariant, provided the handle is correctly identified: replacing `β` on top of the stack with `A` changes the sentential form from `αβw'` to `αAw'`. This is exactly the reverse of the derivation step `αAw' ⇒ αβw'` (expanding `A` via `A → β`), so if `αβw'` was a valid sentential form in the rightmost derivation and `A → β` was truly the last production applied to produce it, then `αAw'` is the previous valid sentential form in that same derivation.
• Termination: the process must terminate because each reduce strictly shortens the total symbol count (replacing `|β| ≥ 1` symbols with one symbol `A`), and shifts are bounded by the finite input, so the number of steps is bounded by `2n` (at most `n` shifts, and reduces bounded by tree size).
• Acceptance implies validity: if the parser reaches the configuration `stack = [$, S]`, `buffer = [$]`, the invariant says `S` (the start symbol) is a valid sentential form of the rightmost derivation of `w` — i.e., `S ⇒*_rm w`, which is precisely the definition of `w` being in the language generated by `S`.

The one place this proof leans on an assumption is "provided the handle is correctly identified" — correctness of the engine (this invariant) is unconditional, but correctness of a specific implementation of `FIND-HANDLE` (simple precedence rules, or a full LR table) depends on whether that oracle really always picks the unique valid handle for the grammar class it targets. This is exactly why grammar classes matter: operator-precedence rules are correct only for operator-precedence grammars; the general LR table is correct (deterministically, with no guessing) exactly for LR(k) grammars.

Tradeoffs, stated honestly. Bottom-up shift-reduce parsing is strictly more powerful than LL(1) top-down parsing — it accepts left-recursive grammars natively and handles ambiguity resolution via precedence declarations rather than grammar rewriting. The price is that building the handle-recognizing automaton (LR table) is significantly more complex to construct by hand than an LL(1) table, and diagnosing why a grammar has a shift-reduce or reduce-reduce conflict requires understanding the underlying automaton states — a genuine usability cost that hand-written recursive-descent parsers avoid.

Grammar for arithmetic expressions with the usual precedence (`` binds tighter than `+`, both left-associative): ``` E → E + T | T T → T F | F F → id ``` Input: `id + id * id`. We trace a shift-reduce parse using the operator-precedence oracle (shift when top-of-stack terminal binds looser than lookahead, reduce otherwise), building the tree bottom-up.

The crucial moment is step 7: a naive parser that always reduces greedily the moment a handle could apply (`T + T` looks like it might close under `E → E + T`) would collapse the `+` before seeing that `` needs to bind first, producing the wrong tree `(id + id) id`. The precedence oracle's shift at step 7 is what enforces `` binding tighter than `+`, giving the correct tree: ``` E / | \ E + T | / | \ T T F | | | F F id | | id id ``` read leaves-to-root: `id`, `id`, `id` at the bottom, `F`/`T` collapsing them, and finally `E → E + T` at the very last reduction — exactly matching that `E`'s right subtree `T → T F` groups `id id` before the outer `+` combines it with the leftmost `id`.

Every compiler-compiler in wide industrial use — Yacc, GNU Bison, CUP, ANTLR's LALR mode ancestors, and the tables inside GCC's and historically Java's frontends — generates a shift-reduce automaton from a grammar specification, exactly the mechanism this article describes conceptually. Configuration-language parsers, SQL parsers inside database engines, and JSON/YAML schema validators frequently use hand-rolled or generated shift-reduce logic when a simple recursive-descent parser cannot cleanly express operator precedence or left recursion. Understanding the stack/buffer/handle model is also the prerequisite for reading LR parser generator error messages ("shift-reduce conflict", "reduce-reduce conflict") that every compiler-course student and many production engineers eventually confront when writing a grammar file. The conceptual leap from this article's brute-force handle search to a genuinely efficient, provably correct engine is precisely the subject of LR and LALR Parsing, which replaces `FIND-HANDLE` with a precomputed deterministic automaton over grammar items.

Ask the tutor: How does the LR(0) item automaton turn the brute-force `FIND-HANDLE` search into a constant-time table lookup?