building a compiler frontend in go

why write a compiler

compilers are the most educational programs you can write. lexers teach you string processing and state machines. parsers teach you recursive descent and grammar. the AST teaches you tree traversal and visitor patterns.

i built a compiler frontend for a small expression language in go.

the lexer

the lexer turns a stream of characters into a stream of tokens.

type TokenType int

const (
    TOK_NUMBER TokenType = iota
    TOK_PLUS
    TOK_MINUS
    TOK_STAR
    TOK_SLASH
    TOK_LPAREN
    TOK_RPAREN
    TOK_EOF
)

type Token struct {
    Type    TokenType
    Lexeme  string
    Line    int
}

the parser

i used recursive descent — one function per grammar rule. the grammar for expressions:

expr   → term (("+"|"-") term)*
term   → factor (("*"|"/") factor)*
factor → NUMBER | "(" expr ")"

func (p *Parser) expr() Node {
    left := p.term()
    for p.match(TOK_PLUS, TOK_MINUS) {
        op := p.previous()
        right := p.term()
        left = BinaryNode{Left: left, Op: op, Right: right}
    }
    return left
}

the AST

the abstract syntax tree is just a tree of nodes. each node type represents a language construct. walking the tree with a visitor generates code, evaluates expressions, or checks types.