Building an Expression Calculator in Rust — Pratt Parsing Turns Precedence into Two Numbers, and Rationals Kill Float Error

A terminal calculator where 1 + 2 * 3 is 7, 2^3^2 is 512 (= 2^9), and 0.1 + 0.2 is exactly 0.3 — not 0.30000000000000004. I wrote pcalc in Rust. Two implementation hinges: (1) a Pratt parser that expresses operator precedence as two "binding power" numbers per operator instead of a tower of grammar rules, and (2) exact rational arithmetic — every value is a reduced fraction — so floating-point rounding error simply doesn't exist.

📦 GitHub: https://github.com/sen-ltd/pratt-calc

(It's a CLI — no live demo. Run with cargo run or Docker.)

Pratt parsing: precedence as two numbers

Parse calculator input with recursive descent and you get a "tower of grammar" — one function per precedence level:

expr   → term (('+' | '-') term)*
term   → factor (('*' | '/') factor)*
factor → power ('^' power)*
power  → atom | '(' expr ')'

Every new precedence level is another function, and right-associativity (^) makes it worse. A Pratt parser (top-down operator precedence) collapses all of it into two numbers per operator — a left and right binding power — driven by one loop:

fn expr(rbp):
  left = nud(token)          // prefix / atom
  while lbp(peek) > rbp:
    left = led(left, next)   // infix: left OP expr(op.rbp)

In Rust:

fn expr(&mut self, rbp: u8) -> Result<Expr, ParseError> {
    let mut left = self.nud()?;             // prefix (number, paren, unary minus)
    while let Some(tok) = self.peek() {
        let (op, lbp, op_rbp) = match infix_bp(tok) {
            Some(x) => x,
            None => break,
        };
        if lbp <= rbp { break; }            // weaker operator → stop
        self.next();                        // consume operator
        let right = self.expr(op_rbp)?;     // right operand, recursively
        left = Expr::Bin(op, Box::new(left), Box::new(right));
    }
    Ok(left)
}

The binding-power table

Precedence and associativity collapse into one table:

operator	lbp	rbp	associativity
+ -	1	2	left
* / %	3	4	left
unary -	—	5	prefix
^	7	6	right

fn infix_bp(t: &Token) -> Option<(BinOp, u8, u8)> {
    match t {
        Token::Plus  => Some((BinOp::Add, 1, 2)),
        Token::Star  => Some((BinOp::Mul, 3, 4)),
        Token::Caret => Some((BinOp::Pow, 7, 6)), // right-assoc
        // ...
    }
}

Right-associativity is just rbp < lbp. With ^ at lbp 7, rbp 6, parsing 2^3^2:

• read 2 → ^ (lbp 7 > 0) → 2 ^ expr(rbp=6)
• expr(6): 3 → ^ (lbp 7 > 6) → 3 ^ expr(6) → 2
• = 3^2 = 9, so 2^9 = 512 ✓ (not the left-assoc (2^3)^2 = 64)

Left-associative + (lbp 1, rbp 2) has rbp > lbp, so the same operator does not recurse on the right — it folds from the left.

Pin the tree shape, not just the value:

#[test]
fn pow_is_right_associative() {
    assert_eq!(ev("2^3^2"), "512"); // 2^(3^2), NOT (2^3)^2
}

#[test]
fn ast_shape_for_precedence() {
    let ast = Parser::new(tokenize("1 + 2 * 3").unwrap()).parse().unwrap();
    match ast {
        Expr::Bin(BinOp::Add, _, right) =>
            assert!(matches!(*right, Expr::Bin(BinOp::Mul, _, _))),
        _ => panic!("expected Add at the root"),
    }
}

Unary minus is the most interesting binding power

Is -2^2 equal to -4 or 4? In math and Python (-2**2 == -4) it's -(2^2) = -4 — unary minus binds looser than ^. But -2*3 is (-2)*3 = -6, where it binds tighter than *.

Pratt expresses this with a single prefix rbp. Set unary minus's rbp to 5 (between *'s rbp 4 and ^'s lbp 7):

const PREFIX_RBP: u8 = 5;
// nud (prefix):
Some(Token::Minus) => Ok(Expr::Neg(Box::new(self.expr(PREFIX_RBP)?))),

• -2^2: consume - → expr(5) → read 2, ^ (lbp 7 > 5) binds 2^2=4 → negate → -4 ✓
• -2*3: consume - → expr(5) → read 2, * (lbp 3 ≤ 5) stops → return 2 → negate → -2 → outer * 3 → -6 ✓

One number tunes the binding strength. That's the joy of Pratt.

#[test]
fn unary_minus_binding() {
    assert_eq!(ev("-2^2"), "-4");  // looser than ^
    assert_eq!(ev("-2*3"), "-6");  // tighter than *
    assert_eq!(ev("--5"), "5");    // double negation
}

Rationals kill floating-point error

The other calculator trap: 0.1 + 0.2 == 0.30000000000000004. Binary floating point can't represent 0.1 exactly.

The fix: hold every value as a reduced fraction num/den. 0.1 is 1/10, 0.2 is 1/5, and 1/10 + 1/5 = 3/10 — exactly 0.3.

#[derive(Clone, Copy, PartialEq, Eq)]
pub struct Rational {
    num: i128,
    den: i128, // invariant: den > 0, gcd(|num|, den) == 1
}

impl Rational {
    pub fn new(num: i128, den: i128) -> Result<Self, RErr> {
        if den == 0 { return Err(RErr::DivZero); }
        let sign = if den < 0 { -1 } else { 1 };
        let g = gcd(num, den).max(1);
        Ok(Rational { num: sign * (num / g), den: (den / g).abs() })
    }
}

#[test]
fn exact_arithmetic_no_float_error() {
    let a = Rational::parse_decimal("0.1").unwrap();
    let b = Rational::parse_decimal("0.2").unwrap();
    assert_eq!(a.add(b).unwrap(), Rational::new(3, 10).unwrap());
}

pcalc "0.1 + 0.2 - 0.3" returns 0. Floating point would give 5.5e-17.

Overflow errors, it doesn't silently wrap

i128 isn't arbitrary precision, so big computations can overflow. Rust's checked_mul detects it and returns an error rather than wrapping:

pub fn mul(self, o: Rational) -> Result<Rational, RErr> {
    let num = self.num.checked_mul(o.num).ok_or(RErr::Overflow)?;
    let den = self.den.checked_mul(o.den).ok_or(RErr::Overflow)?;
    Rational::new(num, den)
}

#[test]
fn overflow_guarded() {
    assert_eq!(
        Rational::from_int(i128::MAX).mul(Rational::from_int(2)),
        Err(RErr::Overflow)); // no wrapping to a wrong answer
}

Saying "exceeds 128-bit range" is more honest than returning garbage.

Bonus: repeating-decimal detection

The --decimal flag shows the decimal expansion. Repeating decimals like 1/3 are detected by recording the position where a remainder repeats during long division:

while rem != 0 && digits.len() < max_digits {
    if let Some(&(_, pos)) = seen.iter().find(|(r, _)| *r == rem) {
        repeat_at = Some(pos); break;
    }
    seen.push((rem, digits.len()));
    rem *= 10;
    digits.push(char::from(b'0' + (rem / den) as u8));
    rem %= den;
}

$ pcalc --decimal "1/7"
1/7  = 0.(142857) (repeating)
$ pcalc --decimal "1/6"
1/6  = 0.1(6) (repeating)

1/7's repetend 142857, and 1/6's "non-repeating 1 then repeating 6," both come out right.

Architecture

src/lexer.rs    — tokenizer
src/parser.rs   — Pratt parser → AST → eval
src/rational.rs — i128 rational arithmetic
src/main.rs     — clap CLI (arg or stdin REPL)

Tests are inline (#[cfg(test)]): Pratt precedence/associativity, rational exactness, overflow, repeating decimals.

Run it

cargo run -- "1/3 + 1/6"      # 1/2
cargo test
# or Docker (static Alpine, non-root)
docker build -t pcalc . && docker run --rm pcalc "2^3^2"   # 512

• GitHub: https://github.com/sen-ltd/pratt-calc

Takeaways

• Pratt parsing expresses precedence as two binding-power numbers per operator, not a tower of grammar rules. The core is one loop.
• Right-associativity is rbp < lbp. ^ at (7, 6) gives 2^3^2 = 2^9.
• One prefix rbp for unary minus makes -2^2 = -4 and -2*3 = -6 both true.
• Rationals (num/den) make 0.1 + 0.2 exactly 3/10 — float rounding error gone.
• Overflow → error via checked_*. Don't wrap and lie.
• Repeating decimals fall out of remainder-cycle detection in long division.

This is OSS portfolio #266 from SEN LLC (Tokyo). https://sen.ltd/portfolio/