151. A Pratt compiler in Rust, part 1

The table you already wrote

In chapter 48 your TypeScript compiler parsed expressions with a Pratt parser driven by a table. Each token type maps to how it starts an expression (prefix), how it continues one (infix), and how tightly it binds:

const RULES = {
  '-': { prefix: unary, infix: binary,
         prec: Prec.TERM },
  '+': { prefix: null, infix: binary,
         prec: Prec.TERM },
  '*': { prefix: null, infix: binary,
         prec: Prec.FACTOR },
  // ...
};
const getRule = (t) => RULES[t] ?? NO_RULE;

drip-rs keeps the same idea, the same rows and the same algorithm. What changes is how a cell holds a function, and how precedences compare.

A cell is a function pointer

From src/compiler.rs:

type ParseFn<'src, 'a> =
    fn(&mut Compiler<'src, 'a>, bool);

struct ParseRule<'src, 'a> {
    prefix: Option<ParseFn<'src, 'a>>,
    infix: Option<ParseFn<'src, 'a>>,
    precedence: Precedence,
}

fn(&mut Compiler, bool) is a function pointer type: it points at some function taking those arguments, and which function needn’t be known at compile time^[2]. Every parse function in drip-rs is a method like fn binary(&mut self, can_assign: bool), and a method is just a function whose first parameter is self. So Self::binary fits. The bool says whether an = may follow (chapter 48’s canAssign). The lifetimes are there because Compiler borrows the source and the heap (chapter 152).

Option stands in for TypeScript’s null. It costs nothing: on this machine size_of::<Option<fn(&mut u8, bool)>>() is 8, the same as the bare pointer. Function pointers are assumed never to be null^[3], so None can use the null pattern. A whole ParseRule measured 24 bytes.

There is one more difference. A TypeScript parse function is a closure that reads previous and current from the enclosing compile. A function pointer captures nothing (chapter 134’s closures can, but then they aren’t plain fn pointers). Everything a parse function needs arrives through its &mut Compiler argument. That is chapter 152’s subject.

The table is a match

TypeScript looks the rule up in an object, and clox indexes an array that has one row for every token type^[1]. drip-rs builds the row with a match on the TokenKind enum (chapter 146). Adapted from Compiler::rule:

use Precedence as P;
use TokenKind as T;
let (prefix, infix, precedence):
    (Option<ParseFn>, Option<ParseFn>, _) =
    match kind {
        T::Minus => (Some(Self::unary),
            Some(Self::binary), P::Term),
        T::Plus => (None,
            Some(Self::binary), P::Term),
        T::Slash | T::Star => (None,
            Some(Self::binary), P::Factor),
        T::Number => (Some(Self::number),
            None, P::None),
        // ... 12 more arms
        _ => (None, None, P::None),
    };
ParseRule { prefix, infix, precedence }

T::Slash | T::Star is one arm for two tokens. The _ arm is ?? NO_RULE: every token not listed can neither start nor continue an expression. (The price of _ is that a new token kind gets an empty rule without a word from the compiler, where clox’s array has a row for every token.)

Why the type annotation on the tuple? In Rust, each function has its own unique type, and Self::unary is not the same type as Self::number. Leave the annotation off, and rustc 1.97 says (trimmed):

error[E0308]: `match` arms have
  incompatible types
  _ => (Some(Self::b), None, 0),
       ^^^^^^^^^^^^^^^^^^^^^^^^
       expected fn item, found a
       different fn item

Annotating the tuple as Option<ParseFn> tells rustc to turn each function into the shared function-pointer type.

Precedence is an ordered enum

TypeScript’s precedences are numbers, NONE: 0 up to PRIMARY: 10. drip-rs’s are an enum, lowest first:

#[derive(Clone, Copy, PartialEq, Eq,
    PartialOrd, Ord)]
enum Precedence {
    None, Assignment, Or, And, Equality,
    Comparison, Term, Factor, Unary,
    Call, Primary,
}

Deriving PartialOrd and Ord on an enum orders the variants by their position: the first is the smallest^[4]. So Precedence::Term < Precedence::Factor, and <= works between precedences exactly as it did between numbers. What doesn’t work is + 1. The TypeScript binary parses its right operand at getRule(op).prec + 1, and clox casts the enum to an integer and adds one. drip-rs writes a method, next(), that is a match from each variant to the one above it. Primary.next() stays Primary.

The heart of the parser

parse_precedence is almost line for line the TypeScript one:

fn parse_precedence(&mut self,
    precedence: Precedence) {
    self.advance();
    let kind = self.previous.kind;
    let rule = Self::rule(kind);
    let Some(prefix) = rule.prefix else {
        self.error("Expect expression.");
        return;
    };
    let can_assign = precedence
        <= Precedence::Assignment;
    prefix(self, can_assign);
    while precedence
        <= Self::rule(self.current.kind)
            .precedence
    {
        self.advance();
        let k = self.previous.kind;
        let infix = Self::rule(k).infix
            .expect("infix rule");
        infix(self, can_assign);
    }
}

(Adapted. The real one goes on to report “Invalid assignment target.”) prefix(self, can_assign) calls through the pointer, handing over the compiler itself. rule has no self: it’s an associated function, so it borrows nothing and can be called in the middle of the loop condition. The expect records a promise the table keeps: every token with a precedence above None has an infix rule.

Step through -1 + 2 * 3:

Your turn

enum Prec {
    None,
    Term,
    Factor,
    Unary,
}

fn infix_prec(c: char) -> Prec {
    todo!()
}

impl Prec {
    fn next(self) -> Prec {
        todo!()
    }
}

fn binds(min: Prec, c: char) -> bool {
    todo!()
}

type BinFn = fn(f64, f64) -> f64;

fn op_fn(c: char) -> Option<BinFn> {
    todo!()
}

fn apply(c: char, a: f64, b: f64)
    -> Option<f64> {
    todo!()
}

What you learned

• A parse-rule table cell is an Option<fn(&mut Compiler, bool)>: a function pointer or nothing. Option adds no size, and a pointer captures nothing, so state arrives through &mut Compiler.
• Compiler::rule is a match on TokenKind. Its arms need a ParseFn annotation, because every function has its own type.
• Precedence is an enum deriving Ord, so variants compare by position. next() replaces + 1.
• parse_precedence calls the prefix rule, then infix rules while the next token binds at least as tightly as the given precedence.