Skip to content
Tutorials Center
My learning

Topics

Lesson 18 of 61 ยท Parsing

Writing a Recursive Descent Parser

Build a recursive descent parser in Python: one function per grammar rule, precedence from layered rules, statements, blocks, calls and clear errors.

Recursive descent is the most approachable way to write a parser, and also one of the most widely used. The idea is almost embarrassingly simple: write one function for every nonterminal in the grammar. The body of each function mirrors the right-hand side of its rule, calling other functions for nonterminals and checking tokens for terminals. Because the grammar is recursive (an expression can contain a parenthesized expression), the functions call each other recursively, and the call stack ends up tracing the parse tree. The parser descends through the grammar, hence the name.

In this lesson you will write a complete parser for the expression and statement syntax of our toy language, run it on real programs and watch it report errors with line and column numbers. You should be comfortable with top-down parsing basics, and the grammar must be free of left recursion. The parser produces plain tuples here; the next lesson replaces them with proper node classes.

From grammar rules to functions

Using EBNF (where { ... } means "zero or more" and [ ... ] means "optional") the expression grammar looks like this. Each line becomes one method:

TEXT
comparison -> sum [ ("<" | ">" | "<=" | ">=" | "==" | "!=") sum ]
sum        -> term { ("+" | "-") term }
term       -> unary { ("*" | "/") unary }
unary      -> "-" unary | primary
primary    -> NUMBER | NAME | "(" comparison ")"

The translation rules are mechanical, and once you know them you can turn any suitable grammar into code:

Grammar piece Code
terminal t expect("t"): check the token, then consume it
nonterminal N call self.N()
sequence A B one call after the other
choice A | B if on the lookahead token, one branch per alternative
repetition { A } a while loop that runs as long as the lookahead can start A
option [ A ] an if on the lookahead token

The parser keeps a list of tokens and a position. Three tiny helpers do all the token handling: peek looks at the current token without consuming it, advance consumes it, and expect consumes it only if it has the right kind and otherwise raises an error.

Precedence comes from the shape of the rules

Notice how the rules are stacked: comparison calls sum, which calls term, which calls unary, which calls primary. The rule that is called last binds tightest. Multiplication lives below addition, so when the parser sees 1 + 2 * 3, the sum function asks term for its first operand, gets 1, sees a +, and asks term for the right operand; that call greedily consumes 2 * 3 before returning. The result is 1 + (2 * 3), and no precedence table was needed. Parentheses reset the whole thing: primary calls back up to the top-level rule between the brackets, which is the recursion that gives the technique its name.

flowchart TD
    C["comparison"] --> S["sum"]
    S --> T["term"]
    T --> U["unary"]
    U --> P["primary"]
    P -->|"( ... )"| C
    U -->|"- ..."| U

The call chain mirrors precedence: later rules bind tighter, and parentheses jump back to the top.

Associativity comes from the loop. In sum, the code left = (op, left, self.term()) inside a while loop folds the operands to the left, so 10 - 4 - 3 becomes (10 - 4) - 3. A right-associative operator (such as exponentiation) would instead call its own function again for the right-hand side. We look at the details in ambiguity, precedence and associativity, and at a more compact technique in Pratt parsing.

An expression parser you can run

The program below has a small regex tokenizer, a parser class with one method per rule, a function that prints the tree fully parenthesized so you can see the structure, and an evaluator to prove the shapes are right. The first run turns on a call trace: each method prints its name when it is entered, indented by the call depth.

Python A recursive descent expression parser

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 trace, sum is entered once and calls term twice: the first term handles the 1, the second handles 2 * 3 (you can see the second term calling unary twice, once per operand of the *). The parenthesized outputs show the structure the parser chose, and 10 - 4 - 3 giving ((10 - 4) - 3) = 3 proves left associativity. The last two inputs are errors: running out of tokens in the middle of an expression, and a stray 4 after a complete expression, which the final expect("eof") catches.

Statements, blocks and functions

Statements are even easier, because most of them start with a keyword that identifies them uniquely. The statement method looks at the first token and picks a branch: let, print, if, while, fun or return. This is exactly the one-token lookahead from the previous lesson, written as an if chain.

One case needs a bit more care. An assignment such as total = total + 1; starts with a name, and a name could also be the start of an expression. In our toy language assignments are statements and expressions cannot stand alone, so a name at the start of a statement can only begin an assignment, but we still check the token after it (peek(1)) before committing. That is a two-token lookahead, and hand-written parsers use such peeks freely. Function calls are handled in primary: after reading a name, if the next token is (, the name is a call and we parse a comma-separated list of arguments.

Blocks are a repetition: {, then statements until a }, then the closing brace. Notice that block stops on eof as well as on }, so an unclosed block produces a clear "expected }" error instead of an endless loop.

The parser below also carries line and column numbers inside each token, so every error can say where the program went wrong. It prints the tree with indentation, then feeds four broken programs to the parser:

Python Parsing statements, blocks and functions

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.

The tree shows what the parser understood: the function square, the loop with its body block, and an if with a "then" block followed by an "else" block. Every error message names a position and says what was expected. Quality of error messages is mostly about passing along information the parser already has: the current token, the token it wanted, and the position. In syntax errors and error recovery you will teach the parser to keep going after the first mistake.

Strengths, weaknesses and common mistakes

Recursive descent has real advantages. The code is the grammar, so it is easy to read, debug and extend. You control everything: you can peek further ahead when the grammar needs it, build any tree you like, and produce hand-crafted error messages. This is why many production compilers use it.

The weaknesses are just as concrete:

  • Left recursion loops forever. A rule like sum -> sum "+" term makes sum() call itself immediately. Rewrite the rule as a loop (as above) or use grammar transformations.
  • Deep nesting can overflow the stack. Python's recursion limit (about 1000 frames) means that an expression with a few hundred nested parentheses may fail. Production parsers either raise the limit or switch to an explicit stack.
  • Choosing alternatives by hand is error-prone. If two alternatives start with the same token, the if chain silently picks the first. Check FIRST sets or restructure the grammar.
  • Forgetting to consume. A loop such as while self.peek() == "+" that never calls advance runs forever. Every loop iteration must consume at least one token.
  • Ignoring the end of input. Without the final expect("eof"), the parser accepts 1 + 2 garbage happily, because it stops after 1 + 2.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In a recursive descent parser, how is a repetition such as { ('+' | '-') term } usually written?

    Repetition in the grammar becomes a loop in the code. The loop condition is the set of tokens that can start another repetition.
  2. 2. Why does 1 + 2 * 3 parse as 1 + (2 * 3) in the layered expression grammar?

    Rules that are called deeper in the chain bind tighter. The operand fetched by the second call to term is the whole product 2 * 3.
  3. 3. What goes wrong with the rule sum -> sum '+' term in a recursive descent parser?

    This is left recursion. The first action of the function is to call itself again with no progress, so a top-down parser never terminates.
  4. 4. Why does the parser finish with expect('eof')?

    Without it, input such as '4 4' would be accepted, because the parser stops once the first complete expression is read.

Summary

  • Recursive descent writes one function per nonterminal; terminals become expect calls, choices become if chains on the lookahead token, and repetition becomes loops.
  • Operator precedence follows from the order of the rules: operators in rules called later bind tighter, and parentheses recurse back to the top rule.
  • Loops that fold results to the left give left associativity.
  • A statement parser dispatches on the first token (a keyword), and occasionally peeks one token further.
  • Tokens that carry line and column numbers let the parser report precise, helpful errors.
  • Beware of left recursion, loops that consume nothing, and forgetting to check for the end of input.

Next: Abstract Syntax Trees