Chapter 4: Precedence, operators, and error recovery

This chapter:

See why naive recursive descent can't handle operator precedence directly.
Build a precedence-climbing expression parser: one loop, one binding-power table, every operator Muspel needs.
Add function declarations and call syntax, calls falling out of the same postfix loop as any future field or index access would.
Replace "stop at the first syntax error" with panic-mode recovery: skip to the next likely statement boundary and keep going, so one pass reports every error in a file.

Where we left off: musc parse handles statements and grammar without operators: literals, names, groups, if/while/blocks. 1 + 2 doesn't parse yet.

4.1 The problem with naive recursive descent and operators

Try teaching last chapter's parse_primary-only expression parser about + the obvious way, add a case that, after parsing a primary, checks for a + and recursively parses another expression, and precedence breaks immediately: 2 + 3 * 4 would parse as (2 + 3) * 4 unless something somewhere knows that * binds tighter than +. Naively recursive grammar rules (one rule per precedence level, each calling down to the next-tighter level) can express this correctly, but it means one parsing procedure per precedence level: one for ||, one for &&, one for equality, one for comparison, one for +/-, one for *//, each nearly identical, differing only in which operators they accept and which procedure they call next. Adding one new operator means adding, or at least touching, an entire procedure.

4.2 Precedence climbing

Precedence climbing (a simplified form of Pratt parsing) replaces that cascade of near-identical procedures with one loop and one small table: for each binary operator, how tightly does it bind?

infix_binding_power :: proc(kind: Token_Kind) -> (bp: int, ok: bool) {
	#partial switch kind {
	case .Or_Or:
		return 1, true
	case .And_And:
		return 2, true
	case .Equal, .Not_Equal:
		return 3, true
	case .Less, .Less_Equal, .Greater, .Greater_Equal:
		return 4, true
	case .Plus, .Minus:
		return 5, true
	case .Star, .Slash:
		return 6, true
	}
	return 0, false
}

Higher numbers bind tighter: *// (6) grab their operands before +/- (5) do, which grab theirs before comparisons (4), and so on down to || (1), the loosest-binding operator Muspel has. One loop reads this table and builds the tree:

parse_precedence :: proc(p: ^Parser, allocator: runtime.Allocator, min_bp: int) -> Expr {
	left := parse_unary(p, allocator)

	for {
		op := peek(p)
		bp, ok := infix_binding_power(op.kind)
		if !ok || bp < min_bp do break
		advance(p)

		right := parse_precedence(p, allocator, bp + 1)

		if op.kind == .And_And || op.kind == .Or_Or {
			node := new(Expr_Logical, allocator)
			node^ = Expr_Logical{line = op.line, op = op.kind, left = left, right = right}
			left = node
		} else {
			node := new(Expr_Binary, allocator)
			node^ = Expr_Binary{line = op.line, op = op.kind, left = left, right = right}
			left = node
		}
	}

	return left
}

Walk 2 + 3 * 4 through it: parse_precedence(min_bp=1) parses 2 as left, sees + (binding power 5, 5 >= 1), and recurses with min_bp=6 (one higher than +'s own power, enforcing left-associativity, more on that in a moment). That inner call parses 3, sees * (binding power 6, 6 >= 6), and recurses again with min_bp=7 to parse 4 alone (nothing left to bind against at power 7). The inner call returns 3 * 4 as one node; the outer call wraps it as 2 + (3 * 4), precedence handled correctly, with no per-level procedures at all.

Design decision: precedence climbing, not a separate grammar rule per level. Alternatives considered: the traditional recursive-descent expression grammar, one rule (and one procedure) per precedence level, each calling the next-tighter one down a fixed chain. Trade-off: the traditional approach maps even more directly onto a written-out grammar, rule for rule, which some readers find easier to trace on a first read. It costs real duplication: six nearly-identical procedures for Muspel's six binary precedence levels, and every new operator or level means writing (or splicing into) another one. Choice: precedence climbing, because the entire precedence table is one data structure (infix_binding_power) read by one loop. Adding % tomorrow is one new case, not a new procedure threaded into a call chain. The technique scales the same way to unary operators and function calls, both covered next, without a combinatorial explosion of grammar rules.

bp + 1, not bp, in the recursive call is what makes the loop left-associative: it demands the next operator bind strictly tighter than the one just consumed to nest under it, so 10 - 3 - 2 parses as (10 - 3) - 2, not 10 - (3 - 2). (A right-associative operator, if Muspel had one, would recurse with bp instead of bp + 1; none of Muspel's current operators need that, but it's worth knowing the knob exists.)

4.3 Unary operators and function calls

parse_precedence's loop only handles infix operators; unary !/- are prefix, checked before falling through to the primary expression, and calls are postfix, checked after it:

parse_unary :: proc(p: ^Parser, allocator: runtime.Allocator) -> Expr {
	#partial switch peek(p).kind {
	case .Bang, .Minus:
		op := advance(p)
		right := parse_unary(p, allocator)
		node := new(Expr_Unary, allocator)
		node^ = Expr_Unary{line = op.line, op = op.kind, right = right}
		return node
	}
	return parse_call(p, allocator)
}

parse_unary recursing into itself (rather than straight to parse_call) is what lets !!x and --x parse correctly: each ! or - wraps whatever comes next, however many more prefix operators that turns out to be.

parse_call :: proc(p: ^Parser, allocator: runtime.Allocator) -> Expr {
	expr := parse_primary(p, allocator)

	for match(p, .Left_Paren) {
		line := previous(p).line
		args := make([dynamic]Expr, allocator)
		if !check(p, .Right_Paren) {
			for {
				append(&args, parse_expression(p, allocator))
				if !match(p, .Comma) do break
			}
		}
		consume(p, .Right_Paren, "expected ')' after arguments")

		node := new(Expr_Call, allocator)
		node^ = Expr_Call{line = line, callee = expr, args = args[:]}
		expr = node
	}

	return expr
}

The for match(p, .Left_Paren) loop, not an if, is deliberate: it's what makes f()() (calling the result of calling f) parse correctly, each (...) wrapping the expression built so far in another Expr_Call. This is the same "postfix operator in a loop" shape a future field access (.name) or index ([i]) would slot into later without disturbing anything above it.

4.4 Declaring functions

Calling a function is only useful once Muspel can declare one, so this chapter adds func to the grammar alongside call syntax:

declaration ::= funcDecl | blockDecl ;
funcDecl    ::= "func" IDENT "(" params? ")" block ;
params      ::= IDENT ( "," IDENT )* ;
blockDecl   ::= varDecl | statement ;
statement   ::= exprStmt | ifStmt | whileStmt | returnStmt | block ;
returnStmt  ::= "return" expression? ";" ;
block       ::= "{" blockDecl* "}" ;

declaration (used only by program, at the very top) now includes funcDecl; block's own inner statements come from the narrower blockDecl, which doesn't. That split is the grammar's way of saying function declarations are top-level only: func can appear directly inside a .mus file, never nested inside { ... }.

Design decision: function declarations are top-level only, not nested. Alternatives considered: allow func anywhere a varDecl is legal, including inside blocks and other function bodies, the way most modern languages do. Trade-off: nested functions are genuinely useful (a small helper local to one function, for instance), but supporting them properly means deciding what a nested function closes over: can it read a variable from its enclosing function's scope after that scope is gone? That's exactly the closures-and-upvalues question the preface names as deliberately out of scope until later, and this chapter's resolver has no mechanism for it yet, only a flat top-level functions table (section 7.4) and a block-scope stack that's popped and discarded the moment its block ends. Choice: restrict func to the top level for now, enforced right here in the grammar and the parser, rather than half-supporting nested functions that silently fail to resolve. A func written inside a block is a clear parse error, not a name that mysteriously can't be found later.

parse_func_decl parses a name, a comma-separated parameter list, and a block body, and Chapter 7's resolver is the reason this arrives now rather than waiting for Part III's compiler: static arity checking (calling add with the wrong number of arguments) needs to know every function's declared parameter count before it walks the code that calls them, which means functions have to be real, parseable AST nodes well before they're ever compiled or executed.

The grammar split above needs a parser that actually enforces it: parse_block calls parse_block_declaration, a sibling of parse_declaration that accepts everything a top-level declaration does except func. A func found there still parses into a full Stmt_Func node (so the rest of the block's tree survives intact, exactly the graceful-degradation philosophy section 4.5 covers next), but it's reported as a Parse_Error rather than silently accepted:

@(private = "file")
parse_block_declaration :: proc(p: ^Parser, allocator: runtime.Allocator) -> Stmt {
	if match(p, .Var) do return parse_var_decl(p, allocator)
	if check(p, .Func) {
		parse_error(p, peek(p), "functions can only be declared at the top level")
		advance(p)
		return parse_func_decl(p, allocator)
	}
	return parse_statement(p, allocator)
}

Try it:

./run.sh check examples/nested_func.mus

2:5: syntax error: functions can only be declared at the top level

Gotcha: a return value has to start on the same line as return. ends_statement (section 2.6) lists .Return itself as a statement-ending token, deliberately, matching Go's own ASI rule: return with nothing after it on the same line is a complete, valid statement (return nil), so a newline right after return inserts a Semicolon immediately, before parse_return_stmt ever gets to look for a value. Write:
func f(x) {
    return
        x
}
and musc parse shows exactly what actually happened: a bare Return with no value, followed by a second, orphaned statement x that never runs as part of the function. The value has to sit on return's own line: return x. This is the single most common real-world ASI mistake in Go code too; Muspel inherits it deliberately rather than pretending the trade-off doesn't exist.

4.5 Error recovery: don't stop at the first mistake

A parser that aborts on the first syntax error is a bad tool: a file with three typos should report three problems in one run, not make you fix them one rebuild at a time. Muspel's parser uses panic-mode synchronisation: on a parse error, skip tokens until the parser is likely standing at the start of the next statement, then keep parsing from there.

Design decision: synchronise-and-continue, not stop-on-first-error. Alternatives considered: stop parsing entirely at the first Parse_Error and report just that one. Trade-off: stopping at the first error is far simpler to implement correctly, no risk of the recovery heuristic itself producing confusing cascading errors, at the real cost of a frustrating edit-rebuild-edit-rebuild loop for anyone fixing more than one mistake at a time. Choice: synchronise-and-continue. A real tool a script author actually uses needs to surface everything wrong with a file in one pass; the occasional confusing cascade (see the worked example below) is a fair price.

synchronize :: proc(p: ^Parser) {
	for !is_at_end(p) {
		if previous(p).kind == .Semicolon do return
		#partial switch peek(p).kind {
		case .Var, .Func, .If, .While, .Return, .Left_Brace:
			return
		}
		advance(p)
	}
}

parse_program (and parse_block, for errors inside a block) calls synchronize whenever a declaration produced at least one new error, discarding tokens until the last one consumed was a ; or the next one looks like the start of a new statement.

A worked example, because synchronisation's output is worth seeing exactly as it happens, not just described. Given:

var x = ;
var y = 1 +;
print(x, y);

./run.sh parse examples/broken.mus

Var x
  Literal nil
Var y
  Binary Plus
    Literal 1
    Literal nil
ExprStmt
  Call
    Ident print [depth=-1 slot=-1]
    Ident x [depth=-1 slot=-1]
    Ident y [depth=-1 slot=-1]
---
1:9: error: expected an expression
2:1: error: expected ';' after variable declaration
2:12: error: expected an expression
3:1: error: expected ';' after variable declaration

Both malformed declarations still produced (partial, nil-patched) tree nodes, and the third line, print(x, y);, parsed perfectly despite two broken lines above it, that ExprStmt/Call block at the bottom of the tree: all three problems surfaced in one run, and the parser never gave up.

broken.mus still uses explicit ; characters throughout, deliberately: they're not required any more (section 2.6), but they're not wrong either, and every error here is a missing expression, not a missing terminator, so ASI has nothing to do with this particular example. The two expected ';' errors are what happens when the parser genuinely can't find a semicolon, inserted or typed, where the grammar demands one; they'd fire identically with or without automatic insertion.

Gotcha: parse_primary's error-recovery fallback consumes a token, and that token might be the one you actually needed. Look closely at the second error: 2:1: error: expected ';' after variable declaration is reported at the token var on line 2, not at the missing expression on line 1. Here's why: when parse_primary finds no valid expression start (it's looking at a ; that closes var x = ;), it records "expected an expression" and unconditionally advances past whatever token it was looking at, so the parser doesn't spin forever retrying the same token. That's the right call in general, but here the token it advances past is the very ; that was about to correctly close the declaration. The next consume(.Semicolon, ...) then fails too, one token later than you'd expect, against var. The fix isn't a bug fix, exactly: it's a reminder that hand-rolled panic-mode recovery is a heuristic, not a proof. musc's first reported error at each site is always accurate; a second error immediately after it is worth reading with this gotcha in mind before assuming the parser itself is broken.

A second worked example, this time triggered by ASI rather than a typo, because Chapter 3's } else { gotcha is worth seeing fail, not just being warned about. Given:

if (true) {
    print(1)
}
else {
    print(2)
}

./run.sh parse examples/dangling_else.mus

If
  Literal true
  Block
    ExprStmt
      Call
        Ident print [depth=-1 slot=-1]
        Literal 1
ExprStmt
  Literal nil
Block
  ExprStmt
    Call
      Ident print [depth=-1 slot=-1]
      Literal 2
---
4:1: error: expected an expression
4:6: error: expected ';' after expression

The if statement ends at the first }, a Semicolon inserted right after it because nothing told the lexer an else was coming. parse_if_stmt never even sees the else keyword: by the time it checks match(p, .Else), the next token is that inserted Semicolon, so it quietly builds an if with no else branch and returns. synchronize then has to make sense of a bare else sitting where a new statement was expected, which it can't, hence the cascading errors on line 4. Moving else back onto the closing }'s own line fixes it completely; no code changes needed, only layout.

4.6 A counting `for`

One more piece of control flow, deliberately small: a C-style counting loop.

forStmt ::= "for" "(" ( varDecl | exprStmt )? ";" expression? ";" expression? ")" block ;

Why introduce this now, as sugar, rather than wait for Chapter 6? There's no real fork here, just a convenience form worth having before Chapter 6 gives the language something more interesting to loop over. A counting for is exactly a while with an initialiser run once before it and a step expression run at the end of every iteration, machinery the grammar already has in full. Rather than add a new Stmt_For node (and teach the resolver, the tree-walker, and the compiler about a fourth kind of loop), parse_counting_for_stmt desugars the whole thing at parse time, directly into the Stmt_Block/Stmt_While/Stmt_Var/Stmt_Expr nodes those three passes already know:

// for (init; cond; step) { body }  desugars to  { init; while (cond) { body; step; } }
inner_stmts := make([dynamic]Stmt, allocator)
append(&inner_stmts, body)
if step != nil {
	step_stmt := new(Stmt_Expr, allocator)
	step_stmt^ = Stmt_Expr{line = line, expr = step}
	append(&inner_stmts, step_stmt)
}
inner_block := new(Stmt_Block, allocator)
inner_block^ = Stmt_Block{line = line, stmts = inner_stmts[:]}

cond_expr := cond
if cond_expr == nil {
	true_lit := new(Expr_Literal, allocator)
	true_lit^ = Expr_Literal{line = line, value = true}
	cond_expr = true_lit
}

while_stmt := new(Stmt_While, allocator)
while_stmt^ = Stmt_While{line = line, cond = cond_expr, body = inner_block}

outer_stmts := make([dynamic]Stmt, allocator)
if init != nil do append(&outer_stmts, init)
append(&outer_stmts, while_stmt)
outer_block := new(Stmt_Block, allocator)
outer_block^ = Stmt_Block{line = line, stmts = outer_stmts[:]}
return outer_block

An empty cond (for (;;) { ... }) becomes a while (true), exactly C's own convention. musc parse shows the desugaring plainly: for (var i = 0; i < 5; i = i + 1) { print(i) } prints as a Block containing a Var i followed by a While, never a node called For at all, because there isn't one.

The one piece of bookkeeping this needs that a real Stmt_For wouldn't: for is one keyword serving two grammars. parse_for_stmt looks one token ahead to decide which it's parsing:

parse_for_stmt :: proc(p: ^Parser, allocator: runtime.Allocator) -> Stmt {
	if check(p, .Left_Paren) do return parse_counting_for_stmt(p, allocator)
	return parse_for_in_stmt(p, allocator)
}

for ( is always the counting form; anything else is Chapter 6's for item in list, which doesn't exist yet at this point in the book but the dispatch is worth showing now so section 6.4 doesn't need to touch this chapter's own parsing entry point at all, only add the sibling function it already calls.

Checkpoint

musc parse handles Muspel's full expression grammar with correct precedence, unary operators, function declarations and calls, and a counting for loop, and reports every syntax error in a deliberately broken file in one pass, recovering after each.

Exercises

Add % (modulo) to infix_binding_power at the same precedence as *//, and confirm musc parse builds the right tree for 10 % 3 + 1.
Parse f(1)(2) and confirm the tree shows two nested Call nodes, the outer one's callee being the inner one, not a flat three-argument call.
Deliberately write a file with a missing closing } on a block and see what synchronize does with it; is the reported error location where you'd expect?
-2 * 3 and -(2 * 3) mean different things. Trace parse_unary and parse_precedence through the first one and explain, from the code, why unary - binds tighter than *.
examples/nested_func.mus declares a func inside a block. Run musc parse (not check) against it and confirm the tree still contains a complete Func node despite the reported error, the same partial-tree-plus-error shape section 4.5's worked example already showed for a broken var.
Parse for (;;) { print(1) } and confirm the tree's While node's condition is a bare Literal true, never a node that mentions the empty parentheses at all.
Parse examples/counting_for.mus and, on paper, redraw its desugared shape as an ordinary while loop by hand before checking it against what musc parse actually printed.