DEV Community: Frederik Gram

Writing Your First Compiler - Part 7: Taking Stock

Frederik Gram — Fri, 14 Nov 2025 01:29:35 +0000

We've built a complete compiler frontend. Source code becomes tokens, tokens become an abstract syntax tree. Before we jump into code generation, let's take a moment to understand what we actually have.

What We Built

Look at the pipeline we've constructed:

Lexer (lexer.py) - Turns source code into tokens
AST Nodes (abstract.py) - Defines the tree structure
Parser (parser.py) - Turns tokens into an AST

A complete frontend. We can take YFC source code and produce a structured representation of what it means.

The language itself:

Functions - named chunks of code with parameters
Conditionals - if/else expressions for branching
Recursion - functions that call themselves
Arithmetic - +, -, *, /
Comparison - <, >, ==
Function calls - with multiple arguments
Extern declarations - for calling C functions

That's it. No loops, no mutable variables, no strings, no arrays. Just functions and recursion.

Sounds limited, right? And for practical programming, it absolutely is. But theoretically - mathematically - it's enough to compute anything that can be computed.

Turing Completeness

The language we've designed is Turing complete. That's a fancy way of saying it can compute anything that's computable - once we implement code generation. Right now we just have a parser that builds trees. But those trees represent a language powerful enough to compute anything.

Why? Because the language has two things:

Conditionals - the ability to make decisions
Recursion - the ability to repeat computations

That's all you need. Every algorithm, every program, every computation - it can be expressed with just those two features.

Now, there's a catch. Turing completeness is a theoretical property. It assumes infinite memory and unbounded time. In practice, your computer has finite RAM, and recursive calls eventually hit stack limits. A recursive factorial(100000) will blow the stack. But mathematically, if we had infinite resources, YFC could compute anything computable. That's what Turing completeness means - theoretical equivalence to a Turing machine with an infinite tape.

Consider what we can already write:

# Factorial - iterative in spirit, recursive in form
func factorial(n) :
    if n < 2
        1
    else
        n * factorial(n - 1)

# Fibonacci - classic recursion
func fib(n) :
    if n < 2
        n
    else
        fib(n - 1) + fib(n - 2)

# GCD - Euclidean algorithm
func gcd(a, b) :
    if b == 0
        a
    else
        gcd(b, a - b)  # (simplified version)

These aren't toy examples. They're real algorithms. And they work because recursion lets us loop, conditionals let us branch, and that's all we need.

In theory, you could write a anything in YFC (in-part because we have the extern that could handle input and output), Would it be painful? Yes. Would it be slow? Absolutely. But it's possible. That's what Turing completeness means.

What's Missing (And Why)

That's the theory. The practice is different. Writing actual programs in YFC would be miserable. Here's what we don't have and why you'd miss it.

Mutable State

The big one. We can't do this:

# Doesn't exist in YFC
x = 5
x = x + 1  # Can't reassign

Everything is immutable. Once a variable (function parameter) has a value, that's its value. You can't change it.

What about for loops? They'd be nice to have:

# Would be nice to write
for i in 1..10 :
    do_something(i)

But here's the problem: what can they actually do? Think about it. The loop variable i changes each iteration (1, 2, 3...), but you can't accumulate anything:

for i in 1..10 i  # Returns... 10? The last value?

# Can't do this - no mutation
sum = 0
for i in 1..10 :
    sum = sum + i  # Can't reassign sum

Without mutation, loops can only:

Call functions with side effects (like putchard(i) to print)
Return the last iteration's value
...that's it

You can't sum numbers. You can't build a list. You can't count matches. For those, you need mutation OR you use recursion with accumulator parameters:

# With recursion and accumulators
func sum_helper(current, end, accumulator) :
    if current > end
        accumulator
    else
        sum_helper(current + 1, end, accumulator + current)

func sum(n) :
    sum_helper(1, n, 0)

It works, but it's verbose. With mutation, this becomes simpler. In expression-based languages like Kaleidoscope, mutable variables use a var/in construct:

# With mutation (doesn't exist yet)
func sum(n) :
    var total = 0 in
        for i in 1..n :
            total = total + i

The var total = 0 in body introduces a mutable variable scoped to that expression. Within the body, you can reassign it. You can declare multiple variables: var x = 1, y = 2 in expr. The whole thing is still an expression - it returns the value of the body.

We'll add mutable state in a future part. When we do, for loops will come back and actually be useful.

Data Structures

We have numbers and functions. That's it.

No strings:

# Can't do this
extern func putchard(char) :
putchard("Hello")  # What's a string? We only have numbers
putchard(72)       # This works - prints 'H' (ASCII 72)

No arrays or lists:

# Can't do this
numbers = [1, 2, 3, 4, 5]

No structs or records:

# Can't do this
person = {name: "Alice", age: 30}

These would be useful. But they also complicate code generation significantly. For now, we're keeping it simple.

More Operators

We have <, >, ==. What about:

<=, >=, != - more comparisons
&&, ||, ! - logical operators
% - modulo
&, |, ^, <<, >> - bitwise operators

We could add these. They're just more cases in the lexer and parser. But for teaching purposes, we've kept it minimal.

Other Missing Features

Multiple return values - functions return one value
First-class functions - can't pass functions as arguments
Closures - functions can't capture variables from outer scopes
Type system - everything is a number, compiler doesn't check types
Error handling - no exceptions or error values
Modules/imports - everything in one file

Real languages have these. We don't (yet). We're building a compiler to learn how compilers work, not to build a production language.

But here's the key insight: adding these features is mostly more parser code. The core ideas - lexing, parsing, AST construction - you've already learned those. Everything else is variations on the same patterns.

Seeing the AST

Let's actually visualize what we've built. We can export our AST to JSON and see it as a tree. This will help us really understand the structure - not just as printed text, but as actual data we can explore.

We need a way to convert our Python objects (Expression nodes, Function nodes) into dictionaries that JSON can handle. Add this helper function to the end of your abstract.py:

def ast_to_dict(obj):
    """Convert AST objects to dictionaries for JSON serialization."""
    if isinstance(obj, Span):
        return f"{obj.start.row}:{obj.start.column}-{obj.end.row}:{obj.end.column}"

    if isinstance(obj, Token):
        return obj.value

    if isinstance(obj, (NumberExpr, IdentifierExpr, BinaryOp, CallExpr, IfExpr)):
        result = {"type": obj.__class__.__name__}

        if hasattr(obj, 'span'):
            result["span"] = ast_to_dict(obj.span)

        if isinstance(obj, NumberExpr):
            result["value"] = obj.value.value
        elif isinstance(obj, IdentifierExpr):
            result["name"] = obj.value.value
        elif isinstance(obj, BinaryOp):
            result["operator"] = obj.op.value
            result["left"] = ast_to_dict(obj.left)
            result["right"] = ast_to_dict(obj.right)
        elif isinstance(obj, CallExpr):
            result["callee"] = obj.callee.value.value
            result["arguments"] = [ast_to_dict(arg) for arg in obj.arguments]
        elif isinstance(obj, IfExpr):
            result["condition"] = ast_to_dict(obj.condition)
            result["then"] = ast_to_dict(obj.then_expr)
            if obj.else_expr:
                result["else"] = ast_to_dict(obj.else_expr)

        return result

    if isinstance(obj, Function):
        return {
            "type": "Function",
            "name": obj.name,
            "parameters": [p.value for p in obj.parameters],
            "body": ast_to_dict(obj.body) if obj.body else None,
            "span": ast_to_dict(obj.span)
        }

    if isinstance(obj, list):
        return [ast_to_dict(item) for item in obj]

    return obj

Now in your parser test:

import json
from abstract import ast_to_dict

# ... after parsing ...

# Export to JSON
program = {
    "type": "Program",
    "functions": ast_to_dict(functions)
}

json_output = json.dumps(program, indent=2)
print(json_output)

# Or write to file
with open("ast.json", "w") as f:
    f.write(json_output)

Run it and you'll get something like:

{
  "type": "Program",
  "functions": [
    {
      "type": "Function",
      "name": "factorial",
      "parameters": ["n"],
      "body": {
        "type": "IfExpr",
        "condition": {
          "type": "BinaryOp",
          "operator": "<",
          "left": {
            "type": "IdentifierExpr",
            "name": "n"
          },
          "right": {
            "type": "NumberExpr",
            "value": "2"
          }
        },
        "then": {
          "type": "NumberExpr",
          "value": "1"
        },
        "else": {
          "type": "BinaryOp",
          "operator": "*",
          "left": {
            "type": "IdentifierExpr",
            "name": "n"
          },
          "right": {
            "type": "CallExpr",
            "callee": "factorial",
            "arguments": [
              {
                "type": "BinaryOp",
                "operator": "-",
                "left": {
                  "type": "IdentifierExpr",
                  "name": "n"
                },
                "right": {
                  "type": "NumberExpr",
                  "value": "1"
                }
              }
            ]
          }
        }
      }
    }
  ]
}

Copy this JSON and paste it into jsoncrack.com or any JSON tree visualizer. You'll see your AST as an interactive tree diagram. Click around. Explore the structure. See how factorial(n - 1) is represented. See how the if-expression contains three sub-expressions. Every node, every connection - it's all there.

That's what the compiler works with.

Reflection

We started with nothing. Now we have a compiler frontend that understands functions, recursion, and conditionals. It turns text into a structured representation of computation.

The language design is Turing complete - conditionals and recursion are all you need theoretically. But we can't run anything yet. We have trees, not executable code. And practically, the language is missing features that make programming bearable - mutation, data structures, better operators. But those are additions, not fundamentals.

The frontend is done. We can lex, we can parse, we can build trees.

Next, the backend. We turn those trees into assembly. We generate code. And then we'll have something that actually runs.

Next: Not Yet Released Part 8: Code Generation
Previous: Part 6: Extending the Language

Code Repository: All accompanying code for this tutorial series is available on GitHub. The repository includes complete source code for each step, example programs, and additional resources to help you follow along.

Writing Your First Compiler - Part 6: Extending the Language

Frederik Gram — Sat, 08 Nov 2025 06:23:42 +0000

We have a parser that handles arithmetic expressions. Numbers, operators, parentheses. It works. But we're not trying to build a calculator - we're building a compiler for a real programming language.

Time to add the rest. Functions, variables, conditionals. Everything we need to write actual programs.

Same strategy as before: one piece at a time. We'll start simple and build up.

Adding Identifiers

The first thing we need is identifiers - names for variables and functions. When you write factorial(n), both factorial and n are identifiers.

Lexing Identifiers

An identifier is a sequence of letters, digits, and underscores. But it can't start with a digit - x1 is valid, 1x is not. That's a convention most programming languages follow, and we will too.

So how do we recognize them? Same approach as numbers. We see a letter or underscore, we know an identifier is starting. Keep reading characters as long as they're valid (letters, digits, underscores), then we've got our identifier.

First, we need a token type for identifiers. Open up your TokenType enum and add it:

class TokenType(Enum):
    Number = auto()
    Plus = auto()
    Minus = auto()
    Mul = auto()
    Div = auto()
    LParen = auto()
    RParen = auto()
    Identifier = auto()  # New!
    Eof = auto()

Now in the lexer's main loop, add identifier recognition after number handling:

# Recognize numbers
if self.current.isdigit():
    start = self.cursor
    while self.current.isdigit():
        self.increment()

    self.push_token(TokenType.Number, self.source[start:self.cursor])
    continue

# Recognize identifiers
if self.current.isalpha() or self.current == '_':
    start = self.cursor
    while self.current.isalnum() or self.current == '_':
        self.increment()

    word = self.source[start:self.cursor]
    self.push_token(TokenType.Identifier, word)
    continue

See the pattern? Both follow the same structure: mark where we start, keep reading valid characters, slice out the substring, create a token.

For numbers: start with a digit, keep reading digits.
For identifiers: start with a letter or underscore, keep reading letters, digits, or underscores.

The difference is what counts as valid. Numbers can't start with letters. Identifiers can't start with digits - x1 is valid, 1x is not.

Parsing Identifiers

Now the parser needs to understand these identifier tokens. When we see x in the token stream, we need to create an AST node for it.

We need a new expression type. Open abstract.py and add:

class IdentifierExpr(Expression):
    def __init__(self, value: Token):
        self.value = value

Just like NumberExpr, but for identifiers instead of numbers. In the parser's parse_primary(), add a case to handle them:

case TokenType.Identifier:
    token = self.consume()
    return IdentifierExpr(token)

Same pattern as numbers: consume the token, wrap it in the appropriate node type.

Let's test it. Add this to parser.py:

if __name__ == "__main__":
    from lexer import Lexer

    # Test identifier parsing
    source = "x + y"
    lexer = Lexer(source)
    tokens = lexer.lex()
    parser = Parser(tokens)
    ast = parser.parse_expression()

    print(f"Root: {ast.op.value}")
    print(f"  Left: {ast.left.value.value}")   # "x"
    print(f"  Right: {ast.right.value.value}")  # "y"

Stop and think about what just happened. We added maybe 15 lines of code total - a few lines to the lexer, a new AST node, one case in the parser. And now our compiler can parse identifier expressions.

This is the pattern. This is how you build a compiler. Not by implementing everything at once, but by adding one piece at a time. Each piece is small. Each piece is testable. And they compose.

Keywords

We need keywords: func, if, else, for, in. But keywords look just like identifiers - they're both sequences of letters.

The solution: lex everything that looks like an identifier, then check if it's a keyword.

First, we need token types for each keyword. Expand the TokenType enum:

class TokenType(Enum):
    # ... existing tokens ...
    Func = auto()
    If = auto()
    Else = auto()
    For = auto()
    In = auto()
    Identifier = auto()
    Eof = auto()

When we lex something like func, how do we know it's a keyword and not just a variable named func? We need to check after we've read the whole word.

Create a keyword lookup table at the top of your lexer file:

KEYWORDS = {
    "func": TokenType.Func,
    "if": TokenType.If,
    "else": TokenType.Else,
    "extern": TokenType.Extern,
}

Now update the identifier lexing code to check this table:

if self.current.isalpha() or self.current == '_':
    start = self.cursor
    while self.current.isalnum() or self.current == '_':
        self.increment()

    word = self.source[start:self.cursor]

    # Check if it's a keyword
    token_type = KEYWORDS.get(word, TokenType.Identifier)
    self.push_token(token_type, word)
    continue

See what we're doing? We read the word first - doesn't matter if it's a keyword or identifier, same characters. Then we check: is this word in our keyword dictionary? If yes, use the keyword token type. If no, it's a regular identifier.

This is why func becomes a keyword but factorial stays an identifier. Same lexing logic, different token types based on the lookup.

More Operators

We can parse identifiers and keywords, but to actually write useful programs we need more operators. Look at what we want to support:

func factorial(n) : if n < 2 1 else n * factorial(n - 1)
func fib(n) : if n < 2 n else fib(n - 1) + fib(n - 2)

We need:

: - separates the function signature from its body
, - separates function parameters and arguments
< > == - comparison operators for conditionals

These aren't arithmetic operators. They're structural - they define the shape of our programs. Without :, we can't define functions. Without ,, we can't have multiple parameters. Without < > ==, we can't make decisions.

Add them to TokenType:

class TokenType(Enum):
    # Delimiters
    LParen = auto()
    RParen = auto()
    Colon = auto()    # Function body separator
    Comma = auto()    # Parameter/argument separator

    # Operators
    Plus = auto()
    Minus = auto()
    Mul = auto()
    Div = auto()
    Less = auto()     # Comparison
    Greater = auto()  # Comparison
    Equal = auto()    # Equality (==)

    # ... rest of tokens ...

Most of these are single characters. Update the single-character token map in the lexer:

single_char_tokens = {
    '(': TokenType.LParen,
    ')': TokenType.RParen,
    ':': TokenType.Colon,
    ',': TokenType.Comma,
    '+': TokenType.Plus,
    '-': TokenType.Minus,
    '*': TokenType.Mul,
    '/': TokenType.Div,
    '<': TokenType.Less,
    '>': TokenType.Greater,
}

But wait, == is two characters. If we just check self.current, we only see the first =. We need to look ahead at the next character without consuming it.

This is a common pattern in lexers: lookahead. Sometimes you need to see what's coming to decide what you're currently looking at. Is = the start of ==, or just a single =?

To solve this, we can create a helper method that lets us look ahead without consuming:

def peek(self, offset: int = 1) -> str:
    """Look ahead at the next character without consuming it."""
    pos = self.cursor + offset
    if pos < len(self.source):
        return self.source[pos]
    return '\0'

This works like current, but it looks ahead by offset positions. peek() gives us the next character, peek(2) gives us the one after that, all without moving the cursor. We can look ahead, decide what we're dealing with, then consume accordingly.

Now in the main loop, before we check single-character tokens, add the check for ==:

# Recognize identifiers and keywords
if self.current.isalpha() or self.current == '_':
    start = self.cursor
    while self.current.isalnum() or self.current == '_':
        self.increment()

    word = self.source[start:self.cursor]
    token_type = KEYWORDS.get(word, TokenType.Identifier)
    self.push_token(token_type, word)
    continue

# Check for == before single characters
if self.current == '=' and self.peek() == '=':
    self.push_token(TokenType.Equal, "==")
    self.increment()
    self.increment()
    continue

# Recognize single-character tokens
single_char_tokens = {
    '(': TokenType.LParen,
    ')': TokenType.RParen,
    ':': TokenType.Colon,
    ',': TokenType.Comma,
    '+': TokenType.Plus,
    '-': TokenType.Minus,
    '*': TokenType.Mul,
    '/': TokenType.Div,
    '<': TokenType.Less,
    '>': TokenType.Greater,
}

if token_type := single_char_tokens.get(self.current):
    self.push_token(token_type, self.current)
    self.increment()
    continue

See the ordering? We check for == before we check single-character tokens. If the current character is = and the next is also =, we have ==. Consume both characters (two increment() calls) and create the token.

This order matters. If we checked single-character tokens first, we'd see the first =, not find it in our dictionary (we don't have a single = token in YFC), and error out before we ever got to check if it was ==. Always check longer matches before shorter ones.

Comments

Comments start with # and go to the end of the line. We don't want to tokenize them - they're for humans, not the compiler. Just skip them entirely.

Add this near the top of the lexer's main loop, right after we skip whitespace:

while self.current != '\0':
    # Skip whitespace
    if self.current.isspace():
        self.increment()
        continue

    # Skip comments
    if self.current == '#':
        while self.current != '\n' and self.current != '\0':
            self.increment()
        continue

    # Recognize numbers
    if self.current.isdigit():
        start = self.cursor
        while self.current.isdigit():
            self.increment()

        self.push_token(TokenType.Number, self.source[start:self.cursor])
        continue

    # ... rest of lexing logic

When we see #, we consume characters until we hit a newline or the end of the file. No token gets created. By the time we get to parsing and code generation, comments are already gone - the compiler never sees them.

Updating the Precedence Map

We've added comparison operators (<, >, ==) to the lexer, but our parser doesn't know how to handle them yet. We need to add them to the precedence map in parser.py:

PRECEDENCE_MAP = {
    TokenType.Less: 10,      # New!
    TokenType.Greater: 10,   # New!
    TokenType.Equal: 10,     # New!
    TokenType.Plus: 20,
    TokenType.Minus: 20,
    TokenType.Mul: 40,
    TokenType.Div: 40,
}

Comparisons have lower precedence than arithmetic, so 2 + 3 < 5 and 1 + 1 == 2 parse as (2 + 3) < 5 and (1 + 1) == 2. The arithmetic happens first, then we compare the results.

This means our existing binary operation parsing already handles these operators - they just flow through the precedence climbing logic we built in Part 5. No new parsing code needed.

Function Calls

Now let's parse function calls like factorial(5).

Here's the thing: when we see an identifier, we don't immediately know what it is. Is factorial a variable, or is it a function call? We need to look ahead. If the next token is (, it's a function call. If not, it's just a variable reference.

This is why lookahead matters. We parse the identifier, then decide what to do based on what comes next.

First, add a CallExpr AST node:

class CallExpr(Expression):
    def __init__(self, callee: IdentifierExpr, arguments: list[Expression]):
        self.callee = callee
        self.arguments = arguments

A function call has a name (the callee) and a list of argument expressions.

In parse_primary(), update the identifier case:

case TokenType.Identifier:
    token = self.consume()
    ident = IdentifierExpr(token)

    # Just an identifier
    if self.current._type != TokenType.LParen:
        return ident

    # It's a function call
    self.consume()  # eat '('
    arguments: list[Expression] = []

    while self.current._type != TokenType.RParen and self.current._type != TokenType.Eof:
        arguments.append(self.parse_expression())
        if self.current._type == TokenType.Comma:
            self.consume()

    self.consume_assert(TokenType.RParen, "Expected ')' after function arguments")
    return CallExpr(ident, arguments)

When we see an identifier, we check what comes next. If it's (, it's a function call. We loop parsing expressions (the arguments) separated by commas, until we hit ).

Notice we're doing a lot of "consume this token and make sure it's the right type." We check for ), we check for ,, we'll be checking for : and other delimiters constantly. Writing if token._type != expected: raise error everywhere gets old fast.

Let's add a helper to clean this up:

def consume_assert(self, expected: TokenType, msg: str) -> Token:
    """Consume a token and assert it's the expected type."""
    token = self.consume()
    if token._type != expected:
        raise ParserError(f"{msg}. Got {token._type}")
    return token

Now instead of consume-check-error, we just consume_assert(TokenType.RParen, "Expected ')'"). One line. Clearer intent. Better error messages.

Let's see if function calls actually work. Add this test to parser.py:

if __name__ == "__main__":
    from lexer import Lexer

    # Test function call parsing
    source = "factorial(5)"
    lexer = Lexer(source)
    tokens = lexer.lex()
    parser = Parser(tokens)
    ast = parser.parse_expression()

    print(f"Function: {ast.callee.value.value}")
    print(f"Arguments: {len(ast.arguments)}")
    print(f"Arg 0: {ast.arguments[0].value.value}")

Run it:

$ python parser.py
Function: factorial
Arguments: 1
Arg 0: 5

The parser sees factorial, looks ahead and finds (. That tells it this is a function call, not just a variable. It then loops, parsing each argument expression (which could be arbitrarily complex - nested calls, arithmetic, whatever), separating them by commas.

If Expressions

Now for conditionals. In most languages, if is a statement - it does something (executes a branch of code) but doesn't return a value. Statements are actions. You can't write x = if condition ... in C or Python because if doesn't produce a value.

YFC is different. We only have expressions, not statements. Everything evaluates to a value. So if is an expression that evaluates to either the then-branch or the else-branch:

if n < 2
    1
else
    n * factorial(n - 1)

Add the IfExpr node:

class IfExpr(Expression):
    def __init__(
        self,
        condition: Expression,
        then_expr: Expression,
        else_expr: Expression | None,
    ):
        self.condition = condition
        self.then_expr = then_expr
        self.else_expr = else_expr  # None if no else clause

An if-expression has three parts: the condition, the then-branch, and optionally an else-branch.

Add the if-expression case to parse_primary():

case TokenType.If:
    self.consume()  # eat 'if'

    condition = self.parse_expression()
    then_expr = self.parse_expression()
    else_expr = None

    if self.current._type == TokenType.Else:
        self.consume()
        else_expr = self.parse_expression()

    return IfExpr(condition, then_expr, else_expr)

Three expressions in a row: condition, then-branch, optional else-branch. The else keyword is optional - if it's not there, else_expr stays None.

Test it:

source = "if n < 2 1 else n * 2"
lexer = Lexer(source)
tokens = lexer.lex()
parser = Parser(tokens)
ast = parser.parse_expression()

print(f"Type: {type(ast).__name__}")
print(f"Condition: {ast.condition.op.value}")  # <
print(f"Then: {ast.then_expr.value.value}")    # 1
print(f"Else: {ast.else_expr.op.value}")       # *

Notice what we just did. We parsed three separate expressions in sequence - condition, then-branch, else-branch - and tied them together into a single IfExpr node. The parser understands that these three pieces form one logical unit.

And because if is an expression, you can nest them. Put an if inside another if. Use one as a function argument. This compositional structure is powerful - you get a lot of flexibility from a simple rule.

Spans

Before we add more features, let's improve error reporting. Back in Part 3, we added Location tracking to tokens - every token knows its row and column. But expressions don't have locations yet. When we report an error in code generation, we want to point to the whole expression, not just one token.

An expression can span multiple tokens. The expression 2 + 3 * 4 starts at the 2 and ends at the 4. We need to capture that range.

A Span is just a pair of locations - where something starts and where it ends:

@dataclass
class Span:
    start: Location
    end: Location

Simple. But powerful. Now we can point to exactly which part of the source code an expression came from.

For example, if we have an error in this code:

if n < 2 1 else n * factorial(n - 1)

The entire if-expression spans from the i in if to the ) in factorial(n - 1). With that information, we can show:

Error: Type mismatch in if expression
  if n < 2 1 else n * factorial(n - 1)
  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

The underline covers the exact expression that's problematic. Much better than just saying "error on line 5."

Update the Expression base class:

class Expression:
    def __init__(self, span: Span):
        self.span = span

Now all expressions need spans. Update NumberExpr:

class NumberExpr(Expression):
    def __init__(self, span: Span, value: Token):
        super().__init__(span)
        self.value = value

For a number, the span is just the token's location:

case TokenType.Number:
    token = self.consume()
    span = Span(token.location, token.location)
    return NumberExpr(span, token)

For a binary operation, the span goes from the start of the left expression to the end of the right:

def parse_binary_op(self, left: Expression, op: Token) -> Expression:
    current_precedence = PRECEDENCE_MAP.get(op._type, 0)
    right = self.parse_primary()

    while PRECEDENCE_MAP.get(self.current._type, 0) > current_precedence:
        next_op = self.consume()
        right = self.parse_binary_op(right, next_op)

    span = Span(left.span.start, right.span.end)
    return BinaryOp(span, left, op, right)

Update all the other expression types similarly:

class IdentifierExpr(Expression):
    def __init__(self, span: Span, value: Token):
        super().__init__(span)
        self.value = value

class CallExpr(Expression):
    def __init__(self, span: Span, callee: IdentifierExpr, arguments: list[Expression]):
        super().__init__(span)
        self.callee = callee
        self.arguments = arguments

class IfExpr(Expression):
    def __init__(
        self,
        span: Span,
        condition: Expression,
        then_expr: Expression,
        else_expr: Expression | None,
    ):
        super().__init__(span)
        self.condition = condition
        self.then_expr = then_expr
        self.else_expr = else_expr

Update the parsing code to create proper spans. For if-expressions:

case TokenType.If:
    start = self.consume().location  # Save start location

    condition = self.parse_expression()
    then_expr = self.parse_expression()
    else_expr = None

    if self.current._type == TokenType.Else:
        self.consume()
        else_expr = self.parse_expression()

    # Span goes from 'if' keyword to end of last expression
    end = then_expr.span.end if else_expr is None else else_expr.span.end
    return IfExpr(Span(start, end), condition, then_expr, else_expr)

For function calls:

case TokenType.Identifier:
    token = self.consume()
    ident = IdentifierExpr(Span(token.location, token.location), token)

    if self.current._type != TokenType.LParen:
        return ident

    self.consume()
    arguments: list[Expression] = []

    while self.current._type != TokenType.RParen and self.current._type != TokenType.Eof:
        arguments.append(self.parse_expression())
        if self.current._type == TokenType.Comma:
            self.consume()

    end_token = self.consume_assert(TokenType.RParen, "Expected ')' after arguments")
    return CallExpr(Span(ident.span.start, end_token.location), ident, arguments)

Now every expression knows exactly where it came from in the source code.

Function Definitions

Now for functions themselves. So far everything we've parsed has been expressions - things that evaluate to values. But functions are different. They're not values themselves - they're named chunks of code.

Think of a function as a label. When we write func factorial(n) : ..., we're saying "here's a piece of code, and its name is factorial." At the assembly level, that's literally what happens - factorial becomes a label in the generated code, and calling the function is just jumping to that label.

Remember the assembly we looked at in Part 2? Here's a snippet:

fib:
        push    rbp
        mov     rbp, rsp
        ...
        call    fib        # Jump to the fib label
        ...
        ret
main:
        push    rbp
        mov     rbp, rsp
        mov     edi, 10
        call    fib        # Jump to the fib label
        pop     rbp
        ret

See? fib: and main: are just labels. When you call fib, the CPU jumps to that label and starts executing instructions. That's all a function is at the machine level - a named location in the instruction stream.

Functions sit at the top level of a program. You don't write a function inside an expression (at least not in YFC - some languages allow this). They're definitions, not computations.

So we need a different kind of AST node - not an Expression, but a Function:

class Function:
    def __init__(
        self,
        span: Span,
        name: str,
        parameters: list[Token],
        body: Expression | None,
    ):
        self.span = span
        self.name = name
        self.parameters = parameters
        self.body = body  # None for extern functions

Functions have the grammar: func name(params) : body. Let's break this down:

func keyword
Function name (an identifier)
( then a list of parameters separated by commas, then )
: separator
Body expression

A concrete example: func add(x, y) : x + y

Add a parse_function() method to the parser:

def parse_function(self, is_extern: bool = False) -> Function:
    """Parse a function definition."""
    start = self.consume().location  # eat 'func'

    name = self.consume_assert(TokenType.Identifier, "Expected function name")
    self.consume_assert(TokenType.LParen, "Expected '(' after function name")

    # Parse parameters
    parameters: list[Token] = []
    while self.current._type != TokenType.RParen and self.current._type != TokenType.Eof:
        param = self.consume_assert(TokenType.Identifier, "Expected parameter name")
        parameters.append(param)
        if self.current._type == TokenType.Comma:
            self.consume()

    self.consume_assert(TokenType.RParen, "Expected ')' after parameters")
    end = self.consume_assert(TokenType.Colon, "Expected ':' before function body").location

    # Parse body (None for extern functions)
    body = None if is_extern else self.parse_expression()

    return Function(
        Span(start, body.span.end if body is not None else end),
        name.value,
        parameters,
        body,
    )

Let's walk through this step by step:

Consume func and save location - We need the start location for our span
Get the function name - Must be an identifier. factorial, add, whatever
Expect ( - Function definitions always have parentheses, even with no parameters
Parse parameters - This is the interesting part. We loop until we hit ):
- Each iteration, we expect an identifier (the parameter name)
- Add it to our parameters list
- If the next token is a comma, consume it and keep going
- If not, we're done with parameters

This handles zero parameters (immediate )), one parameter (no comma), and multiple parameters (comma-separated)

Expect ) - Close the parameter list
Expect : - Separates the signature from the body. Save its location for the span
Parse the body - Here's where is_extern comes in. Extern functions have no body, so we set it to None. Regular functions parse an expression as the body
Build the Function node - The span goes from func to the end of the body (or to : for extern functions)

The parameter parsing loop is the same pattern we used for function call arguments - keep parsing items separated by commas until we hit the closing delimiter. It's a common pattern you'll see in parsers all the time.

A Note on Extern Functions

Notice the is_extern flag and the fact that body can be None. This handles extern function declarations.

Sometimes you want to call functions that aren't written in YFC. Maybe you want to call C standard library functions, or system calls. These functions are defined elsewhere - in compiled C libraries that we'll link against.

An extern declaration looks like:

extern func putchard(char) :

No body. We're just telling the compiler "there's a function called putchard that takes one parameter. Trust me, it exists." During code generation, we'll emit a call to putchard. Then when we link our compiled code with a C library that implements it, the linker finds the actual putchard implementation and wires everything up.

What's putchard? It's short for "put char double" - it takes a number (double) and prints it as an ASCII character. Since YFC only has numbers, we can't have strings or format specifiers like printf. But we can print characters: putchard(72) prints 'H', putchard(105) prints 'i'. That's enough to print text, one character at a time.

This is how YFC can interact with the outside world. Want to print output? Call putchard. Want to allocate memory? Declare extern func malloc(size) : and call it. We just need to declare them as extern, and the linker handles the rest.

Many languages don't do it this way. Python has its own print() built-in. Rust has std::println! in its standard library. These are implemented in the language itself (or in Rust's case, wrapped in Rust code that eventually calls system functions). But we're keeping YFC simple - we'll just call C functions directly.

For now, we just parse them and set body = None. We'll deal with the linking details when we get to code generation.

Top-Level Parsing

So far we've been parsing individual expressions with parse_expression(). But a real program isn't just one expression - it's multiple function definitions, maybe some top-level expressions to execute.

We need a method that parses an entire program from start to finish. Loop through all the tokens, building a list of functions:

def parse(self) -> list[Function]:
    """Parse the entire program."""
    functions = []

    while self.current._type != TokenType.Eof:
        if self.current._type == TokenType.Func:
            functions.append(self.parse_function())
        else:
            # Top-level expression - wrap it in an anonymous function
            expr = self.parse_expression()
            func = Function(expr.span, f"__anon_{len(functions)}", [], expr)
            functions.append(func)

    return functions

Keep going until we hit EOF. At each step: is this a function definition (starts with func)? Parse it as a function. Otherwise, it's a top-level expression - parse it and wrap it in an anonymous function.

Why wrap top-level expressions in functions? Because YFC only has expressions, not statements (yet). When you write 2 + 3 at the top level, or factorial(5), we need a way to execute these in sequence during code generation. Wrapping them as functions gives us a uniform interface - everything becomes a function to compile. Don't worry about the details now; it'll make sense when we get to code generation.

Before we test it, let's add a helper to print the AST tree so we can actually see what we built. We need a function that recursively walks through all the expression types and shows their structure:

def print_expr(expr: Expression, indent: int = 0) -> None:
    """Recursively print the AST structure."""
    prefix = "  " * indent

    if isinstance(expr, NumberExpr):
        print(f"{prefix}NumberExpr({expr.value.value})")

    elif isinstance(expr, IdentifierExpr):
        print(f"{prefix}IdentifierExpr({expr.value.value})")

    elif isinstance(expr, BinaryOp):
        print(f"{prefix}BinaryOp({expr.op.value})")
        print(f"{prefix}  left:")
        print_expr(expr.left, indent + 2)
        print(f"{prefix}  right:")
        print_expr(expr.right, indent + 2)

    elif isinstance(expr, CallExpr):
        print(f"{prefix}CallExpr")
        print(f"{prefix}  callee: {expr.callee.value.value}")
        print(f"{prefix}  args:")
        for arg in expr.arguments:
            print_expr(arg, indent + 2)

    elif isinstance(expr, IfExpr):
        print(f"{prefix}IfExpr")
        print(f"{prefix}  condition:")
        print_expr(expr.condition, indent + 2)
        print(f"{prefix}  then:")
        print_expr(expr.then_expr, indent + 2)
        if expr.else_expr:
            print(f"{prefix}  else:")
            print_expr(expr.else_expr, indent + 2)

This handles all our expression types. For each one, it prints the type and relevant info (like the operator or variable name), then recursively prints any sub-expressions with increased indentation.

Now test the full parser. Add this __main__ block to the bottom of parser.py:

if __name__ == "__main__":
    from lexer import Lexer

    source = """
    # Test the full parser
    func factorial(n) :
        if n < 2
            1
        else
            n * factorial(n - 1)

    func fib(n) :
        if n < 2
            n
        else
            fib(n - 1) + fib(n - 2)

    # Top-level expression
    factorial(5)
    """

    lexer = Lexer(source)
    tokens = lexer.lex()
    parser = Parser(tokens)
    functions = parser.parse()

    print("\nParsed functions:")
    for func in functions:
        print(f"\nFunction: {func.name}")
        print(f"  Parameters: {[p.value for p in func.parameters]}")
        if func.body:
            print(f"  Body:")
            print_expr(func.body, indent=2)

Run it:

$ python parser.py

Output:

Function: factorial
  Parameters: ['n']
  Body:
    IfExpr
      condition:
        BinaryOp(<)
          left:
            IdentifierExpr(n)
          right:
            NumberExpr(2)
      then:
        NumberExpr(1)
      else:
        BinaryOp(*)
          left:
            IdentifierExpr(n)
          right:
            CallExpr
              callee: factorial
              args:
                BinaryOp(-)
                  left:
                    IdentifierExpr(n)
                  right:
                    NumberExpr(1)

Function: fib
  Parameters: ['n']
  Body:
    IfExpr
      condition:
        BinaryOp(<)
          left:
            IdentifierExpr(n)
          right:
            NumberExpr(2)
      then:
        IdentifierExpr(n)
      else:
        BinaryOp(+)
          left:
            CallExpr
              callee: fib
              args:
                BinaryOp(-)
                  left:
                    IdentifierExpr(n)
                  right:
                    NumberExpr(1)
          right:
            CallExpr
              callee: fib
              args:
                BinaryOp(-)
                  left:
                    IdentifierExpr(n)
                  right:
                    NumberExpr(2)

Function: __anon_2
  Parameters: []
  Body:
    CallExpr
      callee: factorial
      args:
        NumberExpr(5)

Look at that tree. That's the entire program - recursive functions with conditionals. Every piece is there.

Check out fib(n - 1) + fib(n - 2): a BinaryOp(+) with two CallExpr nodes, each containing their own BinaryOp(-) for the arguments. The recursive calls are right there in the AST, ready to be compiled.

We didn't just parse the syntax. We built a semantic representation of what the code means. The tree structure shows the relationships between operations, the order of evaluation, everything we need to generate code later.

What We've Built

We started with arithmetic. Now we can parse:

Identifiers: variable and function names
Keywords: func, if, else, extern
Operators: arithmetic (+, -, *, /) and comparison (<, >, ==)
Comments: # to end of line
Function calls: factorial(5) with multiple arguments
Conditionals: if n < 2 1 else n * 2
Function definitions: func factorial(n) : ...
Extern declarations: extern func putchard(char) :
Spans: every expression knows its source range
Location tracking: every token knows where it came from

The frontend is complete. We can take YFC source code and turn it into an AST. We can't run anything yet - that's code generation. But we can parse the full language.

We didn't rewrite anything. Same lexer structure as Part 3 - just more token types. Same parser structure as Part 5 - just more cases in parse_primary(). The architecture scaled.

Understanding the Compiler Structure

What we just built is called the compiler frontend. Compilers are typically split into two main parts:

Frontend (what we have):

Lexer - Source code → Tokens
Parser - Tokens → AST
Semantic Analysis - Type checking, error detection (we're skipping this)

The frontend understands the source language. It knows the syntax, the grammar, what's valid and what's not. Its job is to take text and produce a structured representation.

Backend (what's next):

Code Generation - AST → Assembly/Machine Code
Optimization - Make the code faster, smaller
Linking - Combine with libraries, resolve external symbols

The backend understands the target machine. It knows x86_64 assembly, register allocation, calling conventions. Its job is to take the AST and produce executable code.

The AST is the interface between them. The frontend produces it, the backend consumes it. This separation is powerful - you can have multiple frontends (different languages) targeting the same backend (same CPU architecture), or one frontend targeting multiple backends (different CPUs).

What's Next

This was a lot. If you're feeling overwhelmed, that's normal. Go back and re-read sections. Run the code yourself. Add print statements everywhere - in parse_primary(), in parse_binary_op(), in the lexer. See the recursion happening. Watch how parse_expression() calls parse_primary() which might call parse_expression() again for nested structures. See it build the tree piece by piece.

Change the test program. Add more functions. Try nested conditionals. Break things - remove a closing paren, misspell a keyword. See what error messages you get. The best way to understand a parser is to watch it parse, and to watch it fail.

You built a compiler frontend. That's not nothing.

Next, in Part 7, we'll take stock of what we've built. We'll discuss Turing completeness - why our tiny language can theoretically compute anything. We'll talk about what's missing - mutable state, data structures, loops. We'll visualize the AST and really understand what we have.

After that? The backend. Turning these trees into assembly. That's when we get a working compiler.

Next: Part 7: Taking Stock
Previous: Part 5: Building the Parser

Writing Your First Compiler - Part 5: Building our Parser

Frederik Gram — Wed, 05 Nov 2025 12:35:15 +0000

We have tokens from the lexer. We have AST node definitions. Now we need to connect them - turn that flat list of tokens into a tree structure.

Let's build a parser.

Starting Simple

Just like with the lexer, we'll start simple. For now, we'll handle:

Numbers
Binary operations (+, -, *, /)
Parentheses for grouping

That's enough to parse expressions like (2 + 3) * 4. Once this works, adding functions and other features is straightforward - same approach, just more cases.

The Parser Structure

Let's create a file called parser.py. A parser needs to track where it is in the token list. Similar to how the lexer tracked its position in the source string, the parser tracks its position in the token list:

from lexer import Token, TokenType
from abstract import Expression, NumberExpr, BinaryOp

class ParserError(Exception):
    pass

class Parser:
    def __init__(self, tokens: list[Token]):
        self.tokens = tokens
        self.cursor = 0

    @property
    def current(self) -> Token:
        """Get the current token."""
        if 0 <= self.cursor < len(self.tokens):
            return self.tokens[self.cursor]
        return self.tokens[-1]  # EOF

    def consume(self) -> Token:
        """Consume and return the current token."""
        if 0 <= self.cursor < len(self.tokens):
            token = self.tokens[self.cursor]
        else:
            token = self.tokens[-1]
        self.cursor += 1
        return token

Simple state management. We look at current, and when we're ready, we consume() it and move forward. Same pattern as the lexer, just with tokens instead of characters.

Parsing Primary Expressions

When you see 2 + 3, there are two things being added: 2 and 3. When you see (2 + 3) * 4, there are two things being multiplied: (2 + 3) and 4. The stuff between the operators - those are what we need to parse first.

Right now, that stuff can be:

A number: 42
A parenthesized expression: (2 + 3)

Later, we'll add more:

Function calls: foo(1, 2)
Variable names: x
If expressions: if x > 0 then x else -x

Parser terminology calls these "primary" expressions. Think of them as the things operators operate on. When you see +, you need a primary on the left and a primary on the right.

def parse_primary(self) -> Expression:
    """Parse a primary expression."""
    match self.current._type:
        # Grammar: '(' expression ')'
        case TokenType.LParen:
            self.consume()
            expr = self.parse_expression()
            if self.current._type != TokenType.RParen:
                raise ParserError(f"Expected ')' but got {self.current._type}")
            self.consume()
            return expr

        # Grammar: NUMBER
        case TokenType.Number:
            token = self.consume()
            return NumberExpr(token)

        case _:
            raise ParserError(f"Unexpected token: {self.current._type}")

Look at the structure here. We check the current token type and decide what to do. Python's match statement makes this clear - each case handles one kind of primary expression.

Numbers are straightforward: consume the token, wrap it in a NumberExpr node, done.

Parentheses are more interesting. When we see (, we consume it, then call parse_expression() to handle whatever's inside. Notice we're calling parse_expression() from within the parser - that's the "recursive" in recursive descent. The expression inside could be anything: a number, another set of parentheses, a complex operation. We don't care. We just recursively parse it, check for the closing ), and return the result.

The parentheses themselves don't show up in the AST. They did their job - they forced us to parse the inside as a complete expression before continuing. The grouping is captured by the tree structure now.

The Precedence Problem

Now for the tricky part. When we see 2 + 3 * 4, we need to build this tree:

Not this tree:

The issue is operator precedence. Multiplication binds tighter than addition. We need to encode that in our parser.

Operator Precedence Table

The solution starts with a precedence table. We assign each operator a number - higher number means higher precedence. Add this to the top of parser.py, after the imports:

# Operator precedence - higher number = higher precedence
PRECEDENCE_MAP = {
    TokenType.Plus: 20,
    TokenType.Minus: 20,
    TokenType.Mul: 40,
    TokenType.Div: 40,
}

Multiplication and division (40) bind tighter than addition and subtraction (20). When we see multiple operators, we use this table to decide which one to parse first.

Why 20 and 40 instead of 1 and 2? Because it gives us room to add operators in between later. Want to add comparison operators like < that bind less tightly than addition? Use 10. Want something between addition and multiplication? Use 30. The gaps let the language grow without renumbering everything.

Precedence Climbing

The algorithm is called "precedence climbing". Here's the core idea: after parsing the immediate right side of an operator, we check what's coming next. If the next operator has higher precedence, we don't return yet - we keep extending the right side to include that higher-precedence operation.

Let's see it in code:

def parse_binary_op(self, left: Expression, op: Token) -> Expression:
    """Parse a binary operation using precedence climbing."""
    # Get the precedence of the current operator
    current_precedence = PRECEDENCE_MAP.get(op._type, 0)

    # Parse the immediate right-hand side
    right = self.parse_primary()

    # Look ahead: if next operator has higher precedence, extend the right side
    while PRECEDENCE_MAP.get(self.current._type, 0) > current_precedence:
        next_op = self.consume()
        right = self.parse_binary_op(right, next_op)

    # Build the binary operation node
    return BinaryOp(left, op, right)

The magic is in the while loop. Each time through, right gets bigger - it starts as a simple expression but grows into something more complex if higher-precedence operators appear.

Let's walk through 2 + 3 * 4 step by step:

Start in parse_expression():

Parse the first primary: 2
See + operator, consume it
Call parse_binary_op(left=2, op=+)

Inside the first parse_binary_op call (handling the +):

Current precedence is 20 (addition)
Parse the immediate right side: 3
Now right = 3
Look ahead: next token is *
Check precedence: * is 40, which is > 20
We need to extend the right side!

Enter the while loop, consume *, recursively call parse_binary_op(left=3, op=*):

Inside the second parse_binary_op call (handling the *):

Current precedence is 40 (multiplication)
Parse the immediate right side: 4
Now right = 4
Look ahead: next token is EOF
Check precedence: EOF has no precedence, so 0 < 40
Don't enter the while loop
Return BinaryOp(3, *, 4)

Back in the first parse_binary_op call:

The recursive call returned BinaryOp(3, *, 4)
Update: right = BinaryOp(3, *, 4) (no longer just 3!)
Look ahead again: next token is EOF
Exit the while loop
Return BinaryOp(2, +, BinaryOp(3, *, 4))

See what happened? We started with right = 3, but when we saw the higher-precedence *, we didn't return immediately. Instead, we extended right to be the entire 3 * 4 operation. The higher-precedence operator got parsed in a deeper recursive call, which made it appear deeper in the tree.

This is why the algorithm works: higher precedence operators get parsed in deeper (inner) recursive calls, which makes them appear deeper in the tree, which means they get evaluated first. The precedence numbers directly control tree depth.

The Entry Point

Now we need the main entry point that ties everything together:

def parse_expression(self) -> Expression:
    """Parse an expression."""
    left = self.parse_primary()

    while PRECEDENCE_MAP.get(self.current._type):
        op = self.consume()
        left = self.parse_binary_op(left, op)

    return left

This is our main entry point. We start by parsing a primary expression - that's our left side. Then we loop: as long as we see operators, we consume them and let parse_binary_op() handle the precedence logic. Each time through the loop, left becomes the full expression we've built so far. When we run out of operators, we're done.

You might wonder: why two loops? One here in parse_expression() and one in parse_binary_op()?

The loop in parse_expression() handles a sequence of operations at the same or lower precedence levels. Think 2 + 3 + 4 or 2 + 3 - 4. Each iteration builds a left-associative tree.

The loop in parse_binary_op() handles when the next operator has higher precedence than the current one. It's the lookahead that makes precedence work. It extends the right side before we return.

Together, they handle both chaining operations and precedence correctly.

Testing It

Time to see if this actually works. The real test is operator precedence - does 2 + 3 * 4 build the right tree? The multiplication should be nested deeper (evaluated first), even though addition appears first in the source.

Add this __main__ block to the bottom of parser.py:

if __name__ == "__main__":
    from lexer import Lexer

    # Test operator precedence: 2 + 3 * 4
    source = "2 + 3 * 4"
    lexer = Lexer(source)
    tokens = lexer.lex()
    parser = Parser(tokens)
    ast = parser.parse_expression()

    print(f"Expression: {source}")
    print(f"Root: {ast.op.value}")
    print(f"  Left: {ast.left.value.value}")
    print(f"  Right: BinaryOp {ast.right.op.value}")
    print(f"    Left: {ast.right.left.value.value}")
    print(f"    Right: {ast.right.right.value.value}")

Now run it:

$ python parser.py
Expression: 2 + 3 * 4
Root: +
  Left: 2
  Right: BinaryOp *
    Left: 3
    Right: 4

Perfect! The multiplication is nested under the addition, which means it gets evaluated first. Our precedence climbing algorithm is doing its job.

You can test other expressions too:

2 + 3 should build a simple addition tree
(2 + 3) * 4 should nest the addition under the multiplication (parentheses force grouping)
2 * 3 + 4 should nest the multiplication under the addition (same precedence rules, different order)

What We've Built

We now have a working parser that handles numbers, binary operations with proper precedence, and parentheses for grouping. It even reports errors when it sees unexpected tokens.

The precedence climbing algorithm scales nicely too. When we add comparison operators like < and > later, we just drop them in the precedence table with a lower number - they bind less tightly than arithmetic, so they get a lower precedence value.

The recursive descent structure keeps everything readable. Each grammar rule gets its own method. Want to add function calls? Add a case in parse_primary(). Want if expressions? Same deal - just another case.

What's Next

We've got a working parser for arithmetic expressions. The foundation is solid. Next up, we'll extend it to handle the full YFC language - function definitions, function calls, conditionals, loops.

The core structure won't change though. It's still recursive descent with precedence climbing. Check the current token, dispatch to the right handler, build the tree. Just more cases.

After that? Code generation. That's where we walk the AST and emit x86-64 assembly. That's when things get real - when we finally have a working compiler that produces actual machine code.

Next: Part 6: Extending the Parser
Previous: Part 4: Abstract Syntax Trees

Writing Your First Compiler - Part 4: Abstract Syntax Trees & Recursive Descent

Frederik Gram — Mon, 03 Nov 2025 21:17:57 +0000

Our lexer works great. It takes (2 + 3) * 4 and gives us a neat list of tokens: [LParen, Number(2), Plus, Number(3), RParen, Mul, Number(4), Eof].

But look at that list. When you see *, what does it multiply? The tokens don't say. When you see +, does it happen before or after the multiplication? The list doesn't tell you. The tokens are just sitting there in a line - no indication of what connects to what.

We need to capture that structure. We need to know that * operates on (2 + 3) and 4. We need to know that the parentheses group things, that operations have operands, that some things happen before others.

We need something better. We need trees.

What Is an AST?

All programs have structure. A function call contains arguments. An addition operation has two sides. An if statement has a condition and a body. This structure is hierarchical - it's a tree, not a list.

That's why we use trees. Each node is a piece of your program - a number, an operation, a function call. The tree structure shows how they relate.

Let's look at a simple expression: 2 + 3

As tokens:

[Number(2), Plus(+), Number(3)]

As an AST:

    +
   / \
  2   3

The + sits at the top with two children. That structure means "apply + to these two things."

A More Complex Example

Consider 2 + 3 * 4. You know from math that multiplication happens before addition. But how do we represent that?

As an AST:

Notice what's nested: the * is under the +. That's how the tree shows order - what's deeper happens first. You read bottom-up: multiply 3 and 4 (that's 12), then add 2 to that result (14). The nesting captures the precedence.

Here's that same AST represented as nested Python objects:

BinaryOp(
    op="+",
    left=Number(2),
    right=BinaryOp(
        op="*",
        left=Number(3),
        right=Number(4)
    )
)

Or even as JSON:

{
  "type": "BinaryOp",
  "op": "+",
  "left": {"type": "Number", "value": "2"},
  "right": {
    "type": "BinaryOp",
    "op": "*",
    "left": {"type": "Number", "value": "3"},
    "right": {"type": "Number", "value": "4"}
  }
}

That's it. An AST is nested objects. The Python code above? That's the tree. Each BinaryOp contains other expressions. The nesting creates the tree structure.

Why Trees?

Because programming languages are inherently nested. Expressions contain expressions. Parentheses change grouping. Functions take arguments that are themselves expressions.

Compare 2 + 3 * 4 with (2 + 3) * 4:

  (2 + 3) * 4            2 + 3 * 4

      *                      +
     / \                    / \
    +   4                  2   *
   / \                        / \
  2   3                      3   4

Same tokens, different structure, different meaning. The tree captures this.

What Makes It "Abstract"?

You might wonder why "abstract." It means we keep what matters for meaning and throw away syntax noise.

Consider parentheses in (2 + 3) * 4. They force grouping - do the addition first, then multiply. But once we've built the tree, the grouping is already in the structure. The addition is nested under the multiplication. The parentheses did their job during parsing. We don't need to remember them.

Same with whitespace. Whether you write 2+3 or 2 + 3 or even:

2
  +
    3

It means the same thing. The whitespace helps humans read the code, but it doesn't change what the code does. (In some languages like Python, whitespace can matter for indentation, but not in YFC.)

Same with syntax markers like -> in Python type hints or Rust. In func foo() -> int, the -> just says "return type comes next." It's punctuation. The compiler needs to know the return type is int, but it doesn't need to remember there was an arrow.

We keep: operations and how they nest, values (numbers, names), and location (for error messages).

We throw away: whitespace, parentheses (the tree structure already shows grouping), comments, semicolons, syntax markers.

The AST represents "what the code means", not "exactly how it was typed".

Parse Trees vs ASTs

You might have heard of parse trees. They're different from ASTs, but the distinction only matters if you're building certain kinds of tools.

A parse tree represents every single grammar rule that fired during parsing. If your grammar says "expression can be a parenthesized expression," the parse tree has a node for that rule. It remembers the parentheses, the semicolons, every bit of punctuation.

That's useful if you're building a code formatter or refactoring tool - you need to reproduce the original code exactly. But for a compiler? We don't care. We just need to know what the code means, not how it was typed.

So we build ASTs instead. They keep the structure (what's nested, what operates on what) but throw away the punctuation and formatting.

If you see "parse tree" in other tutorials, that's what they mean. We're building ASTs.

Why ASTs Matter for Compilers

An AST gives you a data structure you can actually work with. You can't easily annotate a string of source code, but you can attach type information to AST nodes. You can't transform source code without parsing it, but you can walk an AST and rewrite parts of it.

The AST is your working representation. Everything that comes after parsing - semantic analysis, type checking, optimization, code generation - operates on the AST.

Some practical benefits:

You can annotate nodes with extra information (types, scope, whatever)
You can transform the tree (optimize, inline functions, etc.)
You can walk it systematically (check that all variables are defined)
Error messages can point to exact locations (we kept the span information)

What Is Parsing?

Parsing is the process of turning tokens into an AST. The parser reads the flat list of tokens and figures out how they fit together structurally.

The parser's jobs:

Recognize patterns (number, operator, number → binary operation)
Handle precedence (multiplication before addition)
Deal with nesting (parentheses, function calls)
Build the tree correctly
Yell at you when the syntax is wrong

Parsing Techniques

There are many ways to build a parser. Here are the common ones:

Recursive Descent: Write a function for each grammar rule. Functions call each other recursively. Simple, no external tools, easy to understand and debug.

Parser Generators (yacc, bison, ANTLR): Write a formal grammar, generate parser code automatically. Powerful for complex languages, but adds tooling and makes debugging harder.

Pratt Parsing (Precedence Climbing): A particularly elegant way to parse expressions with operators. Uses "binding power" to handle precedence. We'll use this for our expression parser.

Parser Combinators: Build complex parsers by composing simple ones. Functional programming style. Popular in Haskell, Scala.

For YFC, we're using recursive descent with precedence climbing. Why?

No external tools - just Python
The code directly mirrors the language structure
Easy to modify and extend
You see exactly how it works
Handles both statements and expressions cleanly

The tradeoff is we write more code manually. But for learning, that's good.

Our AST Design

For YFC, we'll create a file called abstract.py and define AST nodes as Python classes with a base Expression class:

from lexer import Token, TokenType  # TokenType will be used in examples later

class Expression:
    """Base class for all expression nodes."""
    pass

class NumberExpr(Expression):
    """Represents a numeric literal like 42 or 3.14"""
    def __init__(self, value: Token):
        self.value = value

class BinaryOp(Expression):
    """Represents a binary operation like 2 + 3"""
    def __init__(self, left: Expression, op: Token, right: Expression):
        self.left = left
        self.op = op
        self.right = right

We use inheritance so we can refer to any expression generically as Expression. This is useful for type hints - BinaryOp takes two Expression children, which could be numbers, other operations, function calls, whatever.

The nodes store Token objects (from our lexer), not just strings. This keeps the original token information, which we'll need for error messages and later phases of the compiler.

Some nodes have fixed numbers of children (BinaryOp always has left and right). Others will be variable (CallExpr can have any number of arguments). The design is straightforward: model your language constructs as classes.

Later, we'll add span information to track source locations for error messages, but for now we're keeping it simple.

Building an AST Manually

Let's test our AST design by manually building a tree for 2 + 3 * 4. This will help us understand the structure before we write a parser to build it automatically.

Add this __main__ block to the bottom of abstract.py:

if __name__ == "__main__":
    # Manually build AST for: 2 + (3 * 4)
    ast = BinaryOp(
        left=NumberExpr(Token(TokenType.Number, "2")),
        op=Token(TokenType.Plus, "+"),
        right=BinaryOp(
            left=NumberExpr(Token(TokenType.Number, "3")),
            op=Token(TokenType.Mul, "*"),
            right=NumberExpr(Token(TokenType.Number, "4"))
        )
    )

    print("AST for: 2 + 3 * 4")
    print(f"Root operation: {ast.op.value}")
    print(f"  Left: {ast.left.value.value}")
    print(f"  Right operation: {ast.right.op.value}")
    print(f"    Left: {ast.right.left.value.value}")
    print(f"    Right: {ast.right.right.value.value}")

Now run the file:

$ python abstract.py
AST for: 2 + 3 * 4
Root operation: +
  Left: 2
  Right operation: *
    Left: 3
    Right: 4

See how the multiplication is nested under the addition? That's the precedence captured in the tree structure. We built this manually, but in the next part, the parser will build these trees automatically from tokens.

What's Next

Now you understand what ASTs are and why we need them. Programs are trees, not lists. The tree structure captures relationships, precedence, and nesting. The AST is what we'll actually work with throughout the rest of the compiler.

In the next part, we'll build the parser. We'll write code that reads tokens and constructs an AST, handling operator precedence, parentheses, and nested expressions along the way.

Next: Part 5: Building the Parser
Previous: Part 3: Lexical Analysis

Code Repository
All accompanying code for this tutorial series is available on GitHub. The repository includes complete source code for each step, example programs, and additional resources to help you follow along.

Writing Your First Compiler - Part 3: Lexical Analysis

Frederik Gram — Mon, 03 Nov 2025 15:27:20 +0000

The first step in any compiler is lexical analysis - breaking source code into tokens. When you see 2 + 3, you immediately recognize three separate things: a number, a plus sign, and another number. Your brain does this automatically. But a compiler has to explicitly walk through each character and figure out what's meaningful.

Let's say we want to tokenize this expression:

2 + 3

We need to walk through the string character by character. When we see 2, that's a number. The space doesn't mean anything. The + is an operator. Another space. Then 3 is another number.

So we end up with three tokens: NUMBER(2), PLUS(+), NUMBER(3).

That's it. That's what a lexer does - it turns a string of characters into a list of meaningful tokens.

Tokens and Lexemes

Before we start building, let's clarify what these terms actually mean. In compiler theory, a token has two parts:

Token type (sometimes called a tag): The category of the symbol. Examples: NUMBER, IDENTIFIER, PLUS, LPAREN. This tells you what kind of thing you're looking at.

Lexeme (sometimes called the value): The actual substring from the source code that produced the token. Examples: "42", "+", "foo". This is the literal text.

When we say NUMBER(2), we're saying: "This is a token with type NUMBER and lexeme "2"". The type tells the parser how to use it. The lexeme tells us what it actually was in the source.

Some tokens have meaningful lexemes - like numbers (42) or identifiers (factorial). Others don't - the + token's lexeme is just "+", which doesn't tell you anything the type doesn't already say.

Why separate them? Because the parser mostly cares about types. When parsing 2 + 3, the parser just needs to know "number, plus, number" to understand the structure. The actual values (2 and 3) only matter later when we're generating code or evaluating the expression.

Starting Simple

Before building the entire lexer we should discuss how implementation is going to work in our compiler. We'll implement features one-by-one, meaning that although YFC will eventually have if-else control structures, for-loops and similar, the best way to not get overwhelmed when building your first compiler is taking it one step at a time.

With that in mind, we'll build a lexer that handles basic arithmetic: numbers, +, -, *, /, and parentheses. That's enough to tokenize expressions like (2 + 3) * 4. Once we have this working, we can add more features later.

Building the Lexer

Let's start coding. Create a new file called lexer.py - this will be the first real piece of our compiler.

The lexer needs to do two things: recognize what kind of thing each piece of text is (a number? an operator?), and package that information up so the rest of the compiler can use it. That means we need to define what a "token" looks like before we can write code that produces them.

Defining Tokens

First, we need a way to represent tokens. A token needs a type (is it a number? an operator?) and a value (what number? which operator?).

from enum import Enum, auto
from dataclasses import dataclass

class TokenType(Enum):
    Number = auto()
    Plus = auto()
    Minus = auto()
    Mul = auto()
    Div = auto()
    LParen = auto()
    RParen = auto()
    Eof = auto()

@dataclass
class Token:
    _type: TokenType
    value: str

We use an Enum for token types because it gives us type safety and clear naming. You can't accidentally use "Plus" (a string) where you meant TokenType.Plus - the type checker will catch that. It also prevents typos and makes the code self-documenting.

For the Token itself, I use a dataclass because it's just pure data - no behavior, just values we want to store. Dataclasses give us a clean __init__, __repr__, and equality checking for free.

Note that not all tokens have meaningful values. The + token's value is just "+", but a number token like 42 has the actual number as its value.

The Lexer Structure

Now let's build the lexer itself. The core idea is simple: maintain a position in the source string, look at the current character, and decide what to do with it.

class Lexer:
    def __init__(self, source: str):
        self.source = source
        self.tokens: list[Token] = []
        self.cursor = 0

We need three things:

source: The code we're tokenizing
tokens: Where we'll store the tokens we find
cursor: Our position in the source string

This is our state. Everything the lexer needs to know is captured here.

Helper Methods

Before we start lexing, let's create some utility methods to make our life easier:

@property
def current(self) -> str:
    """Return the current character or EOF marker."""
    if 0 <= self.cursor < len(self.source):
        return self.source[self.cursor]
    return "\0"

def increment(self):
    """Move to the next character."""
    self.cursor += 1

def push_token(self, token_type: TokenType, value: str):
    """Add a token to our list."""
    self.tokens.append(Token(token_type, value))

The current property gives us the character we're looking at. When we've read everything, it returns \0 - a sentinel value that means "end of input". This is cleaner than checking bounds everywhere.

The increment() method just moves us forward one character. You might think this is overkill - why not just do self.cursor += 1 directly? Two reasons: First, it makes the code more readable. Second, later we'll expand this to track line and column numbers for error messages, and having it in one place makes that easy.

The push_token() method creates a token and adds it to our list. Again, we could just append directly, but wrapping it in a method gives us a place to add debugging, validation, or extra tracking later.

The Main Loop

Now for the actual lexing. The strategy is simple: loop through characters one by one, figure out what each character starts (a number? an operator?), and handle it accordingly.

def lex(self) -> list[Token]:
    while self.current != '\0':
        # Skip whitespace
        if self.current.isspace():
            self.increment()
            continue

        # Recognize numbers
        if self.current.isdigit():
            start = self.cursor
            while self.current.isdigit():
                self.increment()

            self.push_token(TokenType.Number, self.source[start:self.cursor])
            continue

        # Recognize operators and parentheses
        single_char_tokens = {
            '(': TokenType.LParen,
            ')': TokenType.RParen,
            '+': TokenType.Plus,
            '-': TokenType.Minus,
            '*': TokenType.Mul,
            '/': TokenType.Div,
        }

        if token_type := single_char_tokens.get(self.current):
            self.push_token(token_type, self.current)
            self.increment()
            continue

        raise Exception(f"Unexpected character: '{self.current}'")

    # Add EOF token
    self.push_token(TokenType.Eof, "")
    return self.tokens

Let's break this down:

Whitespace: We check for whitespace first because it's the most common thing we want to ignore. Spaces, tabs, newlines - they separate tokens but aren't tokens themselves. We just skip over them.

Numbers: When we see a digit, we don't just read one character. We keep reading digits until we hit something that isn't a digit. That's how we handle multi-digit numbers like 42 or 1337. We save the starting position, read all the digits, then slice out that substring and make it a token.

Single-character tokens: Operators and parentheses are all one character, so we use a dictionary to map from the character to its token type. If we find it in the dictionary, we make that token and move on. This is cleaner than a long chain of if/elif statements.

Unknown characters: If we see something that isn't whitespace, a digit, or an operator, we error out. This catches typos and unsupported syntax early.

EOF token: At the end, we add an EOF (end-of-file) token. This tells the parser "that's all the input". Without it, the parser would have to constantly check if there are more tokens. With it, the parser can just look for EOF.

Testing It

Let's try it out:

if __name__ == "__main__":
    source = "(2 + 3) * 4"
    lexer = Lexer(source)
    tokens = lexer.lex()

    print(f"Tokenizing: {source}\n")
    for token in tokens:
        print(f"{token._type.name}({token.value})")

Run it:

$ python lexer.py
Tokenizing: (2 + 3) * 4

LParen(()
Number(2)
Plus(+)
Number(3)
RParen())
Mul(*)
Number(4)
Eof()

Perfect. We just built a working lexer in about 50 lines of code.

Adding Debug Information

Before we move on, let's add something important: location tracking. An essential part of any compiler is its ability to tell developers where they've made a mistake. While we're just starting out with the basics, we'll spend a little bit of time now implementing debug information which will prove invaluable later on.

Right now, if we hit an unexpected character, we just say "Unexpected character: 'x'". But in a real program with hundreds of lines, that's useless. We need to know where the error is - which line and column.

First, let's add a Location type to track position:

@dataclass
class Location:
    row: int
    column: int

And update our Token to include it:

@dataclass
class Token:
    location: Location
    _type: TokenType
    value: str

Now we need to track row and column as we lex. Add these to the lexer's __init__:

class Lexer:
    def __init__(self, source: str):
        self.source = source
        self.tokens: list[Token] = []
        self.cursor = 0
        self.row = 0
        self.column = 0

The trick is in increment(). When we move to the next character, we need to check if it's a newline:

def increment(self):
    """Move to the next character."""
    if self.current == '\n':
        self.row += 1
        self.column = 0
    else:
        self.column += 1
    self.cursor += 1

If we hit a newline, increment the row and reset the column to 0. Otherwise, just increment the column. Simple, but effective.

Now update push_token() to include the location:

def push_token(self, token_type: TokenType, value: str):
    """Add a token to our list."""
    token = Token(
        Location(self.row, self.column - len(value) + 1),
        token_type,
        value,
    )
    self.tokens.append(token)

Note the self.column - len(value) + 1 - we've already advanced past the token, so we need to calculate where it started. For a number like 42, when we create the token, we're sitting just after the 2, so we subtract the length to get back to where the 4 was.

Finally, update the EOF token in lex():

# Add EOF token
self.tokens.append(Token(Location(self.row, self.column), TokenType.Eof, ""))
return self.tokens

Now when we have an error, we can do:

raise Exception(f"Unexpected character '{self.current}' at row {self.row}, column {self.column}")

Much better. Try lexing something with an error:

source = "2 + @ + 3"
lexer = Lexer(source)
tokens = lexer.lex()  # Error: Unexpected character '@' at row 0, column 4

Perfect. Now we know exactly where the problem is.

What We've Built

This is a simple lexer, but it's real. It handles the core concepts you'll find in every lexer:

State management (cursor position, row/column tracking)
Character-by-character scanning
Pattern recognition (digits vs operators)
Token generation with location information

The pattern we've established - checking character type and dispatching to the right handler - scales to much more complex languages. When we add support for keywords like func and if, we'll use the same approach: check if we're looking at a letter, read the whole identifier, then check if it's a keyword.

What's Next

Our lexer can break expressions into tokens with proper error reporting, but it doesn't understand what they mean. It doesn't know that * should happen before +, or that parentheses group things together.

That's the parser's job. The parser takes this flat list of tokens and builds a tree structure that represents the actual meaning of the expression - an Abstract Syntax Tree (AST).

We'll build that next.

Next: Part 4: Abstract Syntax Trees & Recursive Descent
Previous: Part 2: What Is a Compiler?

Writing Your First Compiler - Part 2: What Is a Compiler?

Frederik Gram — Sun, 02 Nov 2025 19:42:17 +0000

Before we dive into writing code, let's demystify what a compiler actually does. At its core, a compiler is just a program that translates source code from one language to another. Most commonly, it translates from a high-level programming language (like our YFC language) to something your computer can execute.

Think of compilation as a series of translations, each step getting closer to what your CPU understands:

Let's start with this simple recursive implementation of the Fibonacci sequence in C.

int fib(int n) {
    if (n <= 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

int main() {
    return fib(10);
}

This code should be relatively easy to understand for someone who's familiar with programming or at least has been introduced to the concept of recursion. But if you write this code, you still have to compile it before you can use it, why?

The answer is quite simple, your CPU doesn't actually understand C.

Your processor has no idea what int fib(int n) means or what if (n<=1) is supposed to do. At the hardware level, your CPU only understands the very basic instructions like 'move this number from memory into a register' or 'add these two numbers together.'

So when you write return fib(n - 1) + fib(n - 2); That single line needs to be translated into dozens of simple CPU instructions that handle things like:

Subtracting 1 from n
Calling the function recursively
Storing the result somewhere
Subtracting 2 from the original n
Calling the function again
Adding those two results together
Returning the final value

Phew, that's quite a lot. Which is why we rely on compilers to undertake this job of bridging the gab between the code you want to write, and the instructions your CPU can actually execute.

Let's see what this looks like in practice. If you compile our Fibonacci function with GCC (targeting x86–64 architecture) using -O0 flag (which disables optimizations for clarity), here's what the compiler actually produces:

fib:
        push    rbp
        mov     rbp, rsp
        push    rbx
        sub     rsp, 24
        mov     DWORD PTR [rbp-20], edi
        cmp     DWORD PTR [rbp-20], 1
        jg      .L2
        mov     eax, DWORD PTR [rbp-20]
        jmp     .L3
.L2:
        mov     eax, DWORD PTR [rbp-20]
        sub     eax, 1
        mov     edi, eax
        call    fib
        mov     ebx, eax
        mov     eax, DWORD PTR [rbp-20]
        sub     eax, 2
        mov     edi, eax
        call    fib
        add     eax, ebx
.L3:
        mov     rbx, QWORD PTR [rbp-8]
        leave
        ret
main:
        push    rbp
        mov     rbp, rsp
        mov     edi, 10
        call    fib
        pop     rbp
        ret

Don't worry if this looks intimidating, the key point is that our simple 4-line C function became over a dozen assembly instructions, each doing one very specific thing that your CPU can understand.

But it doesn't quite stop here. Assembly is still human-readable text. What your CPU actually understands is machine code - raw binary instructions, just 1s and 0s.

The program that converts assembly into machine code is called an assembler, and despite the cool name, it's essentially just another compiler. Instead of translating C to assembly, it translates assembly to machine code.

Compilation vs. Translation
You might've heard terms like compiler, transpiler, interpreter, and assembler thrown around. they all involve converting code from one form to another, but there are some useful distinctions. This section can be skimmed over or very briefly read, it is not going to be important to developing our compiler, but it can serve as a good reference. It is important to note that these definitions are very loose, and in many ways just don't matter too much:

Compiler: Typically refers to a program that translates code from a high-level language to a lower-level language. This usually means going from something human-friendly (like C, Rust, or our YFC language) to something closer to what the machine understands (like assembly, machine code, or some intermediate representation). But it's also very common to see compilers translate source code into C - the key characteristic is that you're generally moving down the abstraction ladder, with the target language being at a lower level than the source language.

Transpiler: A program that translates code from one high-level language to another high-level language, typically at roughly the same level of abstraction. TypeScript to JavaScript is a classic example - both are high-level languages, neither is really "closer to the metal" than the other. The same goes for tools like Babel that convert modern JavaScript to older JavaScript syntax, or compilers that convert SASS to CSS. Unlike compilers that move down the abstraction ladder, transpilers generally move horizontally - the source and target languages are at similar levels of abstraction, they're just different languages or different versions of the same language.

Assembler: A program that converts assembly language into machine code. As we saw earlier, assembly language uses human-readable mnemonics like movq and addl, but your CPU needs these translated into raw binary instructions. The assembler handles this final step of translation. While we often give it a special name, an assembler is really just a very simple compiler - it's doing the same translation job, just with an almost 1:1 mapping between assembly instructions and machine code bytes. Each assembly instruction typically corresponds directly to a single machine instruction, which makes the assembler's job much more straightforward than a full compiler like GCC.

Interpreter: A program that executes source code directly without producing a standalone executable. Python is a classic example - when you run a Python script, the interpreter reads and executes your code. While Python does compile to an intermediate bytecode representation (those .pyc files you might have seen), it still interprets that bytecode rather than converting it all the way to machine code. Languages like Java work similarly with the JVM. We'll talk more about intermediate representations and bytecode in a later section.

JIT (Just-In-Time) Compiler: A hybrid approach that combines interpretation and compilation. Modern JavaScript engines (like V8 in Chrome) and the Java Virtual Machine use JIT compilation. The idea is that code starts being interpreted for fast startup, but as the program runs, the JIT compiler identifies "hot" code paths - sections that run frequently - and compiles those to optimized machine code on the fly. This gives you the flexibility of interpretation with the performance of compilation where it matters most. It's called "just-in-time" because the compilation happens right when (or just before) the code is needed, rather than ahead of time

What We're Building
In this tutorial, we're building a true compiler. YFC is a high-level language with functions, conditionals, and loops - abstractions that make it easy for humans to express logic.

x86–64 assembly, on the other hand, is very low-level - it's essentially a thin layer of readable text over raw machine instructions. By translating from YFC down to assembly, we're moving down that abstraction ladder we talked about, doing the same fundamental job that compilers like GCC and Clang do.

Our pipeline is going to look like this:
YFC source code → (our compiler) → x86–64 assembly → (assembler) → machine code

We're responsible for the first and hardest step: taking high-level abstractions and breaking them down into the simple instructions a CPU can execute. The assembler handles the final mechanical translation to binary.

Next: Part 3: Lexical Analysis
Previous: Part 1: Introduction

Writing Your First Compiler - Part 1: Introduction

Frederik Gram — Sun, 02 Nov 2025 19:41:16 +0000

Compilers used to feel like magic to me. Not the fun kind of magic, but the intimidating kind - like something only computer science wizards could understand. Maybe it was that dragon on the cover of Aho's famous compiler textbook, or because I associated compilers with the likes of Ken Thompson and Bjarne Stroustrup.

Today many amazing tutorials exist that guide the developer all the way from opening their first text editor to outputting machine code, but I feel like many of them either leave you with a trivial implementation that's hard to extend into a truly interesting language, or are too complex to be your first experience.

Why This Tutorial?
This tutorial is inspired by the excellent LLVM Kaleidoscope tutorial for C++, but with some key differences:

Python instead of C++: More accessible syntax, faster iteration
x86-64 assembly output: LLVM isn't the first step - learning to work with registers, calling conventions, and assembly gives you foundational knowledge that makes tools like LLVM much more meaningful
And most importantly, a code-structure that is easily extensible and won't fall apart once you try to take it to the next step

What We're Building
We'll be creating a compiler for YFC (Your First Compiler), a simple functional language with functions, conditionals, loops, and arithmetic. Here's what a factorial function looks like in YFC:

# Computes the factorial of n using a simple recursive definition:
func factorial(n) :
 if n < 2
   1
 else
   n * factorial(n - 1)

It's minimal but powerful enough to write interesting programs - and more importantly, simple enough that we can focus on understanding how compilers work rather than getting lost in language complexity.

You don't have to finish this entire tutorial to get value from it. You can stop at any stage and walk away with a cool little project to tinker with. The farther you go, the deeper we'll dive into advanced topics like compiler optimizations, register allocation algorithms, and type systems - but don't worry about any of that yet.

Next: Part 2: What Is a Compiler?