(*
  E1 -> E2 "+" E2 | E2
  E2 -> E3 "*" E3 | E3
  E3 -> n | "(" E1 ")"     

Taking care of the left associativity, we have

  E1 -> E1 "+" E2 | E2
  E2 -> E2 "*" E3 | E3
  E3 -> n | "(" E1 ")"     

By eliminating the left recursion, we obtain

  E1  -> E2 E1'
  E1' -> "+" E2 E1' | ""
  E2  -> E3 E2' 
  E2' -> "+" E3 E2' | ""
  E3  -> n | (E1)     

*)

#load "camlp4o.cma";;
open Genlex;;

type e = Add of e * e | Mul of e * e | Num of int

let lex = make_lexer ["+";"*";"(";")"]

let rec pa_E1 = parser 
  | [< e1 = pa_E2; e = pa_E1' e1 >] -> e
and pa_E1' e1 = parser 
  | [< 'Kwd "+"; e2 = pa_E2; e = pa_E1' (Add (e1, e2)) >] -> e
  | [< >] -> e1
and pa_E2 = parser 
  | [< e1 = pa_E3; e = pa_E2' e1 >] -> e
and pa_E2' e1 = parser 
  | [< 'Kwd "*"; e2 = pa_E3; e = pa_E2' (Mul (e1, e2)) >] -> e
  | [< >] -> e1
and pa_E3 = parser
  | [< 'Int n >] -> Num n
  | [< 'Kwd "("; e = pa_E1; 'Kwd ")" >] -> e;;

let read s = pa_E1 (lex (Stream.of_string s));;
read "1 + 2 * (3 * 4 + (5)) + 6";;