Bottom-up parsing: shift and reduce

Advanced

Introduction

Top-down parsers start from the start symbol and guess which rule comes next. Bottom-up parsers work the other way: they read tokens and, as soon as the top of their stack matches the body of a rule, they replace it with the rule's left side. They build the tree from the leaves up. Most parser generators, from yacc and Bison to the parsers inside many databases, are bottom-up LR parsers, because they accept a wider range of grammars, including left-recursive ones.

How it works

A shift-reduce parser has a stack and the remaining input. At each step it does one of four things:

  • shift: push the next input token onto the stack;
  • reduce: the top of the stack is the body of a rule A → β; pop β and push A;
  • accept: the input is used up and the stack holds just the start symbol;
  • error: no action fits.

The part of the stack that should be reduced next is the handle. Deciding when the top of the stack really is a handle is the whole difficulty. Real LR parsers build a DFA from the grammar to decide; the example uses simpler rules for an expression grammar, E → E + E | E * E | ( E ) | id:

  • id on top is always a handle for E → id;
  • ( E ) on top is a handle for E → ( E );
  • E op E on top is reduced only if the next token does not bind tighter. When the next token is * and the stack holds E + E, the parser shifts instead, so that the multiplication is reduced first.

The case E + E with + next is a shift-reduce conflict: both actions are possible. Choosing reduce makes + left-associative, since a + b is grouped before the next + arrives. This is exactly how Bison's %left and %right declarations resolve conflicts.

Because the parser reduces only after it has seen the whole body, left recursion such as E → E + id causes no trouble: the stack just holds E + id until it is reduced. Reading the reductions from last to first gives a rightmost derivation, which is the R in LR.

Syntax

if top_is_handle(stack, next_token):
    stack[-len(body):] = [head]      # reduce
else:
    stack.append(next_token)         # shift

Example

PREC = {"+": 1, "*": 2}


def parse(tokens):
    stack, tokens, i = [], tokens + ["$"], 0
    print(f"{'stack':14} | {'input':18} | action")
    while True:
        a = tokens[i]
        if stack[-1:] == ["id"]:
            stack[-1:] = ["E"]
            action = "reduce E -> id"
        elif stack[-3:] == ["(", "E", ")"]:
            stack[-3:] = ["E"]
            action = "reduce E -> ( E )"
        elif len(stack) >= 3 and stack[-1] == "E" and stack[-2] in PREC and stack[-3] == "E" and (a in ("$", ")") or (a in PREC and PREC[a] <= PREC[stack[-2]])):
            action = f"reduce E -> E {stack[-2]} E"
            stack[-3:] = ["E"]
        elif a == "$":
            action = "accept" if stack == ["E"] else "error"
        else:
            stack.append(a)
            i += 1
            action = f"shift {a}"
        print(f"{' '.join(stack):14} | {' '.join(tokens[i:]):18} | {action}")
        if action in ("accept", "error"):
            return


parse("id + id * id".split())
Open in compiler

Line by line

  1. PREC gives * a higher precedence than +.
  2. Each step first looks for a handle on top of the stack; if none fits, it shifts. Each row shows the stack and the remaining input after the action.
  3. Every id is reduced to E as soon as it is shifted.
  4. With E + E on the stack and * next, the parser shifts, because * binds tighter; the multiplication is reduced first.
  5. At the end of the input the remaining handles are reduced, leaving just E, so the parser accepts.

Expected result

stack          | input              | action
id             | + id * id $        | shift id
E              | + id * id $        | reduce E -> id
E +            | id * id $          | shift +
E + id         | * id $             | shift id
E + E          | * id $             | reduce E -> id
E + E *        | id $               | shift *
E + E * id     | $                  | shift id
E + E * E      | $                  | reduce E -> id
E + E          | $                  | reduce E -> E * E
E              | $                  | reduce E -> E + E
E              | $                  | accept

In the real world

Bison and yacc generate LALR(1) parsers, a compact kind of LR parser, used for the grammars of PostgreSQL, Ruby (until recently) and many configuration languages. Tree-sitter, used by editors such as Neovim and by GitHub for code navigation, is a generalised LR parser that keeps working on code with errors. The precedence declarations in those tools resolve exactly the conflicts seen in this lesson.

Common mistakes

  • Reducing too early, before a higher-precedence operator has been handled.
  • Shifting on equal precedence, which makes left-associative operators group to the right.
  • Accepting with extra symbols on the stack: the stack must be just the start symbol.
  • Thinking bottom-up parsers need the left-recursion removal that LL parsers need: they do not.

Best practices

  • Print the stack, the remaining input and the action at every step while debugging.
  • State precedence and associativity explicitly, as a table, rather than hiding them in conditions.
  • Use a parser generator for large grammars, and read its conflict reports carefully.

Summary

A shift-reduce parser shifts tokens onto a stack and reduces handles to rule left sides, building the tree from the leaves up. Precedence and associativity settle shift-reduce conflicts. LR parsers built this way handle left recursion and more grammars than LL(1), which is why most parser generators use them.

Quick check

1. What does a reduce step do?
2. The stack is E + E and the next token is *. What does the parser do?
3. The stack is E + E and the next token is +. What makes + left-associative?
4. Why can LR parsers use left-recursive rules such as E → E + id?

Key takeaways

  • Bottom-up parsing builds the tree from the leaves up, by shifting tokens and reducing handles.
  • Precedence and associativity decide whether to shift or reduce when a binary operator is involved.
  • LR parsers handle left recursion naturally and accept more grammars than LL(1).

Practice problems for this lesson

My notes

Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.