Building a Tiny C Compiler: Lexer, Parser, AST

Goal: compile arithmetic expressions like 4 + 3 * 2. Three phases:

1. Lexer — source text → token stream
2. Parser — token stream → AST
3. Codegen — AST → assembly (or direct evaluation)

1. Lexer

The lexer reads a string like "5 + 3" character by character and produces a stream of tokens — typed, meaningful units of code.

Token types, as an enum:

typedef enum {
    TOKEN_NUMBER,
    TOKEN_PLUS,
    TOKEN_MINUS,
    TOKEN_STAR,
    TOKEN_SLASH,
    TOKEN_LPAREN,
    TOKEN_RPAREN,
    TOKEN_EOF
} TokenType;

Each token carries its type plus a numeric value (for numbers):

typedef struct {
    TokenType type;
    int value; // valid when type == TOKEN_NUMBER
} Token;

Example: "42 + 7" → NUMBER(42), PLUS, NUMBER(7), EOF.

Scanning is a single pass over a cursor (const char **), so the lexer state advances as tokens are consumed:

int is_digit(char c) { return c >= '0' && c <= '9'; }

Token get_next_token(const char **src) {
    // 1. Skip whitespace
    while (**src == ' ' || **src == '\t' || **src == '\n') (*src)++;

    // 2. End of input
    if (**src == '\0') return (Token){ TOKEN_EOF, 0 };

    // 3. Multi-digit number
    if (is_digit(**src)) {
        int val = 0;
        while (is_digit(**src)) {
            val = val * 10 + (**src - '0');
            (*src)++;
        }
        return (Token){ TOKEN_NUMBER, val };
    }

    // 4. Single-character operators
    char c = **src;
    (*src)++;
    switch (c) {
        case '+': return (Token){ TOKEN_PLUS, 0 };
        case '-': return (Token){ TOKEN_MINUS, 0 };
        case '*': return (Token){ TOKEN_STAR, 0 };
        case '/': return (Token){ TOKEN_SLASH, 0 };
        case '(': return (Token){ TOKEN_LPAREN, 0 };
        case ')': return (Token){ TOKEN_RPAREN, 0 };
        default:
            fprintf(stderr, "Error: unknown character '%c'\n", c);
            exit(1);
    }
}

Driver loop:

int main(void) {
    const char *src = "432 + 2 * 10";
    Token tok;

    do {
        tok = get_next_token(&src);
        printf("type=%d value=%d\n", tok.type, tok.value);
    } while (tok.type != TOKEN_EOF);
}

2. Parser

The parser turns the flat token stream into an Abstract Syntax Tree (AST) representing the program’s structure.

AST nodes

An expression is either a number (leaf) or a binary operation (operator + left/right subtrees). Model with a recursive struct and a union:

typedef enum { AST_NUMBER, AST_BINARY_OP } ASTNodeType;

typedef struct ASTNode {
    ASTNodeType type;
    union {
        int number_val; // AST_NUMBER
        struct {        // AST_BINARY_OP
            TokenType op;
            struct ASTNode *left, *right;
        } binary_op;
    };
} ASTNode;

Heap-allocated constructors:

ASTNode *create_num_node(int val) {
    ASTNode *node = malloc(sizeof(ASTNode));
    node->type = AST_NUMBER;
    node->number_val = val;
    return node;
}

ASTNode *create_binop_node(TokenType op, ASTNode *left, ASTNode *right) {
    ASTNode *node = malloc(sizeof(ASTNode));
    node->type = AST_BINARY_OP;
    node->binary_op.op = op;
    node->binary_op.left = left;
    node->binary_op.right = right;
    return node;
}

Precedence via recursive descent

4 + 3 * 2 must parse as 4 + (3 * 2), not (4 + 3) * 2. Solution: recursive descent — one function per precedence level:

parse_expression  (+, -)
  └─ parse_term   (*, /)
       └─ parse_factor  (numbers, parentheses)

Higher-precedence operators sit deeper in the call chain, so they bind tighter.

Parser state — the current token plus a cursor into the source:

static Token current_token;
static const char *src_ptr;

void advance(void) {
    current_token = get_next_token(&src_ptr);
}

parse_factor — atomic units

Handles the building blocks: numbers and parenthesized expressions.

ASTNode *parse_factor(void) {
    if (current_token.type == TOKEN_NUMBER) {
        ASTNode *node = create_num_node(current_token.value);
        advance();
        return node;
    }

    if (current_token.type == TOKEN_LPAREN) { // '(' expr ')'
        advance();
        ASTNode *node = parse_expression(); // full expression inside
        if (current_token.type != TOKEN_RPAREN) {
            fprintf(stderr, "Syntax Error: expected ')'\n");
            exit(1);
        }
        advance();
        return node;
    }

    fprintf(stderr, "Syntax Error: expected number or '('\n");
    exit(1);
}

Parentheses belong in parse_factor because a parenthesized expression is an atomic unit, just like a number. The recursive call back to parse_expression handles nesting like ((1 + 2) * 3).

parse_term and parse_expression

Same pattern at both levels: parse the left operand, then loop while the current operator matches this level, building a left-associative tree.

ASTNode *parse_term(void) {
    ASTNode *left = parse_factor();

    while (current_token.type == TOKEN_STAR || current_token.type == TOKEN_SLASH) {
        TokenType op = current_token.type;
        advance();
        left = create_binop_node(op, left, parse_factor());
    }
    return left;
}

ASTNode *parse_expression(void) {
    ASTNode *left = parse_term();

    while (current_token.type == TOKEN_PLUS || current_token.type == TOKEN_MINUS) {
        TokenType op = current_token.type;
        advance();
        left = create_binop_node(op, left, parse_term());
    }
    return left;
}

Trace: 4 + 3 * 2

1. parse_expression → parse_term → parse_factor reads 4.
2. Back in parse_expression: sees +, calls parse_term for the right side.
3. parse_term reads 3, sees *, reads 2, builds subtree (3 * 2).
4. parse_expression links 4 + (3 * 2).

Resulting AST:

    (+)
    / \
  (4) (*)
      / \
    (3) (2)

3. Next: evaluation or codegen

With the AST built, two paths:

• Interpreter: recursively walk the tree and compute the integer result directly in C.
• Compiler: walk the tree emitting x86-64 instructions (mov, add, imul), assemble with GCC, run natively.