Assignment 1: Lexer

Due: Midnight pm, Monday September 21st by git commit.
(That is, end of Monday / beginning of Tuesday.)

Handin method

Email me a git repo url some time before the project deadline. You will use one repository for the entire, semester-long, multi-submission project.

Tagging a repo commit is how you submit. When I grade project submissions, I'll check out your repo at the tagged commit. The git tag for project 1 (this one) is "1-lexer". Make sure that the commit you tag has a time stamp before the project deadline.

Make sure you send me your repo url well before the due date. That way I can clone the repo and make sure that I can do pulls and pushes while time isn't pressing.

Make sure I have permission to push to your repo as well as pull, as I will return marked-up and graded assignments to you this way. I am user olin-shivers at github.com, and shivers at the github.khoury.northeastern.edu server.

And make sure that your repo is otherwise only read- and write-accessible to your course coding partner. If you leave your repo world-readable, you'll be culpable if your project code leaks into the wild, where "culpable" here means "will be held partly responsible and will share in the academic-integrity consequences."

Task

Assignment 1 is to build a lexer for Appel's Tiger language using ML-Lex. The Tiger language is defined in Appendix A of the course textbook. Documentation on ML-Lex is available on the class web page, and also (in less detail) in chapter two of the textbook.

Skeleton files to get you started are available in the $TIGER/chap2/ directory, which you can find at Appel's textbook homepage.

What to hand in

Your repo should contain a directory named 1-lexer that contains:

• A tiger.lex file, with the source for your lexer.
• Any other source files you wrote to support your lexer, such as "driver" code, test harnesses, test suites, sources.cm.
• A Project1.md file describing
  • The members of your team
  • How to use the code,
  • What is interesting about your project (if it is interesting):
    • How you handled comments,
    • How you handled errors,
    • How you handled end-of-file, and
    • How did you disambiguate identifiers (such as variable names) from keywords? Did you just leave this to the lexer tool to back into the finite-state machine, or handle it with a hash table? (The latter trick is discussed in the textbook.)
    • Problems & issues you had to solve, and how you did so.
    • Did you do anything clever? What did you do for the free-form parts of the project? Did you do anything extra?
    • Anything else you think is of interest about your lexer.
  … you know — a writeup. Explain what you're submitting.

Details

• You will work in teams of two on every homework assignment this semester. If the class has an odd number of students, you can request a trio; send me mail or talk to me after class for approval. Feel free to use piazza to find a teammate.
• Bear in mind that clean code and good development practices matter; just getting it to work is not enough. Comment your code. Lay it out. Keep your lines under 80 columns wide, except in rare cases. Use good names for things. I have to read it, and your grade depends on my doing so successfully.
• Everything on the "What to hand in" list above is required. Your Project1.md writeup will be graded. (And make sure the markdown text successfully compiles to html, so I can render it before reading it.)
• Your lexer should use the error-reporting machinery in Appel's ErrorMsg module (see file $TIGER/chap2/errormsg.sml), or something equivalent that you write yourself. In particular, error messages should be reported using line-number/column offsets, not by simply specifying the character offset from the beginning of the file.
• It's amazing but true: I've been completely clear in this homework writeup what the assignment is, in detail. And yet, somehow, it's essentially guaranteed that at least one submitted assignment won't even have a Project1.md writeup, or will include code that runs off the right of my screen to roughly column 200. Code won't be commented or indented. It's a puzzling phenomena, difficult to explain, and, yet, somehow, a law of nature. I am so sure of this that if it doesn't happen, I will buy the entire class the hot, caffeinated beverage of your choice at Tatte. Consider the gauntlet thrown.
• Words to the wise: Relative to, say, an LALR parser, it's not hard to build a lexer, but:
  • Tiger's lexical grammar has some complexities that may take you more work to handle than you might initially suspect:
    • Comments nest in Tiger.
    • The string-literal syntax is especially complex, involving a lot of subcases, some of which are fairly complex in their own right. Did you handle all of these cases? Note that Tiger strings are composed of characters from the ASCII character set. You should probably check the wikipedia page on ASCII to better understand the full set of characters in ASCII — including all the "invisible" control characters that require escape sequences to include in a string.
    • Having all of the above machinery interact with your line-number tracking machinery has its own complications. Just a suggestion: when your lexer is complete, look it over and ask yourself, "Did we catch and account for every newline that could occur anywhere in the input stream?"
  • If this is your first experience ever programming in SML, you'll need to allocate time generously to deal with coming up to speed on the language.
  • Does your lexer do the right thing if eof occurs inside a comment or string-literal?
  • Does your lexer correctly spot illegal escape codes in string literals?
• See the course text for more information, in particular chapter two and appendix A.