Parsing: From Tokens to a Tree

The lexer left us with a flat stream of tokens, but a program is not flat. A loop contains statements, a condition contains an expression, an expression contains smaller expressions. The parser's job is to read the token stream and recover that nesting as a tree. The result is called an abstract syntax tree, or AST, and it is the single most important data structure in this entire academy: compilers optimize it, interpreters walk it, and obfuscators rewrite it.

Think of how you understand the sentence "the dog that bit the mailman ran away". You do not process it word by word in isolation; you group it, so that "that bit the mailman" attaches to the dog, not to the running. Parsing code is exactly that grouping step. The tokens are the words, and the tree records which pieces belong inside which.

Grammar: the rules of assembly

A parser is not guessing. Every language ships with a grammar, a precise set of rules saying which token sequences are legal and how they nest. A rule might say: an if statement is the keyword if, then an expression, then a block of statements in braces. When the incoming tokens fit a rule, the parser builds a node for it; when they fit no rule, you get a syntax error. That is all a syntax error is, tokens that no grammar rule can accept.

This is why syntax errors are caught before your program runs a single statement. Parsing is a separate, earlier phase than execution. A file that does not parse never becomes a tree, and without a tree there is nothing to run, compile, or transform.

Precedence lives in the tree

Here is the idea that makes trees click. In the text 2 + 3 * 4, nothing visually marks that the multiplication happens first. In the tree, it is unmissable: the * node sits deeper, as a child of the + node, so it must be computed first to give + its right operand. Grouping that was invisible in the text becomes physical structure. Parentheses in source code are just instructions to the parser to build a different tree, and after parsing they disappear entirely; the tree shape is the grouping.

Explore a live AST

The explorer below parses the academy's teaching language as you type and redraws the tree. Click nodes to fold and unfold them. Find the arithmetic and check where the * node sits relative to +. Then wrap 2 + 3 in parentheses and watch the tree physically rearrange while the tokens barely change.

Why every serious tool wants the tree

• An interpreter walks the tree and does what each node says, in the order the structure dictates.
• A compiler walks the tree and emits instructions for each node, which is the next lesson.
• An optimizer rewrites the tree: it can replace a subtree that always computes 14 with the number 14.
• An obfuscator also rewrites the tree, then prints it back out as much uglier text with identical behaviour.

Notice what all four have in common: none of them work on your text. The formatting, the comments, even the parentheses are gone by this point. Tools work on structure, and the AST is the structure.

Two details practitioners care about. First, associativity: precedence alone does not decide 10 - 3 - 2. The grammar must also say that - groups left to right, producing (10 - 3) - 2 = 5, not 10 - (3 - 2) = 9. Second, ambiguity: a badly written grammar can allow two different trees for the same tokens, the classic example being which if an else attaches to when ifs nest without braces. Real languages resolve this with an explicit rule (else binds to the nearest if) or by requiring braces. Both details reinforce the same point: the tree, not the text, is the ground truth of what a program means, so the grammar must guarantee exactly one tree per valid input.

A note on the word abstract. A concrete syntax tree records everything, including punctuation like braces and parentheses. An AST drops anything that only existed to guide parsing and keeps pure structure. That is why two very differently formatted files can produce byte-identical ASTs, and why comparing ASTs is a far better way to check whether two programs are the same than comparing their text.

Try to break it

In the explorer above, delete a closing brace or an operand and read the error. The parser tells you the line where the token stream stopped matching any grammar rule. Being comfortable reading parse errors is a small skill that pays off for the rest of your programming life.

Parsing turns a flat token stream into a tree that captures nesting, grouping, and precedence. From here on, when you picture a program, picture the tree: it is what interpreters run, what compilers translate, and what every transformation in Level 4 rewrites.

Frequently asked questions