Skip to content
Tutorials Center
My learning

Topics

Lesson 22 of 61 ยท Parsing

Bottom-Up Parsing: Shift-Reduce

Learn how bottom-up parsers work: handles, rightmost derivations in reverse, shift and reduce actions, stack traces, and a shift-reduce simulator in Python.

Top-down parsers start with the start symbol and try to grow a tree downward until it matches the input. A bottom-up parser works the other way around. It starts with the tokens, which are the leaves, and keeps joining them into bigger and bigger subtrees until a single tree rooted at the start symbol remains. If it manages that, the input is a valid sentence of the grammar.

Bottom-up parsing is the engine behind tools such as Yacc and Bison, and it handles a larger family of grammars than LL(1) parsing. It copes with left-recursive rules directly, so you do not need the rewrites from eliminating left recursion. The price is that the parsing tables are hard to write by hand, which is why they are normally generated. In this lesson you learn the mechanism; the next lesson shows how the tables are built.

The grammar we will use

All examples use the classic expression grammar. Notice that it is left-recursive, which a recursive descent parser could not accept as written.

TEXT
1.  E -> E + T
2.  E -> T
3.  T -> T * F
4.  T -> F
5.  F -> ( E )
6.  F -> id

The layering (E for sums, T for products, F for the smallest pieces) is what gives * a higher precedence than +, as explained in ambiguity, precedence and associativity.

Reductions and handles

The basic step of a bottom-up parser is a reduction: find the right-hand side of some production inside the current string, and replace it with the production's left-hand side. Starting from id + id * id, one possible chain is:

TEXT
id + id * id
F  + id * id      (F -> id)
T  + id * id      (T -> F)
E  + id * id      (E -> T)
E  + F  * id      (F -> id)
E  + T  * id      (T -> F)
E  + T  * F       (F -> id)
E  + T            (T -> T * F)
E                 (E -> E + T)

The parser can pick a wrong reduction, though. Take the line E + T * id: the substring E + T matches rule 1, but reducing it to E would strand the *, because * binds tighter and has to attach to T first. A reduction that keeps the parse on track to the start symbol is the right one, and the substring it reduces has a name.

A handle is the substring that matches the right-hand side of a production and whose reduction is one step of the reverse of a rightmost derivation. Finding the handle at each step is the entire problem of bottom-up parsing.

Why "rightmost"? A bottom-up parser reads input from left to right, and the rightmost derivation replaces the rightmost nonterminal each time. Run that derivation backwards and you get exactly the reductions above, with the handle always sitting at the right end of what the parser has seen so far. That fact is what makes a simple stack enough, as the next section shows.

flowchart BT
    id1["id"] --> F1["F"] --> T1["T"] --> E1["E"]
    id2["id"] --> F2["F"] --> T2["T"]
    id3["id"] --> F3["F"]
    E1 --> E0["E (root)"]
    plus["+"] --> E0
    T2 --> T3["T (T * F)"]
    star["*"] --> T3
    F3 --> T3
    T3 --> E0

Reading from the bottom: each node is created by a reduction, and the root appears last.

Shift and reduce

A shift-reduce parser keeps two things: a stack holding the symbols recognized so far, and the remaining input, ending with a special end marker $. It repeats four possible actions:

Action Effect
Shift Move the next input token onto the top of the stack.
Reduce The top of the stack holds a handle X1 ... Xk for a production A -> X1 ... Xk. Pop it and push A.
Accept The stack holds only the start symbol and the input is $.
Error No action is possible. The input is not valid.

Because handles always appear at the top of the stack, the parser never has to search the middle of it. The only real decision is: shift or reduce, and if reduce, by which rule? Everything else in bottom-up parsing, including the LR tables, exists to answer that question correctly.

Here is a replay. The script lists the decisions ("S" for shift, a number for "reduce by rule N", counting from 0), and the program shows the stack at every step. Each reduce is checked against the stack, so a wrong decision raises an error.

Python Tracing a shift-reduce parse

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the trace slowly. After E + T appears with * id $ still to come, the parser shifts instead of reducing E -> E + T. That single decision is what makes multiplication bind tighter. Only after the * and the last id have been read and reduced to T * F does the parser reduce E + T at the end.

What a conflict looks like

Where did the script above get its decisions from? We wrote them by hand, knowing the answer. A real parser has to decide from the stack and one or more lookahead tokens alone. Let us try the most naive policy, "reduce whenever the top of the stack matches some right-hand side, preferring the longest, otherwise shift", and compare it with the same policy plus one small lookahead rule.

Python Why lookahead is needed

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Without the guard, the parser reduces E -> T the moment it can, ends up with E * E on the stack and gets stuck. With the guard, it shifts when a * is next and succeeds. A proper LR parser generalizes that guard: it automatically knows, for every state and every possible next token, whether to shift, reduce or fail. Whenever two actions look equally valid, the grammar has a conflict:

  • A shift/reduce conflict: the parser could shift the next token or reduce. The classic example is the dangling else in an ambiguous if grammar.
  • A reduce/reduce conflict: two different productions both match the top of the stack.

Conflicts are signs of ambiguity, or of a parser that does not look far enough ahead. The next lesson classifies parsers by how much information they use to avoid them.

Recovering the rightmost derivation

Because a shift-reduce parse is a rightmost derivation in reverse, you can recover the derivation by recording the full string (stack plus remaining input) after each reduction and reading the list backwards. This also helps you see handles: each time, the handle is the part that is replaced.

Python Reading the derivation backwards

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read it top to bottom and you see the derivation E => E + T => E + T * F => ... => id + id * id. Every step rewrites the rightmost nonterminal, exactly as the definition requires.

Viable prefixes and why a stack works

The stack contents at any moment are always a prefix of some right-sentential form, and never extend past the end of the current handle. Such prefixes are called viable prefixes. The set of viable prefixes of a grammar is a regular language, so a finite automaton can recognize it. That is the central trick of LR parsing: build a DFA whose states summarize "what could I be in the middle of recognizing?", push the state onto the stack along with each symbol, and consult it to choose between shift and reduce. You will build exactly that in the next lesson.

Compared with top-down parsing:

Top-down (LL) Bottom-up (LR)
Direction Start symbol toward the tokens Tokens toward the start symbol
Derivation built Leftmost Rightmost, in reverse
Decision point Which production to expand When to reduce a handle
Left recursion Must be removed Fine
Hand-written? Often Rarely; generated

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does a bottom-up parser do in a reduce step?

    Reducing is the reverse of applying a production: the symbols that match a right-hand side are popped and the nonterminal on the left-hand side is pushed in their place.
  2. 2. Which statement about a handle is correct?

    Many substrings can match a right-hand side, but only the handle can be reduced while keeping the parse on a path to the start symbol.
  3. 3. A parser has E + T on the stack and the next token is *. What should it do for the grammar in this lesson?

    Multiplication binds tighter than addition, so T has to absorb the * and the following factor first. Reducing early would produce E * ..., which the grammar cannot continue.
  4. 4. Two productions match the top of the stack and the parser cannot tell which to reduce by. What is this called?

    When more than one reduction is possible, it is a reduce/reduce conflict. A shift/reduce conflict is when shifting competes with one reduction.

Summary

  • A bottom-up parser builds the parse tree from the leaves to the root by repeatedly reducing handles.
  • A shift-reduce parser uses a stack and four actions: shift, reduce, accept and error.
  • A bottom-up parse is a rightmost derivation traced in reverse, and handles always appear at the top of the stack.
  • The hard part is choosing between shifting and reducing; naive policies fail, and lookahead resolves most choices.
  • Conflicts (shift/reduce and reduce/reduce) reveal ambiguity or too little lookahead.
  • Left recursion is no problem for bottom-up parsers; the tables are normally generated rather than written by hand.

Next: LR(0), SLR and LALR Parsers