CS 453 Programming Assignment #4 — Adding tones, less than, classes, methods

Due Tuesday April 2th (by 11:59pm mountain time )

Introduction

This assignment can be done with your CS 453 programming partner. For PA4, PA5, and PA6 joint and separate partner reports are required if you are working with a partner (see below for details). The joint report should be put in the README file and the separate reports should be emailed to cs453@cs.colostate.edu. Both are due with the assignment itself. The partner joint and separate reports will be worth 10% of the programming assignment grade for those of you working with a partner.

In this assignment you will extend MeggyJava and hence the compiler to the PA4 subset that includes the playing tones method (Meggy.toneStart), the less than operator, user-defined methods, and method calls. You will

add the PA4 grammar rules to the parser,
create a set of classes to represent methods and parameters and organize instances of these in the symbol table, and
create a build symbol table visitor, add PA4 type checking to the check types visitor, and code generation visitor for the PA4 grammar.

Note that even though the grammar enables the declaration of classes, you will not be implementing objects until PA5. You need the syntax of class definitions and calling methods on receivers like "new Foo()" and "this". For this assignment, the focus is on code generation for methods. Your compiler needs to check for undefined, doubly defined, and incorrectly typed symbols.

NOTE that MeggyJava does not allow passing buttons as parameters to user-defined functions or assigning button values to variables. This is a pedagogical simplification. For PA3 we discussed an approach for generating the checkButton method that relies on the button values to be passed as constants to the checkButton method. If we enabled button values to be assigned to parameters (or later other variables), then we would have to generate more complex code to determine the button value at runtime and therefore check the correct run-time library variable name OR use the GetButtons() method in the provided MeggyJrSimple interface and do some bit vector manipulation.

Here are some example programs: PA4noDef.java, PA4doubleDef.java, and PA4bluedot.java, its symbol table, and its PA4bluedot.java.s file.

Notice that PA4doubleDef is legal Java but illegal MeggyJava (no overloading is allowed in MeggyJava).

The above .s files are from the reference compiler and therefore include code for passing the pointer to object instances for each method call. See PA4bluedot.java.noObjs.s and PA4raindrop.java.noObjs.s for .s files where there are no object instances being passed around.

The Assignment

We do not provide any new code for PA4. All of the AST nodes and the needed visitor classes such as DepthFirstVisitor were provided in previous assignments. You will be designing and writing your own symbol table data structure.

Your PA3 Makefile will create a .jar file, MJ.jar, that can be executed as follows:

   java -jar MJ.jar InputFile.java

Make sure to include any new *.class and *.java files into the .jar file. Edit the Makefile to ensure this happens.

The input files can be any PA4 MeggyJava program. The PA4Test#.java examples you wrote for PA1 and PA4MazeSolver.java are possible test cases without any semantic analysis errors. Write legal and illegal test cases, and report in README which cases are illegal and why they are illegal.

Getting Started

The following is a suggested progression for starting this assignment:

Start with your working PA3 compiler.
Write test cases for the new features in PA4, one feature at a time.
Extend the grammar for the new features in PA4, one feature at a time.
Write some functions and function calls in AVR by hand. The AVR code you write should be something you could generate with the AVR code generator visitor. Make sure the assembly code you are using works for recursive functions.
Start by assuming that programs have the correct types and modify the AVR code generator visitor to generate code for methods and method calls.
Use additional features in your test inputs such as using function calls in complex expressions and Meggy.toneStart(). Modify the code generator visitor to handle these new features.

To enable type checking, extend the symtable package provided for PA3 so that it keeps track of the type signature for each method and the formal variables for the method and their types. Here is a possible interface for the SymTable data structure:

public class SymTable {
    public SymTable() {
        /* WRITE ME */
    }
    
    /** Lookup a symbol in this symbol table.
     * Starts looking in innermost scope and then
     * look in enclosing scopes.
     * Returns null if the symbol is not found.
     */
    public STE lookup(String sym) {
        /* WRITE ME */
    }

    /** Lookup a symbol in innermost scope only.
     * return null if the symbol is not found
     */
    public STE lookupInnermost(String sym) {
        Scope currentScope = mScopeStack.peek();
        return currentScope.lookupInnermost(sym);
    }
 
    /** When inserting an STE will just insert
     * it into the scope at the top of the scope stack.
     */
    public void insert( STE ste) {
        /* WRITE ME */
    }
    
    /** 
     * Lookup the given method scope and make it the innermost
     * scope.  IOW make it the top of the scope stack.
     */
    public void pushScope(String id) {
        /* WRITE ME */
    }
    
    public void popScope() {
        /* WRITE ME */
    }
    
    public void setExpType(Node exp, Type t)
    {
    	this.mExpType.put(exp, t);
    }
    
    public Type getExpType(Node exp)
    {
    	return this.mExpType.get(exp);
    }

STE stands for Symbol Table Entry. Various STEs hold information about the symbol. For example, a method STE needs to store the method type signature and keep track of the method scope. An STE for a parameter variable needs to keep track of where that parameter will be stored on the stack and how to access that parameter during code generation. We will discuss various design issues related to the symbol table in class.

Create an AST visitor that builds the symbol table. In other words, this visitor over the AST will insert method symbols into the symbol table and associate a type signature and formal parameter variable names with each method symbol.
Modify the CheckTypes visitor so it checks that method call arguments match the formal parameter types in the method signature.

Submitting the Assignment

Make sure you test your implementation thoroughly. You can use the reference compiler in ~cs453/public/MJ.jar to compare against and to view sample outputs. The reference compiler handles the full MeggyJava language, so some things that your PA4 will indicate as type errors (i.e. same method name in more than one class), the reference compiler will accept. If you have any questions as to which errors your PA4 compiler can detect that the reference compiler doesn't, just post them on the PA4 forum.
Only turn in one assignment per group.
Create the MJ.tar file that contains all the source code, two working test cases that you wrote, two test cases with type errors that you wrote, your .cup and .lex files, a README file, and a subversion.txt file.
- The README file should include your usernames, email addresses, group name, a description of what you are testing in the test cases you are submitting, and any information you want the TA to have before grading your assignment. The README file should also include the joint partner report if you are working with a partner (see below for details).
- The subversion.txt file should include output from the following:
```
svn log
svn info
    
```
  Note that svnlook must be issued on the machine where the repository resides.
Submit assignment using checkin utility.
```
~cs453/bin/checkin PA4 PA4.tar
```

Report and Evaluation of Partner Work

The partner joint and separate reports will be worth 10% of the programming assignment grade for those of you working with a partner.

(joint) For each of PA4 through PA6, write a planning paragraph and timeline together and submit with your assignment. Who is going to do what? The plan and the reality. How is the testing going to be done? What actually happened. Timeline for finishing portions of assignment. Meeting schedule.
(separate) Email cs453@cs.colostate.edu for each of PA4 through PA6 an assessment of the partner work by the deadline of the assignment. The assessment should be approximately 1/2 a page with information about the following: What are some organizational strategies that you and your partner are using that are working well? Specifically how did you and your partner divide the work? (e.g., I wrote the type checker for the following set of grammar rules...). How could the division of work between the partners be improved? How could the interaction between the partners be improved?
Your joint and separate evaluations will be graded based on the following criteria: Have all of the relevant questions been addressed in a thoughtful manner. How well do the reports match in terms of the partners both understanding who is doing what. Clarity and succinctness of the writing. There will be a subjective evaluation of how well the partners attempted to make the group programming experience work.

Usual Late Policy

Late assignments will be accepted up to 48 hours past the due date for a 10% deduction. The assignment will not be accepted past this period. Late means anything after 11:59pm on the day the assignment is due, including 12 midnight.

mstrout@cs.colostate.edu, 3/12/13, updated 3/25/13