The abstract syntax tree

An abstract syntax tree is the nested, typed picture of a program that a parser hands back: every construct in the code becomes a node, and the way nodes contain other nodes mirrors the way the code contains its own parts. It is the shape of the program’s meaning, lifted out of the flat text.

From a line of text to a tree

We have seen that parsing reads flat text against a grammar and rebuilds structure. That recovered structure is a tree, and when it represents a program we call it an abstract syntax tree, usually shortened to AST. The word tree is literal. Like a family tree or the folders on your computer, it is a shape where one thing branches into several things beneath it, each of which can branch again, down as far as the code goes.

The best way to feel it is to build one from a real, tiny snippet. Here is a single line:

total = price + tax * 2

As characters this is just a row of symbols. As an AST it has a definite shape, which we can write out by indentation, where each indented item sits inside the one above it:

Assignment
  target: Name "total"
  value: Add
    left: Name "price"
    right: Multiply
      left: Name "tax"
      right: Number 2

Read the tree from the top. The whole line is an assignment, one kind of node. An assignment has two parts, a target and a value. The target is a name, total. The value is not a simple thing; it is itself an addition. The addition has a left side, the name price, and a right side, which is again not simple: it is a multiplication of the name tax by the number 2. Because multiply sits inside add, the tree records that the multiplication happens first, exactly as the arithmetic grammar intended. The meaning is baked into the shape.

Nodes and children

Every item in that tree is a node. A node has a type, which says what kind of construct it is: an assignment, an addition, a name, a number. A node also has children, which are the nodes nested directly inside it. The Add node has two children, its left and its right. A Name node has none; it is a leaf, the end of a branch, holding just its text. This is the whole vocabulary of a tree: nodes, their types, and their children. Everything about a program’s structure is expressed in those terms.

The types are what make an AST so much more useful than raw text. Text search knows only characters. The AST knows that this node is a function definition and that one is a call, that this is a name being assigned and that is a name being read. A name that is defined and a name that is used may look identical in the text, the same handful of letters. In the tree they are different kinds of node in different positions, and that difference is precisely what lets a tool tell a definition from a use without guessing.

Alongside its type and its children, a node usually carries two more things worth naming. The first is the small pieces of information particular to that node, sometimes called its attributes: the actual text of a name, the digits of a number, the operator that an operation uses. Our Number node holds the value 2; our Name nodes hold their spellings. The second is the node’s position, the exact span of the original file it came from, recorded as a start and an end. That position is what lets a tool trace any node in the tree back to the precise line and column it lives on, which is how an editor can underline the right characters or a report can point you at the right place. The tree is not a vague summary of the code. Every node remembers where it came from.

It also helps to see that the tree has exactly one node at the very top, called the root, from which everything else descends. For a whole file the root is usually a node meaning the file or module itself, and its children are the top-level things in the file: its imports, its functions, its classes. Each of those branches into its own contents, and so on down. A single connected tree, one root, no loose pieces, is the shape you get for every file. That single-rooted wholeness is part of why a tree is such a comfortable thing to work with: there is always one place to start and one path to every node.

Abstract versus concrete

The word abstract in the name is doing real work, and it is best understood by contrast. When a parser first matches the grammar, it can produce a very literal record of everything in the text, including the punctuation and spacing that were needed to read it but carry no meaning of their own. That literal record is called a concrete syntax tree, or parse tree. It keeps every parenthesis, every semicolon, every comma, because those tokens were part of matching the rules.

Consider (price + tax). In a concrete tree the two parentheses are their own nodes, faithfully recorded. But once the structure is known, the parentheses have done their job. They existed only to tell the parser that price and tax group together, and the tree already shows that grouping by putting them under the same addition node. So the abstract syntax tree drops them. It keeps what the program means and discards the marks that only helped recover the meaning.

That is the whole distinction. The concrete tree is faithful to the text down to the last comma. The abstract tree is faithful to the meaning and throws away the scaffolding. For understanding a program, the abstract tree is what you want, because you care that tax and 2 are multiplied, not that there did or did not happen to be parentheses around them in the source.

The abstract syntax tree keeps what a program means and drops the punctuation that only helped recover the meaning. It is the structure, with the scaffolding removed.

Why the tree is the right thing to walk

Once code is an AST, questions that were hopeless over raw text become clean and exact. Suppose you want every place a function is called. Over text you would search for the name and get a mess of comments, unrelated matches, and partial words. Over the AST you look for nodes of the type call, and for each one you read its child that names the function being called. You are no longer matching characters. You are asking the structure a structural question, and the structure answers exactly.

The same holds for almost any fact worth knowing about a file. Which functions does this file define? Find the nodes of type function definition. What does this function call? Look at the call nodes inside its body. What does this file import from elsewhere? Find the import nodes. Each fact is a kind of node in a known place, and gathering the facts becomes a matter of visiting the right nodes. The tree turns fuzzy questions about text into precise questions about structure, and that is why it is the substrate every serious code tool builds on.

There is a second reason the tree, and not the text, is the right thing to work on: containment answers the question of scope, of where something lives. When you find a call node, the chain of nodes above it tells you the call sits inside this function, which sits inside this class, which sits inside this file. You did not have to search for that context. It is simply the path from the call back up to the root, read off the tree for free. Over raw text you would have to reconstruct that context by counting braces or watching indentation, fragile work that breaks on the first unusual formatting. In the tree, being inside something is the same as being beneath it, and the shape hands you the answer.

This is also why the tree survives reformatting. Take the assignment we walked through and spread it across several lines, add spaces, wrap parts in extra parentheses. The characters change a great deal. The abstract syntax tree does not, because none of those cosmetic edits change what the code means. Two files that read differently to a text search but mean the same thing produce the same tree, which is exactly the property you want from a representation of meaning. It ignores the surface and keeps the substance.

How you traverse a tree

Reading a tree is called traversal, and the idea is simple even though it powers a great deal. You visit a node, do whatever you came to do, and then visit each of its children the same way, and each of theirs, until you have touched every node in the tree. Because a node’s children may have children of their own, the visiting procedure calls itself on each child, and that self-reference is what lets one short routine walk a tree of any depth.

Picture walking the earlier assignment tree to collect every name it mentions. The steps look like this:

1. Visit the Assignment node. It is not a name, so record nothing, but visit its children.
2. Visit the target, Name “total”. It is a name, so record total. It has no children.
3. Visit the value, an Add node. Not a name, so visit its children.
4. Visit the left, Name “price”. Record price.
5. Visit the right, a Multiply node. Not a name, so visit its children.
6. Visit the left, Name “tax”. Record tax. Visit the right, Number 2, which is not a name.

The walk ends having found total, price, and tax, and nothing spurious, no words from comments and no accidental matches. That is the flavor of nearly every fact-gathering job on code: a traversal that visits nodes, checks each one’s type, and collects what it is looking for. Once you can walk the tree, you can extract almost anything the tree contains.

What one file’s tree can and cannot tell you

It is important to be honest about the reach of a single file’s AST, because it is powerful but not omniscient. From one file’s tree you can learn, with certainty, everything the file states about itself. You can list the functions it defines, the names it uses, the calls it makes by name, the things it imports, and how all of that nests. That is a great deal, and it is exact rather than guessed.

What one file’s tree cannot tell you is anything that lives outside the file. When the tree shows a call to a function named tax, it knows the call is to something called tax. It does not know which tax, because the actual definition may sit in another file the tree has never seen. The tree of the file that reads a database column cannot know which file created that column. The tree of a service that sends a request over the network cannot know which handler in another service receives it, because from the sender’s point of view that connection is just a string. A single tree sees its own file perfectly and the rest of the world not at all.

This is the natural boundary of the AST, and it points straight at the work that follows. Resolving a call to the exact function it lands on, and linking the many trees of many files into one connected picture, is a job that starts from these trees but reaches beyond any one of them. Before that, though, comes the practical matter of producing good trees for every file in a real project, including the many files that are broken while you edit them. The technology built to do that, quickly and forgivingly and across many languages, is called tree-sitter, and it is the next idea in this hub.