Parsingtypical

Parse Tree vs Abstract Syntax Tree

Two trees for the same input `1 + 2 * 3`: one with a node for every grammar rule and every comma, one with five nodes. The difference is not tidiness — it decides which tools you can build.

The question

What is the difference between a parse tree and an AST, and why do compilers build one and IDEs the other?

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

What the program is here

The same program, twice. A parse tree (concrete syntax tree) is a record of the derivation: one node per grammar rule applied, one leaf per token including punctuation, so the source text is recoverable character for character. An AST is a record of the *meaning of the structure*: one node per construct the language actually has, with punctuation and single-child rule chains discarded. The parse tree answers "how did the grammar match this text"; the AST answers "what does this program consist of".

What this phase may assume or do

Going from parse tree to AST is a lossy projection, and it is only sound if nothing downstream needs what is dropped. Dropping a ( node is safe because the grouping it expressed is already encoded in the tree shape; dropping the *span* of that ( is not, because a diagnostic about an unclosed delimiter needs it. The discipline is: discard the node, keep the position. A frontend that also serves a formatter or a refactoring tool may discard nothing at all, and must build a lossless tree instead.

Key points

A parse tree records the derivation: one node per grammar rule, one leaf per token, punctuation included. An AST records the constructs the language has.
For 1 + 2 * 3 that is thirteen nodes against five, and the difference is entirely rule chains and punctuation.
The AST loses nothing about meaning — grouping was always encoded in shape — but loses the ability to reproduce the source text.
Formatters, refactoring tools, highlighters and language servers need the lossless tree; type checkers, optimizers and lowering want the AST.
Modern frontends increasingly build a lossless tree with a typed AST view over it, so the two are not separate structures.
Whatever is discarded, spans must survive — including the operator's own span, and the node span as a union of its children.

The same input, matched by the grammar

Take the stratified grammar from [[what-parsing-does]] — expr -> expr '+' term | term, term -> term '*' factor | factor, factor -> NUMBER | '(' expr ')' — and run it over 1 + 2 * 3. The parse tree below is a faithful transcript of that derivation. Every nonterminal the parser entered is a node. Every token it consumed is a leaf, + and * included. The chains expr -> term -> factor -> NUMBER are there because the grammar went through them, even though they carry no information at all.

Thirteen nodes for a nine-character expression. Nine of them exist purely because the grammar was stratified for precedence — and the precedence they were encoding is now visible in the shape, which means the nodes themselves have done their job and have nothing left to say.

Parse tree (concrete syntax tree) for 1 + 2 * 3 — every rule, every token

Parse tree — every grammar rule and every token

expr“1 + 2 * 3”— Matched `expr -> expr '+' term`.

├── expr“1”— A single-child chain: `expr -> term`. Carries no information.

│ └── term“1”

│ └── factor“1”

│ └── NUMBER "1"“1”

├── '+'“+”— A punctuation leaf. Its only content is its own existence and its span.

└── term“2 * 3”— Matched `term -> term '*' factor`.

├── term“2”

│ └── factor“2”

│ └── NUMBER "2"“2”

├── '*'“*”

└── factor“3”

└── NUMBER "3"“3”

Read it asRead the depth of p4: four levels down for the literal 1, every level a rule the grammar needed to encode precedence. Note also that the tree is *complete* — concatenate the leaves left to right and you get back 1+2*3 exactly. That property is what a formatter and a refactoring tool require, and it is precisely what the next tree gives up.

The same input, as the compiler wants it

Now the AST. The operator is the node, its operands are the children, and every node corresponds to a construct the language actually has. Single-child rule chains collapse. Punctuation leaves vanish — the + is not a child, it *is* the node.

Five nodes instead of thirteen. Nothing about the program's meaning was lost: 1 + (2 * 3) is still exactly what the tree says, because grouping was always a matter of shape rather than of parenthesis nodes. What was lost is the ability to reconstruct the source text, and that is a real loss, just not one an optimizer cares about.

AST for the identical input 1 + 2 * 3 — one node per construct

AST — only what later phases match on

Binary +“1 + 2 * 3”— The operator is the node. There is no separate `+` leaf and no `expr` wrapper.

├── Number 1“1”— One level from the root, not four.

└── Binary *“2 * 3”— Deeper than the `+`, which is exactly what "binds tighter" means once the grammar has done its work.

├── Number 2“2”

└── Number 3“3”

Read it asPut the two trees side by side and the contrast is the lesson. Same input, same language, same meaning; thirteen nodes against five. Every pass written against the AST is a five-case visitor; the same pass written against the parse tree must know about expr, term, factor and the punctuation leaves, and must skip the chains — which means it would also break the moment somebody adds a precedence level to the grammar.

What each tree can and cannot do

implementationTrue of rust-analyzer (rowan green/red trees), Roslyn (full-fidelity syntax trees with trivia) and tree-sitter (lossless concrete trees) as designed. It is not true of every compiler frontend: Clang's AST keeps source locations but not comments or whitespace, which is why clang-format is a separate tool with its own lexer rather than a consumer of the Clang AST.

The choice is not aesthetic. It determines which products you can build on the frontend. A parse tree that keeps every token and every trivium can be printed back out byte for byte, so a formatter can rewrite one statement and leave the file's comments and blank lines untouched. An AST cannot: print it back out and you get *a* valid program, not *the* program the user wrote.

Conversely, every semantic pass wants the AST. Type checking Binary + is one case; type checking expr requires first discovering that this expr is really an addition, which means re-deriving the grammar structure the parse tree was supposed to have already resolved. Optimizers, lowering and IR generation all want the small tree.

Which is why serious modern frontends build both, or rather build one tree that can be viewed as either: rust-analyzer and Roslyn keep a lossless concrete tree with typed accessors layered over it, and tree-sitter keeps a lossless tree by design. The AST is then a view, not a separate structure. See [[concrete-syntax-tree]] and [[ast-as-shared-infrastructure]].

Which tree a given tool needstypical

Tool	Tree it needs	Why
Optimizer / IR generation	AST	Wants one case per construct; rule chains and punctuation are pure noise.
Type checker	AST	Attaches a type to each construct; `expr -> term` has no type of its own.
Code formatter	Lossless parse tree	Must reproduce every byte it did not deliberately change, comments included.
Refactoring / rename	Lossless parse tree	Edits are byte ranges in the original file, not a reprint of the AST.
Syntax highlighter	Lossless parse tree	Needs to colour punctuation and comments, which the AST discarded.
Linter	Either, usually both	Rules about structure want the AST; rules about style want the trivia.
Language serverimplementation	Lossless parse tree with an AST view	Serves all of the above, and must survive a file that does not parse.

The thing that must survive the projection

Collapsing thirteen nodes into five throws away nodes. It must not throw away positions. The Binary + node still carries the span 1 + 2 * 3, and — in a well-built frontend — also the span of the operator token itself, so that a diagnostic can underline the + rather than the whole expression.

This is the single most common place where a frontend quietly limits itself forever. Attach only a start offset instead of a range and you can never underline anything. Attach the span of the first token rather than the union of the children's spans and every error about a compound expression points at its leftmost leaf. Neither mistake produces a test failure; both produce a compiler whose messages are subtly useless — see [[spans-and-ranges]].

The projection, written out: parse node in, AST node out

1// A parse node knows its rule; an AST node knows its construct.
2type ParseNode =
3  | { rule: 'expr' | 'term'; kids: [ParseNode, Token, ParseNode] } // binary form
4  | { rule: 'expr' | 'term' | 'factor'; kids: [ParseNode] }        // chain form
5  | { rule: 'factor'; kids: [Token] }                              // NUMBER
6 
7type Ast =
8  | { kind: 'Binary'; op: string; opSpan: Span; left: Ast; right: Ast; span: Span }
9  | { kind: 'Number'; value: number; span: Span }
10 
11function lower(n: ParseNode): Ast {
12  // Chain rules carry nothing. Collapse them and keep going.
13  if (n.kids.length === 1 && isParseNode(n.kids[0])) return lower(n.kids[0])
14 
15  if (n.kids.length === 3) {
16    const [l, op, r] = n.kids as [ParseNode, Token, ParseNode]
17    const left = lower(l)
18    const right = lower(r)
19    return {
20      kind: 'Binary',
21      op: op.text,
22      opSpan: op.span,              // kept so a diagnostic can underline the operator
23      left,
24      right,
25      span: join(left.span, right.span), // the union, NOT the leftmost child's span
26    }
27  }
28 
29  const tok = n.kids[0] as Token
30  return { kind: 'Number', value: Number(tok.text), span: tok.span }
31}

The two lines that matter are opSpan and join(...). Everything else is bookkeeping. A version that omitted them would produce an identical tree shape, pass every structural test, and give every future user of this compiler worse error messages than they should have had.

How it works

The steps, in the order the compiler takes them.

The parser applies productions; a parse tree is built by creating one node per application, with children in source order and tokens as leaves.
Lowering to an AST walks that tree bottom-up.
A node with exactly one non-token child is a chain rule and is replaced by that child — this is what removes expr -> term -> factor.
A node matching a binary production becomes a single operator node whose children are the lowered operands; the operator token becomes a field, not a child.
Punctuation leaves that only expressed grouping — parentheses, separators, terminators — are dropped, because the grouping is already in the shape.
Each new node computes its span as the union of its children's spans, and retains the spans of any dropped tokens that a diagnostic may need to point at.
A frontend that needs losslessness skips this pass and instead layers typed accessors over the concrete tree, so the AST becomes a view rather than a copy.

How it breaks

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

A refactoring tool rewrites one function and the whole file comes back reformatted with the comments gone, because it round-tripped through an AST that never held them.
A diagnostic about a binary expression underlines the entire statement instead of the operator, because the node kept only a single merged span.
A linter rule written against the parse tree stops firing after somebody adds a precedence level to the grammar, since the rule was matching on a specific chain depth.
Error messages point at the first token of a compound expression, because the node span was taken from the leftmost child rather than as a union.
Memory use of the frontend is several times what was budgeted on a large file, because a lossless tree was kept alive for every open document alongside the AST.
A code-generation tool emits syntactically valid but reformatted output on every run, so every commit shows the entire file as changed and real diffs become invisible.

When it helps

Deciding what to build a new language tool on: if the tool must write source back out, the question is settled before you start — it needs the lossless tree.
Understanding why a compiler and its formatter are separate binaries with separate parsers; that is usually a consequence of an AST-only frontend, not an oversight.
Debugging a pass that behaves differently on (a) and a: an AST should make those identical, and if it does not, parenthesis nodes were kept somewhere they should not have been.

When it hurts

Building a lossless tree for a compiler that only ever compiles. The memory and the extra node kinds buy nothing, and every pass now has to skip trivia.
Treating the AST as canonical when it is not the parser's real output. If the frontend is lossless underneath, an AST-shaped bug report may be about the view rather than the tree, and the fix is in a different layer.

What it costs

Every one of these is paid by something.

The AST buys small, uniform passes and a tree that survives grammar refactoring, and pays with the source text: anything that must reproduce the user's file byte for byte cannot use it.
A lossless concrete tree buys formatters, refactoring, highlighting and error-tolerant IDE behaviour, and pays several times the memory per file plus trivia handling in every consumer.
The hybrid — lossless tree with typed AST accessors, as in rowan or Roslyn — buys both, and pays substantial implementation complexity: two layers, an identity mapping between them, and a much harder debugging story when they disagree.
Dropping parenthesis nodes buys pass simplicity and pays a subtle debt: a tool that wants to preserve the user's redundant parentheses on reprint has to re-derive them from precedence, and will sometimes get it wrong.

What else you could do

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

Keep only the parse tree and write every pass against it, as some generated-parser toolchains encourage. Simpler pipeline, and every pass becomes grammar-shaped and brittle.
Keep only the AST and give the formatter its own independent parser, which is what clang-format does relative to Clang. Two parsers to keep in agreement, and they do drift.
Build the lossless tree as the only tree and derive the AST as a typed view — rust-analyzer's rowan, Roslyn's syntax trees, and Swift's SwiftSyntax all take this route. Highest complexity, and the only one that serves compiler and IDE from one frontend.
For pure data transformation, skip trees and stream events (a SAX-style parser). Constant memory, and no ability to look at anything but the current position.

See it for yourself

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

clang -Xclang -ast-dump -fsyntax-only x.c shows Clang's AST; note that it prints source locations but no comments or whitespace, which tells you directly that it is not lossless.
tree-sitter's CLI: tree-sitter parse file.js prints the concrete tree with byte and (row, col) ranges for every node, punctuation included. Compare it against an ESTree AST of the same file to see the two representations side by side.
python -m ast versus the tokenize module: the AST has no comment nodes at all, while tokenize yields COMMENT and NL tokens — the projection made visible in two lines of shell.
For .NET, SyntaxTree.ToFullString() in Roslyn returns the exact original text from the parsed tree; if it does, the tree is lossless, and that one call is the test.
AST Explorer in a browser shows the AST for many languages; for the concrete tree, use tree-sitter's playground on the same input and count the nodes.

Plausible wrong readings

Stated the way a confident engineer states them.

"The AST is just a tidied-up parse tree." It is a different representation with different guarantees. Tidying implies you could untidy it; you cannot get the source text back.
"Parentheses are stored in the AST so we know the user wrote them." In almost every AST they are not. (1 + 2) * 3 and 1 + 2 * 3 produce different tree shapes, not different parenthesis nodes, and (a) and a produce identical trees.
"A CST is only useful for IDEs." It is also what lets a compiler produce good delimiter diagnostics and what lets a code-mod tool touch one line without rewriting the file.
"The AST is smaller so it is strictly better." It is smaller because it discarded things. Whether that is better depends entirely on whether anything downstream needed them, and the tools that need them are exactly the ones users notice.

Misconceptions

The claim, and what is actually true.

A parse tree and an AST are two names for the same thing.

They differ in what is recoverable. From a lossless parse tree you can reconstruct the file exactly; from an AST you can reconstruct a program with the same meaning and different text.

ASTs drop information, so they lose precision.

They lose *textual* information, not semantic information. The grouping expressed by parentheses survives as tree shape, which is a stronger encoding than a punctuation node because no pass can forget to interpret it.

If my parser builds an AST directly, there is no parse tree, so this distinction does not apply to me.

The distinction still decides what your frontend can support. Building the AST directly is exactly the decision that your compiler will never host a formatter or a rename refactoring.

Go deeper

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

overview

Two trees for the same code. The parse tree writes down every step the grammar took, including a node for the + and for every intermediate rule, so the original text can be rebuilt from it exactly. The AST writes down only the things the language actually has — an addition with two operands — which is five nodes instead of thirteen for 1 + 2 * 3. Compilers want the small one; anything that has to write your file back out wants the big one.

practical

Pick by the question "must this tool reproduce the user's exact bytes?". Yes for formatters, code-mods, rename, highlighting, and any IDE feature that edits a file in place — those need a lossless tree, and retrofitting one later is a frontend rewrite, not a feature. No for type checking, optimization and code generation — those want the AST, and using the concrete tree for them makes every pass depend on grammar details that change. When you do lower to an AST, the two things to get right are the operator span and the union span; both are invisible in tests and both are what your error messages will live on.

advanced

The design that has won in tooling-heavy ecosystems is neither tree but the pair: an untyped, lossless, cheaply-shared green tree plus typed red nodes that present it as an AST, as in rowan and in Roslyn. The reason is incrementality — a green node is immutable and structurally shared, so reparsing one edited function reuses the rest of the file's nodes by pointer, and the language server answers a keystroke in microseconds. That property is unavailable to an AST-only frontend at any price, and it is the real argument for the extra complexity: not fidelity, but the ability to reparse a ten-thousand-line file on every keypress.

How much this depends on

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

typicalThe node counts here come from the specific three-level grammar shown. A grammar written for a generator often has more levels and therefore a deeper parse tree; a hand-written Pratt parser never materialises a parse tree at all and builds the AST directly, so the thirteen-node tree is a conceptual object rather than something in memory.

implementationLossless-tree frontends are the direction of travel but not universal. Roslyn (since 2014), rust-analyzer, SwiftSyntax and tree-sitter are lossless by design; Clang, GCC and CPython are not, and each pairs with a separately implemented formatter. Check before assuming a given compiler can serve a refactoring tool.

simplifiedOur parse tree omits the end-of-file token and the statement-level rules a real grammar would have above expr, and it shows no trivia nodes for the spaces around the operators. A genuinely lossless tree attaches those spaces and any comments to adjacent tokens as leading and trailing trivia, which roughly doubles the leaf count again.

If you were asked this in an interview

Draw the parse tree and the AST for 1 + 2 * 3 and tell me which nodes disappeared and why none of them mattered.
I want to write a tool that adds a missing await to one line and changes nothing else in the file. Which tree do I need, and what happens if I use the other one?
Where do parentheses go in an AST?

Connections

DSAn-ary-tree binary-tree dfs

Domains that do not exist yet

Programming Languages & Runtime Internals — Structural sharing of immutable trees
The green/red tree design that makes lossless parsing affordable is persistent-data-structure engineering — sharing, reference counting and interning — and the general technique is owned there.