Course contentsShow
← Computer Science
Lesson 1960 of 2,87244. Lexical Analysis and ParsingFree lesson

Bottom-Up Parsing Overview

Introduction to shift-reduce parsing and how bottom-up parsers build parse trees from leaves to root.

Bottom-Up Parsing Overview

What You'll Learn

You'll discover how bottom-up parsers work by building parse trees from the leaves (tokens) upward to the root (start symbol), the opposite direction of top-down parsing.

The Core Idea

Bottom-up parsing starts with the input tokens and gradually reduces them into higher-level grammar constructs until reaching the start symbol. Unlike top-down parsing (which predicts productions and expands from the start symbol), bottom-up parsing recognizes the right-hand sides of productions in the input and replaces them with their left-hand side nonterminals.

Think of it like assembling a jigsaw puzzle by first connecting small pieces into recognizable groups, then combining those groups into larger sections, and finally putting everything together to complete the picture. You're working from details to the big picture.

Shift-Reduce Parsing

The most common bottom-up technique is shift-reduce parsing, which uses two main actions:

  • Shift: Move the next input token onto a stack
  • Reduce: When the top of the stack matches the right-hand side of a grammar production, replace (reduce) those symbols with the production's left-hand side

For example, if your grammar has E → E + T and your stack contains E + T, you reduce it to E.

The parser continues shifting and reducing until either the entire input is consumed and the stack contains only the start symbol (success), or no valid moves remain (syntax error).

Why Bottom-Up?

Bottom-up parsers can handle a broader class of grammars than LL(1) parsers. They don't struggle with left recursion and can parse many practical programming language constructs more naturally.

Key Takeaway: Bottom-up parsing builds parse trees from tokens upward using shift-reduce operations, working from specific input patterns toward the general start symbol—the reverse of top-down parsing's approach.