Abstract Syntax Trees

Every time you press a key, your editor silently builds a tree. Not because trees are pretty — because they are the right shape for code.

Source code arrives as a flat stream of characters: 3 * (4 + 5). That string carries meaning, but meaning that depends entirely on context: which operation binds tighter, what the parentheses scope, whether the whole thing is a statement or just part of a larger expression. A flat string cannot answer those questions; a tree can.

The abstract syntax tree (AST) is the data structure a compiler, interpreter, or linter builds immediately after reading your source. It throws away the characters that were only there for human readability — the parentheses once the precedence is captured, the semicolons once the statement boundaries are known — and keeps only the structural relationships that matter for computation.

That act of distillation turns a messy human-friendly syntax into a clean machine-friendly skeleton. Everything a compiler does next — type checking, optimization, code generation — walks this tree.

Type any arithmetic expression in the box below — numbers, +, -, *, /, and parentheses. The demo parses it into an AST, draws the tree, and then evaluates it by walking from the leaves up to the root.

<!-- {{c_html_intro}} -->
<div class="demo-wrap">
  <label class="input-label" for="expr">{{label_expression}}</label>
  <div class="input-row">
    <input id="expr" type="text" placeholder="{{placeholder_expr}}" value="3 * (4 + 5)" autocomplete="off" spellcheck="false" />
    <button id="btn-parse" type="button">{{btn_parse}}</button>
  </div>
  <div id="error" class="error-msg" hidden></div>
  <div class="panels">
    <div class="panel">
      <div class="panel-title">{{panel_tree}}</div>
      <svg id="tree-svg" width="100%" height="260"></svg>
    </div>
    <div class="panel">
      <div class="panel-title">{{panel_eval}}</div>
      <div id="eval-out" class="eval-out"></div>
    </div>
  </div>
</div>

/* {{c_css_reset}} */
* { box-sizing: border-box; margin: 0; padding: 0; }
body { font-family: system-ui, sans-serif; color: #222; background: transparent; }
.demo-wrap { padding: .6rem; }
.input-label { display: block; font-size: .85rem; color: #555; margin-bottom: .3rem; }
.input-row { display: flex; gap: .4rem; }
input[type=text] {
  flex: 1; padding: .4rem .6rem; border: 1px solid #b0b8c1;
  border-radius: 7px; font: 15px ui-monospace, monospace; outline: none;
}
input[type=text]:focus { border-color: #3b7dd8; box-shadow: 0 0 0 2px #3b7dd840; }
button {
  padding: .4rem .9rem; border: none; border-radius: 7px;
  background: #1d3557; color: #fff; font: 600 14px system-ui, sans-serif;
  cursor: pointer; white-space: nowrap;
}
button:hover { background: #26487a; }
.error-msg { margin-top: .4rem; color: #c92f3c; font-size: .88rem; }
.panels { display: flex; gap: .6rem; margin-top: .6rem; flex-wrap: wrap; }
.panel { flex: 1 1 260px; border: 1px solid #dde3ea; border-radius: 8px; overflow: hidden; }
.panel-title {
  background: #f0f4f8; padding: .3rem .6rem; font-size: .8rem;
  font-weight: 600; color: #3a4a5a; border-bottom: 1px solid #dde3ea;
  text-transform: uppercase; letter-spacing: .04em;
}
/* {{c_css_svg}} */
svg { display: block; }
.node-circle { fill: #1d3557; }
.node-circle.leaf { fill: #e8eef3; stroke: #1d3557; stroke-width: 1.4; }
.node-label { font: 700 13px ui-monospace, monospace; fill: #fff; text-anchor: middle; dominant-baseline: central; }
.node-label.leaf { fill: #1d3557; }
.tree-edge { stroke: #aab4c0; stroke-width: 1.5; fill: none; }
/* {{c_css_eval}} */
.eval-out { padding: .5rem .7rem; font-size: .9rem; line-height: 1.7; }
.eval-step { display: flex; align-items: baseline; gap: .4rem; border-bottom: 1px solid #eef0f3; padding: .15rem 0; }
.eval-step:last-child { border-bottom: none; }
.eval-op { font: 700 13px ui-monospace, monospace; color: #1d3557; min-width: 28px; }
.eval-arrow { color: #aab4c0; }
.eval-result { font: 700 14px ui-monospace, monospace; color: #0a7d33; }
.eval-total { margin-top: .4rem; padding-top: .3rem; border-top: 2px solid #dde3ea;
              font-weight: 700; font-size: 1.05rem; }

// Code not found

Notice what the tree makes obvious. Operator precedence is no longer a rule you apply — it is already encoded in the structure: * sits above + when it binds tighter, and parentheses simply change which node becomes a parent. Evaluation is then a single recursive walk: to compute a node, compute its children first, then apply the operator. The tree turns a rule-laden grammar into a uniform algorithm.

Building an AST sounds hard, but the theory behind it is surprisingly clean.

• Tokenizing (splitting text into tokens like NUMBER, PLUS, LPAREN) is a simple scan — $O(n)$ in the length of the source.
• Parsing (turning tokens into an AST) is also $O(n)$ for the grammars used by real languages — LL and LR parsers process each token a constant number of times.
• The tree itself has at most $O(n)$ nodes, one per token that survives into the abstract representation.

So building the AST is fast. The hard questions come next. Type checking can require unification across the whole tree. Optimization over the AST corresponds to program transformation, and deciding whether two programs compute the same function is undecidable in general — a direct consequence of the halting problem.

Even within a fixed language, subtle questions like "is this variable ever used?" or "can this branch ever execute?" are instances of reachability or liveness analysis, which in full generality sit at or above the complexity of P vs NP. The AST is where all those harder problems begin — it is the simplest representation rich enough to ask them.

Any tool that needs to understand code rather than just store it will build some form of AST:

• Compilers and interpreters: the AST is the handoff point between the front end (parsing) and the back end (optimization and code generation). Languages like Python, Java, and Rust all expose their ASTs to library users.
• Linters and static analyzers: checking for unused variables, unreachable code, or security vulnerabilities means walking the tree and looking for specific patterns.
• IDEs: auto-complete, refactoring ("rename this variable everywhere"), and go-to-definition all depend on a live AST updated as you type.
• Transpilers: Babel transforms modern JavaScript to older JavaScript by rewriting one AST into another; TypeScript does the same for its type annotations.
• Code formatters: Prettier and Black parse to an AST, then pretty-print from the AST — ensuring format is independent of the original whitespace.

The AST is also the foundation of tree-sitter, the incremental parsing library embedded in Neovim, GitHub, and countless editors. Wherever a tool needs structured access to source code, the abstract syntax tree is the agreed-upon interface.

The abstract syntax tree is a small idea with enormous reach. Take source code — a flat, human-readable string full of punctuation that only matters to readers — strip away everything that was only there for legibility, and what remains is a tree whose shape encodes meaning directly. Operator precedence, scope, nesting: all of it lives in the parent–child relationships of the tree.

From that tree, a compiler can type-check, optimize, and generate code. A linter can spot bad patterns. An IDE can rename every occurrence of a variable in one shot. A formatter can reprint the code with perfect indentation regardless of how it arrived.

It is a good reminder that the right data structure does not just store information — it makes the right operations obvious. For code, that structure is the abstract syntax tree, and it sits quietly at the center of almost every tool you use to write software.