This is an individual assignment which involves modifying the recursive
descent compiler for the language PL0 to add a skip statement, a
multiple assignment statement, and a case (switch) statement.
Assignment Compiler files
All sources for the assignment PL0 compiler are available as
(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).
• 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 pay attention to course Blackboard announcments, and ensure
you follow the course discussion 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
• 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 some Java compilers and all comments
should be readable by the person assessing your assignment.
• Your implementation should be in Java 1.8. Set the IntelliJ
preferences for the Java compiler to 1.8 (or use the "-source 1.8"
option to the 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) 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.
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 | y := z | z := x
The following case statement assigns to y exactly once.
case i of
when 2: y := 1
when 3: y := x
when 5: y := x*x
default y := 42
Syntax Changes
The following lexical tokens have been added to the scanner module of
PL0 already.
BAR → "|"
KW_CASE → "case"
KW_OF → "of"
KW_WHEN → "when"
KW_DEFAULT → "default"
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 | CaseStatement
SkipStatement → KW_SKIP
Assignment → SingleAssign { BAR SingleAssign }
SingleAssign → LValue ASSIGN Condition
CaseStatement →
KW_CASE Condition KW_OF { CaseBranch }
[ KW_DEFAULT StatementList ] KW_END
CaseBranch → KW_WHEN Constant COLON StatementList
Note that each branch of a case statement contains a statement list,
rather than just a single statement, and that the labels on each branch
are constant expressions (defined using the existing
nonterminal Constant) and hence their values can be determined at
compile time (static analysis time to be more precise).
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:
case x < 0 of
when true: x := -x
when false: skip
Static Semantic Restrictions
Skip statement
There aren't any static semantic restrictions on the skip statement, that
is, it is well formed for any symbol table context.
syms ⊢ WFStatement(skip)
Multiple assignment
All of the variables on the left sides 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.
∀ i, j ∈ [1..n] • i ≠ j ⇒ vi ≠ vj
∀ i ∈ [1..n] • (syms ⊢ vi : ref(Ti)) && (syms ⊢ ei : Ti)

syms ⊢ WFStatement(v1 := e1 | v2 := e2 | ... | vn := en)
Case statement
The type of the expression (condition) for the case statement must be a
scalar type (it could be int or boolean or a subrange thereof) and all
labels of case branches must be compatible with that type and must be
elements of the type (see containsElement in The labels must
be constant expressions, and the value of each label must be unique
within a single case statement. The bodies of all the case branches must
be well formed.
The rule for well formedness of a case statement is given below; within
it T must be a scalar type and for a scalar type values(T) is the set of
values in the type T, e.g. values(boolean) = {false,true} and values([-2..2])
= {-2,-1,0,1,2}.
syms ⊢ e : T
syms ⊢ WFStatement(ss)
∀ j ∈ [1..n] • syms ⊢ WFStatement(ssj) && syms ⊢ cj :
T && (cj →e vj ⇒ vj ∈ values(T))
∀ i,j ∈ [1..n] • i ≠ j && ci →e vi && cj →e vj ⇒ vi ≠ vj

syms ⊢ WFStatement(case e of when c1: ss1 when c2: ss2 ... when cn:
ssn default ss end)
When determining the scalar type T to be used in the rule, it is assumed
that we do not make use of widening or narrowing rules for the types
of expressions but we may need to dereference a reference type (to get
a scalar type).
For the version of the case statement in which there is no default clause,
the requirement for the well-formedness of its statement sequence ss is
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 doesn't 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 the language does not
have any side effects).
Case statement
The case statement evaluates its (scalar) expression to a value, v, and
then selects the branch with the label that has value v and executes the
corresponding statement. If the value of the expression is not equal to
any of the labels of any of the branches then the default branch is
executed. If there is no default branch, this is considered a runtime
error and the interpreter is terminated by a call to
method runtime with an error message "expression in case doesn't
match any label".
On completion of the execution of the appropriate branch within
a case statement, the next statement executed is the one following the
whole case statement. That is, it is NOT like a switch statement in which
execution of one branch flows into the next branch unless
a break statement is placed at the end of the first branch -- a language
feature that is the source of many a bug.
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 case statement is quite simple (a handful of
lines) provided you have chosen a suitable representation for the
Some tests are available in the test-pgm directory (in, and can be
used to help you to debug your code. All of the tests can be run together
using the Test PL0 configuration. You can also individually run a test
using Run PL0 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.