Assignment 2: Parser

Due: Midnight pm, Thursday October 8th by git commit.
(That is, end of Thursday / beginning of Friday.)

Project 2 is to build a parser for Appel's Tiger language using ML-Yacc. The Tiger language is defined in Appendix A of the course textbook. Documentation on ML-Yacc is available on the class web page, and also (in less detail) in chapters three and four of the textbook.

Your parser should produce an abstract syntax tree using the datatypes defined in the Absyn structure defined in the file $TIGER/chap4/absyn.sml.

Skeleton files to get you started are available in the $TIGER/chap3/ and $TIGER/chap4/ directories, which you can find at Appel's textbook homepage. In particular, these files will be useful:

• tiger.grm — Skeleton ML-Yacc file to get you started
• parsetest.sml — Test driver
• parse.sml — Top-level test driver code
• absyn.sml — AST datatypes
• symbol.sml — Support library providing symbols
• table.sml, table.sig — Support library providing tables
• prabsyn.sml — Useful library for printing ASTs

Remember to update your sources.cm file. Be certain to add ml-yacc-lib.cm to it, in addition to any other new files you are using. You'll want to remove tokens.sml from it, because a tokens file will be automatically generated by ml-yacc now. Also, you'll need to update some header information in your lex file—see the end of chapter 3 for details.

You hand in your assignment the usual way: mark the commit you want to submit in your repo with git tag "2-parser". Your repo should contain a directory named 2-parser that contains:

• A tiger.grm file, the ML-Yacc source for your parser.
• Any other source files you wrote to support your parser.
• The usual writeup, a text file named Project2.md describing:
  • The members of your team
  • How you handled your shift-reduce conflicts, and why you think your resolutions are the right ones.
  • Anything else you think is of interest about your parser

Anything subtle about your grammar, such as ambiguity resolutions of various kinds, should be clearly commented. You knew that, of course.

Your parser should use the same error-reporting machinery you employ in your lexer.

Words to the wise:

• When you start, make no attempt to write the ML code for the semantic actions that construct the AST. Your first task should be to simply write the grammar to parse the concrete syntax; just have each rule produce the unit value ().
• Once your grammar is able to parse all of the test files in $TIGER/testcases, then add semantic actions to the grammar to construct the AST while parsing tiger source code (and deal with any issues that arise when you do this).
• I estimate writing the grammar was about 2/3 of the time I spent writing the parser; adding the semantic actions was about 1/3 of the work.
• You may find it helpful to write tiny toy grammars to explore ideas. I did.

• If you don't understand how shift/reduce parsers work, and can't figure out the table information left in the tiger.grm.desc file by ML-Yacc, you are going to be in a world of pain. You actually have to understand the "characteristic finite state machine:" how the grammar gets turned into the CFSM, how LR and LALR lookaheads makes it deterministic (or don't, producing conflicts), etc. Writing a grammar for a parser tool requires going down a level and understanding what goes on under the hood. Put plenty of time into reading and understanding the textbook material on First and Follow sets, the CFSM, LR, etc., and make sure you start early, so you'll have time to loop around, study more, face-plant, think things over, retry, etc. when your simple first attempts collapse into rubble. All that struggle takes time.

  If you have prior experience with parser generators, no worries — you've already paid your dues and should be all set. But you don't, do you? That's why you're taking the class…

• Be warned that there are some grammatically tricky bits to the grammar that will require some thinking. I tried four different grammars before I settled on my final solution. Had I been smarter, I'd have thought more and hacked less.
• Is your LR parser efficiently parsing lists of arbitrary length (e.g., declarations, or expression sequences)? Are you doing things in ways that require O(n^2) space or time that could be done in linear space or time? Are you doing things in ways that require a linear amount of stack space that could be done in constant space?
• Did you report the locations of syntax errors properly?

See the course text for more information, in particular chapters three and four and appendix A.

Good luck; have fun.