Assignment 5: Code Generation
COMP3131/9102: Programming Languages and Compilers
Term 1, 2022
Worth: 28/100 marks Due: 8:00pm Friday 22 April 2022
Revision Log
Nothing at this stage.
End Of Revision Log
Congratulations for having gone this far!
Let us conquer our last assignment!
1. Specification
This is the last assignment for the project! You are now on the way to build a compiler
for VC, a fairly substantial language for a year 3 course!
You are to write a code generator for VC. This last assignment involves developing a
visitor class (named Emitter) that implements the set of visitor methods in the interface
VC.ASTs.Visitor.java. Your code generator will be a visitor object that traverses the
decorated AST representing the source program, emitting Jasmin assembly instructions
incrementally. Both the order of traversal and the instructions to be emitted are specified
by code templates. Code templates for almost all language constructs are discussed in
Week 8.
As before, if no lexical, syntactic or semantic error is found, your compiler should
announce success by printing:
Compilation was successful.
and write the Jasmin assembly code in a file. Otherwise, the following message should be
printed:
Compilation was unsuccessful.
If the input file name is test.vc, then the output file must be test.j.
There are four points to be noted below:
 In this assignment, we make one simplification about the VC language. In VC,
int[] can be passed as an argument to a formal parameter expecting float[]. In this
assignment, you can assume that this is NOT allowed. As a consequence, a formal
parameter of type T[] requires the type of the corresponding argument to be
exactly T[].
 In an assignment statement of the form LHS=RHS, the LHS must be translated
before the RHS. This is the same as in Java. Please refer to the leture slides on
Code Generation for the code template used and an illustrating example.
 Following C, all global variables are initialised with constant expressions only.
This is not checked in Assignment 4. This restriction will be satisfied by all test
cases used for marking Assignment 5. You don't need to do anything special for
this restriction.
 For an array declaration with an initialising expression as follows:
 T a[] = { blah1, blah2, ..., blahn };
where the size of the array is not specified, you can assume that the AST
constructed after our checker, which is used for marking your Assignment 5, has
been invoked is exactly same as that for the same expression except than the array
size is now explicit:
T a[n] = { blah1, blah2, ..., blahn };
The following example illustrates this:
Program: int i[] = { 1, 2 };
AST built by Parser: AST-parser.gif
AST decorated by Checker: AST-checker.gif
2. Jasmin Assembly Language
Jasmin Home Page
Sun has not defined an assembler format for Java byte code. Jasmin is an
assembly language for Java byte code. Jasmin is an assembler that reads as input a
Jasmin assembly program and produces as output a Java class file ready to be run
on a JVM. To access Jasmin installed in the 3131/9102 class accounts, run 3131
or 9102 to set up your environment. Then the command
jasmin Test.j
will assemble the file Test.j and place the output class file Test.class in the
current directory.
If you have a PC yourself, you can download Jasmin from its home page.
Alternatively, you can download the source code from the cs3131 account:
cd ~cs3131/VC/CodeGen
cp jasmin-1_06.zip Your-Installation-Directory

All the classes are pre-compiled. You can run the jasmin assembler once you have
included Your-Installation-Directory/jasmin/classes in your
CLASSPATH. The command to run the assembler on Test.j is:

java jasmin.Main Test.j

As I use bash on my Mac, I have created a simple shell script, named jasmin, as
follows:


#!/bin/bash
#
# jasmin - runs the Jasmin assembler
#
# Usage:
# jasmin [-d ] [ ...]
#

export CLASSPATH=/Users/jingling/JavaTools/jasmin/classes
echo $CLASSPATH
java jasmin.Main $*
where /Users/jingling/JavaTools is my installation directory for the Jasmin
Assembler. Instead of typing

java jasmin.Main Test.j

I can now simply type

jasmin Test.j

to translate Test.j into Test.class (Java bytecode).

Jasmin On-Line Instruction Reference Manual
This manual describes all Jasmin instructions. You can also find more information
at Jasmin Instructions. Only those listed in the file VC.CodeGen.JVM.java will be
used. For every instruction used, you need to understand the effect of its
execution on the operand stack. As an example, an iadd instruction adds the two
values on the top of the operand stack and replaces them with the result of the
operation. As another example, i2f converts the integer value on the top of the
stack to the float result. Such a basic understanding is necessary for you to
calculate the maximum depth of the operand stack used for a function.

Java Class File Disassembler
You can use the Java class file disassembler, javap, to translate a Java class file
into assembly code. The command
javap -c Test > Test.j
will disassemble the class file and produce Test.j.

There are some other disassemblers:
 jasper
 BCEL
3. Installing the Built-In Functions
All the built-in functions of the VC language are implemented as static methods in the
class System.java.
You can install this class as follows:
1. Create the subpackage lang under the package VC.
2. Copy ~cs3131/VC/lang/System.java into your VC.lang.
3. Compile this Java file into a class file.
4. Interpreting VC Programs as Java Programs
The following assumptions are made about every VC program:
1. The name of the class is the same as the file name with the "." and the suffix "vc"
removed.
2. All global variables are assumed to be class variables with the package access.
3. All functions (except the main function) are assumed to be instance methods with
the package access.
4. The main function is interpreted to be the following Java main method:
public static void main(String argv[]) {
Classname vc$
The original variable declarations
vc$ = new Classname();
The original statements
}
where Classname is the name of the class defined in Assumption 1. vc$ is
declared implicitly to be an object reference to the class and initialised at the end
of the original variable declarations, if any. Since every non-main function is an
instance method, every call f(...) in the main method is assumed implicitly to be
vc$.f(...). It is further assumed that the main method cannot be called recursively
either directly or indirectly.
The translation of these changes made to the main function has been implemented
for you in Emitter.java.
5. Attributes Useful in ASTs
Two additional attributes in the AST are used during code generation.
 There is an instance variable called index in the abstract class VC.ASTs.Decl.
This variable, inherited by the concrete classes VC.ASTs.LocalVarDecl and
VC.ASTs.FormalPara, is used to store the local variable index allocated to a
variable or a formal parameter.
 There is an instance variable called parent in the abstract class VC.ASTs.AST.
Therefore, parent is inherited by all the other AST classes. During the
construction of the AST, as a node is linked to its child nodes, the child nodes are
also linked to its parent at the the same time. In our implementation, this parent
link is used in two occasions:
o In a CompoundStmt node that represents the body of a function, its parent
link can be used to access the formal parameters of the function so that the
PL node of the function can be traversed.
o In an AssignExpr node, its parent link can be used to determine if the top
stack value needs to be duplicated by emitting a dup instruction, as
discussed in Week 8.
6. Writing Your Code Generator
1. Set your current directory to VC.
2. Copy ~cs3131/VC/CodeGen/CodeGen.zip into VC.
3. To extract all the files once you have retrieved the zip archive, type:
unzip CodeGen.zip
The files in this zip file are listed below:

VC Package:

vc.java main compiler module

VC.CodeGen Package:

Emitter.java: Code generator skeleton
Frame.java: Information useful about translating a function
JVM.java: Simple JVM definition
Instruction.java: Instruction definition

Test Files: gcd.vc, max.vc

Solution Files: gcd.j, max.j
You need to at least change the two files: JVM.java and Emitter.java.
Modifying JVM.java
Presently, JVM.java defines all necessary instructions for dealing with scalar variables.
You need to add to this file all instructions required for translating array-related
constructs.
Modifying Emitter.java
Emitter.java does not compile. But we have already provided the implementation for
the following:
 The generation of field declarations and the class initialiser for all global
scalar variables in visitProgram. But you are required to modify this method to
deal with all array-related declarations and initialisations.
 The generation of the non-arg constructor initialiser .
 Various visit methods.
Presently, Emitter.java consists of about 700 lines of code. You need to implement all
missing visitor methods and complete those as indicated in the file. You will write
approximately 300 lines of Java code.
The code templates for all constructs are discussed in Week 8. Those that are not have
been implemented for you in Emitter.java.
All auxiliary methods provided in Emitter.java are self-explanatory. However, you are
not obliged to use any of them if you feel constrained. You can develop your code
generator from scratch if you so wish.
Only two test files are provided. The solution files are provided to give an indication
about the Jasmin files produced. You are not required to generate exactly the same code.
The two directives .limit locals and .limit stacks must be contained in every
Jasmin method. The total number of locals is simply the value returned from the call
frame.getNewIndex().
However, you must calculate yourself the maximum depth of the operand stack used for
every function. As discussed in Week 8 and further demonstrated in the partially
implemented Emiter.java, one way to find out the stack size is to simulate the
execution of the byte code generated. You can delay counting the maximum stack size by
using a constant number:

.limit stack 50
The generation of the .var directive is required and can be done in visitLocalVarDecl
and visitFormalPara by using the information from the LocalVarDecl or FormalDec
node and the labels from the two stacks frame.scopeStart and frame.scopeEnd.
The generation of the .line directive is optional.
If you are uncertain what Jasmin instructions to generate for a construct, you can compile
a similar Java program and use the disassembler to convert the class file back into a
Jasmin assembly file.
7. Parser
If you want to use our parser in case yours does not work properly, copy
~cs3131/VC/RefSols/Parser.zip to the directory containing package VC and type:
unzip Parser.zip
This installs the class Parser.class under package VC.Parser. It is not necessary to
understand how this parser works. Your type checker will only work on the AST
constructed for the program by the parser.
8. Type Checker
You will be required to generate Jasmin code only for both syntactically and semantically
correct programs. So this means that how well your type checker detects semantic errors
is irrelevant. However, your type checker is assumed to have produced an annotated AST
correctly. There are two kinds of annotations, as explained in Type Coercions in
Assignment 4 Spec and illustrated by an example there:
 All operators have been replaced with non-overloaded integer or floating-point
operators (such as i+ and f*).
 The type conversion i2f operator has been added wherever it is necessary to
change a number from integer to floating-point representation at run time.
If you want to use our checker in case yours does not work properly, copy
~cs3131/VC/RefSols/Checker.zip to the directory containing package VC and type:
unzip Checker.zip
However, this will only be available after the deadline of Assignment 4.
This installs Checker.class, SymbolTable.class and IdEntry.class under package
VC.Checker and StdEnvironment.class under VC. It is not necessary to understand how
our checker works.
However, our Checker solution will be released on 17 April, two days after the due date
for Assignment 4 has passed.
9. Debugging Your Code Generator
The compiler options are still the same as in Assignment 4:
[jxue@daniel Checker]$ java VC.vc
======= The VC compiler =======

[# vc #]: no input file

Usage: java VC.vc [-options] filename

where options include:
-d [1234] display the AST (without SourcePosition)
1: the AST from the parser (without SourcePosition)
2: the AST from the parser (with SourcePosition)
3: the AST from the checker (without SourcePosition)
4: the AST from the checker (with SourcePosition)
-t [file] print the (non-annotated) AST into
(or filename + "t" if is unspecified)
-u [file] unparse the (non-annotated) AST into
(or filename + "u" if is unspecified)
If the source file being compiled is Test.vc, the output Jasmin file will be Test.j.
When designing your own test files, you need to be aware of the following differences
between VC and Java:
Variable Initialisations
In Java, all variables must be initialised before used. Otherwise, the JVM will
throw an "accessing value from uninitialised register ..." error. In VC, as in C, the
same requirement is unspecified for local variables. But global variables are
initialised according to the VC spec except that all global variables must be
initialised only with constant expressions -- this is not checked in Assignment 4.
Therefore, you should use only test files for which all variables have been
initialised.
return
In Java, the compiler makes sure that every method returning a value contains an
appropriate return in every possible execution path. In VC, this context-sensitive
restriction is specified in the language definition but not enforced by the type
checker. If a return is missing, the JVM will throw a "Falling off the end of the
code" error. Therefore, you should use only test files in which return statements
have been provided in all required places.
You will probably find that the easiest way to debug your code generator is to produce
assembly code and look at it, rather than attempting to run it.
10. Marking Criteria
Your code generator will be assessed by running your compiler on some test cases and
comparing the output with the correct output. Therefore, correct but highly inefficient
code will not be penalised.
The test files used for marking your compiler will all be correct programs free of any
kind of errors. In each test file, all variables are appropriately initialised and all functions
contain return statements wherever they are required.
As before, there are no subjective marks.
11. Submitting Your Code Generator
give cs3131 emitter your-Java-files
You will definitely need to submit Emitter.java and JVM.java.
Submit Frame.java, JVM.java and Instruction.java if you have modified them.
You can ignore all the four files provided and do everything from scratch. But you are
only allowed to submit the files with these names. No additional files will be accepted.
If your code generator need some "personal" information you have decorated in the
AST, you may also submit your Checker.java.
12. Late Penalties
This assignment is worth 28 marks (out of 100). You are strongly advised to start early
and do not wait until the last minute. You will lose 5 marks for each day the assignment
is late.
Extensions will not be granted unless you have legitimate reasons and have let the LIC
know ASAP, preferably one week before its due date.
13. Plagiarism
As you should be aware, UNSW has a commitment to detecting plagiarism in
assignments. In this particular course, we run a special program that detects similarity
between assignment submissions of different students, and then manually inspect those
with high similarity to guarantee that the suspected plagiarism is apparent.
If you receive a written letter relating to suspected plagiarism, please contact the LIC
with the specified deadline. While those students can collect their assignments, their
marks will only be finalised after we have reviewed the explanation regarding their
suspected plagiarism.
This year, CSE will adopt a uniform set of penalties for the programming assignments in
all CSE courses. There will be a range of penalties, ranging from "0 marks for the
assessment item", "negative marks for the value of the assessment item" to "failure of
course with 0FL."
Here is a statement of UNSW on plagiarism:
Have fun!