CS 352 Fall 2020
Compiler Project 2.2
Posted October 9th, Due October 25th, 11:59pm
1. Introduction
Project 2.2 is the second milestone (or the second checkpoint) for Project 2. To review the overview of the entire Project 2, please read the handout for Project 2.1, which also specifies the overall requirement and the distribution of the grade points across different parts of Project 2.
2. Scope and Tasks
Project 2.2 extends the language features covered by Project 2.1 by including the following:
• Allowing WHILE loops
• Allowing IF statements
• Allowing all data types (including arrays) except references to classes/objects
• Allowing construction of arrays and passing their references to array variable names.
• Allowing all expressions whose operands are of data types allowed above. The order of execution of operators follows the rules defined in JSE7, which may have an implication on how to construct the AST and how to traverse it.
This milestone does not implement method invocation, except the standard printing methods and array constructor by the new operator. It also does not require user declared type names yet, i.e. it does not yet implement the production rule PrimeTypeàID. (There is still just one class, the main class, in the input program. The main class has a single method, i.e. the main method.)
The expanded Yacc/Bison program (from Project 2.1) is expected to perform the following tasks on input programs that use language features covered by Project 2.1 and those listed above.
• Build the abstract syntax tree (AST).
• Traverse the AST to first perform type checking on the input program. If no type violations are
found, traverse the AST again to interpret the input program.
• If an operation is found to violate a type rule, then an error message must be printed as specified in Project 2.1 handout. The type of the operation result becomes undefined. Any operation that has an undefined operand will not be reported as a type violation. NOTE: This
prevents excessive error messages due to propagation of undefined types through a sequence of intermediate results.
We remind the students of the following:
• MiniJava+ has no type conversion and type casting between primitive types.
• We do not handle exceptions and do not perform run time type checking.
• We do not implement short-circuit evaluation of Boolean expressions.
• We do not handle the issue of abrupt termination of evaluation of expression (JSE7, Section 15.6).
• The interpreter is not expected to perform array bound checking.
• All type rules must be consistent with Java standard (see Appendix for references), except the
following additional restrictions:
o Both operands of any binary operation must have exactly the same type allowed for that operation.
o The left-hand side and right-hand side of an assignment operation must have the same type.
o Arithmetic and comparison operations are performed on int-typed operands only. o Logical operations are performed on bool-typed operands only.
o IF and WHILE conditions must be of the bool type.
o Concatenation (+) operations are performed on string-typed operands only.
o Array indices must be of int type. To simplify the implementation, we assume that an array is either of one dimension or two dimensions.
• To simplify the handling of strings, it is assumed that the input program contains no back slash character “\”.
Please review the lecture slides for the relevant implementation techniques (for the use of symbol tables and ASTs during interpretation, for example).
3. Submission instruction
Requirements concerning the contents of the submitted directory and makefile can be found in the handout for Project 2.1. It is important to review those requirements again. Some of these requirements are reiterated or customized for this project as shown below.
1) No offline submission (such as email) is accepted.
2) Use the following command on CS lab machines that run any Linux OS, e.g. the XINU machines (i.e., xinu01.cs ~ xinu20.cs) to submit your homework.
turnin –c cs352 –p p2_2 [your working directory]
3) You are free to write your own Make file, as long as the following requirements are met.
The grader will run your Makefile by executing the command “make interpret” to produce the executable program named interpret. Hence, it is important that your Makefile produces such an executable when invoked.
4) Your program MUST compile and run without any error on CS lab’s Linux machines. Please do a final test of this before submission, especially if you do your project on other computers.
5) Your code will be tested for grading by the following command;
> ./interpret program_name
Where “program_name” is the file name containing the input program.
NOTE: Deviation from the above requirement will get a 10 point of penalty. (For example, if your code receives 90 points, the final score on the Blackboard for this assignment will be 80 points.)
APPENDIX Additional Guidelines for Interpretation
In addition to the guidelines given in the handout of Project 2.1, a few new guidelines are offered below.
Expressions
The most important document concerning type rules and run time semantics for expressions is Chapter 15 of JSE7. This may seem to be a long chapter, but much of it covers the syntax rules, which we already covered in Project 1. Also, much of it concerns language features not in MiniJava+ and can be skipped. Descriptions of type rules and run time semantics are the focus of Project 2. For the latter, students should pay special attention to the evaluation order of expressions, argument lists, and statements. For Project 2, we do not handle the issue of abrupt termination of evaluation of expression (Section 15.6). This issue will be discussed in a lecture later this semester.
We note that Chapter 15 often refers to earlier sections, e.g. variable reference issues and types of variables (Chapter 4). Students must follow references that are relevant to Project 2. Keep in mind however, only a very small part of the referenced sections is relevant to MiniJava+. Also, MiniJava+ does not permit any type conversion or type casting, except the widening and narrowing of class references between a class and its extensions.
The following is an incomplete, but most important, list of issues concerning expressions. We will leave lingering issues for the students to discover, as an opportunity to learn how to understand a language specification, such as that in JSE7. Take this also as a great opportunity to strengthen what is learned from an introductory Java programming course and become a better-equipped Java programmer.
A general discussion of types of expression is made in JSE7 Sections 15.3 and 15.5. We suggest the following order (from easiest to the most complicated) for implementation of type checking concerning expressions.
Operations involving simple variables of primitive types
This part involves unary plus, unary minus, and unary complementary logical operation, as well as binary arithmetic, relational, conditional logical, equality and simple assignment operations. The type rules and evaluation rules are specified in JSE7 Sections 15.15.3, 15.15.4, 15.15.6, 15.17, 15.20, 15.21, 15.23, 15.24, 15.26.1.
Note that for comparison operations between reference variables, MiniJava+ has much simpler cases than the full Java, because we do not have casting operations.
Operations involving members of arrays.
A brief discussion of rules governing array member accesses and array creation can be found in JSE7, Chapter 10. In this course, we do not handle array bound checking at run time. A brief discussion of rules governing array member accesses and array creation can be found in JSE7, Chapter 10.