(* COMP 321 Homework 01 Fall 2026 Before you start: * You might want to review the lecture notes at https://dlicata.wescreates.wesleyan.edu/teaching/ppl-26f/lect.html for a commented version of this code. * If your COMP 212 used OCaml instead of SML, a quick reference for translating the syntax you know to SML is https://people.mpi-sws.org/~rossberg/sml-vs-ocaml.html or https://adam.chlipala.net/mlcomp/ * See the schedule of help sessions https://dlicata.wescreates.wesleyan.edu/teaching/ppl-26f/resource.html and come ask for help! * See the course policies here https://dlicata.wescreates.wesleyan.edu/teaching/ppl-26f/policy.html In particular, no generative AI tools can be used to produce the code you submit for this assignment, and you must turn off auto-completion in your text editor. The goal for this assignment is for you to build certain skills and understanding (how to write a parser, understand concrete vs. abstract syntax) and you will not achieve that if you look up the answers or use a tool to solve the problems for you. We may have some assignments later in the semester that explore the use of AI for generating programs, but the academic integrity policy for those problems will note specifically that AI is allowed. If there is no such note, AI is disallowed by default. * You can find documentation of library functions here: https://smlfamily.github.io/Basis/char.html https://smlfamily.github.io/Basis/string.html * Look for the word TASK below to see everything you are supposed to fill in. * To load this code, start smlnj from the directory containing this file, and then type - use "hw01.sml"; at the prompt. *) datatype token = NUM of int | GET | PLUS | LPAREN | RPAREN | VAR of string fun is_digit(c : char) : bool = ord #"0" <= ord c andalso ord c <= ord #"9" fun tokenize_number (l : char list, sofar : int) : int * char list = case l of [] => (sofar , []) | x :: xs => if is_digit x then tokenize_number(xs , 10 * sofar + (ord x - ord #"0")) else (sofar, x::xs) val (123, []) = tokenize_number(String.explode "23", 1) val (123, [#" "]) = tokenize_number(String.explode "23 ", 1) val (123, [#" "]) = tokenize_number(String.explode "3 ", 12) (* TASK 1: Modify this tokenizer so that it allows an arbitrary number of whitespace characters (space, newline, tab, etc.) before or after tokens. You can use Char.isSpace : char -> bool to detect whitespace. For example, the current version of the tokenizer will not accept "get ( 1 )" but your new version should accept that. *) (* TASK 2: Modify this tokenizer so that any sequence of alphabetic characters (upper or lowercase letters) s that is not a keyword (in this case, get) is tokenized as the token VAR s. *) fun tokenize (l : char list) : token list = case l of [] => [] | #"(" :: xs => LPAREN :: tokenize xs | #")" :: xs => RPAREN :: tokenize xs | #"+" :: xs => PLUS :: tokenize xs | #"g" :: #"e" :: #"t" :: xs => GET :: tokenize xs | x :: xs => if is_digit x then let val (n , rest) = tokenize_number (xs, ord x - ord #"0") in NUM n :: tokenize rest end else raise Fail "tokenizer: unexpected character" val (NUM 123) :: [] = tokenize (String.explode "123") val [GET, LPAREN, NUM 1, RPAREN ] = tokenize (String.explode "get(1)") val [RPAREN, PLUS, NUM 1, LPAREN,GET ] = tokenize (String.explode ")+1(get") (* A note on testing. One way to record tests in your file is to put a binding like val [GET, LPAREN, NUM 1, RPAREN ] = tokenize (String.explode "get( 1 )") below the function. If the test passes, you don't see anything; if the test fails, you will get an "uncaught exception Bind" pointing to the line number. This is a good way to record "regression tests" once you know what they are supposed to do and once they pass. While developing code, it is useful to test interactively. For example, I would suggest loading SMLNJ, loading the file, and then doing - tokenize (String.explode " 1"); to see what it does, and then edit the code until it does what you want it to do. The advantage of the interactive tests is that you can see the output even if it is wrong. Write some of your own tests for Task 1 and Task 2 *) datatype exp = Num of int | Get of exp | Plus of exp * exp (* TASK 3: Fill in the case of the parser for plus expressions. The token sequence LPAREN e1 PLUS e2 RPAREN should get parsed as the syntax tree Plus(e1,e2) for any token sequences e1 and e2 that can be parsed into expressions. *) fun parse (l : token list) : exp * token list = case l of [] => raise Fail "expected some token" | NUM k :: xs => (Num k , xs) | GET :: LPAREN :: xs => (case parse xs of (e , RPAREN :: rest) => (Get e , rest) | _ => raise Fail "expected RPAREN") | GET :: _ => raise Fail "expected LPAREN" | _ => raise Fail "unexpected token" fun run(s : string) : exp * token list = parse(tokenize (String.explode s)) val (Get(Num 11),[]) = run ("get(11)") val (Get(Get(Num 11)),[]) = run ("get(get(11))") (* Here is a test for Task 3 val (Plus (Num 11,Plus (Num 2,Num 3)),[]) = parse(tokenize (String.explode "(11+(2+3))")) You should write some more tests of your own as well. *) (* A downside of the above grammar is that it requires parentheses after get and around x+y even when the grouping is unambiguous. In this problem, you will parse a relaxed grammar that allows, for example, get 2 in addition to get(2) 1 + 2 + 3 in addition to (1 + (2 + 3)) By convention, addition will be "right-associative", which means that if you leave off the parens, it groups as x+(y+z) not (x + y) + z. Here is a new grammar for the concrete syntax: f ::= e + f | e e :: k | get e | (f) This grammar has two kinds of expressions, called f and e. An f is either an e + f or an e. An e is a numeric constant, or get before an e, or parentheses around an f. At the level of tokens, this translates to f ::= e PLUS f | e e :: NUM k | GET e | LPAREN f RPAREN TASK 4: Write functions parse_f and parse_e that parse a token list matching f and e, respectively. Hint: the 'and' keyword allows each function to call the other recursively. *) fun parse_f (l : token list) : exp * token list = raise Fail "Unimplemented" and parse_e (l : token list) : exp * token list = raise Fail "Unimplemented" fun run_f(s : string) : exp * token list = parse_f(tokenize (String.explode s)) (* A test for Task 4: val (Plus(Num 1, Plus(Num 2, Num 3)), []) = run_f("1 + 2 + 3") *) (* TASK 5: According to your parser, what abstract syntax trees are "get get 1" and "get 1 + 1" parsed into? Discuss the ways in which this syntax is better or worse than the one from the previous problem. *)