Syntactic Analysis

Assignment 3
CPTR 415 Compiler Construction

  1. Overview

    2. In this assignment you will implement a syntactic analyzer for the Decaf language.

  2. Issues

    1. Teams. You are welcome to work with another student in this class for this part of the project. Submit just one copy of your work, but make sure to include the names of both team members in your code. You make work alone, if you prefer.

    2. Tool. You are to use Yacc to implement your syntactic analyzer. The Decaf grammar is given on the Decaf Language Specification page.

    3. Ambiguity. The Decaf grammar presented in the language specification is ambiguous. Consequently, you will have to use the associativity rules and operator precedence rules to tell Yacc how to resolve the ambiguities. See the Lex and Yacc book about how to resolve the dangling else conflict.

    4. Grammar refinement. The Decaf grammar specification uses some notational conventions such a Kleene closure (*) and positive closure (+) that are not recognized by Yacc. You will need to rewrite the productions (as we discussed in class) so that Yacc will recognize them.

    5. Errors. Your syntactic analyzer is expected to recognize syntax errors but not semantic errors (for example, it is not expected to recognize type checking errors, multiply defined identifiers, undefined indentifiers, etc.). The next assignment will tackle semantic errors.

      To assist the parser in recognizing syntax errors, Yacc provides error tokens. The dragon book suggests that error recovery be associated with "major" nonterminals that generate expressions, methods, statements, and classes. Using error tokens with finer-grained nonterminals allows you to report as many errors as possible but may hopelessly confuse the parser. Error productions on coarser-grained nonterminals allows the parser to continue longer but may miss reporting a large number of errors. You should experiment with error tokens and their placement to see what works best for you.

      Any errors detected by the lexical analyser should be reported, and error tokens should not be passed to the parser. Deleting these tokens may cause parse errors, but passing them would not be helpful either.

    6. Parse tree. Your syntactic analyzer should build a parse tree. This serves to verify the correctness of your parser. Later assignments will be a bit more ambitious, building an abstract syntax tree instead which will be used for semantic analysis.

  3. Format of Output

    4. Your syntactic analyzer should produce two outputs:

    1. A set of error messages. Each error message should consist of
      1. the line number where the error was detected,
      2. the contents of the line, and
      3. an informative error message describing the nature of the error.
      If the program has no errors, nothing should be printed for this part.

    2. The parse tree. Each interior node of the parse tree should be printed showing the production to which it was expanded. For example, if the node is ClassDeclaration, the production printed would be (nonterminals should be enclosed in angle braces( < >): 

      		    < ClassDeclaration >  ->  class  identifier  < ClassBody >

      The nodes should be printed in preorder. Hence, the productions that are output will form a leftmost derivation. Leaf nodes should not be printed, since they will occur on the righthand side of the appropriate productions.

      The two sections of the output should be distinct. The error output should appear first, and then the parse tree output should follow. The output from the lexical analysis assignment, with the exception of the error messages, should be eliminated. Thus, you should print no messages about tokens recognized.

  4. Assignment Submission and Grading

    5. You should do all your developement within a single directory. When you are ready to submit the assignment, create a directory in your home directory called submit_parser and copy all your files into this submission directory. Be sure to provide a make file so I need only unpack your files, run make, and then execute your program.

    Your syntactic analyzer will be tested against a variety of test files.

    You source code should use comment blocks to explain any non-obvious operations (for example, how you handle errors).

    The possible number of points for this assignment is 10. Points are weighted as follows:

    Correct and complete parse tree
    built and displayed for correct
    Decaf programs    		 6
    Error messages are informative 2
    Program builds flawlessly 1
    Source code is readable and
    well commented    		 1