COS 320, Spring 1999. Programming Assignment

Programming Assignment 3: Syntactic Analysis (Parsing)

In this assignment, you will use ML-Yacc to build a parser for the Fun language.  The assignment is due in one and half weeks (March 1st). Chapter 3 of your textbook (particularly 3.4) explains many of the concepts you'll need to know to complete this assignment.    There is also documentation on ML-Yacc here.  You will also need to refer to the Fun language reference here.

Using ml-yacc

  1. Make a new directory as3 for this assignment.
  2. Copy all files from /u/cos320/chap3/ including *.fun *.sml *.sig *.lex *.grm and *.cm into as3.
  3. Please, familiarize yourself with the code that is already there.
  4. We made a couple of changes to the error reporting interface.  Therefore, if you would like to use the lexer you have built already you'll need to make a few changes to your fun.lex file before copying these files into your as3 directory.  If your lexer is not working, please use the lexer we have provided you. If you wish to use your own fun.lex, make sure it contains the following code (you may have to make other changes as well):


  5. Edit fun.grm until it specifies a parser for the Fun language. (The documentation on the language Fun contains a series of BNF rules that describes the syntactic structure of Fun.).  Your parser's semantic actions should generate abstract syntax in the Fun intermediate language.  Here are a list of concerns to keep in mind.


  6. Compile using CM.make(); This will automatically run ml-lex and ml-yacc as necessary.
  7. Test your parser by invoking Compile.compile "filename". This calls Parse.parse and then invokes the interpreter on the file.  The file tests all syntactic constructs in a trivial way but you will certainly want to write other fun files to debug your compiler.  If you want to submit additional test files, please do so.  We might use them to test the other projects!  You can also send them to the cos320 mailing list for others to use.
  8. Write a README file with a detailed description of any shift/reduce conflict that your parser might have. Explain why it is not harmful. You must eliminate all reduce/reduce conflicts, though. (By the way, our parser has no conflicts. However, shift/reduce conflicts are ok as long as they correspond to phenomena, such as "dangling else", that are well understood.)
  9. Submit your solution with submit 3 <all files>.