169 Advanced

Operator Precedence

Functional Programming

Tutorial

The Problem

Operator precedence determines how 1 + 2 * 3 - 4 / 2 is parsed: multiplication and division bind tighter than addition and subtraction, so the result is 1 + (2*3) - (4/2) = 5. Associativity determines how 1 - 2 - 3 groups: left-associativity gives (1-2)-3 = -4, right-associativity gives 1-(2-3) = 2. Encoding both correctly in a parser requires a systematic approach: this example shows the classic table-driven, multi-level recursive descent method.

🎯 Learning Outcomes

• Understand precedence levels and how they create a parse hierarchy

• Learn left vs. right associativity and how to encode each in recursive descent

• See the Assoc enum and precedence table as the structured alternative to Pratt's binding power

• Practice parsing real arithmetic with correct operator grouping

Code Example

#[derive(Clone, Copy)]
enum Assoc { Left, Right }

struct OpInfo { symbol: &'static str, precedence: u8, associativity: Assoc }

const OPERATORS: &[OpInfo] = &[
    OpInfo { symbol: "+", precedence: 5, associativity: Assoc::Left },
    OpInfo { symbol: "^", precedence: 7, associativity: Assoc::Right },
];

type assoc = Left | Right
type op_info = { symbol: string; precedence: int; associativity: assoc }

let operators = [
  { symbol = "+"; precedence = 5; associativity = Left };
  { symbol = "^"; precedence = 7; associativity = Right };
]

Key Differences

Precedence climbing vs. Pratt: Example 168 uses Pratt (binding powers as numbers); this example uses precedence climbing (precedence + associativity table) — both are equivalent in expressive power.

Generator vs. manual: OCaml Menhir encodes precedence declaratively; hand-written parsers in both languages use procedural algorithms.

Associativity encoding: Left-associativity uses prec + 1 for recursive right-side parsing; right-associativity uses prec — the same in Pratt.

Non-associativity: Some operators are non-associative (a < b < c is an error in Python); this requires checking after parsing and emitting an error.

OCaml Approach

OCaml's Menhir generator handles this declaratively. Hand-written OCaml parsers use either recursive descent (one parse_X function per level) or the precedence-climbing algorithm (same as this example). The %left/%right/%nonassoc declarations in Menhir are compiled into identical shift-reduce decisions in the generated LALR table.

Full Source

#![allow(clippy::all)]
// Example 169: Operator Precedence
// Binary operators with left/right associativity and precedence levels

type ParseResult<'a, T> = Result<(T, &'a str), String>;

#[derive(Debug, Clone, PartialEq)]
enum Expr {
    Num(f64),
    BinOp(String, Box<Expr>, Box<Expr>),
}

#[derive(Debug, Clone, Copy)]
enum Assoc {
    Left,
    Right,
}

#[derive(Debug, Clone)]
struct OpInfo {
    symbol: &'static str,
    precedence: u8,
    associativity: Assoc,
}

// ============================================================
// Approach 1: Table-driven operator precedence
// ============================================================

const OPERATORS: &[OpInfo] = &[
    OpInfo {
        symbol: "||",
        precedence: 1,
        associativity: Assoc::Left,
    },
    OpInfo {
        symbol: "&&",
        precedence: 2,
        associativity: Assoc::Left,
    },
    OpInfo {
        symbol: "==",
        precedence: 3,
        associativity: Assoc::Left,
    },
    OpInfo {
        symbol: "!=",
        precedence: 3,
        associativity: Assoc::Left,
    },
    OpInfo {
        symbol: "<=",
        precedence: 4,
        associativity: Assoc::Left,
    },
    OpInfo {
        symbol: ">=",
        precedence: 4,
        associativity: Assoc::Left,
    },
    OpInfo {
        symbol: "<",
        precedence: 4,
        associativity: Assoc::Left,
    },
    OpInfo {
        symbol: ">",
        precedence: 4,
        associativity: Assoc::Left,
    },
    OpInfo {
        symbol: "+",
        precedence: 5,
        associativity: Assoc::Left,
    },
    OpInfo {
        symbol: "-",
        precedence: 5,
        associativity: Assoc::Left,
    },
    OpInfo {
        symbol: "*",
        precedence: 6,
        associativity: Assoc::Left,
    },
    OpInfo {
        symbol: "/",
        precedence: 6,
        associativity: Assoc::Left,
    },
    OpInfo {
        symbol: "%",
        precedence: 6,
        associativity: Assoc::Left,
    },
    OpInfo {
        symbol: "^",
        precedence: 7,
        associativity: Assoc::Right,
    },
];

fn find_op(input: &str) -> Option<(&OpInfo, &str)> {
    let s = input.trim_start();
    // Try 2-char operators first
    for op in OPERATORS {
        if op.symbol.len() == 2 && s.starts_with(op.symbol) {
            return Some((op, &s[2..]));
        }
    }
    for op in OPERATORS {
        if op.symbol.len() == 1 && s.starts_with(op.symbol) {
            return Some((op, &s[1..]));
        }
    }
    None
}

fn binding_power(op: &OpInfo) -> (u8, u8) {
    let base = op.precedence * 2;
    match op.associativity {
        Assoc::Left => (base, base + 1),
        Assoc::Right => (base + 1, base),
    }
}

fn parse_number(input: &str) -> ParseResult<'_, Expr> {
    let s = input.trim_start();
    let bytes = s.as_bytes();
    let mut pos = 0;
    while pos < bytes.len() && bytes[pos].is_ascii_digit() {
        pos += 1;
    }
    if pos < bytes.len() && bytes[pos] == b'.' {
        pos += 1;
        while pos < bytes.len() && bytes[pos].is_ascii_digit() {
            pos += 1;
        }
    }
    if pos == 0 {
        return Err("Expected number".to_string());
    }
    let n: f64 = s[..pos]
        .parse()
        .map_err(|e: std::num::ParseFloatError| e.to_string())?;
    Ok((Expr::Num(n), &s[pos..]))
}

// ============================================================
// Approach 2: Pratt parser using the table
// ============================================================

fn pratt_expr(input: &str, min_bp: u8) -> ParseResult<'_, Expr> {
    let s = input.trim_start();
    let (mut lhs, mut rest) = if s.starts_with('(') {
        let (e, r) = pratt_expr(&s[1..], 0)?;
        let r = r.trim_start();
        if r.starts_with(')') {
            (e, &r[1..])
        } else {
            return Err("Expected ')'".to_string());
        }
    } else {
        parse_number(s)?
    };

    loop {
        let (op, after_op) = match find_op(rest) {
            Some(r) => r,
            None => break,
        };
        let (lbp, rbp) = binding_power(op);
        if lbp < min_bp {
            break;
        }
        let (rhs, r) = pratt_expr(after_op, rbp)?;
        lhs = Expr::BinOp(op.symbol.to_string(), Box::new(lhs), Box::new(rhs));
        rest = r;
    }
    Ok((lhs, rest))
}

// ============================================================
// Approach 3: Precedence climbing
// ============================================================

fn climb_expr(input: &str, min_prec: u8) -> ParseResult<'_, Expr> {
    let s = input.trim_start();
    let (mut lhs, mut rest) = parse_number(s)?;

    loop {
        let (op, after_op) = match find_op(rest) {
            Some(r) => r,
            None => break,
        };
        if op.precedence < min_prec {
            break;
        }
        let next_min = match op.associativity {
            Assoc::Left => op.precedence + 1,
            Assoc::Right => op.precedence,
        };
        let (rhs, r) = climb_expr(after_op, next_min)?;
        lhs = Expr::BinOp(op.symbol.to_string(), Box::new(lhs), Box::new(rhs));
        rest = r;
    }
    Ok((lhs, rest))
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_precedence_mul_over_add() {
        let (e, _) = pratt_expr("1 + 2 * 3", 0).unwrap();
        // Should be 1 + (2*3)
        match e {
            Expr::BinOp(ref op, _, ref rhs) => {
                assert_eq!(op, "+");
                assert!(matches!(rhs.as_ref(), Expr::BinOp(ref o, _, _) if o == "*"));
            }
            _ => panic!(),
        }
    }

    #[test]
    fn test_right_associativity() {
        let (e, _) = pratt_expr("2 ^ 3 ^ 2", 0).unwrap();
        // Should be 2 ^ (3^2)
        match e {
            Expr::BinOp(ref op, _, ref rhs) => {
                assert_eq!(op, "^");
                assert!(matches!(rhs.as_ref(), Expr::BinOp(ref o, _, _) if o == "^"));
            }
            _ => panic!(),
        }
    }

    #[test]
    fn test_left_associativity() {
        let (e, _) = pratt_expr("1 + 2 + 3", 0).unwrap();
        // Should be (1+2) + 3
        match e {
            Expr::BinOp(ref op, ref lhs, _) => {
                assert_eq!(op, "+");
                assert!(matches!(lhs.as_ref(), Expr::BinOp(ref o, _, _) if o == "+"));
            }
            _ => panic!(),
        }
    }

    #[test]
    fn test_comparison_ops() {
        let (e, _) = pratt_expr("1 == 2", 0).unwrap();
        assert!(matches!(e, Expr::BinOp(ref o, _, _) if o == "=="));
    }

    #[test]
    fn test_multi_char_op() {
        let (e, _) = pratt_expr("1 <= 2", 0).unwrap();
        assert!(matches!(e, Expr::BinOp(ref o, _, _) if o == "<="));
    }

    #[test]
    fn test_climb_matches_pratt() {
        let (e1, _) = pratt_expr("1 + 2 * 3", 0).unwrap();
        let (e2, _) = climb_expr("1 + 2 * 3", 0).unwrap();
        assert_eq!(e1, e2);
    }

    #[test]
    fn test_parens() {
        let (e, _) = pratt_expr("(1 + 2) * 3", 0).unwrap();
        match e {
            Expr::BinOp(ref op, _, _) => assert_eq!(op, "*"),
            _ => panic!(),
        }
    }
}

(* Example 169: Operator Precedence *)
(* Binary operators with left/right associativity and precedence levels *)

type 'a parse_result = ('a * string, string) result
type 'a parser = string -> 'a parse_result

type assoc = Left | Right

type op_info = {
  symbol: string;
  precedence: int;
  associativity: assoc;
}

type expr =
  | Num of float
  | BinOp of string * expr * expr

(* Approach 1: Table-driven operator precedence *)
let operators = [
  { symbol = "||"; precedence = 1; associativity = Left };
  { symbol = "&&"; precedence = 2; associativity = Left };
  { symbol = "=="; precedence = 3; associativity = Left };
  { symbol = "!="; precedence = 3; associativity = Left };
  { symbol = "<";  precedence = 4; associativity = Left };
  { symbol = ">";  precedence = 4; associativity = Left };
  { symbol = "<="; precedence = 4; associativity = Left };
  { symbol = ">="; precedence = 4; associativity = Left };
  { symbol = "+";  precedence = 5; associativity = Left };
  { symbol = "-";  precedence = 5; associativity = Left };
  { symbol = "*";  precedence = 6; associativity = Left };
  { symbol = "/";  precedence = 6; associativity = Left };
  { symbol = "%";  precedence = 6; associativity = Left };
  { symbol = "^";  precedence = 7; associativity = Right };
]

let find_op sym = List.find_opt (fun op -> op.symbol = sym) operators

let binding_power op_info =
  let base = op_info.precedence * 2 in
  match op_info.associativity with
  | Left -> (base, base + 1)    (* left: left bp < right bp *)
  | Right -> (base + 1, base)   (* right: left bp > right bp *)

let ws0 input =
  let rec skip i = if i < String.length input &&
    (input.[i] = ' ' || input.[i] = '\t') then skip (i+1) else i in
  let i = skip 0 in String.sub input i (String.length input - i)

let parse_number input =
  let s = ws0 input in
  let len = String.length s in
  let pos = ref 0 in
  while !pos < len && s.[!pos] >= '0' && s.[!pos] <= '9' do incr pos done;
  if !pos < len && s.[!pos] = '.' then begin
    incr pos;
    while !pos < len && s.[!pos] >= '0' && s.[!pos] <= '9' do incr pos done end;
  if !pos = 0 then Error "Expected number"
  else Ok (Num (float_of_string (String.sub s 0 !pos)),
           String.sub s !pos (len - !pos))

(* Try to parse a multi-char operator *)
let parse_operator input =
  let s = ws0 input in
  (* Try 2-char ops first, then 1-char *)
  let try_len len =
    if String.length s >= len then
      let sym = String.sub s 0 len in
      match find_op sym with
      | Some info -> Some (info, String.sub s len (String.length s - len))
      | None -> None
    else None in
  match try_len 2 with
  | Some result -> Ok result
  | None ->
    match try_len 1 with
    | Some result -> Ok result
    | None -> Error "Expected operator"

(* Approach 2: Pratt parser using the table *)
let rec parse_expr_pratt min_bp input =
  let (lhs, rest) = match parse_number input with
    | Ok r -> r
    | Error e -> raise (Failure e) in
  pratt_loop min_bp lhs rest

and pratt_loop min_bp lhs input =
  match parse_operator input with
  | Error _ -> (lhs, input)
  | Ok (info, _) ->
    let (lbp, rbp) = binding_power info in
    if lbp < min_bp then (lhs, input)
    else
      match parse_operator input with
      | Ok (_, after_op) ->
        let (rhs, rem) = parse_expr_pratt rbp after_op in
        pratt_loop min_bp (BinOp (info.symbol, lhs, rhs)) rem
      | Error _ -> (lhs, input)

let parse_expr input =
  try Ok (parse_expr_pratt 0 input)
  with Failure e -> Error e

(* Approach 3: Precedence climbing *)
let rec climb_expr input min_prec =
  let (mut_lhs, mut_rest) = match parse_number input with
    | Ok r -> r | Error e -> raise (Failure e) in
  let lhs = ref mut_lhs in
  let rest = ref mut_rest in
  let continue_loop = ref true in
  while !continue_loop do
    match parse_operator !rest with
    | Error _ -> continue_loop := false
    | Ok (info, _) ->
      if info.precedence < min_prec then continue_loop := false
      else begin
        let next_min = match info.associativity with
          | Left -> info.precedence + 1
          | Right -> info.precedence in
        let (_, after_op) = match parse_operator !rest with
          | Ok r -> r | Error _ -> continue_loop := false; ("", !rest) in (* dummy *)
        if !continue_loop then begin
          let (rhs, rem) = climb_expr after_op next_min in
          lhs := BinOp (info.symbol, !lhs, rhs);
          rest := rem end
      end
  done;
  (!lhs, !rest)

(* Tests *)
let () =
  (match parse_expr "1 + 2 * 3" with
   | Ok (BinOp ("+", Num 1., BinOp ("*", Num 2., Num 3.)), "") -> ()
   | _ -> failwith "Precedence test");

  (match parse_expr "2 ^ 3 ^ 2" with
   | Ok (BinOp ("^", Num 2., BinOp ("^", Num 3., Num 2.)), "") -> ()
   | _ -> failwith "Right assoc test");

  (match parse_expr "1 + 2 + 3" with
   | Ok (BinOp ("+", BinOp ("+", Num 1., Num 2.), Num 3.), "") -> ()
   | _ -> failwith "Left assoc test");

  print_endline "✓ All tests passed"

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_precedence_mul_over_add() {
        let (e, _) = pratt_expr("1 + 2 * 3", 0).unwrap();
        // Should be 1 + (2*3)
        match e {
            Expr::BinOp(ref op, _, ref rhs) => {
                assert_eq!(op, "+");
                assert!(matches!(rhs.as_ref(), Expr::BinOp(ref o, _, _) if o == "*"));
            }
            _ => panic!(),
        }
    }

    #[test]
    fn test_right_associativity() {
        let (e, _) = pratt_expr("2 ^ 3 ^ 2", 0).unwrap();
        // Should be 2 ^ (3^2)
        match e {
            Expr::BinOp(ref op, _, ref rhs) => {
                assert_eq!(op, "^");
                assert!(matches!(rhs.as_ref(), Expr::BinOp(ref o, _, _) if o == "^"));
            }
            _ => panic!(),
        }
    }

    #[test]
    fn test_left_associativity() {
        let (e, _) = pratt_expr("1 + 2 + 3", 0).unwrap();
        // Should be (1+2) + 3
        match e {
            Expr::BinOp(ref op, ref lhs, _) => {
                assert_eq!(op, "+");
                assert!(matches!(lhs.as_ref(), Expr::BinOp(ref o, _, _) if o == "+"));
            }
            _ => panic!(),
        }
    }

    #[test]
    fn test_comparison_ops() {
        let (e, _) = pratt_expr("1 == 2", 0).unwrap();
        assert!(matches!(e, Expr::BinOp(ref o, _, _) if o == "=="));
    }

    #[test]
    fn test_multi_char_op() {
        let (e, _) = pratt_expr("1 <= 2", 0).unwrap();
        assert!(matches!(e, Expr::BinOp(ref o, _, _) if o == "<="));
    }

    #[test]
    fn test_climb_matches_pratt() {
        let (e1, _) = pratt_expr("1 + 2 * 3", 0).unwrap();
        let (e2, _) = climb_expr("1 + 2 * 3", 0).unwrap();
        assert_eq!(e1, e2);
    }

    #[test]
    fn test_parens() {
        let (e, _) = pratt_expr("(1 + 2) * 3", 0).unwrap();
        match e {
            Expr::BinOp(ref op, _, _) => assert_eq!(op, "*"),
            _ => panic!(),
        }
    }
}

Deep Comparison

Comparison: Example 169 — Operator Precedence

Operator table

OCaml:

type assoc = Left | Right
type op_info = { symbol: string; precedence: int; associativity: assoc }

let operators = [
  { symbol = "+"; precedence = 5; associativity = Left };
  { symbol = "^"; precedence = 7; associativity = Right };
]

Rust:

#[derive(Clone, Copy)]
enum Assoc { Left, Right }

struct OpInfo { symbol: &'static str, precedence: u8, associativity: Assoc }

const OPERATORS: &[OpInfo] = &[
    OpInfo { symbol: "+", precedence: 5, associativity: Assoc::Left },
    OpInfo { symbol: "^", precedence: 7, associativity: Assoc::Right },
];

Binding power from table

OCaml:

let binding_power op_info =
  let base = op_info.precedence * 2 in
  match op_info.associativity with
  | Left -> (base, base + 1)
  | Right -> (base + 1, base)

Rust:

fn binding_power(op: &OpInfo) -> (u8, u8) {
    let base = op.precedence * 2;
    match op.associativity {
        Assoc::Left => (base, base + 1),
        Assoc::Right => (base + 1, base),
    }
}

Exercises

Add ** (exponentiation) as right-associative with higher precedence than * and /.

Verify 1 - 2 - 3 parses as (1 - 2) - 3 = -4 (left-associative), not 1 - (2 - 3) = 2.

Implement comparison operators (<, >, ==) as non-associative — a < b < c should be a parse error.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust