CS 432

PA3: Decaf Parser

Objective

The goal of our semester-long project is to gain experience in compiler implementation by constructing a simple compiler.

The goal of this part of the project is to gain experience implementing syntax analysis by implementing a recursive-descent parser as the second pass of our Decaf compiler.

Introduction

The semester-long project for this course is to build a compiler for the Decaf language. In this project, you will implement a parser for Decaf, which will be the second phase in our compiler. You will do this by transforming the given Decaf grammar into an LL(1) grammar and implementing a recursive descent parser.

Thoroughly read the Decaf grammar in the reference document. For this assignment, you will need to construct a parser that will accept a stream of tokens and return an abstract syntax tree (AST). There are various AST objects, each of which represents some construct in the Decaf grammar.

You should download the project starter files from the "Files" tab in Canvas. The starter files include many new .java files as well as .class files representing compiled solutions.

Before you begin writing code, you should spend some time reading through all of the infrastructure files provided in the starter files. Our compiler this semester is a large project. Your solution will need to interface with several other classes, and you will need to thoroughly read through those classes to understand their interactions. Also, there are utility functions that you may find useful.

As you study the code, you may find it useful to generate Javadoc references for the existing project files. To do this, run mvn site and then open (using a web browser) the index.html file that is created in the target/site/apidocs folder.

If you have questions about the existing code, please ask them on the Piazza forum (see the link on the sidebar in Canvas).

Assignment

WARNING: You should only proceed with actual development once you are SURE you understand exactly what your task is and how your code should interact with the rest of the system.

Implement the MyDecafParser class by providing an implementation for the following function:

    public ASTProgram parseProgram(Queue<Token> tokens)
            throws InvalidSyntaxException

This function takes as input a Queue of Token objects from the lexing phase. The function should return an abstract syntax tree (AST), rooted in an ASTProgram object. This function represents the root non-terminal (i.e., start symbol) parsing routine in your recursive descent parser.

For this particular project, you should pay special attention to the following classes:

• DecafParser - Base class for your parser. Provides some useful helper methods for manipulating the queue of tokens.
• ASTNode - Abstract syntax tree (AST) base class. All other AST node objects inherit from this one.
• InvalidSyntaxException - Special exception that your code should throw when you detect invalid syntax.

You will first want to make sure you understand the grammar in the Decaf reference document. Then, you will want to spend some time modifying it so that it is more useful to you for this assignment (i.e., converting it to be LL(1) with proper precedence and associativity). Then, you should begin writing your parser, using your LL(1) grammar as a guide as discussed in class and the textbook.

WARNING: This is a large project! The code you will write is not terribly complicated, but there is a lot of it because you will be writing a method for almost every non-terminal in your grammar. This is a daunting task if you have never written a parser before, so you must start early and ask questions. I suggest starting with a much-reduced form of the grammar, then gradually expanding it. Here is an example LL(1) grammar that represents a small portion of the Decaf grammar (formatted for use with Grammophone), suitable for getting started on this project:

Program -> VarDecls FuncDecls .

VarDecls -> Var VarDecls .
VarDecls -> .

FuncDecls -> Func FuncDecls .
FuncDecls -> .

Var -> Type ID ; .
Func -> def Type ID ( ) Block .
Block -> { } .
Type -> int | bool .

Of course, variable declarations are more complex in real Decaf because they could be arrays, and function declarations may include parameters (or have a 'void' return type). The definition of a block is also clearly incomplete. However, the above grammar does describe a complete language, and that language is a subset of the real Decaf language. Thus, it is an easier target to aim for when you first start working on the project.

Sample Input

def int add(int x, int y)
{
    return x + y;
}

def int main()
{
    int a;
    a = 3;
    return add(a, 2);
}

Sample Output

Program  [add.decaf:1]
  Function: add : int (x:int, y:int)  [add.decaf:1]
    Block  [add.decaf:2]
      Return  [add.decaf:3]
        BinaryExpr: +  [add.decaf:3]
          Location: x  [add.decaf:3]
          Location: y  [add.decaf:3]
  Function: main : int ()  [add.decaf:6]
    Block  [add.decaf:7]
      Variable: a : int  [add.decaf:8]
      Assignment: a = 3  [add.decaf:9]
        Location: a  [add.decaf:9]
        Literal: 3 : int  [add.decaf:9]
      Return  [add.decaf:10]
        FunctionCall: add (a, 2)  [add.decaf:10]
          Location: a  [add.decaf:10]
          Literal: 2 : int  [add.decaf:10]

Reflection

One of the goals of this course is to encourage introspection and thoughtful, deliberate development processes. For this project, you will submit a short (2-3 paragraphs) reflection, answering any (or all) of the following questions as appropriate:

• How does this project fit into the overall picture of our semester-long compiler project? Why is it important?
• Describe your design and development process. Did you use a formal software development method?
• What aspects of this project proved to be the most rewarding?
• What aspects of this project proved to be the most challenging? How did you overcome these challenges?
• How do you know your submission is correct? Briefly describe your testing regimen.
• If you had to start the project again from scratch, what would you do differently?
• What concepts from our theoretical class material or techniques from our classroom activities did you apply in this project?
• Suppose you weren’t using any of the concepts or techniques we’ve covered in class this semester; how would your solution to this project be different?
• What other areas of computer science (or CS courses you’ve taken) impacted your solution to this project?
• Do you have any other feedback about this project?

Include as much detail as you can, but do not ramble. Concise answers are preferred over verbose ones. Your reflection will be graded on a five-point scale:

Submission

DUE DATE: Friday, October 13, 23:59 EDT (11:59PM)

Please submit your MyDecafParser.java file and your reflection to the appropriate assignments on Canvas.

Code Reviews

One of the goals of this course is to encourage good software development practices, especially when building a large software system (such as a compiler). For this project, you will be assigned two other random students in the course. You must review their code and offer constructive feedback according to the given rubric.

Submit your review on Canvas by Friday, October 20. Please submit your review as a comment (not an attached file).

Grading

Here is the grading breakdown for this project: