let rec listFromString s =
   if String.length s = 0 then
      []
   else
      (String.get s 0)::(listFromString (String.sub s 1 ((String.length s) - 1)))
;;

type arith =
        Number of int
      | Sum of arith * arith
      | Prod of arith * arith
;;

exception InvalidExpression of string;;

let parseGiven lr c =
   match !lr with
      [] -> raise (InvalidExpression ("Expecting "^(Char.escaped c)^" but found END"))
      | (h::t) -> if h=c then lr:= t
         else raise (InvalidExpression ("Expecting "^(Char.escaped c)^" but found "^(Char.escaped h)))
;;

(* 
   S -> T + S | T
   T -> U * T | U
   U -> (S) | V
   V -> 0 | 1 | ... | 9
 *)

let parseV lr =
   match !lr with
      (h::t) when h >= '0' && h <= '9' ->
         lr := t;
         Number ((int_of_char h) - (int_of_char '0'))
      | _ ->
         raise (InvalidExpression "Expected digit not found")
;;

let rec parseU lr =
   match !lr with
      [] -> raise (InvalidExpression "parseU called with empty list")
      | ('('::t) ->
         lr := t;
         let x = parseS lr in
         parseGiven lr ')';
         x
      | _ -> parseV lr

and parseT lr =
   let x = parseU lr in
   match !lr with
      | ('*'::t) ->
         lr := t;
         Prod (x,parseT lr)
      | _ -> x

and parseS lr =
   let x = parseT lr in
   match !lr with
      | ('+'::t) ->
         lr := t;
         Sum (x,parseS lr)
      | _ -> x
;;

let parseArith s =
   let lr = ref (listFromString s) in
   let exp = parseS lr in
   if !lr = [] then
      exp
   else
      raise (InvalidExpression "Expression not completely consumed!")
;;