Skip to content
Tutorials Center
My learning

Topics

Lesson 17 of 61 ยท Parsing

Top-Down Parsing Basics

Understand top-down parsing: leftmost derivations, backtracking, why left recursion loops, and how one token of lookahead gives predictive parsing.

A lexer turns characters into tokens. A parser turns tokens into structure: it decides whether the tokens form a valid program and shows how the pieces nest. There are two big families of parsing strategies. Bottom-up parsers start from the tokens and combine them into bigger and bigger phrases. Top-down parsers start from the grammar's start symbol and try to grow it into exactly the token sequence they see. This lesson explains the top-down idea, the problems it runs into, and the trick (lookahead) that makes it fast.

Top-down parsing is popular for a practical reason: the parsers are easy to write by hand and easy to read. Most hand-written compilers for real languages, including large production ones, use a top-down technique called recursive descent, which you will build in the next lesson. To follow this lesson you should know context-free grammars and have seen FIRST and FOLLOW sets.

Parsing as a search for a derivation

Recall that a grammar generates strings by derivation: start with the start symbol, and repeatedly replace a nonterminal with the right-hand side of one of its productions. A top-down parser performs this process on purpose, and the input tells it when it is on the right track.

In a leftmost derivation you always expand the leftmost nonterminal first. Top-down parsers use leftmost derivations because they read the input from left to right: everything to the left of the leftmost nonterminal is already a terminal, and it has to match the tokens we have read so far.

flowchart TD
    S["S"] --> id["id"]
    S --> assign[":="]
    S --> E["E"]
    E --> num["num"]

The parse tree for the statement id := num, built from the root downward.

The tree grows from the root (the start symbol) to the leaves (the tokens), which gives the technique its name. The question at every step is the same: which production do I use for this nonterminal? If a nonterminal has only one production, there is nothing to decide. When it has several, a wrong choice leads to a dead end somewhere further along.

Approach 1: try everything and backtrack

The simplest answer is brute force. Try the first alternative. If the input does not match, undo and try the next one. This is backtracking. It is correct for any grammar without left recursion, but it can be slow, because work done under a wrong guess is thrown away and often redone.

Here is a compact backtracking recognizer. The function parse is a generator: it yields every input position where a symbol could end, and the caller tries them in turn. The counters tell us how much work was done. We use a grammar where two alternatives begin with the same long prefix:

TEXT
S -> A c | A d
A -> a A | b

Both alternatives of S start with A, so for the input a a a b d the parser first parses all of a a a b as an A, finds that the next token is d instead of c, backs up, and parses the same a a a b again under the second alternative. The factored version S -> A T, T -> c | d parses A once and chooses between c and d afterward.

Python Backtracking: how much work does a bad grammar waste?

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.

Look at the first block of output. For a a a b d the naive grammar tries 15 alternatives and makes 15 token comparisons, while the factored grammar needs 8 and 7. For a a a b c the naive grammar is lucky, because its first guess is right, and it is actually a little cheaper. This is the nature of backtracking: the cost depends on whether the guesses happen to be good. In a real compiler, the penalty compounds, because wrong guesses can be nested inside other wrong guesses and the running time can grow exponentially with the input length.

Backtracking has two more disadvantages. Error messages are poor, because after all alternatives fail the parser can only say "something went wrong somewhere". And semantic actions (building trees, adding to symbol tables) must be undone when the parser backs up.

The left recursion trap

The last lines of the program show the other classic failure. The grammar E -> E + n | n is perfectly good as a description of sums, but a top-down parser that expands E by its first alternative immediately needs to expand E again, without consuming a single token, and so on without end. The program crashes with a RecursionError.

This is left recursion, and any top-down parser, backtracking or not, loops on it. The fix is to rewrite the grammar, as shown in eliminating left recursion and left factoring. Bottom-up parsers have no such problem, which is one reason they handle a wider range of grammars.

If your hand-written parser hangs or hits Python's recursion limit on valid input, check for left recursion first: a rule that begins with a call to itself, directly or through other rules, before consuming any token.

Approach 2: predict with lookahead

Instead of guessing and undoing, a predictive parser peeks at the next input token (the lookahead) and uses it to choose the right production with certainty. If the choice is always possible with one token of lookahead, the grammar is called LL(1): the first L means the input is read Left to right, the second L means the parser builds a Leftmost derivation, and the 1 is the number of lookahead tokens.

flowchart LR
    N["Expand nonterminal X"] --> L{"Look at next token t"}
    L -->|"t in FIRST of alternative 1"| P1["use alternative 1"]
    L -->|"t in FIRST of alternative 2"| P2["use alternative 2"]
    L -->|"t matches no alternative"| ERR["syntax error"]

A predictive parser chooses by looking at one token, never by trial and error.

Where do we get the rule "t is in FIRST of alternative 1"? From the sets you computed in the previous lesson. If an alternative can vanish, the FOLLOW set takes over: use the empty alternative when the lookahead is something that may legally come after the nonterminal.

Here is a tiny predictive derivation engine for a statement grammar. It always expands the leftmost nonterminal, looks at the token in the matching position of the input, and picks the single alternative whose first token matches. It prints every sentential form, so you can see the derivation unfold:

Python A predictive leftmost derivation

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.

In the first two runs there is never a moment of doubt: S has three alternatives that start with if, while and id, which are different tokens, so one look at the input is always enough. The third run is a syntax error, and the parser notices exactly where: after expanding C into id < E, the next input token is then, but the derivation requires <. Predictive parsers detect errors as early as the language allows, which is much better than a backtracking parser's "nothing worked".

What makes lookahead work

For a predictive parser to be sure of its choice, the grammar must pass a few tests:

  • No left recursion. Otherwise the parser loops.
  • No common prefixes. If two alternatives of a nonterminal begin with the same token, one token of lookahead cannot separate them. Left factoring removes the common part.
  • Disjoint FIRST sets. The alternatives of every nonterminal must start with different tokens.
  • Compatible empty alternatives. If a nonterminal can vanish, the tokens that select its other alternatives must not overlap with its FOLLOW set.

Some languages need more than one token of lookahead in a few places, and some constructs cannot be handled at all without rewriting. Hand-written parsers are often "LL(1) with a few peeks further", which is perfectly fine in practice. The next two lessons show two ways to turn the predictive idea into code: recursive descent writes one function per nonterminal, and table-driven LL(1) drives a generic loop from a table.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why do top-down parsers use leftmost derivations?

    Expanding the leftmost nonterminal keeps the parser in step with the input: the terminals to its left have been matched, and the next token guides the next choice.
  2. 2. What is the main weakness of a backtracking top-down parser?

    Work done under a wrong alternative is discarded and often repeated, so the running time can blow up, and when everything fails the parser has little idea which token was the real problem.
  3. 3. What happens when a top-down parser expands E using the rule E -> E + n?

    That is left recursion: the first thing the rule does is to expand the same nonterminal, so no progress is made. The grammar must be rewritten for top-down parsing.
  4. 4. In the name LL(1), what does the 1 stand for?

    An LL(1) parser reads Left to right, builds a Leftmost derivation and decides using one lookahead token.
  5. 5. Two alternatives of the same nonterminal both begin with the token 'if'. What does that mean for an LL(1) parser?

    Overlapping FIRST sets are an LL(1) conflict. Left factoring pulls the common prefix out so the choice is postponed to a later token.

Summary

  • A top-down parser builds a leftmost derivation from the start symbol, matching the input from left to right; its central question is which production to apply.
  • Backtracking tries alternatives in turn and undoes failures; it works for any non-left-recursive grammar but wastes work and reports vague errors.
  • Left recursion makes any top-down parser loop and must be removed from the grammar.
  • A predictive parser uses one token of lookahead (the FIRST and FOLLOW sets) to choose the right production every time; such grammars are LL(1).
  • Predictive parsers find syntax errors at the first token that cannot continue a valid program.

Next: Writing a Recursive Descent Parser