CD Notes

Toy Compiler Project: Minimal Complete Compiler

Step-by-step guide to building a complete toy compiler from scratch

Introduction: Why Build a Toy Compiler?

There is a profound difference between reading about compilers and building one. A toy compiler is a complete, end-to-end implementation that takes source code in a simple language and produces executable output — typically assembly code or bytecode. It is "toy" only in the sense that the source language is small, but the compiler itself is real, implementing all the essential phases that a production compiler like GCC or Clang would have.

This project is your capstone exercise. By building it, you prove that you can take a blank page and produce a working compiler. Every concept from the course — regular expressions, grammars, parse trees, type systems, intermediate representations, and code generation — comes together in one cohesive system.

Language Specification

Our toy language supports enough features to write meaningful programs:

// Types	int and bool
// Arithmetic	+, -, *, /
// Comparison	<, >, <=, >=, ==, !=
// Logical	&&, \|\|, !
// Control flow	if-else, while

Phase 1: Lexer Design

The lexer converts source text into tokens. For our toy language, we need approximately 30 token types:

c example

// Token types for our toy language
typedef enum {
    // Literals and identifiers
    TOK_INT_LIT, TOK_BOOL_LIT, TOK_IDENT,
    // Keywords
    TOK_INT, TOK_BOOL, TOK_IF, TOK_ELSE, TOK_WHILE,
    TOK_RETURN, TOK_PRINT, TOK_TRUE, TOK_FALSE,
    // Operators
    TOK_PLUS, TOK_MINUS, TOK_STAR, TOK_SLASH,
    TOK_LT, TOK_GT, TOK_LE, TOK_GE, TOK_EQ, TOK_NE,
    TOK_AND, TOK_OR, TOK_NOT, TOK_ASSIGN,
    // Delimiters
    TOK_LPAREN, TOK_RPAREN, TOK_LBRACE, TOK_RBRACE,
    TOK_COMMA, TOK_SEMI,
    // Special
    TOK_EOF, TOK_ERROR
} TokenType;

The lexer uses a simple state machine that reads character by character:

Example

Token next_token(Lexer *lex) { skip_whitespace_and_comments(lex); char c = peek(lex); if (c == '\0') return make_token(TOK_EOF); // Numbers if (isdigit(c)) return scan_number(lex); // Identifiers and keywords if (isalpha(c) || c == '_') return scan_identifier(lex); // Two-character operators if (c == '<' && peek_next(lex) == '=') { advance2(lex); return make_token(TOK_LE); } if (c == '>' && peek_next(lex) == '=') { advance2(lex); return make_token(TOK_GE); } if (c == '=' && peek_next(lex) == '=') { advance2(lex); return make_token(TOK_EQ); } if (c == '!' && peek_next(lex) == '=') { advance2(lex); return make_token(TOK_NE); } if (c == '&' && peek_next(lex) == '&') { advance2(lex); return make_token(TOK_AND); } if (c == '|' && peek_next(lex) == '|') { advance2(lex); return make_token(TOK_OR); } // Single-character tokens advance(lex); switch (c) { case '+': return make_token(TOK_PLUS); case '-': return make_token(TOK_MINUS); // ... remaining single-char tokens } return make_token(TOK_ERROR); }

Phase 2: Parser and AST Construction

The parser uses recursive descent to build an Abstract Syntax Tree. Each grammar rule becomes a function:

Example

// Grammar (simplified): // program → function* // function → type IDENT '(' params ')' block // block → '{' statement* '}' // statement → declaration | assignment | if_stmt | while_stmt | return_stmt | print_stmt // expression → comparison (('&&' | '||') comparison)* // comparison → addition (('<' | '>' | '==' | '!=') addition)* // addition → multiplication (('+' | '-') multiplication)* // multiplication → unary (('*' | '/') unary)* // unary → ('!' | '-') unary | primary // primary → INT_LIT | BOOL_LIT | IDENT | IDENT '(' args ')' | '(' expr ')' ASTNode* parse_function(Parser *p) { char *ret_type = parse_type(p); // "int" or "bool" char *name = expect_identifier(p); // function name expect(p, TOK_LPAREN); Param *params = parse_parameters(p); // parameter list expect(p, TOK_RPAREN); ASTNode *body = parse_block(p); // function body return make_function_node(ret_type, name, params, body); } ASTNode* parse_if(Parser *p) { expect(p, TOK_IF); expect(p, TOK_LPAREN); ASTNode *cond = parse_expression(p); expect(p, TOK_RPAREN); ASTNode *then_block = parse_block(p); ASTNode *else_block = NULL; if (match(p, TOK_ELSE)) else_block = parse_block(p); return make_if_node(cond, then_block, else_block); }

Phase 3: Semantic Analysis

The semantic analyzer walks the AST and performs type checking and scope validation:

Example

void check_function(ASTNode *func, SymbolTable *global) { // Create local scope SymbolTable *local = create_scope(global); // Register parameters for (Param *p = func->params; p; p = p->next) declare_variable(local, p->name, p->type, func->line); // Check function body check_block(func->body, local, func->return_type); destroy_scope(local); } Type check_binary_op(ASTNode *node, SymbolTable *scope) { Type left = check_expression(node->left, scope); Type right = check_expression(node->right, scope); if (is_arithmetic_op(node->op)) { if (left != TYPE_INT || right != TYPE_INT) error(node->line, "Arithmetic requires int operands, got %s and %s", type_name(left), type_name(right)); return TYPE_INT; } if (is_comparison_op(node->op)) { if (left != right) error(node->line, "Cannot compare %s with %s", type_name(left), type_name(right)); return TYPE_BOOL; } }

Phase 4: Code Generation

The code generator traverses the AST and emits target code. For simplicity, we generate stack-based bytecode:

Example

typedef enum { OP_PUSH, OP_POP, OP_ADD, OP_SUB, OP_MUL, OP_DIV, OP_LT, OP_GT, OP_EQ, OP_AND, OP_OR, OP_NOT, OP_LOAD, OP_STORE, OP_JUMP, OP_JUMP_IF_FALSE, OP_CALL, OP_RETURN, OP_PRINT, OP_HALT } OpCode; void generate_expression(ASTNode *node, CodeGen *gen) { switch (node->type) { case NODE_INT_LIT: emit(gen, OP_PUSH, node->int_value); break; case NODE_IDENTIFIER: emit(gen, OP_LOAD, lookup_local_index(gen, node->name)); break; case NODE_BINARY: generate_expression(node->left, gen); generate_expression(node->right, gen); emit(gen, op_for_binary(node->op), 0); break; case NODE_CALL: // Push arguments in order for (int i = 0; i < node->arg_count; i++) generate_expression(node->args[i], gen); emit(gen, OP_CALL, function_address(gen, node->name)); break; } } void generate_if(ASTNode *node, CodeGen *gen) { generate_expression(node->condition, gen); int false_jump = emit(gen, OP_JUMP_IF_FALSE, 0); // Placeholder generate_block(node->then_block, gen); if (node->else_block) { int end_jump = emit(gen, OP_JUMP, 0); // Skip else patch_jump(gen, false_jump); // False → else generate_block(node->else_block, gen); patch_jump(gen, end_jump); // End of if } else { patch_jump(gen, false_jump); } }

Phase 5: Virtual Machine (Interpreter)

A simple stack-based VM executes the generated bytecode:

Example

int vm_execute(Bytecode *code) { int stack[1024]; int sp = 0; // Stack pointer int ip = 0; // Instruction pointer while (1) { Instruction instr = code->instructions[ip++]; switch (instr.op) { case OP_PUSH: stack[sp++] = instr.operand; break; case OP_ADD: sp--; stack[sp-1] += stack[sp]; break; case OP_SUB: sp--; stack[sp-1] -= stack[sp]; break; case OP_MUL: sp--; stack[sp-1] *= stack[sp]; break; case OP_LT: sp--; stack[sp-1] = stack[sp-1] < stack[sp]; break; case OP_PRINT: printf("%d\n", stack[--sp]); break; case OP_JUMP: ip = instr.operand; break; case OP_JUMP_IF_FALSE: if (!stack[--sp]) ip = instr.operand; break; case OP_HALT: return stack[sp-1]; } } }

Testing Strategy

Build a comprehensive test suite that exercises each language feature:

bash example

# Run all tests
for test in tests/*.toy; do
    echo "Testing $test..."
    ./toyc "$test" > /tmp/output.txt
    diff /tmp/output.txt "${test%.toy}.expected"
done

Test files should cover: basic arithmetic, variable declarations and assignments, if-else branching, while loops, function calls, recursion, type errors (expecting failure), and edge cases.

Key Takeaways

Building a toy compiler from scratch demonstrates that a compiler is not a monolithic mystery — it is a pipeline of well-defined transformations, each doing one job well. The lexer handles characters, the parser handles structure, the semantic analyzer handles meaning, and the code generator handles execution. This modular design means you can modify any phase independently, add new features incrementally, and test each phase in isolation. These architectural principles apply to any compiler, regardless of the source or target language.

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Toy Compiler Project: Minimal Complete Compiler.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.

Search Terms

compiler-design, compiler design, compiler, design, projects, toy, project, toy compiler project: minimal complete compiler

Continue learning this concept

ProjectsExpression Parser ProjectBuild an advanced mathematical expression parser with tree visualization ProjectsLexical Analyzer ProjectPractical project for building a lexical analyzer with token recognition ProjectsSyntax Checker ProjectBuild a comprehensive syntax and semantic analyzer with error reporting ProjectsCalculator Compiler ProjectDetailed project guide for building a mathematical expression evaluator ProjectsMini Programming Language ProjectComplete project building an interpreter for a small procedural language Parser GeneratorsPractical Parser ProjectsReal-world parser implementation guide with AST construction, symbol tables, and code generation

PreviousSyntax Checker Project NextCompiler Design Cheatsheet

CD Notes

Toy Compiler Project: Minimal Complete Compiler

Step-by-step guide to building a complete toy compiler from scratch

Introduction: Why Build a Toy Compiler?

Language Specification

Our toy language supports enough features to write meaningful programs:

// Types	int and bool
// Arithmetic	+, -, *, /
// Comparison	<, >, <=, >=, ==, !=
// Logical	&&, \|\|, !
// Control flow	if-else, while

Phase 1: Lexer Design

The lexer converts source text into tokens. For our toy language, we need approximately 30 token types:

c example

// Token types for our toy language
typedef enum {
    // Literals and identifiers
    TOK_INT_LIT, TOK_BOOL_LIT, TOK_IDENT,
    // Keywords
    TOK_INT, TOK_BOOL, TOK_IF, TOK_ELSE, TOK_WHILE,
    TOK_RETURN, TOK_PRINT, TOK_TRUE, TOK_FALSE,
    // Operators
    TOK_PLUS, TOK_MINUS, TOK_STAR, TOK_SLASH,
    TOK_LT, TOK_GT, TOK_LE, TOK_GE, TOK_EQ, TOK_NE,
    TOK_AND, TOK_OR, TOK_NOT, TOK_ASSIGN,
    // Delimiters
    TOK_LPAREN, TOK_RPAREN, TOK_LBRACE, TOK_RBRACE,
    TOK_COMMA, TOK_SEMI,
    // Special
    TOK_EOF, TOK_ERROR
} TokenType;

The lexer uses a simple state machine that reads character by character:

Example

Phase 2: Parser and AST Construction

The parser uses recursive descent to build an Abstract Syntax Tree. Each grammar rule becomes a function:

Example

Phase 3: Semantic Analysis

The semantic analyzer walks the AST and performs type checking and scope validation:

Example

Phase 4: Code Generation

The code generator traverses the AST and emits target code. For simplicity, we generate stack-based bytecode:

Example

Phase 5: Virtual Machine (Interpreter)

A simple stack-based VM executes the generated bytecode:

Example

Testing Strategy

Build a comprehensive test suite that exercises each language feature:

bash example

# Run all tests
for test in tests/*.toy; do
    echo "Testing $test..."
    ./toyc "$test" > /tmp/output.txt
    diff /tmp/output.txt "${test%.toy}.expected"
done

Test files should cover: basic arithmetic, variable declarations and assignments, if-else branching, while loops, function calls, recursion, type errors (expecting failure), and edge cases.

Key Takeaways

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Toy Compiler Project: Minimal Complete Compiler.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.

Search Terms

compiler-design, compiler design, compiler, design, projects, toy, project, toy compiler project: minimal complete compiler

Continue learning this concept

PreviousSyntax Checker Project NextCompiler Design Cheatsheet