Skip to content
Tutorials Center
My learning

Topics

Lesson 37 of 40 ยท Projects and Practice

Project: Build an Expression Parser, Evaluator and Simplifier

Build a calculator in OCaml from scratch. Tokenize text, parse it with recursive descent into a variant type, evaluate with variables, simplify symbolically and take derivatives, with a runnable Python mirror.

Language processing is where OCaml shines: variant types describe syntax trees, and pattern matching transforms them. In this project you build a small calculator in four stages: a tokenizer, a parser, an evaluator and a simplifier, then finish with symbolic differentiation. Every stage is a short function, and the types guide the design.

OCaml is not available in the site's code runners. The OCaml code below is written for OCaml 5 and standard library only (save it as calc.ml and run ocaml calc.ml, or build with dune). A Python program mirrors it so you can run and extend the algorithm here; the printed results shown come from that mirror and match what the OCaml code produces.

Plan

flowchart LR
    S["text<br/>\"2 * (x + 3)\""] --> T["tokenize"] --> P["parse"] --> A["expr tree"]
    A --> E["eval env"]
    A --> M["simplify"]
    A --> D["derive"]

Figure: from text to a tree, and three things to do with the tree.

1. Types

OCAML
type expr =
  | Num of float
  | Var of string
  | Neg of expr
  | Add of expr * expr
  | Sub of expr * expr
  | Mul of expr * expr
  | Div of expr * expr
  | Pow of expr * int

type token =
  | TNum of float
  | TId of string
  | TPlus | TMinus | TStar | TSlash | TCaret
  | TLParen | TRParen

The tree is the only representation the later stages see, which is the central idea of a variant type.

2. Tokenizer

OCAML
let is_digit c = c >= '0' && c <= '9'
let is_alpha c = (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || c = '_'

let tokenize s =
  let n = String.length s in
  let rec go i acc =
    if i >= n then List.rev acc
    else
      match s.[i] with
      | ' ' | '\t' -> go (i + 1) acc
      | '+' -> go (i + 1) (TPlus :: acc)
      | '-' -> go (i + 1) (TMinus :: acc)
      | '*' -> go (i + 1) (TStar :: acc)
      | '/' -> go (i + 1) (TSlash :: acc)
      | '^' -> go (i + 1) (TCaret :: acc)
      | '(' -> go (i + 1) (TLParen :: acc)
      | ')' -> go (i + 1) (TRParen :: acc)
      | c when is_digit c || c = '.' ->
          let j = ref i in
          while !j < n && (is_digit s.[!j] || s.[!j] = '.') do incr j done;
          go !j (TNum (float_of_string (String.sub s i (!j - i))) :: acc)
      | c when is_alpha c ->
          let j = ref i in
          while !j < n && (is_alpha s.[!j] || is_digit s.[!j]) do incr j done;
          go !j (TId (String.sub s i (!j - i)) :: acc)
      | c -> failwith (Printf.sprintf "unexpected character %C at %d" c i)
  in
  go 0 []

The loop is a tail-recursive function carrying the output list in reverse, a standard idiom, and the inner while uses a reference as a scanning index.

3. Parser: recursive descent

The grammar, from loosest to tightest binding:

TEXT
expr   = term   { ("+" | "-") term }
term   = unary  { ("*" | "/") unary }
unary  = "-" unary | power
power  = atom [ "^" integer ]
atom   = number | identifier | "(" expr ")"

Each rule becomes one function that takes the token list and returns the tree plus the remaining tokens:

OCAML
let rec parse_expr ts =
  let lhs, rest = parse_term ts in
  expr_loop lhs rest

and expr_loop lhs = function
  | TPlus :: rest -> let r, rest = parse_term rest in expr_loop (Add (lhs, r)) rest
  | TMinus :: rest -> let r, rest = parse_term rest in expr_loop (Sub (lhs, r)) rest
  | ts -> (lhs, ts)

and parse_term ts =
  let lhs, rest = parse_unary ts in
  term_loop lhs rest

and term_loop lhs = function
  | TStar :: rest -> let r, rest = parse_unary rest in term_loop (Mul (lhs, r)) rest
  | TSlash :: rest -> let r, rest = parse_unary rest in term_loop (Div (lhs, r)) rest
  | ts -> (lhs, ts)

and parse_unary = function
  | TMinus :: rest -> let e, rest = parse_unary rest in (Neg e, rest)
  | ts -> parse_power ts

and parse_power ts =
  match parse_atom ts with
  | base, TCaret :: TNum n :: rest -> (Pow (base, int_of_float n), rest)
  | r -> r

and parse_atom = function
  | TNum n :: rest -> (Num n, rest)
  | TId x :: rest -> (Var x, rest)
  | TLParen :: rest -> (
      match parse_expr rest with
      | e, TRParen :: rest -> (e, rest)
      | _ -> failwith "expected )")
  | _ -> failwith "unexpected token"

let parse s =
  match parse_expr (tokenize s) with
  | e, [] -> e
  | _ -> failwith "unexpected input after expression"

Because each *_loop function builds Add (Add (a, b), c), subtraction and division are left associative: 8 - 3 - 2 is (8 - 3) - 2 = 3, not 8 - (3 - 2).

4. Evaluator

OCAML
let rec eval env = function
  | Num n -> n
  | Var x -> (
      match List.assoc_opt x env with
      | Some v -> v
      | None -> failwith ("unbound variable " ^ x))
  | Neg e -> -.eval env e
  | Add (a, b) -> eval env a +. eval env b
  | Sub (a, b) -> eval env a -. eval env b
  | Mul (a, b) -> eval env a *. eval env b
  | Div (a, b) ->
      let d = eval env b in
      if d = 0.0 then failwith "division by zero" else eval env a /. d
  | Pow (b, n) -> eval env b ** float_of_int n

Evaluate "2 * (x + 3)" with x = 4: the parser builds Mul (Num 2., Add (Var "x", Num 3.)) and eval [("x", 4.)] gives 14..

5. Simplifier

Rewrite rules with patterns, applied bottom-up:

OCAML
let rec simplify e =
  match e with
  | Add (a, b) -> (
      match (simplify a, simplify b) with
      | Num x, Num y -> Num (x +. y)
      | Num 0., e | e, Num 0. -> e
      | a, b -> Add (a, b))
  | Mul (a, b) -> (
      match (simplify a, simplify b) with
      | Num x, Num y -> Num (x *. y)
      | Num 0., _ | _, Num 0. -> Num 0.
      | Num 1., e | e, Num 1. -> e
      | a, b -> Mul (a, b))
  | Sub (a, b) -> (
      match (simplify a, simplify b) with
      | Num x, Num y -> Num (x -. y)
      | e, Num 0. -> e
      | a, b -> Sub (a, b))
  | Neg a -> ( match simplify a with Num x -> Num (-.x) | Neg e -> e | a -> Neg a)
  | e -> e

6. Derivatives

OCAML
let rec deriv x = function
  | Num _ -> Num 0.
  | Var y -> if y = x then Num 1. else Num 0.
  | Neg e -> Neg (deriv x e)
  | Add (a, b) -> Add (deriv x a, deriv x b)
  | Sub (a, b) -> Sub (deriv x a, deriv x b)
  | Mul (a, b) -> Add (Mul (deriv x a, b), Mul (a, deriv x b))
  | Div (a, b) -> Div (Sub (Mul (deriv x a, b), Mul (a, deriv x b)), Pow (b, 2))
  | Pow (b, n) -> Mul (Mul (Num (float_of_int n), Pow (b, n - 1)), deriv x b)

The raw result is full of 0 + ... and 1 * ..., which is why the simplifier exists: simplify (deriv "x" (parse "x^2 + 3*x")) shrinks the tree.

Runnable mirror in Python

This is the same program, using tuples for the tree. Run it and extend it with new operators or functions such as sqrt.

Python Stand-in: tokenizer, parser, evaluator, simplifier, derivative

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Ideas to extend

  • Add functions such as sin(x) and sqrt(x) as Call of string * expr.
  • Return (float, string) result instead of raising (option and result).
  • Add let x = 3 in x * x to the grammar for a tiny language with variables.
  • Print trees with Format so long expressions wrap.
  • Rewrite the typed evaluator as a GADT with booleans and comparisons.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does the parser use one function per grammar rule?

    Calling the tighter-binding rule from the looser one makes * bind tighter than + automatically.
  2. 2. What makes 8 - 3 - 2 evaluate as (8 - 3) - 2?

    expr_loop builds Sub (lhs, r) with the accumulated left tree as the first argument.
  3. 3. What is the simplifier's job after differentiation?

    Raw derivative formulas produce many neutral terms that simplify cleans up.
  4. 4. What would the compiler tell you if you added a new constructor Sqrt of expr to expr?

    Exhaustiveness warnings point at every function such as eval and deriv that must handle the new case.

Summary

  • A variant type describes the syntax tree. Tokenizing, parsing, evaluation, simplification and differentiation are small pattern-matching functions.
  • Recursive descent maps each grammar rule to a function and gets precedence and associativity from loops.
  • The compiler's exhaustiveness checks keep every stage in step when you extend the language.

Next: Project: A JSON Parser and Pretty Printer