Parsing & ASTs: Structure Over Text

Why this module exists

Parsing gives shape to tokens. We will build a small expression parser and produce an AST. This AST becomes the shared structure for later stages.

1) Grammar for our tiny language

We will parse expressions with precedence and function calls:

expr       -> equality

equality   -> comparison ( ("==" | "!=") comparison )*
comparison -> term ( ("<" | "<=" | ">" | ">=") term )*
term       -> factor ( ("+" | "-") factor )*
factor     -> unary ( ("*" | "/") unary )*

unary      -> ("!" | "-") unary | primary
primary    -> NUMBER | IDENT | "(" expr ")" | call
call       -> IDENT "(" args? ")"
args       -> expr ( "," expr )*

This grammar encodes precedence and left associativity.

2) Recursive descent is readable

Each grammar rule becomes a function. The order of functions matches precedence.

Example (sketch):

func parseTerm() Expr {
    left := parseFactor()
    for match("+", "-") {
        op := previous()
        right := parseFactor()
        left = Binary(op, left, right)
    }
    return left
}

The loop handles left associativity cleanly.

3) AST shape we will use

We keep one struct with a Kind and fields:

• Number: value
• Ident: name
• Unary: operator + operand
• Binary: operator + left/right
• Call: function name + args

This keeps the code simple and testable.

4) Error handling

Good parse errors are precise and short:

• "expected ')'" instead of "parse failed"
• include the token that caused the issue

Readable errors make the language easier to learn.