up - cont

Parsing expressions

In a previous course, we saw "abstract" expressions defined by values and binary operators. We also defined generic functions (reduce/interpretation) to evaluate eval:Exp->int, or print an expression print:Exp->string.

In this section, we define the inverse function parse:string->Exp by the way of generic "parsers".

type Exp = 
  | Val of int
  | Add of Exp*Exp
  | Mul of Exp*Exp;;

let e = Add (Val 1, Mul (Val 2, Val 3));;

let rec reduce v a m = function 
  | Val x       -> v x
  | Add (e1,e2) -> a (reduce v a m e1) (reduce v a m e2)
  | Mul (e1,e2) -> m (reduce v a m e1) (reduce v a m e2);;

let eval  = reduce id (+) (*);;
let print = reduce string (fun s1 s2->s1+"+"+s2) (fun s1 s2->s1+"*"+s2);;

printfn "%s = %i" (print e) (eval e);;