1 + 2 * 3 is 6 tokens sitting in a row. The answer is 7, not 9, which
means something has to know that * happens before + even
though + comes first in the source. A flat list cannot hold that fact.
A tree can.
A syntax tree is a small structure where each piece of the expression is a node, and a
node can point at other nodes underneath it. 1 + 2 * 3 becomes a
+ node with two children: the number 1 on the left, and a
* node on the right holding 2 and 3. Nothing
about the order tokens appeared in the source survives into the tree. What survives is
which operations are grouped with which. That grouping is precedence, made physical as
shape instead of left-to-right position.
Once you have that shape, evaluating it is trivial: a number means itself, and an
operator node means "combine my children the way I say". You do not need to remember
any rule about * binding tighter than + at evaluation time,
because the tree already encodes the decision. All the hard thinking happens once,
while building the tree. That is the whole reason a parser exists instead of just
evaluating tokens as they arrive.
Checkpoint
Nothing to build yet. Confirm your checkout still passes chapter one's lexer tests before you add a single line here.
izvor has exactly three kinds of node: a number, a unary operator with one operand, and
a binary operator with two. Node is one struct that can hold any of the
three, and a tag that says which one it currently is.
src/ast.h · the enum and the struct
typedef enum {Three cases, no more. Adding a fourth kind of expression later means adding a fourth name here, and the compiler will then point at every switch on NodeType that forgot about it.
NODE_NUMBER, NODE_UNARY, NODE_BINARY} NodeType; typedef struct Node Node; struct Node {This is a tagged union. type is the tag. The union below it is one block of memory that can hold a long, or the unary shape, or the binary shape, but never more than one at a time, and C will not stop you from reading the wrong one.
NodeType type; union {A union's size is the size of its biggest member, because every member overlaps the same bytes. A struct instead would add all three sizes together for no reason, since a node is never a number and a binary op at once.
long number; struct { TokenType op; Node *operand; } unary; struct { TokenType op; Node *left; Node *right; } binary; } as;Called as because reading code out loud that way makes sense: node->as.number reads as "node, as a number". node->as.binary.left reads as "node, as a binary, its left side".
};
The comment at the top of ast.h says it plainly: always check node->type
before reading anything under node->as. If a node is tagged
NODE_NUMBER and you read node->as.binary.left anyway,
the compiler will not stop you. You will get whatever bytes happen to be sitting
where left would be, reinterpreted as a pointer, and then a crash or
worse somewhere far from this line. The tag is the only thing standing between a
union and undefined behavior. Nothing enforces checking it except you.
Checkpoint
Nothing calls any of this yet, so this should still build clean off the back of chapter one.
Every node lives on the heap, because a tree of fixed-size local variables cannot
have a size decided at parse time. new_node does the allocation once;
the three public constructors each ask it for a node already tagged, then fill in
the payload.
src/ast.c · new_node, ast_number, ast_unary, ast_binary
static Node *new_node(NodeType type) {static keeps this name private to ast.c. Nothing outside this file is allowed to build a raw, unfilled node, which is exactly why the three public functions below exist: they are the only door in.
Node *node = malloc(sizeof(Node)); if (node == NULL) {malloc can fail. It returns NULL when the system has no memory left to give you, and this check is the only thing standing between that and a crash the moment something tries to write through the pointer.
return NULL; } node->type = type; return node;}Node *ast_number(long value) { Node *node = new_node(NODE_NUMBER); if (node == NULL) { return NULL; } node->as.number = value;The failure check happens before this line, never after. Writing to node->as.number when node is NULL is exactly the bug the check exists to prevent, so the order is not a style choice.
return node;}Node *ast_unary(TokenType op, Node *operand) { Node *node = new_node(NODE_UNARY); if (node == NULL) { return NULL; } node->as.unary.op = op; node->as.unary.operand = operand; return node;} Node *ast_binary(TokenType op, Node *left, Node *right) {Same shape again: allocate, check, stamp the payload. Three functions that each do the same three things is not repetition worth fixing. It is three tiny, obviously correct functions instead of one function with a branch, and each one reads as exactly what it does.
Node *node = new_node(NODE_BINARY); if (node == NULL) { return NULL; } node->as.binary.op = op; node->as.binary.left = left; node->as.binary.right = right; return node;}
Notice what none of these three do: none of them build a whole expression. ast_binary
takes a left tree and a right tree that already exist and joins them under one operator.
The parser is the thing that decides which trees go where. The constructors just do the
allocation and the bookkeeping honestly, one node at a time.
Checkpoint
Expect unused-function warnings on all three constructors. Nothing calls them until the parser exists, later in this chapter.
ast_free is the one function in ast.c that has to visit the whole tree,
because freeing a node is only safe once nothing points at its children anymore.
src/ast.c · ast_free
void ast_free(Node *node) {This takes a plain Node *, not a pointer to a pointer. It frees the memory node points to; it does not and cannot set the caller's variable back to NULL. That is on the caller.
if (node == NULL) {The base case. Every recursive function needs one place where it stops instead of calling itself again, and "there is nothing here" is the natural place for a tree walk to stop.
return; } switch (node->type) {The tag decides which fields it is even safe to read, same as everywhere else a Node gets touched. A number has no children, so its case does nothing extra.
case NODE_NUMBER: break; case NODE_UNARY:Free the one child before falling through to the shared free(node) at the bottom.
ast_free(node->as.unary.operand); break; case NODE_BINARY:Both children, left then right. The order between the two does not matter, since neither points at the other. What matters is that both happen before this node frees itself.
ast_free(node->as.binary.left); ast_free(node->as.binary.right); break; } free(node);This line runs last, after the switch, for every case. Free a node before its children and you have just handed the recursive call below it a pointer into memory that free already reclaimed. Reading through it after that is undefined behavior, and it will not always crash where you can see it.
}
This is post-order traversal, though you do not need that name to write it. You only
need one rule: a parent cannot be freed until it has already asked each of its children
to free themselves. The recursion handles the rest, because each call to
ast_free obeys that same rule on whatever subtree it was handed.
Checkpoint
Still unused. The parser is next, and it is the thing that finally builds a tree worth freeing.
The lexer from chapter one only moves forward: call lexer_next and the
previous token is gone. The parser needs to look at a token, decide what to do, and
still have that same token available to actually consume. That gap is Parser.
src/parser.h · the Parser struct
typedef struct {The comment above this in the real file says it outright: a lexer plus one token of lookahead. The lexer has no rewind, so the parser holds the token it has fetched but not yet consumed.
Lexer lexer; Token current;One token of lookahead, no more. Every decision the parser makes, "is this a number, a minus, an open paren", is a question about current. You never need to see two tokens ahead to parse arithmetic, so the struct does not carry more than it needs.
} Parser;
Why is lookahead needed at all, rather than just calling lexer_next and
acting on whatever comes back? Because deciding what to parse next almost always means
asking "what token is sitting right in front of me" without committing to eating it
yet. parse_factor, which you will write in step 8, has to check whether the
next token is a number, an open paren, or a minus sign before it knows which branch to
take. If asking the question consumed the token, you would have to somehow put it back
to then act on it, and the lexer this parser sits on top of cannot do that. Holding one
token in current is the fix: asking and consuming become two separate
operations.
Checkpoint
Still just a struct definition. Nothing runs differently yet.
Everything else in parser.c is built out of these four. Learn them once and every later line reads as some combination of "look at current" and "move current forward".
src/parser.c · parser_init, parser_advance, parser_check, parser_match
void parser_init(Parser *p, const char *src) {Sets up the lexer, then immediately calls parser_advance. Without that second call current would start out as garbage, because nothing has ever asked the lexer for a token yet. This is what the comment on parser_init in parser.h means by "advance once so current is loaded before anyone reads it".
lexer_init(&p->lexer, src); parser_advance(p);} void parser_advance(Parser *p) {The entire function is one line. It asks the lexer for the next token and overwrites current with it. The token that used to be in current is gone the moment this runs, which is exactly why nothing calls this until it is done looking at the old value.
p->current = lexer_next(&p->lexer);} bool parser_check(const Parser *p, TokenType type) {A pure question. const Parser *p is a promise that this function will not change the parser, and the body keeps that promise: it reads p->current.type and returns, nothing else. Calling this as many times in a row as you like changes nothing.
return p->current.type == type;} bool parser_match(Parser *p, TokenType type) {The only one of the four that can change something, and it decides whether to based on parser_check. Ask a yes-or-no question with check, act on the answer with match. Nearly every line in the grammar below is one call to one of these two.
if (!parser_check(p, type)) return false; parser_advance(p); return true;}
Look at what parser_match does on a "no". It calls parser_check,
gets false back, and returns false immediately. current
is untouched. That matters a lot in step 8, where the parser tries a number, then tries
an open paren, then tries a minus, one after another. Each failed parser_match
has to leave the token exactly where it found it, or the next check down the chain would
be asking about the wrong token.
Checkpoint
tests/test_parser_1.c already exercises exactly these four functions by
hand against the input 1+2. Run it directly and read it once, since step
10 comes back to it.
Before any more code, the shape of the whole parser, written out as three rules. This is what the comments directly above each function in parser.c already say.
expression -> term (("+" | "-") term)*An expression is a term, then zero or more of a plus or minus followed by another term.
term -> factor (("*" | "/") factor)*A term is a factor, then zero or more of a star or slash followed by another factor.
factor -> NUMBER | "(" expression ")" | "-" factorA factor is a number, or a parenthesized expression, or a minus sign followed by another factor.
Read from the bottom up, this is precedence expressed as nesting rather than as a table
of numbers. expression is built out of terms, and
term is built out of factors. To reach a bare number you have
to pass through both levels. That means a * can never end up as a direct
child of a + without a term boundary between them, and a
term boundary is exactly where the multiply-and-divide loop lives. The
grammar does not mention precedence as a concept anywhere. The nesting order is the
precedence.
izvor turns each of those three rules into one function: parse_expression,
parse_term, parse_factor. This is recursive descent, and the
name describes exactly what you see in the code: functions calling functions in a
pattern that mirrors the grammar rules, descending from the loosest-binding operators
at the top to the tightest at the bottom. One function per rule is not a style choice
either. It means that if izvor ever grows a fourth precedence level, say a comparison
operator that binds looser than +, you add one function and slot it into
the chain. You do not touch the other three, because each one only knows about the
level directly below it.
Checkpoint
Everything else calls down into this eventually. It handles the three things a factor can be, in the same order the grammar rule lists them.
src/parser.c · parse_factor
/* factor -> NUMBER | "(" expression ")" | "-" factor */static Node *parse_factor(Parser *p) { if (parser_check(p, TOK_NUMBER)) {parser_check, not parser_match, because the branch still needs to read p->current.value on the next line before the token is gone.
long value = p->current.value; parser_advance(p); return ast_number(value); } if (parser_match(p, TOK_LPAREN)) {Here match is right, because there is nothing left to read off an open paren token once you know it is one. Consuming it and moving on is the whole job.
Node *inner = parse_expression(p);This is the recursive part of recursive descent, made literal: parsing what is inside the parentheses means calling all the way back up to parse_expression, the top of the grammar, not back into parse_factor itself. That single call is what makes (2 + 3) * 4 work at all.
if (inner == NULL) return NULL; if (!parser_match(p, TOK_RPAREN)) {The open paren was matched already, so if a close paren does not show up here the input is broken: something like (1+2 with no end. This is where that gets caught.
error_at(p, "expected ')'"); ast_free(inner);The parse failed, so the tree built so far for the inside of the parens is never going to be returned to anyone who could free it later. Free it right here, or it leaks.
return NULL; } return inner; } if (parser_match(p, TOK_MINUS)) {Unary minus. Notice the recursive call two lines down is to parse_factor, itself, not parse_expression. That is deliberate: it is what makes --7 parse as two nested unary nodes instead of forcing - to only ever appear once.
Node *operand = parse_factor(p); if (operand == NULL) return NULL; return ast_unary(TOK_MINUS, operand); } error_at(p, "expected expression");All three branches failed to match anything at all. Whatever token current holds now is not the start of anything this grammar knows how to parse, so this is where an input like *3 gets caught.
return NULL;}
Every path through this function returns either a real Node * or
NULL. Nothing in parser.c ever ignores that return value without checking
it first, because a NULL means the parse already failed somewhere below,
and an error has already been printed for it. Passing a NULL further up
without checking would just crash later, further from the real cause.
Checkpoint
parse_expression is only forward-declared so far, referenced but not yet defined below. That warning clears once step 9 writes it.
These two functions are almost identical on purpose. Once you understand the shape of one, you already understand the other.
src/parser.c · parse_term, parse_expression
/* term -> factor (("*" | "/") factor)* */static Node *parse_term(Parser *p) { Node *left = parse_factor(p);The first factor. Whatever this returns becomes the running left side of the loop below, and it starts out as the whole answer in case there is no operator to follow it.
if (left == NULL) return NULL; while (parser_check(p, TOK_STAR) || parser_check(p, TOK_SLASH)) {A while, not an if. That is what lets 2*3*4 chain as many multiplications as the source actually has, rather than stopping after the first one.
TokenType op = p->current.type; parser_advance(p); Node *right = parse_factor(p); if (right == NULL) {By this point left is a real tree that was already built. If the right side fails, that tree still needs freeing before returning, or it leaks. This is the same free-on-the-way-out rule as step 8's unmatched close paren.
ast_free(left); return NULL; } left = ast_binary(op, left, right);This is the line that produces left associativity. The new binary node's left child is the entire tree built so far, not just the previous single factor. Reassigning left to that new node is what lets the next lap of the loop nest the next operation one level deeper on the left side.
} return left;}
10 - 3 - 2 only has one correct reading in ordinary arithmetic: subtract
left to right, giving 5. If the parser nested the other way, 10-(3-2),
it would compute 9 instead. The loop in parse_term and
parse_expression produces the correct one because it always makes the
new node's left side the tree accumulated so far. After one lap on
10-3-2, left is the tree for 10-3. The second
lap wraps that whole tree as the left child of a new node with 2 on the
right: (10-3)-2. Building the new node the other way around, with the
fresh operand on the left, would silently flip every chained subtraction and division
in the language.
/* expression -> term (("+" | "-") term)* */static Node *parse_expression(Parser *p) { Node *left = parse_term(p); if (left == NULL) return NULL; while (parser_check(p, TOK_PLUS) || parser_check(p, TOK_MINUS)) {The only real difference from parse_term: this checks PLUS and MINUS, and it calls parse_term for its operands instead of parse_factor. That one substitution is the entire reason * binds tighter than + in this language.
TokenType op = p->current.type; parser_advance(p); Node *right = parse_term(p); if (right == NULL) { ast_free(left); return NULL; } left = ast_binary(op, left, right); } return left;}
Walk 2+3*4 through both loops to see precedence actually happen.
parse_expression calls parse_term for its first operand.
That call to parse_term reads 2, sees a + next
rather than a * or /, and returns immediately with just the
number 2. Back in parse_expression, the loop sees the +,
consumes it, and calls parse_term again for the right side. That second
call reads 3, then does see a *, and its own loop consumes
3 * 4 as one unit before returning. parse_expression never
had to know a multiplication happened. It just asked for "the next term" and got back
a tree with the multiplication already resolved inside it.
Checkpoint
That printed tree is precedence made visible. If it printed
(* (+ 1 2) 3) instead, the nesting would be backwards and step 9 would
not be finished.
parser_parse is the one function anything outside parser.c is meant to
call. It is four lines, and the last check in it is the one that catches trailing
garbage.
src/parser.c · parser_parse
Node *parser_parse(Parser *p) { Node *expr = parse_expression(p); if (expr == NULL) return NULL; if (!parser_check(p, TOK_EOF)) {parse_expression can succeed and still leave tokens sitting unread. Given 1 2, it happily parses 1 as a complete expression and stops, because nothing about 2 looks like a continuation of it. Without this check, izvor would silently accept 1 2 and just throw the 2 away.
error_at(p, "expected end of input"); ast_free(expr); return NULL; } return expr;}
tests/test_parser_1.c never calls parser_parse at all. It
drives the four helpers from step 6 by hand against "1+2", checking
current after every single call, right down to proving that calling
parser_advance once already sitting on EOF just leaves you on EOF. That
file exists to pin the primitives down in isolation, before trusting them inside a
bigger function.
tests/test_parser_2.c is the one that tests the tree shapes this whole
chapter built toward: 2+3*4 comes back as a + node whose right
child is a * node, 10-3-2 nests to the left, (2+3)*4
proves parentheses actually override precedence, and --7 proves unary
minus nests on itself. Then it flips to the failure side: "1+",
"(1+2", "1 2", "", "*3", and
"()" each have to come back NULL. That last group is what
actually exercises every error path you just wrote across steps 8, 9, and this one.
A parser that only gets tested on valid input has only proven half of itself.
Checkpoint
Both files passing means the constructors, the destructor, the four helpers, and all three grammar functions agree with each other end to end.