Programming Assignment 3: Syntactic Analysis (Parsing)

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):
   • In the first section, replace the first few lines with:

     type arg = int
     type svalue = Tokens.svalue
     type pos = int*int
     type ('a,'b) token = ('a,'b) Tokens.token
     type lexresult = (svalue,pos) token 

   • Add the definition of the make_pos function.
     
     fun make_pos yypos yytext = 
       ( (!lineNum, charPos yypos), 
         (!lineNum, (charPos yypos) + String.size(yytext) - 1) )

   • After the first %%:

           %header (functor FunLexFun (structure Tokens: Fun_TOKENS));
           

   • The token constructors now take objects with type pos*pos where pos 
     is the new position type (int*int). You can generate these using the 
     make_pos function. For example:
     
     <INITIAL>fun => (Tokens.FUN(make_pos yypos yytext));

   • Similarly the type of ErrorMsg.error uses the new pos type,
     and so you should use make_pos to pass positions to it.

    

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.
   • You will need to specify terminal names that corresponds to the names of tokens generated by the lexer.  ML-Yacc automatically generates a structure that will build the tokens.  In other words, fun.grm will need to contain the following code (extended with the other terminal names):
     
     %term EOF
     | INT of int
     | ID of string
     | COMMA | SEMICOLON | COLON
     | LPAREN | RPAREN | ...
     
     The non-terminals you use can have any names that you want.  For example,
     
     %nonterm foo of Fun.exp | ...
     
     But I recommend more descriptive names than "foo".
      
   • Some of the source level operations do not appear in the intermediate language. For instance, the "and", "or", "sequencing" (i.e., semicolon), and "unary minus" need to be compiled into other existing constructs.
   • In order to do type checking for Fun, the ref operator will need to be annotated with a type. The source language syntax for this is
     
     exp ::= ref (exp:tp)
     
     In the target language, this should be compiled to a combination of a ref operation and a Annot construct:
     
     ref (3:int) ==> Fun.Op(Fun.Ref,[Fun.Annot(Fun.Int 3)])
      
   • Each object that you generate in the abstract syntax should be wrapped in a Fun.Pos constructor that marks the beginning and ending line and column numbers of the construct in the source code.
   • Use precedence directives only where necessary and intuitive.  (In other words, don't just throw in precedence directives to correct any random error in your grammar.  Use them when they actually correspond to precedence of operators in the fun language.)
   • Add some support for detection and correction of common errors. Explain the support you add in your README file.

    

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 all.fun 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>.