CS152: Compiler Design Assignments CS152: Assignments All programming assignments after the first (warm-up) one will be dealing with MiniJava. Note: All assignments should be submitted via the turnin system. The turnin program always keeps the most recent version of the program submitted. Assignment 1 Assigned: Monday, October 10, 2005, in class Due: Monday, October 17, 2005, 23:59 Late submission accepted until: Wednesday, October 19, 2005, 23:59. Goal: Implement the straight-line program interpreter as described on page 11 of the textbook. Steps: Read the project description given on page 11 of your textbook Download slp.java,which includes the type declarations for the tree representation of the straight-line programs. You have to write the code for three classes. class Table {
String id;
int value;
Table tail;
Table(String i, int v, Table t) {
id=i;
value=v;
tail=t;
}
}
This class is used to store the values that are assigned to variable names by AssignStm's. It has two methods update and lookup. update does not search for a variable name and updates its value content rather it returns a new Table, where the first node contains the value of the most recent update. lookup is the method that returns the most recent value assigned to a variable.
class IntAndTable {
int i;
Table t;
IntAndTable(int ii, Table tt) {
i = ii;
t = tt;
}
}
This class is used to return the integer value of an interpreted expression together with the most recent state of the table following the interpretation of the expression. The table has to be returned, since this language has expression types, which not only returns an integer value but also contains a statement, which may change the state of the table. class Interpreter {
/* Comment on what this is */
static Table interpStm(Stm s, Table t){
/* your code goes here */
}
/* Comment on what this is */
static IntAndTable interpExp(Exp e, Table t){
/* your code goes here */
}
/* Comment on what this is */
static void interp(Stm s){
/* your code goes here */
}
/* Comment on what this is */
static int countExpsInExpLists(Stm s){
/* your code goes here */
}
/* Comment on what this is */
public static void main(String[] Args){
/* your code goes here */
}
}
This class is where bulk of your code for this project goes. It includes five methods as shown above. interp(Stm s) is the method you call to start interpreting your straight-line programs. It makes a call to interpStm(Stm s, Table t). interpStm(Stm s, Table t) and interpExp(Exp e, Table t) are used to interpret instances of Stm and Exp classes respectively. You also need to find the length of the longest ExpList in the input program. Keep it in mind that ExpList's only appear in PrintStm's and there can be nested PrintStm's in the staright-line programming language. Finally, do not forget to test your programs extensively. Sample straight-line programs: prog.java prog1.java prog2.java prog3.java prog4.java Assignment 2 Assigned: Friday, October 14, 2005, in class Due: Monday, October 24, 2005, 23:59 Late submission accepted until: Wednesday, October 26, 2005, 23:59. [picture taken from slides by Peter H. Froelich] Goal: Write the lexical-analysis specification for JFlex for the MiniJava language. Steps: Read the "Lexical Issues" section of the MiniJava specification. Read the on-line JFlex manual. Chapter entitled "A simple Example: How to work with JFlex" might be particularily useful. Write the JFlex file for MiniJava. You can use the MiniJava.jflex skeleton file as the starting point. Here's a list of tokens in the MiniJava language: "class" "{" "public" "static" "void" "main" "(" "String" "[" "]" ")" "}" "extends" ";" "return" "," "int" "boolean" "=" "if" "else" "while" "System.out.println" "&&" "<" "+" "-" "*" "." "length" "true" "false" "this" "new" "!" For every terminal you have used in MiniJava.jflex, you need to add a constant to the file Sym.java. Download this file and compile it. In the next assignment, this file will be automatically generated; more about it next time. Download jflex script which contains paths to the Java compiler and JFlex classes. chmod +x it to make it executable. Run jflex script on the file you have written. If everything goes OK, you will have a file Lexer.java as the result. Compile and build the lexer. Note that JFlex was built (among other things) to be integrated with CUP parser generator (which will be used in Assignment 3), so CUP classes have been imported in the skeleton. To get this to compile, you must have the path to CUP classes in your CLASSPATH. One way to accomplish this is to pass the CLASSPATH as an argument to the Java compiler:
/usr/csshare/pkgs/jdk1.5.0_05/bin/javac -classpath /usr/csshare/pkgs/jdk1.5.0_05/jre/lib/ext/java-cup-v11a.jar:. Lexer.java
Test the Lexer class on several sample MiniJava programs:
/usr/csshare/pkgs/jdk1.5.0_05/bin/java -classpath /usr/csshare/pkgs/jdk1.5.0_05/jre/lib/ext/java-cup-v11a.jar:. Lexer
Because of the %debug directive in the MiniJava.jflex file, no actions will get executed; instead, the lexer will output the token and line and column where the token was found. Assignment 3 Assigned: Monday, October 24, 2005, in class Due: Friday, November 4, 2005, 23:59 Late submission accepted until: Sunday, November 6, 2005, 23:59. [picture taken from slides by Peter H. Froelich] Goal: Generate a parser for the MiniJava language using the CUP parser generator. Steps: Study the CUP manual. Study the grammar section of the MiniJava specification. You have to be able to distinguish between the terminals and non-terminals in your grammar. Terminals are the tokens you receive from the lexer. Non-terminals are the symbols appearing on the left hand side of the production rules in the grammar and are used to name syntactically equivalent groupings. Write the CUP parser generator file for MiniJava. You can use the MiniJava.cup skeleton file as the starting point. Download compile and run-parser scripts which contain paths to the Java compiler, JFlex and CUP classes. chmod +x it to make them executable. Run the compile script on the files you have written as follows.
./compile MiniJava.cup
If no error messages are displayed, following files are generated: Lexer.java, Parser.java, Sym.java, after running the script. Test your parser on the sample MiniJava programs using the run-parser script as follows:
./run-parser
Expected output of your parser is a list of the production rules reduced upon parsing a given source file. You should also overwrite the method report_error(String message, Object info) to report the line and column number of a caught syntax error. Your output for syntax errors should be displayed as follows:
Error in line , column : Syntax error
Please refer to the updated skeleton file to see where you should place the report_error(...) method in your .cup file. Submission guidelines: You should only submit your MiniJava.jflex and MiniJava.cup files. No compressed files, nor any test or script files should be submitted. Points will be taken off from your Assignment 3 grade if your submission fails to follow this guideline. Partial outputs for some of the MiniJava programs: Factorial.java BubbleSort.java QuickSort.java Sample MiniJava programs: Factorial.java BinarySearch.java BubbleSort.java TreeVisitor.java QuickSort.java LinearSearch.java LinkedList.java BinaryTree.java Assignment 4 Assigned: Monday, November 7, 2005, in class Due: Thursday, November 17, 2005, 23:59 Late submission accepted until: Saturday, November 19, 2005, 23:59. [picture taken from slides by Peter H. Froelich] Goal: Add semantic actions to your parser to produce abstract syntax for the MiniJava language. Steps: Download syntaxtree.jar and visitor.jar jars. Those two jar files contain compiled Java Syntax Tree classes and Visitor and TypeVisitor interfaces. (Alternatively, you can download syntaxtree.tar.gz and visitor.tar.gz tarballs, in case you want to have the files localy.) If you would like to compile Java code which includes classes contained in the two jars, you would type:
javac -classpath syntaxtree.jar:visitor.jar:. YourFile.java
but ultimately, you would like to avoid typing altogether by automating your builds with an appropriately written Makefile (needless to say, feel free to modify it as you please, but from now on include one Makefile with every assignment submission). Read Section 4.3 entitled Visitors from the text so you get comfortable with the idea of visitor patterns. Understanding how accept and visit methods interact is crucial for this assignment. Assignment 3 taught you how to specify actions for production rules in CUP. Those actions by themselves allow for writing an interpreter for MiniJava. However, such an interpreter is difficult to read and maintain, and does not allow for various optimizations and improvements that we expect from modern compilers. Instead, we would like the parser to build a parse tree as a form of intermediate representation (IR) suitable for further stages of processing. Your goal in this assignment is to modify the actions of the parser that you have programmed before in your CUP file so that the generated parser returns the IR. (Remember the IR's used as input for the straight-line language in Assignment 1? That's what we have in mind, except that MiniJava is considerably more complex.) If you will be using the Syntax Tree and/or visitor classes, because they are in a different package, you have to explicitly import them with:
import syntaxtree.*;
import visitor.*;
Those two lines will probably go to the header of your MiniJava.cup file, among other places. Once you have coded the semantic actions of the parser, you can test your program with the following PrettyPrintVisitor. (Which comes along with the Main driver class). To test your program, you need to type:
java -classpath ./syntaxtree.jar:./visitor.jar:. Main
You may as well place the above line in a script file to avoid the typing. Possible input files are MiniJava samples used in previous assignments. Submission guidelines: You should submit only your MiniJava.jflex, MiniJava.cup, and PrettyPrintVisitor.java files, along with the Makefile which automates the process. No compressed files, nor any test or other script files should be submitted. We will be taking off points if your submission fails to follow this guideline. Assignment 5 Assigned: Friday, November 18, 2005, in class Due: Friday, December 2, 2005, 23:59 Late submission accepted until: Sunday, December 4, 2005, 23:59. Goal: Design a set of visitors to type-check any given MiniJava program for the MiniJava language. Steps: Download SymbolTable.java, BuildSymbolTableVisitor.java and, TypeCheckVisitor.java files. Files: SymbolTable.java file is complete and contains the class definitions for the SymbolTable, Class, Method and Variable classes. SymbolTable class holds the type information of all the declared classes in your program, where each class name is mapped to a Class object, which holds all the type information about a given class's variable and method declarations. 'class to Class object' mappings are stored in a Hashtable inside the SymbolTable class. Each method is mapped to an instance of the Method class, which holds all the type information about a method's parameters, result-type and local variables. A 'method to Method object' mapping is stored inside the methods Hashtable member of the SymbolTable entry of the class in which the method is declared. Similarly, each variable is mapped to an instance of the Variable class, which stores the variable's type information. This 'variable to Variable object' mapping is stored either inside the locals Hashtable of a Method object or inside the globals Hashtable of a Class object, depending on whether the variable is declared as a local variable inside a method or as an attribute of a class. BuildSymbolTableVisitor.java and TypeCheckVisitor.java files are incomplete and simply contain the skeleton code that visits the AST of a given MiniJava program in a depth first order. For this assignment you're expected to place your code inside these two files. Type checking of a MiniJava program proceeds in two phases. In the first phase, you need to build the SymbolTable with all declared type information. Your implementation of this phase should go inside the BuildSymbolTableVisitor.java file. First Phase: Study the SymbolTable.java and BuildSymbolTableVisitor.java files For the first phase, you need to add code to the BuildSymbolTableVisitor.java file to process all the declaration nodes such as ClassDeclSimple, ClassDeclExtends, MethodDecl, VarDecl, etc. When visiting the nodes derived from ClassDecl, you need to first form an entry for the ClassDecl node inside the SymbolTable using the addClass(...) method of the SymbolTable class. Next, you should set the BuildSymbolTableVisitor's currClass variable to that new entry (i.e. the Class object) for the current ClassDecl node in the SymbolTable. This way, refering to the currClass variable from within the visit methods for the VarDecl and MethodDecl nodes will allow you to add any member variables and methods of a ClassDecl into the right SymbolTable entry object. Similary, when visiting a MethodDecl, you should set the BuildSymbolTableVisitor's currMethod class variable to the Method (SymbolTable entry) object of the current MethodDecl node. This way you can refer to the currMethod variable from within other visit methods and add any local variables and formals of a MethodDecl into the right Method object. Once all the declarations are processed and stored in the SymbolTable, you should type-check the statements and expressions. Your implementation of this phase should go inside the TypeCheckVisitor.java file. Second Phase: Every statement and expression has its own type-checking rules. Following is an incomplete list of such rules. Others can be derived from MiniJava's semantics or by refering to the JAVA Language Specification: Operands of arithmetic operations must have the same type and it's Integer Operands of logical operations must have the same type and it's Boolean Condition expressions of while and if statements must be of type Boolean Right hand side of an assignment statement must either be of the same type as the left hand side or be a sub type of it Last but not least, please note the updates to the Main driver class. Update your Makefile from the previous assignment. Once everything compiles fine, you can test your program by typing:
java -classpath ./syntaxtree.jar:./visitor.jar:. Main
You may as well place the above line in a script file to avoid the typing. Possible input files are MiniJava samples used in previous assignments. Submission guidelines: You should only submit the following files:
MiniJava.jflex
MiniJava.cup
BuildSymbolTableVisitor.java
TypeCheckVisitor.java
, along with your updated Makefile. No compressed files, nor any test or other script files should be submitted. We will be taking off points if your submission fails to follow this guideline. Assignment 6 Assigned: Wednesday, November 30, 2005, in class Due: Wednesday, December 14, 2005, 23:59 Late submission accepted until: Friday, December 16, 2005, 23:59. Goal: Integrate all previous assignments (scanner, parser, AST generation, type checking) and write additional code to produce a working interpreter for the MiniJava language. Steps: Download Environment.java, InterpreterVisitor.java, Input.java, syntaxtree.jar and visitor.jar files. Files: Environment.java file is complete and contains the class definitions for the Environment, ClassEnv, and MethodEnv classes. Environment class keeps a stack of MethodEnv objects as well as the methods for getting/setting variable values within the active scope. Each time a method call orrcurs, the call should create an instance of the MethodEnv class for the called method. MethodEnv class keeps two hashtables to store the run-time values of the called method's parameters and locals respectively. In addition, since each method has to be in some specific class's scope, the enclosingClass data member of MethodEnv class points to the ClassEnv of that class scope. Similarly, each time a new instance of a MiniJava class is created, an instance of the ClassEnv class has to be formed for that MiniJava class. ClassEnv class keeps a hashtable that is used to store the run-time values of the data members of the formed MiniJava class instance. Whenever a method of a class instance is called, the ClassEnv for that class instance should be passed to the called method's MethodEnv constructor. InterpreterVisitor.java contains the skeleton code for this assignment. You should mainly place your code inside this file. The updated visitor.jar file contains a new visitor interface i.e. the InterpretVisitor.java and the updated syntaxtree.jar file contains accept methods that match the new interface and return values of type Object. Built-in methods: For this assignment you have two built-in methods: int getDigit() - which reads a single digit from the terminal, and returns it as an int. In case that the character was not a digit, the method returns 0. int getInt() - which reads a string of digits terminated with a new line (enter), and returns it as an int. In case the user input is not a valid integer, the method returns 0. You should treat those two input methods as being built into every MiniJava class: in short, a.getInt() is always legal for any class instance a. Interpretation: Interpretation means that you start executing from the public static void main(String[] args) method in the MainClass of your program. You need not to build a MethodEnv for the main method. This is because, neither the main method nor the MainClass contains any locals or data members whose values need to be accessed later in the program. For all other methods, at the point of the method's call you should create a new MethodEnv instance for the called method and push it into the environment so that you may be able to access its contents from other visit methods. For any method, the variables visible in the scope are: locals - Variables locally declared in the body of the method. formals - Formal arguments (parameters) of the method. data members - Variables declared when the class was instantiated. (optional, read the Extra Credit part) data members of the ancestor classes Declaring a local shadows a formal with the same name, and a formal or a local shadows a data member with the same name. Download the driver class Main.java, compile your compiler (or interpreter, rather), and test it on the MiniJava sample programs. Additionally, you may want to experiment with editing the sample programs to add the built-in functions to make your programs more interactive. Extra credit tasks: If you finished the mandatory part of the assignment, you might want to try the following: Implement inhertiance (+10% extra) In this part you have to take care of the polymorphism issues: if class FlipFlop is a child of the class GenericShoe, then every time you create a FlipFlop object, you have to create data members of class FlipFlop (naturally), but also, you have to create data members of class GenericShoe because it may happen that inside a FlipFlop method you will need the data member from its parent. Since in Assignment 5 you had to take care of similar issues for the purposes of type checking, the concept should not be difficult to grasp. Implement error handling (+5% extra) Runtime errors such as array index out of bounds as in new int[-56] or user input being different than an integer, should be reported. All errors should be reported as meaningfully as possible and with as much information as possible. "ERR23: 5>4" for example is not a meaningful message, while "Trying to access field 5 in array XY, which has only 4 elements" is. If you solve any of the above extra credit tasks, please let us know explicitly, so that we can grade you on those: state it explicitly in the header comment, after your name, and e-mail both Vlada and Betul and let us know what you did. Submission guidelines: You should only submit the following files:
MiniJava.jflex
MiniJava.cup
BuildSymbolTableVisitor.java
TypeCheckVisitor.java
InterpreterVisitor.java
Environment.java (Only and only if you implemented inheritance)
Makefile
No compressed files, nor any test or other script files should be turned in. We will be taking off points if your submission fails to follow this guideline. Side note: In general, the story of scope and variable visibility can be much more complex than in MiniJava, but this is out of scope for this class. Those interested in learning more should consider registering for the CS181: Programming Languages course.
