C Academy · Lesson

Parsing Expressions

Build a parse tree.

Parsing Expressions is a free C Academy lesson on CoddyKit — 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, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.

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.

Frequently asked questions

Is the “Parsing Expressions” lesson free?

Yes — the full text of “Parsing Expressions” is free to read here on the web, and the C Academy course includes 4 lessons in total. 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.

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; this is — lesson 2 of 4, so you can start here or from the beginning and move at your own pace.

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

← Back to C Academy