Recursive descent parsing

A recursive descent parser is one of the simplest and most readable parser architectures. The core idea: each grammar rule becomes a function. When one rule references another, the function calls the other function.

The grammar shapes the code

Here is the core of the arithmetic grammar for first — a slice of the full grammar in include/parser.h:

<addition>       ::= <multiplication> { ("+" | "-") <multiplication> }
<multiplication> ::= <exponent> { ("*" | "/" | "%") <exponent> }
<exponent>       ::= <unary> { "**" <unary> }
<unary>          ::= ("+" | "-") <unary> | <primary>
<primary>        ::= "(" <expression> ")" | <block> | <literal> | <identifier>

parse_addition() calls parse_multiplication(), which calls parse_exponation(), which calls parse_unary(), which calls parse_primary(). This nesting creates operator precedence. To parse 2 + 3 * 4:

• parse_addition() calls parse_multiplication() for the left side, which returns 2
• Back in parse_addition(), we see + and call parse_multiplication() again
• That call finds 3 * 4 and handles multiplication internally, returning 12
• Result: 2 + 12 = 14

Precedence emerges from the grammar nesting — no explicit table needed. first actually has more layers above addition — boolean_or, boolean_and, equality, and relational each wrap the next, so 1 < 2 == true && false || true parses with exactly the precedence you'd expect, purely from which function calls which.

All of these layers share one generic helper, binary_expression(self, op_check, next_op), parameterized by an operator-check predicate and the next-tighter parse function — so parse_addition, parse_multiplication, and parse_exponation are each a one-line call into it.

eat_token and next_token

The parser uses two internal helpers. eat_token() advances the token stream and returns the current token's value as a strdup-ed string. next_token() is a wrapper that automatically skips whitespace tokens, so the parser never has to think about whitespace.