Operator Precedence

Operator Precedence

In math, * and / bind tighter than + and -. The expression 2 + 3 * 4 equals 14, not 20.

We encode this in the grammar by using separate rules for each precedence level:

expr   -> term (('+' | '-') term)*
term   -> factor (('*' | '/') factor)*
factor -> NUMBER

• factor: the tightest — just numbers
• term: handles * and /
• expr: handles + and -

Implementation

Each grammar rule becomes a method:

parseExpr() {
    let left = this.parseTerm();
    while (this.peek().type === "PLUS" || this.peek().type === "MINUS") {
        const op = this.advance().value;
        left = { type: "BinaryExpr", op, left, right: this.parseTerm() };
    }
    return left;
}

parseTerm() {
    let left = this.parseFactor();
    while (this.peek().type === "STAR" || this.peek().type === "SLASH") {
        const op = this.advance().value;
        left = { type: "BinaryExpr", op, left, right: this.parseFactor() };
    }
    return left;
}

Your Task

Write a parser with proper operator precedence. 2 + 3 * 4 should parse as (+ 2 (* 3 4)), not (* (+ 2 3) 4).