Brainfuck parser

bf.ml

(*
  We use the following grammar, which can be proven to be LL(1) by the derivation below
  
  D  -> >|<|+|-|.|,
  E  -> D E'
  E  -> [ E ] E'
  E' -> E
  E' -> epsilon ; null/empty terminal
  
  from the above, we build the following First sets
  
  First(D) = {'>','<','+','-','.',','}
  First(E -> D E') = {'>','<','+','-','.',','}
  First(E -> [ E ] E') = {'['}
  First(E' -> E) = {'>', '<', '+', '-', '.', ',', '['}
  First(E' -> epsilon) = {epsilon}
  
  Since the production E' -> epsilon is nullable, we must also compute the Follow(E')
  
  For E', we only encounter the production
  E -> D E'
  E -> [E] E'
  
  which gives us Follow(E') = Follow(E)
  rules containing E:
  E -> [E] E' (follow = {']'}
  and
  E' -> E (follow = Follow(E') = Follow(E)}
  
  So we just have Follow(E') = {']'}
  
  With the above sets, we can construct a predictive parse table for the LL(1) grammar:
  
     |  ><+-.,  |   [    |    ]    |
  ---+----------+--------+---------+
   D | anything |        |         |
   E |   D E'   |  [E]E' |         |
   E'|    E     |   E    | epsilon |
  ---+----------+--------+---------+
*)
open Stream

let rec d stream = 
  match peek stream with
  | Some '>' | Some '<' | Some '+' | Some '-' | Some '.' | Some ',' ->
    let op = next stream in
    Printf.printf "D(%c)\n" op
  | _ -> failwith "Parse error in D";
and e stream = 
  match peek stream with
  | Some '>' | Some '<' | Some '+' | Some '-' | Some '.' | Some ',' ->
    (* E -> D E' *)
    print_endline "E -> D E'";
    d stream;
    e' stream
  | Some '[' ->
    (* E -> [ E ] E' *)
    print_endline "E -> [ E ]";
    assert (next stream = '[');
    e stream;
    assert (next stream = ']');
    e' stream
  | _ -> failwith "Parse error in E";
and e' stream = 
  match peek stream with
  | Some '>' | Some '<' | Some '+' | Some '-' | Some '.' | Some ','
  | Some '[' ->
    (* E' -> E *)
    print_endline "E' -> E";
    e stream
  | Some ']' | Some '\n' ->
    (* E' -> epsilon *)
    print_endline "E' -> epsilon"
  | _ -> failwith "Parse error in E'"
  
(* Parse a simple bf expression *)
let () = e (of_channel stdin)