Commits

vfiack  committed c9b7f9b

separation between parser and optimizer

  • Participants
  • Parent commits e7b099f

Comments (0)

Files changed (1)

File brainfuck/brainfuck.ml

 (** The abstract syntax tree (AST) that will be build then executed *)
 module ParseTree = struct
   type operation =
-    | PtrAdd of int          (** add n to the cell pointer *)
-    | DataAdd of int         (** add n to the current cell's value *)
+    | Move of int          (** add n to the cell pointer *)
+    | Add of int         (** add n to the current cell's value *)
     | Output                 (** write the current cell as an ascii char *)
     | Input                  (** read a char and write it in the current cell *)
     | Loop of operation list (** loop while the current cell is <> 0 *)
   let string_of_op ops =
     let open Printf in
     let rec to_string indent = function
-      | PtrAdd i -> sprintf "%sPtrAdd(%d)" indent i
-      | DataAdd i -> sprintf "%sDataAdd(%d)" indent i
+      | Move i -> sprintf "%sMove(%d)" indent i
+      | Add i -> sprintf "%sAdd(%d)" indent i
       | Output -> sprintf "%sOutput" indent
       | Input -> sprintf "%sInput" indent
       | Loop nodes ->
   open ParseTree
   
   (* lexical analysis, build token list from chars *)
+  
   type token =
     | IncrPtr | DecrPtr
     | IncrData | DecrData
     | '[' -> Open
     | ']' -> Close
     | c -> Comment c
-  
+
   let tokenize charstream =
     let tokens = ref [] in
     Stream.iter (fun c -> tokens := (token_of_char c) :: !tokens) charstream;
     List.rev !tokens
   
   (* syntaxic analysis, build AST from tokens *)
-  let build_group incr decr constructor tokens =
-    let rec loop i lst = match lst with
-      | token :: rest when token = incr -> loop (succ i) rest
-      | token :: rest when token = decr -> loop (pred i) rest
-      | _ -> (constructor i), lst
-    in loop 0 tokens
-  
-  let build_ptr_add = build_group IncrPtr DecrPtr (fun i -> PtrAdd i)
-  
-  let build_data_add = build_group IncrData DecrData (fun i -> DataAdd i)
   
   let build_loop tokens =
     let rec loop acc opened = function
     let rec loop tokens acc =
       match tokens with
       | [] -> acc
-      | (IncrPtr | DecrPtr) :: _ ->
-          let op, rest = build_ptr_add tokens in
-          loop rest (op:: acc)
-      | (IncrData | DecrData) :: _ ->
-          let op, rest = build_data_add tokens in
-          loop rest (op:: acc)
+      | IncrPtr :: rest -> loop rest (Move 1 :: acc)
+      | DecrPtr :: rest -> loop rest (Move (-1) :: acc)
+      | IncrData :: rest -> loop rest (Add 1 :: acc)
+      | DecrData :: rest -> loop rest (Add (-1) :: acc)
       | Write :: rest -> loop rest (Output :: acc)
       | Read :: rest -> loop rest (Input :: acc)
       | Open :: rest ->
     build_ast tokens
 end
 
+module Optimizer = struct
+  open ParseTree
+   
+  let rec group = function
+    | Move a :: Move b :: rest -> group (Move (a+b) :: rest)
+    | Add a :: Add b :: rest -> group (Add (a+b) :: rest)
+    | Loop a :: rest -> (Loop (group a)) :: (group rest)
+    | other :: rest -> other :: (group rest)
+    | [] -> []
+    
+  let optimize ast = group ast
+  
+end
+
 (** Runs the AST *)
 module Interpreter = struct
   open ParseTree
   
   let rec exec ast =
     let exec_node = function
-      | PtrAdd i -> pointer := !pointer + i
-      | DataAdd i -> memory.(!pointer) <- memory.(!pointer) + i
+      | Move i -> pointer := !pointer + i
+      | Add i -> memory.(!pointer) <- memory.(!pointer) + i
       | Output -> Printf.printf "%c%!" (char_of_int memory.(!pointer))
       | Input ->
           let c = input_char stdin in
     List.iter exec_node ast
 end
 
-let brainfuck dump filename =
+let brainfuck optimize dump filename =
   let stream = Stream.of_channel (open_in filename) in
   let ast = Parser.parse stream in
-  if !dump then ParseTree.dump ast else Interpreter.exec ast
+  let ast' = if !optimize then Optimizer.optimize ast else ast in
+  if !dump then ParseTree.dump ast' else Interpreter.exec ast'
 
 let _ =
   let dump = ref false in
-  let args = [("-dump", Arg.Set dump, "dump ast, don't execute")] in
-  Arg.parse args (brainfuck dump) "usage"
+  let optimize = ref false in
+  let args = [
+    ("-optimize", Arg.Set optimize, "optimize ast");
+    ("-dump", Arg.Set dump, "dump ast, don't execute");
+    ] in
+  Arg.parse args (brainfuck optimize dump) "usage"