teejparser.mly

%{
open Tree
(*
type expr = Tree.expr =
  | Literal of int
  | Add of (expr * expr)
  | Sub of (expr * expr)
  | Mul of (expr * expr)
  | Div of (expr * expr)
*)
%}
%token <int> NUMBER (* 123 *)
%token PLUS (* + *)
%token DASH (* - *)
%token ASTERISK (* * *)
%token BAR (* / *)
%token LEFT_PARENS (* ( *)
%token RIGHT_PARENS (* ) *)

%token EOF

%start <Tree.expr option> expr_opt
 
%%

let expr_opt :=
  | EOF;
    { None }
  | expr = expr; EOF;
    { Some expr }

(*
  right-associative infix has the following pattern
  let self := 
    | left = self; TOKEN; right = lower; {}
    | lower
  
  higher precedence means closer to atom
*)

let expr := expr_add_and_sub

let expr_add_and_sub :=
  | left = expr_add_and_sub; ASTERISK; right = expr_mul_and_div;
    { Mul (left, right) }
  | left = expr_add_and_sub; BAR; right = expr_mul_and_div;
    { Div (left, right) }
  | expr_mul_and_div

let expr_mul_and_div :=
  | left = expr_mul_and_div; PLUS; right = expr_atom;
    { Add (left, right) }
  | left = expr_mul_and_div; DASH; right = expr_atom;
    { Sub (left, right) }
  | expr_atom

let expr_atom :=
  | n = NUMBER;
    { Literal n }
  | LEFT_PARENS; expr = expr; RIGHT_PARENS;
    { expr }