Last updated: Mon 23 Mar 2020 10:20:57 AEST.
COMP4403/COMP7402 - Compilers and
Interpreters
Assignment 1
Due date: 15:00 Thursday 9th April, 2020
Modify the recursive descent compiler for the language PL0 (provided on the course web page
with this assignment) to add a skip statement, a multiple assignment statement, and an
extended version of a loop statement.
Assignment Compiler Files
All sources for the assignment PL0 compiler are available as a1.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
this version).
a1.zip Save this .zip file and follow the instructions for setting up a compiler project in
IntelliJ
Setting up and running PL0 in IntellliJ
Brief documentation on assignment 1 files
Please ensure you follow the course Piazza bulletin board 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
taking 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 may not include the external libraries. Please check
you are not importing external libraries before submitted.
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.
Your implementation should be in Java 1.8 and Project language level 8. Set the IntelliJ
preferences for the Java compiler to 1.8 (or use the "-source 1.8" option to the command
line Java compiler).
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 all the fine print below in detail before you start! And, most important, when you have
finished implementing the assignment, come back and re-read the fine print again.
Overview
The multiple assignment statement allows a list of variables to be simultaneously assigned the
values of a list of expressions. The trick is that all the expressions are evaluated before any of
the assignments takes place, for example, the following multiple assignment swaps the values
of x and y:
x,y := y,x
The following assignment rotates the values of x, y and z:
x,y,z := y,z,x
A do statement chooses a branch with a true guard and executes it; if the chosen branch ends
with exit, the do statement terminates, otherwise it repeats from the beginning. The following
do statement calculates the greatest common divisor of positive integers x and y using Euclid's
algorithm.
// requires 0 < x 0 < y
do x < y then y := y - x
[] x = y then gcd := x exit
[] y < x then x := x - y
od
The GCD program above repeatedly executes either the first or third branches until x equals y, at
which point it executes the middle branch, which assigns to gcd and terminates the do
statement.
Syntax Changes
The following lexical tokens have been added to the scanner module of PL0 already.
SEPARATOR → ">@"
KW_OD → "od"
KW_EXIT → "exit"
KW_SKIP → "skip"
Keywords are case sensitive.
The non-terminal Statement in the grammar for PL0 is modified to the following Extended
Backus-Naur Form (EBNF) grammar rules.
Statement → WhileStatement | IfStatement | CallStatement |
Assignment | ReadStatement | WriteStatement |
CompoundStatement | SkipStatement | DoStatement
where
SkipStatement → KW_SKIP
Assignment → LValueList ASSIGN ConditionList
LValueList → LValue { COMMA LValue }
ConditionList → Condition { COMMA Condition }
DoStatement → KW_DO DoBranch { SEPARATOR DoBranch } KW_OD
DoBranch → Condition KW_THEN StatementList > KW_EXIT @
Note that the branches of the do statement contain statement lists rather than just a single
statement, and the do statement is terminated by the keyword od.
The addition of a skip statement allows one to write
if x < 0 then x := -x else skip
to assign x its absolute value. Equivalently one can use the following:
do x < 0 then x := -x exit
[] 0 <= x then skip exit
od
Static Semantic Restrictions
Skip statement
There are not any static semantic restrictions on the skip statement, that is, it is well formed for
any symbol table context.
syms ⊢ WFStatement(skip)
Multiple assignment
The lists of left values and right values must be the same length. All of the variables on the left
side of a multiple assignment must be distinct. The type of each condition (expression) must be
assignment compatible (coercible) to the type of the corresponding variable to which it is
assigned.
n = m
∀ i, j ∈ >1..n@ • i ≠ j ⇒ v ≠ v
∀ i ∈ >1..n@ • (syms ⊢ v : ref(T )) (syms ⊢ e : T )
syms ⊢ WFStatement(v , v , ... , v := e , e , ... , e )
Do statement
A branch of a do statement is well formed if its condition c is of type boolean (it could be a
variable of type ref(boolean) or even a subrange of boolean or ...) and its body ss (a statement
list) is well formed.
syms ⊢ c : boolean
i j
i i i i
1 2 n 1 2 m
syms ⊢ WFStatement(list(ss))
syms ⊢ WFDoBranch(c then ss)
The do branch with a exit is similar.
syms ⊢ c : boolean
syms ⊢ WFStatement(list(ss))
syms ⊢ WFDoBranch(c then ss exit)
A do statement is well formed if all its branches are well formed.
∀ j ∈ >1..n@ • (syms ⊢ WFDoBranch(b ))
syms ⊢ WFStatement(do b >@ b >@ ... >@ b od)
Dynamic Semantics
Skip statement
The skip statement does nothing. The less it does the better.
Multiple assignment
For a multiple assignment, all the expressions in all the assignments are evaluated before any of
the variables are assigned, and then all of the assignments take place. Note that it does not
matter in what order the simple assignments are done because the left sides are all distinct and
the expressions have all been evaluated using the values of the variables before any
assignments take place (and expression evaluation does not have any side effects in PL0).
Do statement
The do statement selects a branch for which the condition is true and executes the
corresponding statement list. If more than one condition is true, any one (but only one) of the
corresponding statement lists may be executed. That is, the branch selected does not have to
be the first with a true guard, but it may be. When the selected branch has finished execution, if
the branch ends in the keyword exit, the whole do statement terminates, otherwise the do
statement is repeated from the beginning. For example, the following calculates the maximum of
x and y. Because both branches exit, this particular statement is more like a multiple branch if
statement.
do x <= y then max := y exit
[] y <= x then max := x exit
j
1 2 n
od
Note that if x equals y then both guards are true and either branch may be executed (and the
same value is assigned to max via either branch in this example). In your implementation you are
free to choose a particular order in which to evaluate the conditions.
A do statement that does not have any branch with an exit will loop forever. That is the intended
semantics.
If all the conditions in a do statement evaluate to false, this is considered a runtime error and
the interpreter is terminated by a call to method runtime with an error message "No branch of
do loop has a true guard".
Interpreter
The PL0 compiler for this assignment uses an interpreter (rather than generate code). A
description of the interpreter is available in Interpreter.pdf.
The interpretation is done in class Interpreter, which uses class Frame for its runtime stack and
class Value for the runtime representation of values. Each kind of expression/statement node in
the PL0 abstract syntax tree has a "visit" method that interprets (evaluates/executes) the
corresponding expression/statement.
The interpreter for the skip statement is trivial.
The interpreter for the multiple assignment has to be careful to evaluate all expressions before
doing any assignments.
The interpreter for the do statement needs to handle multiple branches and either breaking out
of the loop or repeating it. For the do statement, you can determine in what order to evaluate the
conditions (but keep it simple).
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, including the bulletin board or emailing to other
students. If you need that sort of help consult the lecturer and/or tutor. Note that Piazza 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
A penalty of 5% of the maximum mark for an assignment will be deducted for each day or part
thereof late up to a limit of 7 days, after which time assignments will not be accepted for
assessment unless you have been granted an extension.
As we plan to hand back assignments a week or two after submission, requests for an extension
will not be accepted more than one week late, unless there are exceptional circumstances.
Requests for extensions should be accompanied by suitable documentation (see the course
profile for details).
Personal hardware or computer failures are not grounds for extension. Assignments must be
backed up on the university system.
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. You must only modify
the files
Interpreter.java
Parser.java
StatementNode.java
StatementVisitor.java
StaticChecker.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 20 marks. Marks will be allocated as follows:
8 - Syntax analysis including syntax error recovery and tree building
7 - Static semantics checking
5 - Interpreter
Marks will be awarded for the correctness of the changes to each category.
Readability, modular structure, and structural and computational complexity are also 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 especially 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).
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 10/20.
The program submitted will not correctly handle any test case with the new facilities:
Maximum 13/20.
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.