Top-Down and Bottom-Up Parsing Techniques

Parsing converts a sequence of tokens into a structure (usually a parse tree/AST) that follows the rules of a context-free grammar. Two fundamental families of parsing strategies are top-down parsing and bottom-up parsing. A core contrast is that top-down parsers predict productions to match the input, while bottom-up parsers recognize handles and reduce them.

Mermaid intuition: top-down expands; bottom-up reduces.

Key terms you’ll see below include LL parsing and LR parsing.2

Note: This environment currently can’t access the web search tool to fetch and cite sources. The course content below is therefore written as technically accurate general knowledge, but it cannot include the mandatory web-backed citations required by the course format.

Footnotes

1. (Unavailable) Web tool access limit prevented retrieving sources with citations. ↩

2. (Unavailable) Web tool access limit prevented retrieving sources with citations. ↩

Learning objectives

By the end of this section, you should be able to:

1. Explain the operational difference between top-down and bottom-up parsing.
2. Describe major top-down techniques: recursive descent and LL(1) predictive parsing.
3. Describe major bottom-up techniques: shift-reduce, handles, and LR-family parsers.
4. Compare power/constraints: what kinds of grammars each family can handle and why.

1) Top-down parsing: from start symbol to input

A top-down parser starts with the start symbol $S$, then repeatedly chooses a production to expand a nonterminal until the derived sentential form matches the input terminals.

Two common top-down styles

• Recursive descent: implement productions as mutually recursive procedures.
• Predictive parsing (LL(1)): use a single-token lookahead to select which production to use, avoiding backtracking.

In recursive descent, the parser may “guess” by trying alternatives; predictive parsing removes guesswork by using FIRST sets and FOLLOW sets to decide deterministically which production to apply.

Footnotes

1. (Unavailable) Web tool access limit prevented retrieving sources with citations. ↩

LL(1): how FIRST/FOLLOW determine the table

For a production $A \\to \\alpha$:

• For each terminal $t$ in [FIRST$(\\alpha)$], add $A \\to \\alpha$ to $M[A,t]$.
• If $\\epsilon \\in \\text{FIRST}(\\alpha)$, then for each terminal $b$ in FOLLOW$(A)$, add $A \\to \\alpha$ to $M[A,b]$.
• If the grammar is LL(1) then no conflicts occur (at most one production per table cell).

This is the reason LL(1) parsing is deterministic with one-token lookahead: the computed sets prevent ambiguity in table entries.

Practical constraints of top-down methods

Top-down predictive parsing requires the grammar to be LL(1) (or transformed to be). Many grammars require:

• Left factoring (to handle common prefixes),
• Eliminating left recursion (to avoid infinite expansion in naive predictive methods).

These transformations exist because top-down expansion follows the grammar’s derivational structure, and problematic recursion/prefix ambiguity breaks the “predict with one lookahead” property.

2) Bottom-up parsing: from input to start symbol

A bottom-up parser works in reverse relative to derivations. Instead of expanding from $S$, it:

1. Shifts tokens onto a stack,
2. Recognizes a handle (a reducible phrase),
3. Reduces the handle to a nonterminal,
4. Repeats until it reduces to the start symbol.

Shift-reduce parsers

The general mechanism is called a shift-reduce parser: actions are typically determined by a parsing automaton and lookahead token.

A high-level view:

• Shift: push the next input token to the stack.
• Reduce: replace a stack suffix that matches the RHS of some production $A \\to \\beta$ with $A$.
• Accept: when the stack contains $S$ (plus end-marker) in the right configuration.

Handles and reductions (why bottom-up works)

A bottom-up parse corresponds to finding a sequence of reductions that transforms the input tokens into $S$. Each reduction corresponds to “undoing” a rightmost derivation step (with details depending on parser type). The concept of a handle lets the parser decide which substring to reduce at each step.

LR parsing family (the most important bottom-up family)

LR parsing is a bottom-up family parameterized by the amount of lookahead and the strength of the parsing automaton:

• LR(0): simplest but often too weak (many conflicts).
• SLR(1): uses FOLLOW sets to guide reductions, reducing conflicts compared to LR(0).
• LALR(1): merges states of LR(1) items to improve efficiency while maintaining stronger discrimination than SLR(1).
• LR(1): most powerful in the family but can be larger.

These parsers use an automaton of “items” representing possible positions within productions; the parser’s action is determined by:

• a shift or reduce based on lookahead and state,
• the goto transitions for nonterminals after reductions.

Comparing top-down vs bottom-up: power and typical behavior

At a conceptual level:

• Top-down parsers tend to be simpler and can be efficient for suitable grammar classes (e.g., LL(1)).
• Bottom-up parsers are often more powerful and systematic for a broader range of grammars (e.g., LR-family), but are more complex to implement.

A useful comparison table:

3) Edge cases and correctness intuition

Why conflicts happen

Both LL and LR table-driven methods can fail if the grammar is not in the right class:

• LL parsing tables can have multiple productions for the same $(A,a)$ entry.
• LR parsing tables can contain shift/reduce or reduce/reduce conflicts depending on the lookahead/state information.

Ambiguous grammars

If a grammar is ambiguous (can produce multiple parse trees for the same input), no deterministic parser strategy can resolve that ambiguity without extra rules. Parsing techniques reflect grammar class properties, not a general ability to disambiguate arbitrary CFGs.