ASTtypical

Walking the Tree

Every frontend pass is a depth-first search over a tree, and which analyses are correct depends on *when* the node is processed: scopes open on the way down, types are computed on the way up, and getting that backwards produces a compiler that is confidently wrong.

The question

How does a compiler pass actually visit every node, and does the order matter?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute

What the program is here

The tree is unchanged; what this lesson adds is an *order*. A traversal turns the tree into a sequence of visit events — enter node, visit children, exit node — and that sequence is the only thing a pass ever really sees. Choosing pre-order or post-order is choosing whether a node is processed before or after everything it contains, which decides what information is available when the node is handled.

What this phase may assume or do

A traversal may assume the tree is acyclic and finite, so a naive recursive walk terminates and visits each node exactly once. A pass may only rely on facts established by an earlier visit in its own traversal order: a post-order pass may use its children's results, a pre-order pass may use its ancestors' results, and neither may use the other without an extra pass. A traversal that mutates the tree while walking it may only do so if the mutation does not invalidate the iteration — otherwise the walk must collect the edits and apply them afterwards, which is why [[ast-transformations]] treats rewriting as a separate step.

Key points

An AST traversal is depth-first search on a rooted acyclic tree; every property of DFS transfers, including stack depth.
Pre-order processes a node before its contents; post-order processes it after. That choice decides what information is available.
Type checking, constant folding and free-variable analysis are post-order because information flows up from children.
Scope entry and name resolution are pre-order because information flows down from enclosing constructs.
The call stack of a recursive walk is the ancestor chain, which is why parent pointers are usually unnecessary.
Multiple small passes beat one fused walk almost everywhere; the exception is a collect-then-resolve pair, which is a correctness requirement.

This is DFS, and it is the same DFS

typicalRecursive descent over the AST is what mainstream frontends do, and it is why every serious compiler ships a recursion-depth limit: Clang defaults to 256 levels of bracket nesting and errors out beyond it, and CPython raises a RecursionError compiling sufficiently nested literals. The limit is a diagnostic, not a crash, and a compiler that lacks one segfaults on machine-generated input instead. Some frontends — the TypeScript checker among them — use manual stacks for the specific constructs known to nest without bound.

A compiler pass is a depth-first search over a tree. Not analogous to one — literally one. Depth-first search as taught in the data-structures domain is the same algorithm, with the same recursion, the same explicit-stack alternative, and the same stack-depth failure on deep input. The only difference is that the graph is guaranteed acyclic and rooted, so there is no visited set.

That has practical consequences you already know. Recursion depth is bounded by tree height, not node count, so a wide file is fine and a deeply nested one is not. Converting to an explicit worklist stack removes the native-stack limit at the cost of writing the state machine by hand — which is why several production parsers and walkers keep a manual stack for exactly the constructs that nest arbitrarily, such as chained binary operators and nested parentheses.

Because a tree has one path from the root to each node, the traversal *is* the ancestor chain: at any moment, the frames on the call stack are precisely the enclosing constructs. That is why [[ast-node-design]] can argue against parent pointers — the parent chain already exists, for free, in the walk. It is also why an explicit-stack traversal has to reconstruct that chain by hand, which is real work you should count before converting.

The whole algorithm, with both visit points exposed

1function walk(node: Node, enter: (n: Node) => void, exit: (n: Node) => void) {
2  enter(node)                       // pre-order:  before any child
3  for (const child of childrenOf(node)) walk(child, enter, exit)
4  exit(node)                        // post-order: after every child
5}

Almost every real walker exposes both hooks, because almost every real pass needs one or the other and a few need both. A walker that offers only one visit point forces half of its users into a second traversal.

Pre-order and post-order are not stylistic

A node visited in pre-order is processed before anything it contains. A node visited in post-order is processed after everything it contains has already been processed. Which one a pass needs is determined entirely by where its information flows from, and there is nothing to debate once you ask that question.

Type checking flows *upward*. The type of 1 + 2 is a function of the types of 1 and 2; you cannot compute it until both children have answered. So type checking is post-order, and every type-checking bug of the form "the type is undefined here" is at bottom a claim that something asked before the children were done. The same is true of constant folding, of "does this expression have side effects", of size and complexity metrics, and of every synthesised attribute in the attribute-grammar sense.

Scope handling flows *downward*. Entering a Block must push a scope before any statement inside it is examined, because the statements resolve names against it; leaving the block must pop it. So scope construction is pre-order on the way in and needs the post-order hook on the way out — it is the classic case for a walker with both. [[lexical-scope]] and [[symbol-table]] are this traversal, and nothing more.

Passes that need both directions in the same walk are the interesting ones. A definite-assignment analysis carries a set of initialised variables downward and needs the merged result of the branches upward; that combination is what eventually motivates leaving the tree entirely for a [[control-flow-graph]], where the flow direction is explicit rather than implied by tree position.

Which order each frontend pass needs, and whytypical

Pass	Order	Because
Type checking	Post-order	A node's type is computed from its children's types; asking earlier has nothing to read
Constant folding on the AST	Post-order	`(1 + 2) * 3` folds only after the inner addition has already become `3`
Scope construction	Pre-order enter, post-order exit	The scope must exist before its contents are examined and must be gone afterwards
Name resolution	Pre-order (with the scope stack)	A use resolves against bindings established by enclosing constructs, i.e. by ancestors
Reachability / dead statement warnings	Pre-order	Whether a statement is reachable is a fact inherited from what precedes and encloses it
Free-variable computation for closures	Post-order	A lambda's free set is the union of its body's free sets minus its own parameters
Pretty-printing	In-order-ish, structure-driven	Output interleaves node text with child text, so neither pure order describes it

Order made visible

The tree below is let x = 1 + 2; again, annotated with the visit number each node receives under each order. Read the two columns side by side: the declaration is node 1 in pre-order and node 5 in post-order, which is exactly the difference between "open a binding before looking at the initializer" and "know the initializer's type before recording the binding's type".

That single row is a real language-design question, not a bookkeeping detail. If the declaration is processed before its initializer, let x = x; resolves the inner x to the one being declared — which is how JavaScript's let produces a temporal-dead-zone error and how Rust's let does *not*, because Rust processes the initializer against the *old* scope and only then introduces the binding. Same tree, different traversal decision, observably different language.

Visit numbers for let x = 1 + 2; — pre / post

AST — only what later phases match on

VariableDeclaration pre 1 / post 5— Pre-order sees it first and knows nothing about the initializer. Post-order sees it last and knows the initializer is `int`.

├── Identifier x pre 2 / post 1

└── BinaryExpression + pre 3 / post 4— Its type cannot be computed at visit 3. At visit 4 both operands have answered `int`, and `+` is defined for that pair.

├── NumberLiteral 1 pre 4 / post 2

└── NumberLiteral 2 pre 5 / post 3

Read it asLeaves are visited early in post-order and late in pre-order; the root is the exact reverse. A pass that reads a child's result must be post-order, and a pass that establishes context for children must be pre-order. Everything else about traversal is packaging.

One walk or several

The obvious economy is to do everything in one traversal. It is usually the wrong economy. Passes that share a walk share an order, and the orders they need conflict; they also become mutually dependent, so the resulting function cannot be tested, reordered or skipped independently. Multi-pass frontends run many small traversals over the same tree, and the extra walks are cheap — the tree is in cache after the first one, and the pass count is not what makes a frontend slow.

The place a single walk genuinely wins is where a pass must *establish* something for the next: collecting all declarations in a scope before resolving any use in it, so that a function may call one defined later in the file. That is not an optimization, it is a correctness requirement, and it is why [[declaration-order]] describes a collect-then-resolve pair rather than one clever walk.

Separate passes are independently testable, independently skippable, and can be reordered when a dependency turns out to run the wrong way round.
Separate passes make the dependency graph between analyses explicit instead of implicit in the order of if statements inside one visitor.
Fusing passes is a compile-time optimization with a real cost in coupling; measure before paying it.
A pass that needs two different orders is two passes that happen to share a file.

How it works

The steps, in the order the compiler takes them.

Start at the root and call the enter hook.
Visit each child in source order, recursing; the recursion stack now holds exactly this node's ancestors.
After the last child returns, call the exit hook — at which point every result computed by the subtree is available.
A pass that synthesises information (types, sizes, free variables) does its work in the exit hook and stores the result in a side table keyed by node id.
A pass that inherits context (scopes, reachability, enclosing function) pushes state in the enter hook and pops it in the exit hook.
A walker that must not blow the native stack replaces recursion with an explicit worklist of (node, phase) pairs, reconstructing the ancestor chain manually.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

A type checker runs pre-order and reads a child's type before the child has one. The symptom is not a crash: it is an error message saying an expression has type unknown or error, pointing at code that is perfectly correct, and only for some nesting depths.
A scope is pushed in the enter hook and the exit hook is missing on one branch — usually an early return inside the visitor. Names leak out of the block, and a variable declared inside an if is silently visible afterwards.
A pass mutates the child list while iterating it. Some nodes are visited twice and some are skipped entirely; the compiler produces different output for the same input depending on which mutation ran first.
A generated file nests ten thousand array literals and the recursive walker overflows the native stack. The compiler dies with a segmentation fault and no diagnostic, and the user reasonably concludes the compiler is broken rather than that their input is deep.
Two analyses were fused into one walk for speed. A later change requires one of them to run earlier; splitting them turns out to be a week of work because they read each other's half-built state.

When it helps

Writing any frontend pass at all: naming the direction the information flows tells you the traversal order before you write a line.
Debugging a "this is undefined here" error in a compiler you did not write — it is nearly always an order mismatch between a producer and a consumer.
Reasoning about language design questions whose answer is literally a traversal decision, such as whether a declaration's initializer sees the new binding.

When it hurts

Flow-sensitive analysis. "Is this assigned on every path" is not answerable by tree order at all, because tree position and execution order diverge the moment there is a branch or a loop. Build a CFG.
Interprocedural questions. A traversal of one function's tree cannot answer anything about its callers; that needs a call graph.
Very deep machine-generated input, where the elegance of recursion is exactly what makes the compiler fall over.

What it costs

Every one of these is paid by something.

Recursive traversal buys code that reads like the grammar and costs a hard dependency on native stack depth, which turns machine-generated input into crashes unless an explicit depth limit is added and maintained.
An explicit-stack walker buys unbounded depth and costs readability plus the manual reconstruction of the ancestor chain that recursion gave you for free.
Many small passes buy testability, reorderability and clear dependencies, and cost repeated traversals of the tree — cheap in cache terms, but not free, and visible in a frontend with a hundred passes.
Fusing passes into one walk buys compile time and costs the ability to change either pass independently; the coupling is discovered later, when a dependency needs to be inverted.
Exposing both enter and exit hooks buys every pass its natural order and costs a slightly larger walker interface that every visitor must implement or explicitly ignore.

What else you could do

What a different compiler or language does instead, and when that is better.

Attribute grammars make the direction explicit in the language: synthesised attributes flow up, inherited attributes flow down, and the evaluation order is derived from the dependencies rather than chosen by hand. Used in some generated frontends; less common because the dependency solving is opaque when it fails.
Query-based, demand-driven traversal: instead of walking everything, ask "what is the type of node N" and let a memoising query engine pull only what it needs. rustc and rust-analyzer both work this way, which is what makes them incremental — you pay a query framework, a hashing scheme and a cycle detector.
Iterative worklist traversal over an explicit stack, when depth is unbounded and the input is machine-generated.
Abandon the tree and analyse the [[control-flow-graph]] instead, once the questions become flow-sensitive. That is a change of representation, not a change of traversal, and it is the right move at exactly that point.

See it for yourself

The flag, dump or tool that shows you this directly.

Python: ast.NodeVisitor gives you visit_* methods (pre-order) and generic_visit for recursion; ast.NodeTransformer is the rewriting variant. Twenty lines will print the visit order for any file.
Clang: RecursiveASTVisitor exposes TraverseX, WalkUpFromX and VisitX precisely because pre- and post-order are different hooks; reading its header is a short lesson in why both exist.
Add a depth counter to any walker and print the maximum: comparing it against your language's recursion limit tells you how close a real codebase gets.
ESLint rules receive Node for enter and Node:exit for exit — writing one of each over the same file makes the ordering difference immediate.

Plausible wrong readings

Stated the way a confident engineer states them.

"Traversal order is an implementation choice." It determines which facts are available at each node. Choosing wrongly produces a compiler that reports errors on correct code, which is not a style question.
"Post-order is just bottom-up and bottom-up is more efficient." Neither is more efficient; they visit the same nodes the same number of times. They differ in *what is known* when the visit happens.
"A single well-written pass can do all of it." It can, until two of its jobs need opposite orders — and then it cannot, and untangling it is much more expensive than never fusing them.
"Deep recursion is fine, the compiler is not the bottleneck." Depth is bounded by the native stack, not by your patience. Machine-generated code routinely exceeds it and the failure is a crash without a message.

Misconceptions

The claim, and what is actually true.

Pre-order and post-order are two ways of writing the same pass.

They are two different passes. Information available at a node differs completely between them, and a pass written in the wrong one is not slower, it is wrong.

An AST traversal visits nodes in execution order.

It visits them in *source structure* order. The body of an if is visited whether or not it would ever execute, and a loop body is visited once. Execution order needs a CFG.

You need parent pointers to know the enclosing function.

The recursive walk's call stack already is the ancestor chain. Pass the enclosing function down as a parameter.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

Visiting every node of an AST is depth-first search. The only real decision is whether you do your work when you arrive at a node or when you leave it. Arrive-first is pre-order and is what you want when the node sets up context for its contents, like opening a scope. Leave-last is post-order and is what you want when the node needs answers from its contents, like computing a type.

practical

When a frontend pass misbehaves, instrument the walk before reading the pass. Print node kind and span on enter and on exit, and compare with what you expected: nine times in ten a pass that "cannot see" a fact is running in the wrong order relative to whatever produces it, and one in ten a scope was pushed on a path where the matching pop was skipped. Both are visible in the visit trace and neither is visible by reading the visitor.

advanced

A traversal is a fixed, eager schedule, and its limit is that everything gets computed whether or not anything asks. Query-driven frontends invert it: type_of(node) recursively demands only what it needs, memoises the result, and records the dependency edges — which turns the same computation into an incremental one, because a changed node invalidates only what actually read it. rustc's query system and rust-analyzer's salsa are both this. The tree traversal has not gone away; it has become the *default* order in which a demand happens to unfold, and it stops being a schedule you control.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

typicalThat type checking is post-order describes checking of *expressions*, which is where the bulk of the work is. Whole-program inference does not fit the description: Hindley-Milner collects constraints during a walk and then solves them globally, so the order of the walk determines constraint generation order and not the order in which types are decided — see [[hindley-milner]]. Bidirectional type checking mixes the two deliberately, pushing an expected type downward and synthesising upward in alternation.

implementationRecursion limits are per-implementation and change between versions. Clang uses a 256-level bracket-depth limit adjustable with -fbracket-depth; CPython's compiler limit is separate from sys.setrecursionlimit and has moved in recent releases. Do not encode any specific number in a tool; detect the failure and report it instead.

simplifiedThe walker shown treats every node uniformly through a childrenOf function. Real walkers are usually generated or hand-written per node kind, because children are named fields rather than a homogeneous list, and because most passes want to skip entire subtrees (function bodies during a declaration-collection pass, for instance) rather than visit everything.

If you were asked this in an interview

Should a type checker walk the AST pre-order or post-order? Justify it in one sentence, then name a pass that needs the other one.
A compiler crashes with a stack overflow on a generated file. What is the likely cause and what are the two ways to fix it?
How does a pass find its enclosing function without a parent pointer?
When would you fuse two AST passes into one traversal, and what do you give up?

Connections

DSAdfs binary-tree n-ary-tree stack recursion

OS & Networkingstack-frames stack-overflow