Introduction

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.

Parse an Expression

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.

<!-- Demo: parse an arithmetic expression into an AST and evaluate it -->
<div class="demo-wrap">
  <label class="input-label" for="expr">Expression</label>
  <div class="input-row">
    <input id="expr" type="text" placeholder="e.g. 3 * (4 + 5)" value="3 * (4 + 5)" autocomplete="off" spellcheck="false" />
    <button id="btn-parse" type="button">Parse & Evaluate</button>
  </div>
  <div id="error" class="error-msg" hidden></div>
  <div class="panels">
    <div class="panel">
      <div class="panel-title">AST</div>
      <svg id="tree-svg" width="100%" height="260"></svg>
    </div>
    <div class="panel">
      <div class="panel-title">Evaluation steps</div>
      <div id="eval-out" class="eval-out"></div>
    </div>
  </div>
</div>

/* Basic reset and layout */
* { 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;
}
/* SVG tree node styles */
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; }
/* Evaluation steps panel */
.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; }

/* AST demo: tokenize -> parse -> draw tree -> evaluate */
const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

/* Tokenizer: splits the source string into a flat list of tokens */
function tokenize(src) {
  const tokens = [];
  let i = 0;
  while (i < src.length) {
    if (/\s/.test(src[i])) { i++; continue; }
    if (/\d/.test(src[i])) {
      let num = '';
      while (i < src.length && /[\d.]/.test(src[i])) num += src[i++];
      tokens.push({ type: 'NUM', val: parseFloat(num) });
    } else if ('+-*/()'.includes(src[i])) {
      tokens.push({ type: src[i], val: src[i] });
      i++;
    } else {
      throw new Error(i18nFmt('Unexpected character: %ch%', { ch: src[i] }));
    }
  }
  tokens.push({ type: 'EOF' });
  return tokens;
}

/* Recursive-descent parser (LL(1)): each grammar rule is one function */
/* Grammar: expr = addSub; addSub = mulDiv (('+' | '-') mulDiv)*; mulDiv = unary (('*' | '/') unary)*; unary = '-' unary | primary; primary = NUM | '(' expr ')' */
let pos, toks;
function peek() { return toks[pos]; }
function consume(type) {
  const t = toks[pos];
  if (type && t.type !== type) throw new Error(i18nFmt('Expected %exp%, got %got%', { exp: type, got: t.type }));
  pos++;
  return t;
}
/* Entry point for expression parsing */
function parseExpr() { return parseAddSub(); }
function parseAddSub() {
  let node = parseMulDiv();
  while (peek().type === '+' || peek().type === '-') {
    const op = consume().val;
    const right = parseMulDiv();
    node = { op, left: node, right };
  }
  return node;
}
function parseMulDiv() {
  let node = parseUnary();
  while (peek().type === '*' || peek().type === '/') {
    const op = consume().val;
    const right = parseUnary();
    node = { op, left: node, right };
  }
  return node;
}
function parseUnary() {
  if (peek().type === '-') { consume('-'); const n = parseUnary(); return { op: 'neg', left: n }; }
  return parsePrimary();
}
function parsePrimary() {
  if (peek().type === 'NUM') { const t = consume('NUM'); return { val: t.val }; }
  if (peek().type === '(') {
    consume('(');
    const node = parseExpr();
    if (peek().type !== ')') throw new Error('Missing closing parenthesis');
    consume(')');
    return node;
  }
  throw new Error(i18nFmt('Unexpected token: %tok%', { tok: peek().type }));
}
function parse(src) {
  toks = tokenize(src);
  pos = 0;
  const tree = parseExpr();
  if (peek().type !== 'EOF') throw new Error('Unexpected tokens after expression');
  return tree;
}

/* Post-order tree walk: evaluate leaves first, then operators */
const steps = [];
function evaluate(node) {
  if ('val' in node) return node.val;
  if (node.op === 'neg') {
    const v = evaluate(node.left);
    const r = -v;
    steps.push({ op: 'neg', args: [v], result: r });
    return r;
  }
  const l = evaluate(node.left);
  const r = evaluate(node.right);
  let result;
  if (node.op === '+') result = l + r;
  else if (node.op === '-') result = l - r;
  else if (node.op === '*') result = l * r;
  else if (node.op === '/') {
    if (r === 0) throw new Error('Division by zero');
    result = l / r;
  }
  steps.push({ op: node.op, args: [l, r], result });
  return result;
}

/* Recursive layout: assign x in [0,1] and y = depth */
function layout(node, depth, bounds) {
  /* Subdivide horizontal range between left and right subtrees */
  if (!node.left && !node.right) {
    node._x = (bounds[0] + bounds[1]) / 2;
    node._y = depth;
    return;
  }
  const mid = (bounds[0] + bounds[1]) / 2;
  if (node.left && !node.right) {
    layout(node.left, depth + 1, bounds);
    node._x = mid;
  } else {
    layout(node.left, depth + 1, [bounds[0], mid]);
    layout(node.right, depth + 1, [mid, bounds[1]]);
    node._x = (node.left._x + node.right._x) / 2;
  }
  node._y = depth;
}

/* Draw the tree onto the SVG element */
const SVG_NS = 'http://www.w3.org/2000/svg';
function drawTree(node, svg) {
  svg.innerHTML = '';
  const W = svg.clientWidth || 400;
  const H = 240;
  const PAD = 24;
  /* Compute max depth first so we can space levels evenly */
  let maxDepth = 0;
  function mdepth(n, d) { if (d > maxDepth) maxDepth = d; if (n.left) mdepth(n.left, d+1); if (n.right) mdepth(n.right, d+1); }
  mdepth(node, 0);
  layout(node, 0, [0, 1]);
  const R = 18;
  const yStep = maxDepth > 0 ? (H - PAD * 2 - R * 2) / maxDepth : 0;
  function px(n) { return PAD + n._x * (W - PAD * 2); }
  function py(n) { return PAD + R + n._y * yStep; }
  /* Draw edges before nodes so nodes render on top */
  function drawEdges(n) {
    if (n.left) {
      const line = document.createElementNS(SVG_NS, 'line');
      line.setAttribute('x1', px(n)); line.setAttribute('y1', py(n));
      line.setAttribute('x2', px(n.left)); line.setAttribute('y2', py(n.left));
      line.setAttribute('class', 'tree-edge');
      svg.appendChild(line);
      drawEdges(n.left);
    }
    if (n.right) {
      const line = document.createElementNS(SVG_NS, 'line');
      line.setAttribute('x1', px(n)); line.setAttribute('y1', py(n));
      line.setAttribute('x2', px(n.right)); line.setAttribute('y2', py(n.right));
      line.setAttribute('class', 'tree-edge');
      svg.appendChild(line);
      drawEdges(n.right);
    }
  }
  drawEdges(node);
  /* Draw circle + label for every node */
  function drawNodes(n) {
    const isLeaf = !n.left && !n.right;
    const g = document.createElementNS(SVG_NS, 'g');
    const circle = document.createElementNS(SVG_NS, 'circle');
    circle.setAttribute('cx', px(n)); circle.setAttribute('cy', py(n)); circle.setAttribute('r', R);
    circle.setAttribute('class', isLeaf ? 'node-circle leaf' : 'node-circle');
    g.appendChild(circle);
    const text = document.createElementNS(SVG_NS, 'text');
    text.setAttribute('x', px(n)); text.setAttribute('y', py(n));
    text.setAttribute('class', isLeaf ? 'node-label leaf' : 'node-label');
    text.textContent = 'val' in n ? String(n.val) : (n.op === 'neg' ? '-' : n.op);
    g.appendChild(text);
    svg.appendChild(g);
    if (n.left) drawNodes(n.left);
    if (n.right) drawNodes(n.right);
  }
  drawNodes(node);
}

/* Render the list of evaluation steps */
function renderEval(evalSteps, total) {
  const out = document.getElementById('eval-out');
  out.innerHTML = '';
  if (evalSteps.length === 0) {
    /* Single-value expression (just a number), no steps */
    const d = document.createElement('div');
    d.className = 'eval-step';
    d.innerHTML = '<span class="eval-result">' + total + '</span>';
    out.appendChild(d);
    return;
  }
  evalSteps.forEach(step => {
    const d = document.createElement('div');
    d.className = 'eval-step';
    let expr = '';
    if (step.op === 'neg') expr = '-' + step.args[0];
    else expr = step.args[0] + ' ' + step.op + ' ' + step.args[1];
    d.innerHTML =
      '<span class="eval-op">' + expr + '</span>' +
      '<span class="eval-arrow">&#8594;</span>' +
      '<span class="eval-result">' + step.result + '</span>';
    out.appendChild(d);
  });
  const tot = document.createElement('div');
  tot.className = 'eval-step eval-total';
  tot.innerHTML = i18nFmt('= %val%', { val: total });
  out.appendChild(tot);
}

/* Wire the button and Enter key to the main run() function */
function run() {
  const src = document.getElementById('expr').value.trim();
  const errDiv = document.getElementById('error');
  errDiv.hidden = true;
  try {
    const tree = parse(src);
    steps.length = 0;
    const total = evaluate(tree);
    drawTree(tree, document.getElementById('tree-svg'));
    renderEval(steps, total);
  } catch (e) {
    errDiv.textContent = e.message;
    errDiv.hidden = false;
  }
}

document.getElementById('btn-parse').addEventListener('click', run);
document.getElementById('expr').addEventListener('keydown', e => { if (e.key === 'Enter') run(); });
run();
Result
Console

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.

The Real Complexity

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)O(n) in the length of the source.
  • Parsing (turning tokens into an AST) is also O(n)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)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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/abstract-syntax-trees/Content licensed under CC BY-NC 4.0.