Reading

Overview

Your job is to complete the CUP specification of a LALR parser for Tiger with semantic actions that build a program's corresponding abstract syntax tree. The AST hierarchy has already been implemented and requires no further modification.

You may choose to complete this assignment in one of two ways, which are detailed below.

Files in this distribution

  1. Download hw5.zip , which contains several new files to add to your existing tigerc project. The new files are the following:

    tigerc
      --> doc
            -- tiger_absyn.pdf                   (Listing of the AST classes)
      --> src
            --> tigerc
                   --> syntax
                         --> absyn               
                               -- (various files, all of which you need)
                         --> parse
                               -- cs433_hw5_Tiger.cup     
                                                (The JFlex specification file)
                         --> util
                               -- AbsynPrintVisitor.java  
                                                (pretty-printer for ASTs)
                               -- ErrorMsg.java (note the new location, as well as
                                                 the updated code)
                               -- Symbol.java
                   --> util
                         -- List.java           (basic singly-linked list)
                         -- Pair.java           (pair class)
      --> test
            --> testcases                       (very simple Tiger source files,
                   -- simplest.tig               usable for testing your parser)
                   -- array_exp.tig
                   -- assign.tig
                   -- decls1.tig
                   -- decls.tig
                   -- record_exp.tig
                   -- str_test2.tig
                   -- vars.tig
            --> notes
                   --> reference_solution       (source files generated from my
                                                 JFlex and CUP files:  rename
                                                 appropriately & copy to the
                                                 appropriate package)
                         -- lasseter_TigerLex.java
                         -- lasseter_TigerParse.java
                         -- lasseter_TigerSyms.java
                   -- file_list.txt             (concatenation of all Tiger files
                                                 in the test/testcases folder)
                   -- all_absyn.txt             (abstract syntax trees printed by 
                                                 my solution on the 49 test**.tig
                                                 files)
            -- TestParser.java                  (test driver for the parser)
    

    The directory structure given dictates where each file/folder should go in your project.

    The classes for representing abstract syntax trees are in the tigerc.syntax.absyn, and are documented in the file doc/tiger_absyn.pdf.

    Your Job

    Option 1

    Add the appropriate modifications to your own CUP specification, completed in Assignment 4. If you choose this option, begin by printing out an untouched copy of what you turned in for Assignment 4. The reason for this is that if, during the course of this work, you discover errors in your that specification, you may fix them, mark the corrections on the original printout (so that I don't go mad trying to find them), and resubmit your work for re-grading. I will count the better of the two efforts for your HW #4 grade.

    Option 2

    The distribution for this assignment includes a nearly-complete but error-ridden CUP specification. Instead of your own work, you may use mine as a jumping off point for modification. You will also need to include a short report, as described below.

    You will begin by making a few small corrections to the file in order to produce a working parser specification from which the source files TigerParse.java and TigerSyms.java are generated. Modify the grammar so that all reduce/reduce conflicts are eliminated, and and all shift/reduce conflicts are either eliminated or judged to be safe.

    Following this, you will add to the parser the actions necessary to produce a correct abstract syntax tree from any legal Tiger source code. The syntax-direct construction of the abstract syntax is only partially given in the distributed CUP file. In other places, the corresponding action is simply the stub

    {: RESULT = null; :}
    

    Replace these with appropriate Java statements to yield a complete construction (note that not all of the assignments to null are wrong).

    A note about this option

    Once you fix all of the necessary precedence and associativity conflicts, you'll end up with four remaining shift/reduce conflicts. Shift/reduce conflicts are always resolved by shifting, and if this is the right thing to do, then this conflict can be considered "expected" and thus ignored.

    Save the report of these four conflicts to a file, which you'll turn in with your finished work.

    However, at least one of these conflicts should be resolved by reduction, and thus it must be fixed by changing the grammar. To see that shifting does the wrong thing, try the testParser task on the file array_test2.tig, which consists of the sequence

        (iarr[i] := 5; x := iarr [2] of 0)
    

    This should result in the parse tree

    ExpSeq(
      [List of Exps:
        ExpAssign(
          VarSubscript(
            VarSimple(iarr),
            ExpVar(
              VarSimple(i))),
              ExpInt(5)),
            ExpAssign(
              VarSimple(x),
              ArrayExp(
                iarr,
                ExpInt(2),
                ExpInt(0)))
           ])
    

    but with the grammar as distributed, it is reported as a syntax error.

    You will need to rewrite the corresponding productions to eliminate this ambiguity.

    On the report of the four conflicts, identify the ones that are acceptable, and modify the build.xml file appropriately.

John H. E. Lasseter