CANDIDATE: pleaseattach Student
Support Unit sticker,
if relevant
THE UNIVERSITY OF SUSSEX
BSc and MComp SECOND YEAR EXAMINATION
Compilers and Computer Architecture
G5035
You can start this exam at a time of your choosing within a 24 hour window. Once started
you will have a set exam duration in which to complete it (note: the assessment will close
at end of the 24 hour window; start with sufficient time to complete).
If you have extra time due to Reasonable Adjustments this is additional to the exam
duration below and has been added to your assessment on Canvas.
Date: Thursday, 11 August 2022
24 Hour Window starts at: 09:30
Exam Duration: 3 hours (including time for scanning, collating, uploading)
Candidates should answer TWO questions out of THREE.
If all three questions are attempted only the first two answers will be marked.
Each question is worth 50 marks.
Write or type your answers on A4 paper, scan and save as a single PDF file
and upload to Canvas.
Please make sure that your submission includes the following:
Your candidate number (Do not put your name on your paper)
The title of the module and the module code.
Read Academic Integrity Statement
You MAY access online materials, notes etc. during this examination. You must complete
this assessment on your own and in your own words. DO NOT discuss this assessment
with others before the end of its 24 hour window. By submitting this assessment you
confirm that your assessment includes no instances of academic misconduct, for example
plagiarism or collusion. Any instance of academic misconduct will be thoroughly
investigated in accordance with our academic misconduct regulations.
G5035
Compilers and Computer Architecture
1. This question is about lexical and syntactic analysis.
(a) Define lexical analysis. What does it achieve? Why do we do it, instead of simply
parsing an entire string using a context-free grammar?
[4 marks]
(b) Let R and S be regular expressions. Suppose you are given ε-automata, each
with one accepting state, to recognise the languages of R and of S. Illustrate how
to construct ε-automata with one accepting state, to recognise the languages of:
i. the regular expression R S ;
[4 marks]
ii. the regular expression RS;
[2 marks]
iii. and the regular expression R∗ .
[4 marks]
(c) Let R be a regular expression. Suppose you are given a DFA to recognise the
language of R. Describe how to construct a DFA with one accepting state, to
recognise the complement of the language of R.
[6 marks]
(d) Write a regular expression which is accepted by the following DFA.
[10 marks]
q4
0
1
q1
0
1
q3
1
0
1
0
q5
q2
(e) Describe a CFG with a start symbol S, for the language given by the regular
expression a b ab∗ a ba∗ b ∗ ba∗ . In particular: describe production rules, so
that no production begins with a non-terminal.
[8 marks]
(f) For the following CFG,
E → E-E
int
where ‘int’ corresponds to a non-negative integer in decimal, write three different
parse trees for the string “ 8 – 4 – 2 – 1 ”. Interpreting these parse trees as
different orders of evaluating integer subtraction, describe the different values
assigned to this string by these different parse trees.
[12 marks]
2
Compilers and Computer Architecture
G5035
2. This question concerns RISC-V code generation, to evaluate arithmetic expressions
in a simple memory model.
In this question, you will write (short) RISC-V assembly programs for four different
tasks. Your programs may only use instruction labels for branching, the registers x0,
a0, t1, t2, sp, and fp, and the following RISC-V assembly commands:
lw
register1
offset ( register2 )
load a word of data at offset from an
address stored in register2 , into register1 .
sw
register1
offset ( register2 )
store the value of register1 into memory
at offset from an address stored in
register2 .
add
register1
register2
register3
add the values stored in register3 and
register2 , and store the result in
register1 .
mul
register1
register2
register3
multiply the values stored in register3
and register2 , and store (the lowest 32
bits of) the result in register1 .
addi register1
register2
constant
add the signed 16-bit value constant to
the value stored in register2 and and
store the result in register1 .
jump to the instruction at address .
b
address
beq
register1
register2
address
if the contents of register1 and register2
are equal, jump to the instruction at
address .
bne
register1
register2
address
if the contents of register1 and register2
are different, jump to the instruction at
address .
Each instruction is to be written on a separate line. Use the convention that the stack
grows “downwards” (i.e., that the front of the stack is at a lower address than the rest
of the stack) and that sp points at an unused word in memory below the front of the
stack.
(a) Write a RISC-V assembly program that pushes the value 0 onto the front of the
stack.
[10 marks]
(b) Write a RISC-V assembly program to add two numbers at the front of the stack,
explicitly popping each of those stored numbers off of the stack in doing so, and
separately pushing the result onto the stack.
[10 marks]
(c) Write a RISC-V assembly program, which reads elements from the front of the
stack, popping them off the stack as it goes and adding them to a running total,
stopping when it encounters a value of 0 on the stack (without popping that 0
value off the stack). You may assume that there is at least one non-zero value on
the stack to be added. The result should be pushed onto the stack after the first
0 value found on the stack.
[10 marks]
3
Turn over/
G5035
Compilers and Computer Architecture
(d) Write a RISC-V assembly program, which reads elements z1 , z2 , z3 , and z4 , from
the stack (where z1 is at the front, z2 is next from the front, etc.) popping them
off the stack as it does so; computes the value (2z1 + 3z2 )2 + z3 · z4 (with
the usual order of operations); and pushes the result back on the stack. Only
use the instructions provided above. You may assume that the final result and all
intermediate results can be stored as 32-bit integers without overflow. [20 marks]
4
Compilers and Computer Architecture
G5035
3. This question is about the principles of memory management and garbage
collection for object oriented programming.
Throughout the following, we consider a single running example involving fragments
in a Java-like language; each snippet of Java should be considered to build this
running example further. (You will not be asked to write any code in your answers.)
In your answers, make reference to the stack, activation frame, method table, object
header, or heap as appropriate.
(a) Consider the following class definition.
class Animal {
List < String > sounds ;
Random mood ;
public Animal () {
mood = new Random ();
sounds = new LinkedList < String >( Arrays . asList ( ” quiet ” ));
}
public String makeSound () {
String sound ;
int index = mood . nextInt ( sounds . size ());
if ( sounds . isEmpty ()) sound = ” ” ;
else sound = sounds . get ( index );
return sound ; } }
At run-time, the instructions for the methods Animal() and makeSound() have to
be stored somewhere in memory.
i. Where in memory would the instructions for these methods be stored?
[2 marks]
ii. How could this location be found at run-time, for an instance of to generate the
code for a method invocation?
[4 marks]
(b) Consider two further class definitions:
class Cat extends Animal {
int lives ;
public Cat () {
super (); lives = 9;
kittens = new LinkedList < Cat >();
sounds . addAll ( Arrays . asList ( ” meow ” , ” purr ” , ” hiss ” )); }
public String watch () { return ” ( watches lazily ) ” ; } }
class Tiger extends Cat {
public Tiger () { super (); }
@Override public String makeSound () { return ” ROAR ” ; }
@Override public String watch () {
return ” ( watches hungrily ) ” ; } }
where in both cases, “super()” is actually an alias for the constructor of the
corresponding super-class (which the defined class is extending).
i. Where are the instructions for the methods Cat(), Tiger(), makeSound(), and
watch() stored for the Cat and Tiger classes?
[2 marks]
ii. Do any of the method memory locations have something in common with each
other, or the methods of the class Animal?
[6 marks]
5
Turn over/
G5035
Compilers and Computer Architecture
iii. How can these memory locations be found at run-time?
[2 marks]
(c) Consider the following snippet:
Cat newCatWithSounds () {
Cat figaro = new Cat ();
System . out . println ( figaro . makeSound ());
System . out . println ( figaro . watch ());
return figaro ;
}
i. When the method newCatWithSounds() is invoked, where in memory is the
instance of Cat stored, which is created by the command “ new Cat() ” ? What
is the relationship between this and the location in memory indicated by the
identifier figaro?
[6 marks]
ii. That object (the Cat figaro) has members: an integer ‘ lives ’, a ‘Random’
object mood, and a list of Strings ‘sounds’. Where is figaro.lives stored, and
where in memory are the object figaro.mood and the list pointed to by sounds
stored? Is there anything about the memory locations that the members lives
and sounds have in common?
[8 marks]
(d) Consider the following snippet:
void ghostCat () {
Cat cheshire = new Cat ();
System . out . println ( cheshire . makeSound ());
System . out . println ( cheshire . watch ());
return ;
}
i. When the method ghostCat() is invoked, and the invocation comes to an end,
what happens to the memory address associated with the identifier cheshire,
and the Cat object which is assigned to it?
[4 marks]
ii. For both the location of cheshire in memory, and the location of the Cat object
to which cheshire refers, state how long it takes to make the memory they
reference reusable again. What factors are important in making the memory
reusable?
[8 marks]
iii. Describe the following possible techniques for reclaiming the memory stored
by the new Cat() object:
A. Mark and sweep;
B. Stop and copy.
In each case, describe the principle behind the technique.
[8 marks]
6