Last updated: Sun 30 Mar 2025 23:50:50 AEST.
COMP4403 - Compilers and Interpreters
Assignment 1
Due date: 15:00 Thursday 17th April, 2025
This is an individual assignment which involves modifying the recursive descent compiler for the language PL0 to add if expressions and multiple
assignment statements.
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 IntelliJ
Brief documentation on assignment 1 files
Please pay attention to course Blackboard announcements, 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 taking this option because it will often add an erroneous import that you will not need. Such imports
2025/4/12 18:02 COMP4403 Assignment 1 - Recursive descent
https://alt-5fd17f67f4120.blackboard.com/bbcswebdav/pid-10880693-dt-content-rid-70494992_1/courses/COMP4403_7520_21328/publicweb/2025-assignment1.html?one_hash=9A4426452139D030DB7E9FE7A09… 1/10
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.
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 one or more assignments to take place simultaneously. The trick is that all of the expressions (all of the
left and right values that comprise the multiple assignment statement) are evaluated before 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 | y := z | z := x
An if expression chooses a branch with a true guard and evaluates to its guarded expression. For example, the following if expression evaluates to
either variable x, if x is greater than y, or variable y otherwise.
2025/4/12 18:02 COMP4403 Assignment 1 - Recursive descent
https://alt-5fd17f67f4120.blackboard.com/bbcswebdav/pid-10880693-dt-content-rid-70494992_1/courses/COMP4403_7520_21328/publicweb/2025-assignment1.html?one_hash=9A4426452139D030DB7E9FE7A09… 2/10
ife x > y then x
[] x <= y then y
fi
As such, the following statement assigns the maximum value of variables x and y to variable z:
z := ife x > y then x
[] x <= y then y
fi
We can also write, for example,
x := ife x <= 0 then -x
[] x >= 0 then x
fi
to assign x its absolute value.
If expressions can appear as the left values in assignment statements (including multiple assignment statements), and so the following statement
assigns variable x to zero, if x is greater than y, and variable y to zero otherwise:
ife x > y then x [] x <= y then y fi := 0
and the following multiple assignment statement
ife x > y then x [] x <= y then y fi := 0 |
ife x > y then y [] x <= y then x fi := 1
assigns x to zero and y to one, if x is initially greater than y, and x to one and y to zero otherwise.
Syntax Changes
2025/4/12 18:02 COMP4403 Assignment 1 - Recursive descent
https://alt-5fd17f67f4120.blackboard.com/bbcswebdav/pid-10880693-dt-content-rid-70494992_1/courses/COMP4403_7520_21328/publicweb/2025-assignment1.html?one_hash=9A4426452139D030DB7E9FE7A09… 3/10
The following lexical tokens have been added to the scanner module of PL0 already.
BAR → "|"
SEPARATOR → "[]"
KW_IFE → "ife"
KW_FI → "fi"
Keywords are case sensitive.
The non-terminals Assignment and LValue in the grammar for PL0 are replaced by the following Extended Backus-Naur Form (EBNF) grammar rules:
Assignment → SingleAssign { BAR SingleAssign }
LValue → IDENTIFIER | IfExp
where
SingleAssign → LValue ASSIGN Condition
IfExp → KW_IFE IfExpBranch {SEPARATOR IfExpBranch} KW_FI
IfExpBranch → Condition KW_THEN Condition
2025/4/12 18:02 COMP4403 Assignment 1 - Recursive descent
https://alt-5fd17f67f4120.blackboard.com/bbcswebdav/pid-10880693-dt-content-rid-70494992_1/courses/COMP4403_7520_21328/publicweb/2025-assignment1.html?one_hash=9A4426452139D030DB7E9FE7A09… 4/10
Static Semantic Restrictions
Multiple assignment
For a multiple assignment to be a well formed we require each left value in the multiple assignment statement to be well-typed, and to have a
reference type, and each right value to be well-typed and assignment compatible with its corresponding left value:
∀ i ∈ [1..n]   •   (syms   ⊢   left : ref(T ))  &&  (syms   ⊢   right : T )
                                                                                                                                     
syms  ⊢  WFStatement( left := right  | left := right  |  ...  |  left := right )
If expression
For an if expression to be well-typed, we require the guard of each branch to be well-typed and to be of type boolean (it could be a variable of type
ref(boolean) or even a subrange of boolean or ...); we require the guarded expression of each branch to be well-typed; and we require the least type
that is greater than or equal to the types of all of the guarded branch expressions, i.e. join(T1,..,Tn), to exist.
The rule for an if expression is given below:
∀ i ∈ [1..n]   •    (syms  ⊢   g : boolean)  &&  (syms  ⊢   e : Ti)
                                                                                                                         
syms   ⊢   ife g then e [] ... [] g then e fi   :   join(T1, ... , Tn)
Note that class Type has been extended with a static method join that takes two types as arguments, and returns the join of those two types, i.e. the
least type that is greater than or equal to both of its arguments, if it exists, and Type.ERROR_TYPE otherwise. It has also been extended with a static
method join that takes a list of types as an argument and returns the join of that list of types, i.e. the least type that is greater than or equal to all of
the arguments in the list, if it exists, and Type.ERROR_TYPE otherwise.
Dynamic Semantics
i i i i
1 1 2 2 n n
i i
1 1 n n
2025/4/12 18:02 COMP4403 Assignment 1 - Recursive descent
https://alt-5fd17f67f4120.blackboard.com/bbcswebdav/pid-10880693-dt-content-rid-70494992_1/courses/COMP4403_7520_21328/publicweb/2025-assignment1.html?one_hash=9A4426452139D030DB7E9FE7A09… 5/10
Multiple assignment
A multiple assignment needs to be implemented so that it appears as though all of the constituent single assignments take place simultaneously,
using the values of each left and right value before before any of the assignments have taken place. That is, each left value to be assigned must be
evaluated before any of the constituent single assignments have taken place, and it must be assigned its corresponding right value, that was also
evaluated before any of the constituent single assignments have taken place.
At runtime, if all of the left values being assigned in a multiple assignment statement are not distinct, then this is considered a runtime error and
the interpreter is terminated by a call to method runtime with an error message "simultaneous assignment to the same left value".
(Note that as long as the left and right values have all been determined prior to performing any of the individual assignments, it does not matter in
which order the single assignments actually take place because (unless there is a runtime error) all left values will be distinct, and the language does
not have any side effects.)
If expression
An if expression selects a branch for which the guard is true and evaluates to the corresponding guarded expression of the branch. If the guard of
more than one branch is true, any one of the branches with a guard evaluating to true may be selected, and the expression will evaluate to the
guarded expression of the selected branch. For example, in the following if expression
ife x >= y then x
[] x <= y then y
fi
if the value of x equals the value of y, then the guards of both branches are true, and so the expression may evaluate to either variable x or y. That is,
the branch selected does not have to be the first with a true guard, but it may be. In your implementation you are free to choose a particular
method to resolve the nondeterminism.
If the guards of all of the branches 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 alternative can be selected".
Only the guarded expression of the selected branch should be evaluated.
2025/4/12 18:02 COMP4403 Assignment 1 - Recursive descent
https://alt-5fd17f67f4120.blackboard.com/bbcswebdav/pid-10880693-dt-content-rid-70494992_1/courses/COMP4403_7520_21328/publicweb/2025-assignment1.html?one_hash=9A4426452139D030DB7E9FE7A09… 6/10
Interpreter
The PL0 compiler for this assignment uses an interpreter (rather than a code generator). 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 multiple assignment has to be careful to evaluate all expressions (left and right values) before performing any assignments.
The interpreter for if expressions needs to handle multiple branches. For the if expression, you can determine how to resolve any nondeterminism
that arises (but keep it simple).
The interpreter for the if expressions has to be careful to only evaluate the expression of the selected branch.
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.
2025/4/12 18:02 COMP4403 Assignment 1 - Recursive descent
https://alt-5fd17f67f4120.blackboard.com/bbcswebdav/pid-10880693-dt-content-rid-70494992_1/courses/COMP4403_7520_21328/publicweb/2025-assignment1.html?one_hash=9A4426452139D030DB7E9FE7A09… 7/10
This assessment task evaluates students' abilities, skills and knowledge without the aid of generative Artificial Intelligence (AI) or Machine Translation
(MT). Students are advised that the use of AI or MT technologies to develop responses is strictly prohibited and may constitute student misconduct
under the Student Code of Conduct.
Late Submission
See 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. A penalty of 10% of the maximum
possible mark will be deducted per 24 hours from time submission is due for up to 7 days. After 7 days, you will receive a mark of 0.
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.
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
ExpNode.java
ExpTransform.java
Interpreter.java
2025/4/12 18:02 COMP4403 Assignment 1 - Recursive descent
https://alt-5fd17f67f4120.blackboard.com/bbcswebdav/pid-10880693-dt-content-rid-70494992_1/courses/COMP4403_7520_21328/publicweb/2025-assignment1.html?one_hash=9A4426452139D030DB7E9FE7A09… 8/10
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 15 marks. Marks will be allocated as follows:
6 - Syntax analysis including syntax error recovery and tree building
5 - Static semantics checking
4 - 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 8/15.
The program submitted will not correctly handle any test case with the new facilities: Maximum 10/15.
2
2025/4/12 18:02 COMP4403 Assignment 1 - Recursive descent
https://alt-5fd17f67f4120.blackboard.com/bbcswebdav/pid-10880693-dt-content-rid-70494992_1/courses/COMP4403_7520_21328/publicweb/2025-assignment1.html?one_hash=9A4426452139D030DB7E9FE7A09… 9/10
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.
2025/4/12 18:02 COMP4403 Assignment 1 - Recursive descent
https://alt-5fd17f67f4120.blackboard.com/bbcswebdav/pid-10880693-dt-content-rid-70494992_1/courses/COMP4403_7520_21328/publicweb/2025-assignment1.html?one_hash=9A4426452139D030DB7E9FE7A0… 10/10

学霸联盟