Chapter 3: Grammar and a first parser

This chapter:

Meet Muspel's grammar, written formally as EBNF, piece by piece.
Design the AST: one distinct node type per construct, each carrying its own span.
Hand-write a recursive-descent parser for statements and simple expressions, enough to parse var x = 1 / print(x)-shaped programs.
Grow musc parse, printing the AST as an indented tree.

Where we left off: musc lex turns a .mus file into a correct, spanned token stream. Nothing yet understands how those tokens fit together.

3.1 Why recursive descent

A parser's job is to turn a flat token stream into a tree that reflects the structure the tokens imply: 1 + 2 isn't just three tokens in a row, it's a + with two operands. Recursive descent is the technique this book uses to build that tree: one procedure per grammar rule, each calling the procedures for the rules it references, the parse tree falling directly out of the call stack as the procedures recurse into each other.

Design decision: recursive descent, not a parser-generator or a combinator library. Alternatives considered: a parser generator (yacc/ANTLR-style, generating parsing tables from a grammar file), a parser-combinator library (composing small parsing functions with combinators like many, or, then). Trade-off: a generator or combinator library can express some grammars more tersely and catches certain classes of grammar ambiguity mechanically, at the cost of a build-time code generation step (for a generator) or a genuinely third-party dependency (for a combinator library), either of which this book's "only what Odin ships" rule already rules out. Recursive descent's real cost is verbosity: one procedure per rule, however small the rule. Choice: recursive descent, and not only because it's the only option that fits the constraint. It mirrors the grammar directly enough that a reader can set a breakpoint in parse_if_stmt and be looking at exactly the code that parses if statements, nothing more, nothing generated. This is also what real production parsers reach for over generators for precisely this readability reason: rustc's early parsing stages and CPython's parser (before its PEG rewrite) are both hand-written recursive-descent parsers.

3.2 Muspel's grammar, so far

Grammar rules are shown as EBNF throughout this book, collected in full in Appendix A. Here's everything this chapter's parser handles:

program     ::= declaration* EOF ;
declaration ::= varDecl | statement ;
varDecl     ::= "var" IDENT ( "=" expression )? ";" ;

statement   ::= exprStmt | ifStmt | whileStmt | block ;
exprStmt    ::= expression ";" ;
ifStmt      ::= "if" "(" expression ")" block ( "else" ( ifStmt | block ) )? ;
whileStmt   ::= "while" "(" expression ")" block ;
block       ::= "{" declaration* "}" ;

expression  ::= primary ;
primary     ::= NUMBER | STRING | "true" | "false" | "nil"
              | IDENT | "(" expression ")" ;

(Chapter 4 splits declaration in two once funcDecl exists: a func is legal directly inside program, but not inside a block. This chapter's grammar doesn't need the split yet, since it has no funcDecl at all.)

expression is deliberately thin for now, just primary: a literal, a name, or a parenthesised expression. Chapter 4 grows it into the real thing, operators, precedence, and function calls. That's enough already to parse real (if arithmetic-free) programs: var x = 1, print(x), while (running) { print(x) }, and so on.

That trailing ";" in varDecl and exprStmt is real, the parser genuinely does consume(.Semicolon, ...) at both those points, but section 2.6 already showed why it's rarely something a reader types: the lexer inserts that Semicolon token automatically at the end of almost every line. The grammar is written with an explicit ; because that's what the parser consumes; it says nothing about who, lexer or human, put it there.

There is one relaxation, and it is worth stating now because it decides how a block may be laid out. A statement's terminating semicolon may be omitted immediately before a closing }. This is the second half of Go's own semicolon rule (the lexer's newline insertion from section 2.6 is the first half), and both varDecl and exprStmt honour it through a small helper rather than a bare consume:

consume_statement_end :: proc(p: ^Parser, message: string) {
	if match(p, .Semicolon) do return
	if check(p, .Right_Brace) do return   // '}' stands in for the terminator; parse_block consumes it
	consume(p, .Semicolon, message)        // otherwise it's a genuine "missing ;"
}

Without this, a whole block body written on one line, if (x < 0) { x = -x }, would fail to parse: the lexer only inserts a semicolon at a newline, and there is no newline between x = -x and the }, so the statement would run straight into the brace. With it, x = -x is terminated by the } the block is about to consume, and the one-line form works. Note the deliberate limit: the relaxation applies only before a } (and so only inside a block), never at top level, and it does not touch struct or array literals, whose } is parsed on a different path entirely (Chapter 5). It also does not introduce a one-line if without braces, which the next box explains Muspel still refuses.

Why require blocks, not bare statements, for if/while bodies? ifStmt and whileStmt both demand a block, { ... }, rather than allowing a single bare statement the way C does (if (x) print(x);). This sidesteps the classic dangling else ambiguity (which if does a trailing else belong to, in if (a) if (b) x(); else y();?) by construction, and it means every control-flow body is a Stmt_Block uniformly, which the Chapter 11 compiler's jump patching leans on directly. The cost is that Muspel has no one-line if without braces; a small, defensible trade for a parser (and later, a compiler) with one fewer edge case.

Gotcha: } else { has to stay on one line. ends_statement (section 2.6) says a Right_Brace can end a statement, which it usually should: after the closing } of a while body, a newline really does mean "that statement's over." But an if's then branch closes with a } too, and if else starts on the next line, the lexer has no way to know a trailing else is coming: it sees a Right_Brace, then a newline, and inserts a Semicolon, which ends the if statement right there and leaves a stray else for the parser to choke on. The fix is layout, not code: write } else { cuddled on one line, the same convention Go enforces for exactly this reason. Chapter 4's error-recovery section shows what the parser actually does when this bites.

3.3 The AST: one type per construct

Muspel's AST is not a single generic Node struct with an any-typed payload; it's a family of distinct structs, one per construct, grouped into two tagged unions:

Expr :: union {
	^Expr_Literal,
	^Expr_Ident,
	^Expr_Group,
	^Expr_Unary,
	^Expr_Binary,
	^Expr_Logical,
	^Expr_Call,
	^Expr_Assign,
}

Stmt :: union {
	^Stmt_Var,
	^Stmt_Func,
	^Stmt_Expr,
	^Stmt_If,
	^Stmt_While,
	^Stmt_Return,
	^Stmt_Block,
}

(A few of these, Expr_Unary, Expr_Call, Expr_Assign, Stmt_Func, Stmt_Return, belong to Chapter 4; they're declared here because Odin unions are declared whole, not extended incrementally, but this chapter's parser doesn't produce them yet.)

Every node carries a line: int, its span's start, exactly as every Token does. A representative pair:

Expr_Literal :: struct {
	line:  int,
	value: Literal_Value, // union{f64, string, bool}; nil for the Nil literal
}

Stmt_Var :: struct {
	line:  int,
	name:  string,
	init:  Expr, // nil union value if there was no initialiser
	depth: int,  // filled in by the Chapter 7 resolver; -1 until then
	slot:  int,
}

Why not one generic Node type? A single Node struct with a kind tag and an any (or a big union of every possible field) payload is less code to declare up front, and it's a real pattern in some parsers. The cost shows up immediately in every later pass: switch node.kind gives you no compiler help if you forget a case, and every field access needs a manual type assertion out of the any. With Muspel's per-construct structs, switch node in expr is an Odin tagged-union switch: the compiler can (and, with #partial deliberately omitted, does) insist every case is handled, and each case ^Expr_Binary: block gets node.op, node.left, node.right as real typed fields, not payload to unpack. For a book about understanding every line, that compiler-checked exhaustiveness is worth the extra struct declarations.

depth/slot on Stmt_Var (and, from Chapter 4, Expr_Ident, Expr_Assign) are worth flagging now even though nothing sets them yet: they're where Chapter 7's resolver will record which scope a name belongs to and which slot within it, information the parser has no way to know (it hasn't seen the rest of the program yet) but the AST needs a place to hold. They default to -1, unresolved, until then.

3.4 A first parser

Parser is a cursor over the token slice musc lex already knows how to produce, plus a list of errors found along the way:

Parser :: struct {
	tokens: []Token,
	pos:    int,
	errors: [dynamic]Parse_Error,
}

The core helpers mirror the lexer's peek/advance/match almost exactly, one level up: peek looks at the current token, advance consumes it, match consumes it only if it's the kind the caller wants. parse_program is the entry point, looping over top-level declarations until the token stream runs out:

parse_program :: proc(p: ^Parser, allocator := context.allocator) -> []Stmt {
	stmts := make([dynamic]Stmt, allocator)
	for !is_at_end(p) {
		s := parse_declaration(p, allocator)
		if s != nil do append(&stmts, s)
	}
	return stmts[:]
}

(This chapter's version doesn't yet recover from a bad token the way the final one does; that's Chapter 4's job. For now, a malformed program can still produce a garbled tree, just not a crash, since consume always returns some token even when it's not the one it expected.)

parse_var_decl, parse_if_stmt, parse_while_stmt and parse_block each follow the grammar rule they implement almost line for line. parse_if_stmt is representative:

parse_if_stmt :: proc(p: ^Parser, allocator: runtime.Allocator) -> Stmt {
	line := previous(p).line
	consume(p, .Left_Paren, "expected '(' after 'if'")
	cond := parse_expression(p, allocator)
	consume(p, .Right_Paren, "expected ')' after if condition")
	then_branch := parse_block(p, allocator)

	else_branch: Stmt
	if match(p, .Else) {
		if check(p, .If) {
			advance(p)
			else_branch = parse_if_stmt(p, allocator)
		} else {
			else_branch = parse_block(p, allocator)
		}
	}

	node := new(Stmt_If, allocator)
	node^ = Stmt_If{line = line, cond = cond, then_branch = then_branch, else_branch = else_branch}
	return node
}

else if chains fall out for free: an else immediately followed by if recurses into parse_if_stmt again rather than requiring its own grammar rule.

Expressions, for now, are just parse_primary: a literal, an identifier, or a parenthesised group:

parse_expression :: proc(p: ^Parser, allocator: runtime.Allocator) -> Expr {
	return parse_primary(p, allocator)
}

parse_primary switches on the next token's kind and builds the matching leaf node:

case .Ident:
	advance(p)
	node := new(Expr_Ident, allocator)
	node^ = Expr_Ident{line = tok.line, name = tok.lexeme, depth = -1, slot = -1}
	return node

case .Left_Paren:
	advance(p)
	inner := parse_expression(p, allocator)
	consume(p, .Right_Paren, "expected ')' after expression")
	node := new(Expr_Group, allocator)
	node^ = Expr_Group{line = tok.line, inner = inner}
	return node

3.5 `musc parse`: printing the tree

musc parse lexes, parses, and pretty-prints the resulting AST as an indented tree, one node per line, children indented two spaces under their parent:

./run.sh parse examples/hello.mus

Var greeting
  Literal "hello, muspel"
ExprStmt
  Call
    Ident print [depth=-1 slot=-1]
    Ident greeting [depth=-1 slot=-1]

(That Call node is Chapter 4's; hello.mus calls print, so it's a fair preview of where expressions are headed. This chapter's parser alone can't yet produce it, since it can't yet parse function calls, only the simpler examples in this section's exercises.) The [depth=-1 slot=-1] tags on every Ident are the resolver annotations from section 3.3, visibly unresolved: that's exactly what Chapter 7 fills in.

The printer itself is a straightforward recursive walk, a switch node in stmt (or expr) with one case per AST type, printing the node's own line and recursing into its children one indent level deeper, the same shape the parser itself uses to build the tree in the first place.

Checkpoint

musc parse correctly parses variable declarations, blocks, if/else, while, and simple expression statements built from literals, names and parenthesised groups, printing a readable indented AST for each.

Exercises

Parse var x = (1) and confirm the printed tree shows a Group node wrapping the literal, not just the literal on its own; explain in a sentence why the parentheses still show up in the tree even though they don't change the program's meaning.
Parse a file with a nested if/else if/else chain and confirm the tree's shape matches your mental model of which else binds to which if.
Try parsing var x = 1 + 2. It won't work yet (there's no operator support until Chapter 4); read the parse error musc parse reports and confirm you understand exactly which rule in section 3.2's grammar has nothing to say about +.