type token = Number of int | OP_PLUS | LPAREN | RPAREN | EOF

exception End_of_stream

type 'a stream = 
{ 
  peek : unit -> 'a;     
  read : unit -> 'a          (* removes the first element of the stream and returns it *)
}

(* Convert a token list to a stream *)
(* Note: there is a Stream library that provide similar functionality *)
let mk_stream s =
  let stream = ref s in
  let peek () = match !stream with
    | [] -> raise End_of_stream
    | x::xs -> x
  in
  let read () = match !stream with
    | [] -> raise End_of_stream
    | x::xs -> (stream := xs; x)
  in
{peek = peek;
 read = read}

type ast = Int of int | Plus of ast * ast

exception ParseError

(* Helpful for debugging/experimenting *)
let token_to_string t =
  match t with
    | Number n -> string_of_int n
    | LPAREN -> "("
    | RPAREN -> ")"
    | OP_PLUS -> "+"
    | EOF -> "$"

(* LL(1) Parser that converts a token stream into an ast *)	
let parse (s:token stream):ast =
  let rec parse_S () =
    match s.peek() with
      | Number _  | LPAREN -> 
	  let left = parse_E () in
	    parse_S' left
      | _ -> raise ParseError
  and parse_E () =
    match s.read() with
      | Number n -> Int n
      | LPAREN -> 
	   let a = parse_S () in
	     match s.read() with
	       | RPAREN -> a
	       | _ -> raise ParseError
      | _ -> raise ParseError
  and parse_S' left =
    match s.peek() with
      | EOF -> (ignore(s.read()); left)
      | OP_PLUS -> 
	  (ignore(s.read());
	  let right = parse_S () in
	    Plus (left, right))
      | RPAREN -> left
      | _ -> raise ParseError
		   
  in
    parse_S ()

(* Test input for the source string: (1 + 2 + (3 + 4)) + 5 *)
let test_input = [LPAREN;Number 1;OP_PLUS;Number 2;OP_PLUS;LPAREN;Number 3;OP_PLUS;Number 4;RPAREN;RPAREN;OP_PLUS;Number 5;EOF]
let token_stream = mk_stream test_input
let run ()  = parse token_stream