The Concrete Syntax Tree

An AST is a compression. It keeps the structure that determines meaning and drops everything else: parentheses that only grouped, the exact spelling of a numeric literal, the choice between ' and ", blank lines, and comments. For a compiler that is unambiguously the right design — every discarded thing is by definition irrelevant to what the program does, and the smaller tree makes every later pass simpler.

It is the wrong design for any tool that has to produce source code as output. A formatter must preserve comments. A refactoring engine must produce a file that differs from the original only where the refactoring applied. A codemod must not reflow a thousand unrelated lines. An IDE's "extract method" must leave the rest of the file byte-identical, or the diff is unreviewable. And a syntax highlighter must classify every character, including the ones between tokens.

So a second tree exists, and the rule of thumb is simple: a tool that only reads the program wants an AST; a tool that writes the program back out wants a CST. Most modern language toolchains build the CST first and derive the AST from it, rather than the reverse, because the derivation only goes one way.

The mechanism is straightforward: the lexer, instead of skipping whitespace and comments, collects them and attaches them to an adjacent token as leading or trailing trivia. Roslyn — Microsoft's C# and Visual Basic compiler platform — introduced the terminology most people use, and its rule is representative: trivia up to and including the end of a line attaches as trailing trivia to the token before it; everything after that attaches as leading trivia to the token that follows.

That rule is arbitrary and it has to be. Consider a comment on its own line between two functions: it is documentation for the second one nine times out of ten, and a closing remark about the first one occasionally. No parser can tell. So the tool commits to a convention, documents it, and every refactoring engine built on it inherits the convention — which is why "move this function" sometimes takes the wrong comment with it in every IDE you have used.

Two design points are worth naming because they distinguish serious implementations. First, whether disabled preprocessor regions are in the tree: Roslyn keeps #if branches that were not taken as trivia, so a refactoring can see and update code the compiler never compiled. Second, whether the tree is *lossless in the presence of errors*: tree-sitter and rust-analyzer both produce a complete tree for broken input, with error nodes covering the parts that did not parse, precisely so that an editor can keep working while you type. A tree that only exists for valid programs is not usable in an editor at all — see [[language-server]].

Both solve the same problem — a full-fidelity tree that can be edited cheaply while you type — and they solve it differently enough to be worth knowing as a pair.

Roslyn uses *red-green trees*. The green tree is immutable, has no parent pointers and stores only widths rather than absolute positions, which means an identical subtree can be shared between many places and between many versions of a file. The red tree is a thin lazily-created facade over it that adds parent links and absolute positions, computed by walking down from the root. The consequence is the useful part: editing one token produces a new green tree that shares every unchanged subtree with the old one, so a keystroke costs work proportional to the depth of the edit rather than to the size of the file. rust-analyzer uses the same design in its rowan library, and Swift's SwiftSyntax is a close relative.

tree-sitter takes the incremental-parsing route: a GLR-family parser that, given the previous tree and a list of edits, reparses only the affected region and reuses the rest of the tree directly. It is language-agnostic — grammars are separate artifacts — it produces a complete tree with error nodes for broken input, and it exposes a query language for matching patterns in the tree, which is what makes it the substrate for syntax highlighting, structural search and code navigation in editors that do not have a full language server for every language.

The shared insight is that structure sharing is what makes a full-fidelity tree affordable. The CST is several times larger than the AST, and rebuilding it on every keystroke would be hopeless; keeping unchanged subtrees identical between versions is what turns an expensive representation into a cheap one.

A CST has several times the node count of the equivalent AST, most of them punctuation, and every one of them costs allocation, cache footprint and traversal time. A compiler pass that pattern-matches on Binary(Add, l, r) becomes a pass that must skip past token nodes for the operator and possibly parentheses. That is why compilers that do not need to emit source keep the AST as the working representation and build a CST only in the tooling layer — or, like Clang, keep a rich AST that retains enough source information for most tooling purposes without going to full fidelity.

The other cost is duplication. A project with both a CST and an AST has two definitions of the language's structure, and they must agree. Toolchains solve this by deriving one from the other automatically (rust-analyzer generates its typed AST accessors from the grammar over rowan nodes; Roslyn generates its node classes from an XML description), which turns the problem into a code-generation problem rather than eliminating it.

The honest guidance: if the tool only reads, do not pay for it. If the tool writes source, you need it and there is no shortcut — every attempt to reprint from an AST plus "some" position information ends up rebuilding a worse CST incrementally, with comments going missing in the meantime.