CPSC425 Spring 2008
Lexical Analysis in ML

Your assignment is to write a simple lexical analyzer in ML for tokens in the language Simple as described here. Lexers are often table-driven, taking the lexical grammar for the language as input, but you will use some unique features of ML to take a somewhat different approach.

Input and Output

You should provide the following top-level function:

lex : string -> string list Function lex should take a filename and return a list of the tokens in the file. Each token should be represented as a string. If a lexical error is encountered, lex should create an error token that includes the characters that could not be tokenized and include it in the resulting list. The rest of the file should be lexed as usual.

You may find it convenient to view your result using function printTokens:string list -> unit, which take a list of strings and prints the strings one per line. That is, typing printTokens(lex "testfile")) will give you nicer looking output than just lex "testfile".

Program Structure

Lexical analysis is usually quite tedious, with much of the processing devoted to getting and checking characters to determine where one token stops and the next begins. But this sort of processing can be minimized by strategic use of the following built-in functions from ML's String structure:

String.tokens : (char -> bool) -> string -> string list String.tokens takes a function, a string, and a list of strings. The function takes a character and returns true if that character should be considered a delimiter, that is, something that separates tokens. It then breaks the string into tokens accordingly, returning a list of those tokens represented as strings. The delimiter(s) are not included. Examples:
- String.tokens Char.isSpace "this is a test" => ["this","is","a","test"]
- String.tokens (fn c => (c = #".") orelse (c = #"*")) "one.two*three" => ["one","two","three"];
This is not unlike the capabilities of the StringTokenizer and Scanner classes in Java.
Of course, you can't count on tokens being nicely delimited in program input; for example, given the string x:=3+foo-(AnotherID/123.4) you need to be able to extract the tokens x, := (note that this is just one token), 3, +, foo, -, (, AnotherID, /, 123.4, and ). There is another ML function that can help you with this:
String.translate : (char -> string) -> string -> string String.translate takes a function f and a string s and returns a string in which each character c in s has been replaced with the string (f c). These strings are concatenated together to form the resulting string. Example:
- ```
fun foo #"*" = "**"
 |  foo #" " = ""
 |  foo c    = str c;
String.translate foo "a * b*c" => "a**b**c"
```

The strategy for the lexer is to use String.translate to separate out characters that need to be dealt with in special ways, leaving characters that will ultimately stay together (e.g., in numbers and identifiers) intact. That is, the delimiters that are needed by String.tokens can be inserted by String.translate before the string is passed to String.tokens. The string returned by String.tokens will still need some work, of course (e.g., distinguishing between < and <=, and between 23 and 23.4), but it's a good start.

General Comments

Be sure that you use good ML style throughout, pattern matching as appropriate and so on. Your program should be clearly written but should still be well documented. In addition to a brief description, be sure to include a type signature with each function. -

CPSC425 Spring 2008 Lexical Analysis in ML

Input and Output

Program Structure

General Comments

CPSC425 Spring 2008
Lexical Analysis in ML