Writing a Simple Compiler: Lexers and Parsers Explained

Every compiler and interpreter, from GCC to a JSON parser to your JavaScript engine, starts with the same two stages: turning raw text into tokens, then turning tokens into a structured tree. Building a tiny one for a simple arithmetic expression demystifies the whole pipeline.

Stage 1: The Lexer (Tokenizing)

The lexer’s job is turning a flat string into a stream of meaningful tokens, discarding whitespace and classifying each chunk:

import re

TOKEN_SPEC = [
    ('NUMBER',   r'\d+'),
    ('PLUS',     r'\+'),
    ('MINUS',    r'-'),
    ('TIMES',    r'\*'),
    ('LPAREN',   r'\('),
    ('RPAREN',   r'\)'),
    ('SKIP',     r'[ \t]+'),
]

def tokenize(text):
    tokens = []
    pos = 0
    while pos < len(text):
        for kind, pattern in TOKEN_SPEC:
            match = re.match(pattern, text[pos:])
            if match:
                if kind != 'SKIP':
                    tokens.append((kind, match.group()))
                pos += len(match.group())
                break
        else:
            raise SyntaxError(f"Unexpected character at position {pos}")
    return tokens

tokenize("3 + 4 * (2 - 1)")
# [('NUMBER','3'),('PLUS','+'),('NUMBER','4'),('TIMES','*'),
#  ('LPAREN','('),('NUMBER','2'),('MINUS','-'),('NUMBER','1'),('RPAREN',')')]

Stage 2: The Parser (Building an AST)

The parser consumes tokens and builds a tree that respects operator precedence — * binding tighter than +/-, exactly as a human would expect:

class Parser:
    def __init__(self, tokens):
        self.tokens = tokens
        self.pos = 0

    def peek(self):
        return self.tokens[self.pos] if self.pos < len(self.tokens) else None

    def consume(self):
        tok = self.tokens[self.pos]
        self.pos += 1
        return tok

    def parse_expr(self):  # handles + and -
        node = self.parse_term()
        while self.peek() and self.peek()[0] in ('PLUS', 'MINUS'):
            op = self.consume()
            node = ('binop', op[1], node, self.parse_term())
        return node

    def parse_term(self):  # handles *, binds tighter than + / -
        node = self.parse_factor()
        while self.peek() and self.peek()[0] == 'TIMES':
            op = self.consume()
            node = ('binop', op[1], node, self.parse_factor())
        return node

    def parse_factor(self):
        kind, value = self.consume()
        if kind == 'NUMBER':
            return ('num', int(value))
        elif kind == 'LPAREN':
            node = self.parse_expr()
            self.consume()  # closing paren
            return node

Stage 3: Evaluating the Tree

def evaluate(node):
    if node[0] == 'num':
        return node[1]
    _, op, left, right = node
    l, r = evaluate(left), evaluate(right)
    return {'+': l + r, '-': l - r, '*': l * r}[op]

tokens = tokenize("3 + 4 * (2 - 1)")
tree = Parser(tokens).parse_expr()
print(evaluate(tree))  # 7 — correctly respects precedence

Real compilers add many more stages (type checking, optimization, code generation), but the lexer-then-parser foundation is identical — understanding these ~60 lines demystifies a huge amount of what a “real” compiler is actually doing.