(* Put your lexer, parser, and interpreter here *) #load "str.cma" (* Use this as your abstract syntax tree *) type ast = Id of string | Num of int | Bool of bool | String of string | List of ast list (* An unparser turns an AST back into a string. You may find this unparser handy in writing this project *) let rec unparse_list = function [] -> "" | (x::[]) -> unparse x | (x::xs) -> (unparse x) ^ " " ^ (unparse_list xs) and unparse = function | Id id -> id | Num n -> string_of_int n | Bool true -> "#t" | Bool false -> "#f" | String s -> "\"" ^ s ^ "\"" | List l -> "(" ^ unparse_list l ^ ")" (************************************************************************) (* Lexing *) let rec regex_or = function [] -> "" | (r::[]) -> r | (r::rs) -> r ^ "\\|" ^ (regex_or rs) let token_re = Str.regexp (regex_or ["("; ")"; "[a-zA-Z0-9=*+/<>!?-]+"; "#t"; "#f"; "\"[^\"]*\""]) let whitespace_re = Str.regexp "[ \t\n]" exception Lex_error of int let tokenize s = let rec tokenize' pos s = if pos >= String.length s then [] else begin if (Str.string_match token_re s pos) then let token = Str.matched_string s in let new_pos = Str.match_end () in (token)::(tokenize' new_pos s) else if (Str.string_match whitespace_re s pos) then tokenize' (Str.match_end ()) s else raise (Lex_error pos) end in tokenize' 0 s (************************************************************************) (* Your parser goes here *) let parse l = Bool false (* write this function *) (* HINT: If you need to define mutually recursive functions, use "and", e.g. let rec parse_list = and parse_sexpr = *) type value = Val_Num of int | Val_Bool of bool | Val_String of string | Val_Nil | Val_Cons of value * value (* You may extend this type, but do not change any of the constructors we have given you *) (* The following function may come in handy *) let rec string_of_value = function Val_Num n -> string_of_int n | Val_Bool true -> "#t" | Val_Bool false -> "#f" | Val_String s -> "\"" ^ s ^ "\"" | Val_Nil -> "nil" | Val_Cons (v1, v2) -> "(cons " ^ (string_of_value v1) ^ " " ^ (string_of_value v2) ^ ")" (************************************************************************) (* Write your evaluator here *) let eval _ = Val_Nil