Nestor G Pestelos Jr · ELI5

Abstract Syntax Trees

Code is a line. Meaning is a tree.

The computer keeps a family tree of who belongs to whom.

Same idea. Two shapes.

the line you type

total = price * qty

the tree the computer keeps

= total * price qty

Leaves are names and numbers. Joints are the work.

Why two shapes
  • The line is what you typed.
  • The tree is the structure the computer keeps.
  • The equals sign sits at the top. total hangs on the left. price * qty hangs on the right.

The tree remembers what happens first.

1 + 2 * 3

this tree
+ 1 * 2 3

Multiply lives under plus, so the answer is 7.

not left to right
* + 3 1 2

That tree would mean (1 + 2) * 3, which is 9.

Why the answer is 7
  • Multiply happens before add. That rule is called precedence.
  • The tree stores the rule as shape: * sits under +.
  • Left to right would mean (1 + 2) * 3, which is 9. The language does not read that way.

Now change the line.

Type. The tree has to follow.

tokens

+ 1 * 2 3

The tree says 7.

What you can change
  • This tiny language is names, numbers, + - * /, parentheses, and =.
  • School order puts multiply under plus, so 1 + 2 * 3 is 7.
  • Left to right ignores that rule. The same line becomes 9.
  • Parentheses drop out of the tree. That drop is the abstract in AST.

Three steps. Then you have an AST.

1 · letters

price * qty

2 · tokens

price * qty

3 · tree

* price qty

Tokens are the words; the tree hangs each word on a parent.

What each step is
  • Letters are characters in a file. They have no structure yet.
  • A lexer splits the characters into tokens: names, numbers, signs.
  • A parser hangs each token on a parent. That hanging is the tree.

After the tree exists, tools walk it.

* price qty 1 2 3

A compiler, a linter, and a rewriter all visit the same nodes in order.

What a walk does
  • The numbers on the picture are one visit order: the parent, then the left child, then the right child.
  • A tool can pick another order. Evaluation often does the children first, then the operator.
  • Compiler, linter, and rewriter share the tree. They differ in the work they do at each node.

Keep the family. Drop the commas.

(price * qty)

price * qty

* price qty

The dropped extra is the abstract in Abstract Syntax Tree.

What “abstract” drops
  • Concrete syntax keeps every mark you typed, including parentheses.
  • Abstract syntax keeps the family: who is whose parent.
  • (price * qty) and price * qty are the same tree. The parens were only a grouping hint.

Back to top