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. This involves two major tasks:

  1. Complete the skeleton CUP specification for the Tiger programming language. Refer to the language manual for details of the syntax. Your grammar should correctly reflect all precedence and associativity rules.

    It is possible (indeed likely) that you will encounter one or more shift/reduce conflicts. By default, CUP resolves such conflicts in favor of shifting. If this is the correct choice for the conflict, you should add a directive to CUP, telling it to expect this conflict. Specifically, in the build.xml file, there is a task, genParse:

    <target name="genParse" depends="init" description="Generate the parser">
        <cup srcfile="${src_root}/tigerc/syntax/parse/Tiger.cup" 

    Change the value of the expect attribute to reflect the number of acceptable shift/reduce conflicts in your grammar.

    All reduce/reduce conflicts should be considered errors in your grammar, and they must be eliminated. Similarly, if you have any shift/reduce conflicts that should resolve in favor of reduction, you will need to eliminate them by rewriting that part of your grammar.

  2. For each grammar production rule, add action code that constructs an appropriate abstract syntax tree.

The classes for the AST hierarchy have already been implemented, and they're included in the package tigerc.syntax.parse.absyn. This part requires no further modification (we'll talk about that weird-looking accept() method when we get to our study of interpretation; suffice it to say for now that it's used by the pretty-printer and other tasks we'll define on AST structure).

Files in this distribution

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

      --> doc
            -- tiger_absyn.pdf                   (Listing of the AST classes)
      --> src
            --> tigerc
                   --> syntax
                         --> absyn               
                               -- (various files, all of which you need)
                         --> parse
                               -- Tiger.cup     
                                                (The JFlex specification file)
                               -- reference solutions for the lexer and parser
                         --> util
                               -- ErrorMsg.java (note the new location, as well as
                                                 the updated code)
                               -- Symbol.java
                   --> util
                         -- Pair.java           (pair class)
                         -- ErrorMsg.java
                         -- Symbol.java         (these were also part of HW1)
      --> 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
                   -- binop.tig     (this one should work with the CUP skeleton)
                   -- test**.tig    (many other Tiger files, legal and illegal)
            -- 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.

John H. E. Lasseter