CISC 471/672 Programming Assignment #4 — Adding tones, less than, classes, methods
Introduction
This assignment can be done with your CISC 471/672 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 uploaded to sakai. 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,
- check for undefined, doubly defined, and incorrectly typed symbols,
- add PA4 type checking to the check types visitor, and
- code generation visitor for the PA4 grammar.
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.
While there are not starter files, we provide some example programs for you at PA4Examples.
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 in the PA4Examples folder for .s files where there are no object instances being passed around.
The Assignment
We do not provide any new code for PA4, just examples. 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. Copy and edit the PA3 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 in the PA4Examples folder 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. That is, 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 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 one assignment per group, in your shared github repository.
- 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, and a README 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).
- Submit assignment by committing to your github repository.
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.
- (individually) Submit on sakai 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.
Evaluation
This assignment is graded on a 100 point scale. Your submission will be graded with the following breakdown:- 15 points: Extension of your parser spec to correctly scan all tokens and parse for the PA4 grammar demonstrated with test cases
- 15 points: Creates a symbol table that accurately represents the static scoping of the MeggyJava programs of PA4
- 10 points: Check for undefined, doubly defined, and incorrectly typed symbols
- 15 points: Performs correct type checking for the PA4 grammar rules according to the MJ.jar reference compiler type errors
- 10 points: Continues to perform code generation to AVR assembly code for the PA3 AST nodes using a visitor
- 15 points: Performs correct code geneation to AVR assembly code for the added features in PA4 grammar:
- Meggy.toneStart
- less than operator
- user-defined methods
- method calls
- 10 ponits: test cases for PA4 features
- 5 points: README file explaining the file structure (your test files) and other comments you want your TA to know (e.g. features not implemented)
- 5 points: Follows instructions for submission correctly