Skip to content
Tutorials Center
My learning

Topics

Lesson 19 of 61 ยท Parsing

Abstract Syntax Trees

Learn how parse trees differ from abstract syntax trees, design AST node classes with dataclasses, build them in a parser, unparse them and use visitors.

A parser's job is not finished when it says "yes, this program is valid". The later phases of the compiler (name resolution, type checking, optimization, code generation) need the program's structure in a form that is easy to inspect and transform. That form is the abstract syntax tree, or AST. It is the central data structure of almost every compiler: the parser builds it, and every later pass reads it or rewrites it.

This lesson shows what an AST contains and, just as importantly, what it leaves out. You will design node classes with Python dataclasses, make the recursive descent parser build them, turn a tree back into source text, and write visitors, which are reusable passes that walk the tree.

Parse tree versus AST

A parse tree (also called a concrete syntax tree) records every step the grammar took: one node for every nonterminal that was expanded and one leaf for every token. For our layered expression grammar, even the tiny expression 2 * 3 passes through comparison, sum, term, unary and primary.

flowchart TD
    subgraph PT["Parse tree"]
      C["comparison"] --> S["sum"] --> T["term"]
      T --> U1["unary"] --> P1["primary"] --> N1["2"]
      T --> OP["*"]
      T --> U2["unary"] --> P2["primary"] --> N2["3"]
    end
    subgraph AST["AST"]
      B["Binary *"] --> A1["Num 2"]
      B --> A2["Num 3"]
    end

The same expression twice: every grammar step on the left, only the meaning on the right.

The AST keeps what matters for meaning and drops the scaffolding:

  • Chain rules disappear. comparison -> sum -> term -> unary -> primary was only there to encode precedence.
  • Punctuation disappears. Parentheses, semicolons, braces and commas guided the parser, but once the tree has the right shape, the shape already says which operator applies to which operands.
  • Operators become node kinds or fields. A Binary node stores the operator and two children.
  • Lists become real lists. A block with five statements becomes one node with five children, not a chain of "statement list" nodes.

Because parentheses vanish, 1 + 2 * 3 and 1 + (2 * 3) give identical ASTs, while (1 + 2) * 3 gives a different one. That is exactly the right notion of "same program".

Designing node classes

An AST node is a record: a kind plus some fields. Python's dataclass decorator gives us a constructor, a readable repr and field-wise equality for free. We make the nodes frozen (immutable), which prevents passes from changing a tree they share with others by accident, and we store sequences as tuples so that whole trees are hashable and comparable.

A good node design follows a few rules:

  • One class per construct, named after what it means (Binary, If, While), not after the grammar rule that produced it.
  • Children are fields, in the order a reader would expect (If has cond, then, other).
  • Absent parts are explicit. A missing else is an empty tuple, not None sprinkled everywhere, so passes can loop without special cases.
  • Location data is welcome (line and column on each node) because every error message from a later phase needs it. We leave it out here to keep the code short, and the project lessons add it back.

Building the tree in the parser

The parser from the previous lesson barely changes. Instead of returning tuples such as ("+", left, right), each method returns a node: Binary("+", left, right). A rule that only groups, such as a parenthesized expression, simply returns the inner node, so the parentheses leave nothing behind. To keep this program compact, the loop for the three binary precedence levels is written once and driven by a table (LEVELS), instead of one method per level.

The program also contains unparse, which turns an AST back into source text. It inserts parentheses only where the tree needs them: a child gets parentheses if its operator binds looser than its parent, or if it binds equally and sits on the right (because our operators are left-associative, 10 - (4 - 3) is not the same as 10 - 4 - 3). Unparsing is useful for error messages, code formatters and debugging, and it gives us a neat test: parsing the output should give back an equal tree.

Python AST nodes as dataclasses, a parser that builds them, and unparse

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 first output line is the entire AST of 1 + 2 * (3 - x) as a nested repr: a Binary plus whose right child is a Binary times, and so on. There is no node for the parentheses. The second block proves that spacing and redundant parentheses do not matter, because equal source meanings give == trees. In the round-trip block, 1+2*3 came back as 1 + 2 * 3 (new spacing, same tree), and 10 - (4 - 3) kept its parentheses because they were needed.

Equality on frozen dataclasses is a powerful testing tool. A parser test can be a single assertion: parse("1+2") == Binary("+", Num(1), Num(2)).

The visitor pattern

Compilers run many passes over the same tree: print it, count things, look up names, check types, optimize, generate code. The obvious way to organize this is to put a method for each pass on each node class, but then every new pass touches every class. The visitor pattern turns this around: each pass is one class with one method per node kind, and a small dispatch function sends every node to the right method.

flowchart LR
    T["One AST"] --> V1["TreePrinter"]
    T --> V2["NodeCounter"]
    T --> V3["UndefinedNames"]
    T --> V4["Evaluator"]

Many independent passes, one shared tree. Adding a pass never changes the node classes.

Python makes the dispatch trivial. visit builds the name "visit_" + type(node).__name__ and calls the method with that name with getattr. If a visitor has no method for a kind of node, it falls back to generic_visit. For analysis passes it is very convenient to give the base class a default traversal (a Walker) that visits every child, so a subclass only overrides the nodes it cares about. The NodeCounter below overrides only visit itself, and UndefinedNames overrides only Let, Assign and Var.

Python Four visitors over the same tree

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.

Study how differently the four passes behave. TreePrinter handles each node itself and recurses explicitly. NodeCounter relies completely on the default traversal. Evaluator returns values instead of just walking: the visit of a Binary node returns a number, and the visit of a While node loops by calling visit on its body again and again, which is a complete tree-walking interpreter in about twenty lines. UndefinedNames shows why order matters: in Let, the value is visited before the name is defined, so let a = a + 1; is correctly reported as a use of an undeclared a. This is a miniature version of the name resolution you will write in symbol tables and scopes.

Choices you will face

  • Visitor or pattern matching? Python's match statement can dispatch on node classes just as well, and many modern compilers use match or a big if isinstance chain. The visitor pattern shines when you have many passes and want a default traversal.
  • Immutable or mutable trees? Immutable trees are safer and make "transform" passes produce a new tree; mutable trees are faster for in-place rewriting. This track uses immutable nodes for clarity.
  • Typed or annotated trees? Later phases attach information to nodes, for example a type for every expression. Either add optional fields that a pass fills in, or keep a separate dictionary from node to information.
  • One node class per operator or one Binary with an operator field? A single class with an op field keeps the number of classes small; separate classes help when each operator is handled very differently.

Common mistakes

  • Keeping parentheses or semicolons as nodes. They are syntax, not meaning.
  • Copying grammar rule names into node names. Term and Factor describe how precedence was encoded, not what the program does.
  • Mutable defaults and shared children. Use tuples and frozen classes, or two parts of a tree can silently change each other.
  • Forgetting a node kind in a visitor. Always provide a clear generic_visit error so that missing cases are loud, not silent.
  • Losing positions. If nodes carry no line numbers, type errors will point nowhere.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which of these is normally NOT stored in an AST?

    Parentheses only guide the parser. Once the tree has the right shape, grouping is implied by the nesting, so no node is needed.
  2. 2. Why do 1 + 2 * 3 and 1 + (2 * 3) produce equal ASTs?

    Both programs group 2 * 3 first. The AST records only that structure, and a dataclass compares all fields recursively.
  3. 3. What is the main benefit of the visitor pattern for compilers?

    Each pass is its own class with one method per node kind, so new analyses or transformations do not touch the AST definitions.
  4. 4. In the UndefinedNames visitor, why is the value of a Let statement visited before the name is added to the defined set?

    The name does not exist until the statement has finished evaluating its value, so a self-reference in the value refers to an undeclared variable.

Summary

  • A parse tree mirrors every grammar step; an AST keeps only the structure that carries meaning.
  • Frozen dataclasses make convenient AST nodes: readable output, structural equality and safe sharing.
  • The parser builds nodes directly; grouping rules such as parentheses return the inner node and leave no trace.
  • unparse turns a tree back into source text with only the parentheses that are needed, which doubles as a round-trip test.
  • A visitor is a class with one method per node kind; a default traversal lets analysis passes override only what they need.
  • The same tree supports printing, counting, checking names and evaluating without changing the node classes.

Next: LL(1) Table-Driven Parsing