How operator precedence emerges from a recursive descent parser

When I first learned about recursive descent parsers, I expected to need an explicit precedence table somewhere. It turns out that is not how it works. Precedence emerges from the grammar structure, and understanding why is one of the most satisfying moments in building first.

The grammar trick

In first's grammar, <expression> is defined in terms of <term>, and <term> is defined in terms of <factor>:

<expression> ::= <term> { ("+" | "-") <term> }
<term>        ::= <factor> { ("*" | "/") <factor> }
<factor>      ::= "(" <expression> ")" | <primary>

To parse an expression, you always parse a term first. Multiplication lives in parse_term(), which is called by parse_expression() — so multiplication is always resolved before addition returns. That is the precedence hierarchy, encoded directly in the function call stack. No table needed.

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

Left-associativity from a loop

The repetition in the grammar maps to a loop in code, and the loop shape gives left-associativity for free. This ended up generalized into one shared helper, binary_expression(), parameterized by an operator-check predicate and the next-tighter parse function — every precedence layer in first calls into the same loop:

static AST *binary_expression(Parser *self, bool (*op_check)(TokenType),
                              AST *(*next_op)(Parser *)) {
  AST *left = next_op(self);
  while (op_check(self->token->type)) {
    AST *node = create_node(AST_BINARY_EXPRESSION);
    Operation op = parser_symbol_to_operation(expect_token(self, self->token->type));
    AST *right = next_op(self);
    node->data.AST_BINARY_EXPRESSION.left  = left;
    node->data.AST_BINARY_EXPRESSION.right = right;
    node->data.AST_BINARY_EXPRESSION.op    = op;
    left = node;
  }
  return left;
}

Each iteration wraps the accumulated left as the left child of a new binary node. The tree grows left-leaning: 1 - 2 - 3 parses as (1 - 2) - 3 = -4, not 1 - (2 - 3) = 2. Correct subtraction associativity falls out of the loop naturally.

A gotcha this generality introduced: parse_exponation() is just another binary_expression() call, sharing the same left-folding loop as addition and multiplication. That means ** is left-associative in first — 2 ** 3 ** 2 parses as (2 ** 3) ** 2 = 64, not the right-associative 2 ** (3 ** 2) = 512 that most languages give exponentiation. The parser test suite names this test exponent_is_left_associative_in_current_implementation — explicit enough that nobody mistakes it for a bug report.

When you would need something else

Recursive descent with grammar layers works great for a small, fixed set of operators. When you want user-definable operators with custom precedences, a Pratt parser is more flexible — each operator carries its own binding power rather than having precedence encoded structurally. first now has fourteen binary operators (plus unary +/-) spread across eight grammar layers (boolean or, boolean and, equality, relational, additive, multiplicative, exponent, unary), and the grammar-layer approach is still exactly right for that — it only starts to strain if operators need to be user-definable.