Last updated: Mon 15 Apr 2024 08:42:39 AEST.
COMP4403 - Compilers and Interpreters
Assignment 2
Due date: 3pm (15:00) Friday 3rd May, 2024
This is an individual assignment which involves modifying the LALR assignment 2 compiler for the PL0
language to add array types and operations on arrays.
Assignment Compiler Files
All sources for the assignment PL0 compiler are available as a2.zip (below). Please be sure to use the
version for this assignment and not the one used for the tutorials or another assignment. There are
differences (like the lexical tokens you need for this assignment are only defined in the assignment
version).
a2.zipSun 14 Apr 2024 12:12:22 AEST Save this .zip file and follow the instructions for setting up
a compiler project in IntelliJ
Setting up and running PL0 in IntelliJThu 21 May 2020 16:46:06 AEST
Brief documentation on assignment 2 filesSun 7 Apr 2024 18:29:52 AEST
Here is the documentation for
Java CUP [HTML]
JFlex [HTML]
For the most part you will not need these.
Please pay attention to course Blackboard announcments, and ensure you follow the course
discussion board (https://edstem.org/) for any updates and further information on the assignment.
Do not use imports for external packages other than those in java.util.*. Note that IntelliJ may
offer the option of importing an external package to resolve an issue; please avoid accepting
this option because it will often add an erroneous import that you will not need. Such imports
lead to the compilation failing in the environment in which your compiler will be assessed
because that environment does not include the external libraries. Please check you are not
importing external libraries before submitting.
You must only modify the files that must be submitted (see below).
You must not modify any other files because we will be testing your implementation using the
existing other files with your submitted files.
Please do not reformat the files because we would like to just print the differences between the
originals and the versions you hand in.
Please keep the length of lines in your files below 100 characters, so that we can print them
sensibly.
Please avoid using non-standard characters, e.g. Chinese characters, including in the
comments. Non-standard characters are not accepted by the Java compiler used to test your
assignment and all comments should be readable by the person assessing your assignment.
Please remove any debugging output before your assignment is submitted because
debugging output will cause your program to fail our automated testing of your assignment.
Either avoid using tabs or set your tabs stops to 4 spaces (this is the default for IntelliJ/Eclipse)
so that your files will print sensibly.
Read the fine print in detail before you start! And, most important, when you have finished
implementing the assignment, come back and reread the fine print again.
Overview
Array types
An array type may be declared in a type definition. In the following declarations V is an array type
with elements of type integer, and M is an array type with elements of type V. Each element of M is
itself an array of integers. One may declare a variable to be of an array type:
const N = 3;
type
V = array of int;
M = array of V;
var
vec : V;
mat: M;
Arrays are indexed by integers. The length of an instance of an array will be fixed when the array is
created. (The minimum length of an array is one.) Once an array has been instantiated, its first index
will be index 0 and its last index will be the length of the array minus one. An instance of an array may
be created using a new expression. For example,
vec := new V[N];
mat := new M[N-1]
assigns to variable vec a new (dynamically allocated) array with three elements, each of type integer,
with indices 0 to 2 (inclusive); and assigns to variable mat a new array with two elements, each of type
V, with indices 0 to 1 (inclusive).
The length of an initialised array may be accessed. For example
write vec.length
writes the length of array vec. Elements of initialised arrays may be assigned appropriate values: After
the array assignment mat[1] := vec, both mat[1] and vec refer to the same array. And so, for example,
after the assignment mat[1][0] := 300 both mat[1][0] and vec[0] will have the same value (300). The
values of the elements may be accessed, for example, the following assigns to index 1 of the array vec
the value of mat[0][9] minus one.
vec[0] := 100;
mat[0] := new V[10];
mat[0][9] := 200;
mat[1] := vec; // array assignment (mat[1] and vec now refer to the same array)
mat[1][0] := 300
vec[1] := mat[0][9] - 1
Syntax Changes
The reserved keywords "array", "of" and "new" have already been added to the lexical analyser input
file (PL0.flex) as the tokens KW_ARRAY, KW_OF and KW_NEW, and the symbol "." has been added as
the token PERIOD. They have also been added to the terminal definitions in PL0.cup.
The syntax is given here in BNF. The syntax for type definitions (Type) is extended with an additional
alternative for array types:
Type →   ...  |  "array" "of" Type
A reference to an element of an array can be used as an LValue either within an expression or on the
left side of an assignment:
LValue →   IDENTIFIER  |  LValue "[" Condition "]"
A new array expression or an access to the length attribute of an array can be used as a Factor in an
expression:
Factor →   ...  |  "new" TypeIdentifier "[" Condition "]"  |  LValue "." IDENTIFIER
You need to add these productions and their associated actions to build the symbol table entries and
abstract syntax trees to PL0.cup.
The Parser Generator Java-CUP
The parser specification for the compiler is specified in the file PL0.cup. You will need to add
productions (and their associated actions) to the specification and then run the parser generator Java-
CUP (manually or automatically) to generate the files CUPParser.java and CUPToken.java. Do not
modify these two Java files directly (even if you think you understand them (do you really?)) - remake
them from PL0.cup. You should make the compiler before you change anything just to see what forms
of messages to expect. When you make the compiler (before you modify it) there will be some
warning messages about the terminal symbols like ILLEGAL being declared but never used; these are
to be expected at this stage. Any new warning/error messages will be significant. Beware that if there
are Java-CUP errors reported, the Java files for the parser will not be generated, so check for Java-CUP
errors first. There is HTML documentation for Java-CUP available from the class web page (with the
assignment).
The Scanner Generator JFlex
All the lexical tokens for this version of the compiler have already been added to the lexical analyser.
The file Lexer.java is automatically generated by the scanner generator JFlex from PL0.flex; again, do
not modify Lexer.java - remake Lexer.java from PL0.flex.
Both Java-CUP and JFlex are available with the assignment files on the course web page, with
instructions on how to run them in IntelliJ. Java archives for Java-CUP and JFlex are part of the IntelliJ
project for the assignment.
Static Semantic Restrictions
Array types
In an array type declaration, array of t,
the element type, t, can be any type including another array type, but cycles in type definitions
are not permitted, e.g. the following is not valid as the definitions of types C and D form a cycle.
C = array of D;
D = array of C;

In Type.java a class ArrayType has already been added to represent array types within the compiler.
The type of array of t is ArrayType(T), where T is the type of t:
syms ⊢ typeof(t) = T
                                                                        
syms ⊢ typeof(array of t) = ArrayType(T)
In a new expression, new id[e], the type identifier id must be that of an array type; the expression e
must be compatible with the integer type; and the type of the new expression will correspond to the
array type of the type identifier:
id ∈ dom(syms)
syms(id) = TypeEntry(ArrayType(T))
syms   ⊢   e : int                                                                         
syms   ⊢   new id[e] : ArrayType(T)
For a reference to the length attribute of an array, e.id, expression e must have an array type, and
identifier id must be the identifier "length". A reference to the length of an array, e.id is of type
integer:
syms ⊢ e : ArrayType(T)
id = "length"                                                      
syms ⊢ e.id : int
For a reference to an element of an array, e1[e2], expression e1 must have an array type, and
expression e2, used as the array index, must be compatible with the integer type (the type of array
indices). The type of a reference to an element of an array, e1[e2], is a reference to the element type
of the array:
syms ⊢ e1 : ArrayType(T)
syms ⊢ e2 : int
                                                                        
syms ⊢ e1[e2] : ref(T)
Note that the type of e1[e2] is ref(T) rather than T so that the subscripted array element can be used
as an L-value, e.g., it can be used on the left side of an assignment.
Assignment of arrays is allowed but other operations on arrays (e.g., comparison, etc.) are not
supported.
Dynamic Semantics
Arrays
Arrays are dynamically allocated via a new expression. As such, the value of an array will be an
absolute (i.e. global) address: the address where the length of the array and the elements of the array
are stored. The value of an array will be null (StackMachine.NULL_ADDR) until it has been otherwise
assigned.
When one array is directly assigned to another, such as in
vec2 := vec1
then the value (an absolute address) stored by vec2 will become the same value (an absolute address)
stored by vec1. Hence, following the assignment, vec1 and vec2 will refer to the same array object in
memory.
The expression new id[e] dynamically allocates space on the heap to store both the length, e, of the
new array, as well as all of its e elements; it writes the length of the new array to that address at an
offset of 0; and it evaluates to the absolute address of the new array that has been allocated.
The length of a new array should be checked at run time to ensure that it is greater than or equal to
the minimum length of an array (one): if it is not then this is a run time error, and the stack machine
should be stopped with an exit code of StackMachine.INVALID_ARRAY_LENGTH.
Objects dynamically allocated via a new array expression have a life time that is not restricted to that
of the variable to which they were allocated. For example, a new array may be created within a
procedure and assigned to a local variable within that procedure. Provided that variable's value (the
absolute address of the allocated array) is assigned to a variable or field that is accessible via variables
global to the procedure, before the procedure exits, the object will remain accessible.
Although we dynamically allocate arrays via the new expression, we won't implement garbage
collection of objects that are no longer accessible.
A reference to the length of an array, i.e. e.length, should evaluate to the length of the array.
The dynamic semantics of array accessing, i.e. e1[e2], is conventional. An element of an array may be
used like a variable whose type is the same as the element type of the array. For example, if the
element type is int then it may be "assigned to", read, written and used in arithmetic expressions and
comparisons (but if you start worrying about each of these you are making way more work for
yourself than you need to).
If the value of an array is null (StackMachine.NULL_ADDR) when either at attempt is made to access
its length, or to access one of its elements then this is a run time error and the stack machine should
be stopped with an exit code of StackMachine.NULL_ARRAY.
Accesses to array elements should be bounds checked at run time, i.e., the value of the index
expression should be checked to make sure that it is a valid index of the array. If it is not, then this is a
run time error and the stack machine should be stopped with an exit code of
StackMachine.OUT_OF_BOUNDS. (See the discussion of the genBoundsCheck method below.)
Variables of an array type are local variables and hence are allocated on the stack just like any other
local variable. The main difference from scalar variables is that the value stored in the local variable
will be the absolute address of an array. The absolute address of the array (unless it is
StackMachine.NULL_ADDR) can then be used to access the length of the array, and the elements of
the array.
Object Code
The PL0 compiler generates code for the Stack Machine. A description of the stack machine is
available in StackMachineHandout.pdf. See also the file StackMachine.java (near the end) for details of
the instruction set.
Dynamic allocation of arrays
There is an instruction, ALLOC_HEAP, which assumes that there is an integer on the top of the stack
that represents the size of the object to be allocated. It pops that value from the stack and replaces it
with the absolute address of a newly allocated object of that size. The stack machine does not
support disposing objects or garbage collection.
If there is insufficient space then ALLOC_HEAP will fail with a "memory overflow" message. In the
implementation of the stack machine there is a single array representing the whole of memory: the
stack (the bottom end of the array) and the heap of dynamically allocated objects (the top end). If
either pushing onto the stack reaches the lower limit of the heap, or allocating on the heap reaches
the top of the stack, then there is insufficient memory and the program aborts (with the same error
message in both cases).
You need to be aware that the instructions LOAD_FRAME and STORE_FRAME expect an address that
is an offset from the frame pointer for the current (procedure) scope. You can use instruction
TO_LOCAL to convert an absolute address into an address relative to the current frame pointer.
Reporting runtime errors
Under exceptional circumstances, the STOP instruction can be used to stop execution of the stack
machine. The top of the stack is popped to get an exit code.
Array indexing and bounds checking
The BOUND instruction expects that the following have been loaded (pushed) onto the stack (in this
order):
1. a value to be bounds checked,
2. a lower bound, and
3. an upper bound.
The BOUND instruction pops the upper and lower bound as well as the value to be checked. If the
value to be checked is not within the given bounds (inclusive) then value false is pushed on top of the
stack, else the value true is pushed on top of the stack.
The genBoundsCheck method of the Code class can be used to generate code for checking that a
value is within bounds. It assumes the value to check is already on the stack. If the bounds check
succeeds the value checked is left on the top of stack, otherwise the stack machine interpreter halts
with an StackMachine.OUT_OF_BOUNDS runtime error.
Additional stack machine instructions
Additional instructions (not in the Stack Machine handout) STORE_STACK and LOAD_STACK have
been added to the Stack Machine. You do not have to use these instructions, however you may find
them useful. For a precise description of their behaviour, refer to StackMachine.java.
STORE_STACK: The value of the second top of the stack is stored at the (absolute) address given by
the stack pointer minus one (sp-1), minus the top of the stack. The two values on the stack are
popped.
LOAD_STACK: The top of the stack is replaced with the contents of the memory location whose
(absolute) address is given by the stack pointer minus one (sp-1), minus the top of the stack.
Tests
Some tests are available in the test-pgm directory (in a2.zip), and can be used to help you to debug
your code. All of the tests can be run together using the Test_LALR configuration. You can also
individually run a test using PL0_LALR on a selected PL0 program. The test cases of the form test-
base*.pl0 are useful for regression testing, to make sure that you haven't broken any existing
functionality in the compiler, and the other tests can help you find bugs in the new compiler features.
Student Misconduct
Students are reminded of the University's policy on student misconduct, including plagiarism. See the
course profile and the School web page http://www.itee.uq.edu.au/itee-student-misconduct-
including-plagiarism
You are expected to protect your files so that they are not readable by other users.
Your assignment is expected to be your own individual work and must not include code copied from
other students, current or past. You are also reminded not to post your (partial) solutions to
assignments to any place accessible by others (before or after the assignment deadline), including the
course discussion board or emailing to other students. If you need that sort of help consult the
lecturer and/or tutor. Note that course discussion board allows private posts to the instructors.
This assignment compiler is provided solely for the purposes of doing this assignment and your
solutions must never be shared, especially publicly, even after completion of the course. Such
publication would be considered both student misconduct and a breach of copyright.
Late Submission
See section 5.3 of the course profile for details.
If there are documented medical or exceptional circumstances that will affect your ability to complete
the assignment by the due date, then you can apply for an extension (up to 7 days). Extensions to
non-exam assignments must be requested via my.UQ. You can find instructions on how to submit
your request online.
If the assignment is submitted after the deadline, without an approved extension, a late penalty will
apply. The late penalty shall be 10% of the maximum possible mark for the assessment item will be
deducted per calendar day (or part thereof), up to a maximum of seven (7) days. After seven days, no
marks will be awarded for the item. A day is considered to be a 24 hour block from the assessment
item due time. Negative marks will not be awarded.
Submission
Please keep the length of lines in your files below 100 characters, so that we can print them sensibly.
You should avoid using tabs or set your tabs stops to 4 spaces so that when we print them (with tab
stops set to 4 spaces) they will print sensibly. Do not forget to remove any code generating
debugging output and any rogue external imports before submission.
You must submit your completed assignment electronically through the assessment section of the
course BlackBoard site (the BlackBoard Assessment page rather than the course web pages).
You need to submit the following list of individual files (not a .zip or any other form of archive file) for
evaluation and marking. Note that file names are case-sensitive.
PL0.cup
ExpNode.java
ExpTransform.java
StaticChecker.java
CodeGenerator.java
You can submit your assignment multiple times, but only the last copy submitted will be retained for
marking.
Assessment
The assignment is marked out of a total of 15 marks.
Marks will be allocated as follows:
3.5 - Syntax analysis and tree building
5.5 - Static semantics checking
6.0 - Code generation
Marks will be awarded for the correctness of the changes to each category. Readability and modular
structure will also be criteria. For readability, we expect that you follow good software engineering
practice, such as appropriate choices of variable names, consistent indentation, appropriate
comments where needed, etc. For modularity we expect you introduce new methods where it makes
sense to help structure the program and to avoid unnecessary duplication of code. Use of generic
Java utility interfaces (like Set, Map, List, Queue, ...) and their implementations (like HashSet, ...,
TreeMap, ..., LinkedList, ...) is encouraged. We expect you to produce well structured programs that are
not unnecessarily complex, both structurally (e.g. complex control flow that is hard to follow), and in
terms of execution time and space requirements, (e.g. an O(n) algorithm is preferred to an O(n )
algorithm, and a O(log n) algorithm is even better).
We will not be concerned with the quality of syntactic error recovery because the parser generator
CUP takes care of that for the most part, but you must handle semantic errors appropriately,
including handling the situation when there is a syntax error, i.e., your compiler should not crash
because of a syntax error.
Your assignment files will be compiled in the context of the remaining assignment files and put
through a sequence of tests. The total mark for this assignment will be limited by the overall success
of the development in the following way:
The program submitted does not compile: Maximum 8/15.
The program submitted will not correctly handle any test case with the new facilities: Maximum
10/15.
You are not required to correct any bugs that may exist in the original compiler. However, we would
appreciate being informed of any such bugs that you detect, so that we can correct them, or any
improvements to the compiler you might like to suggest.