Parsing Expressions
Build a parse tree.
Parsing Expressions is a free C Academy lesson on CoddyKit. This is lesson 2 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the C Academy learning path, and your progress syncs across the web and the CoddyKit app. The C Academy course includes 4 lessons in total.
From Tokens to Tree
Parsing turns a flat token stream into a structured Abstract Syntax Tree (AST). The tree encodes precedence and grouping that the raw tokens only imply.
For 3 + 4 * 2, the AST nests the multiplication under the addition, so it evaluates to 11, not 14.
AST Node Shape
Each node is either a number leaf or a binary operation with two children. A tagged struct with a union keeps memory compact.
The operator character distinguishes +, -, *, and / at runtime.
typedef struct Node {
enum { N_NUM, N_BINOP } kind;
union {
int value; /* N_NUM */
struct { /* N_BINOP */
char op;
struct Node *left, *right;
} bin;
};
} Node;Allocating Nodes
Two small constructors heap-allocate nodes. Building the tree bottom-up means leaves are created first, then wrapped in operator nodes.
In a production interpreter you would track these allocations to free them later.
#include <stdlib.h>
static Node *num(int v) {
Node *n = malloc(sizeof *n);
n->kind = N_NUM; n->value = v;
return n;
}
static Node *binop(char op, Node *l, Node *r) {
Node *n = malloc(sizeof *n);
n->kind = N_BINOP;
n->bin.op = op; n->bin.left = l; n->bin.right = r;
return n;
}The Grammar
We use a classic precedence grammar. expr handles + and -, term handles * and /, and factor handles numbers and parentheses.
Because higher-precedence rules sit deeper, multiplication binds tighter than addition automatically.
/* Grammar (EBNF):
expr = term { ('+' | '-') term } ;
term = factor { ('*' | '/') factor } ;
factor = NUMBER | '(' expr ')' ; */Matching Tokens
An expect helper consumes a token of a required kind or aborts. It is the parser's contract with the lexer.
We reuse the cur and bump lookahead helpers from the tokenizer lesson.
#include <stdio.h>
#include <stdlib.h>
static void expect(TokKind k) {
if (cur().kind != k) {
fprintf(stderr, "parse error: unexpected token\n");
exit(1);
}
bump();
}Parsing a Factor
A factor is the atom of the grammar: either a literal number or a parenthesized sub-expression. Parentheses recurse back into parse_expr.
This recursion is what gives recursive-descent parsers their name.
static Node *parse_expr(void);
static Node *parse_factor(void) {
if (cur().kind == TOK_NUM) {
int v = cur().value; bump();
return num(v);
}
expect(TOK_LPAREN);
Node *e = parse_expr();
expect(TOK_RPAREN);
return e;
}Parsing a Term
A term parses one factor, then loops while it sees * or /, folding each into a left-associative binop node.
Left-associativity means 8 / 4 / 2 parses as (8 / 4) / 2 = 1.
static Node *parse_term(void) {
Node *left = parse_factor();
while (cur().kind == TOK_STAR || cur().kind == TOK_SLASH) {
char op = (cur().kind == TOK_STAR) ? '*' : '/';
bump();
left = binop(op, left, parse_factor());
}
return left;
}Parsing an Expression
The top rule mirrors parse_term but handles + and -. Each layer calls the next-higher-precedence rule, so the tree comes out correctly nested.
This three-function structure is the heart of the parser.
static Node *parse_expr(void) {
Node *left = parse_term();
while (cur().kind == TOK_PLUS || cur().kind == TOK_MINUS) {
char op = (cur().kind == TOK_PLUS) ? '+' : '-';
bump();
left = binop(op, left, parse_term());
}
return left;
}Inspecting the Tree
This program parses an expression and prints it back in fully parenthesized form, revealing how precedence was resolved.
The pretty-printer recurses over the same node structure the parser built.
#include <stdio.h>
typedef struct Node {
int is_num; int value;
char op; struct Node *l, *r;
} Node;
static Node *N(int v){ Node*n=calloc(1,sizeof*n); n->is_num=1; n->value=v; return n; }
static Node *B(char o,Node*a,Node*b){ Node*n=calloc(1,sizeof*n); n->op=o; n->l=a; n->r=b; return n; }
static void show(Node *n){
if (n->is_num){ printf("%d", n->value); return; }
printf("("); show(n->l); printf(" %c ", n->op); show(n->r); printf(")");
}
int main(void){
/* 3 + 4 * 2 -> (3 + (4 * 2)) */
Node *ast = B('+', N(3), B('*', N(4), N(2)));
show(ast); printf("\n");
return 0;
}Avoiding Left Recursion
A naive grammar like expr = expr '+' term would make parse_expr call itself forever. Recursive descent cannot handle direct left recursion.
Rewriting the rule as a while loop over { '+' term } sidesteps the infinite recursion entirely.
Why an AST?
The AST separates syntax from execution. The same tree can be evaluated, optimized, or compiled to bytecode without re-parsing.
Next we walk this tree to compute its value.
Quick Check
Consider how the grammar layers enforce precedence.
Recap
You wrote a recursive-descent parser: AST node structs, constructors, and the expr/term/factor functions that encode precedence and left-associativity.
The resulting tree is ready for evaluation.
Learn C with an AI tutor — free
Write and run real code in your browser, get instant help from a 24/7 AI tutor, and pick up where you left off on the web or in the app.
- Courses
- 39
- Lessons
- 144
Frequently Asked Questions
Is the “Parsing Expressions” lesson free?
Yes — the full text of “Parsing Expressions” is free to read here on the web. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the C Academy course, upgrade to CoddyKit PRO. The C Academy course includes 4 lessons in total.
What will I learn in “Parsing Expressions”?
Build a parse tree. You practise C Academy with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start C Academy?
No prior experience is required. C Academy on CoddyKit is structured for beginners through advanced learners, so you can start here or from the beginning and move at your own pace. This is lesson 2 of 4.
How long does the “Parsing Expressions” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this C Academy lesson?
Yes. Every C Academy lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Tokenizing Input
- Parsing Expressions
- Evaluating the Tree
- Adding Variables