THE UNIVERSITY OF SUSSEX
INFORMATICS
BSc AND MComp SECOND YEAR EXAMINATION 2021
January 2021 (A1)
Compilers and Computer Architecture
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 your answers on A4 paper, scan and save as a single PDF file and
upload to Canvas
PDF file name: candidate number module title
Read Academic Integrity Statement
You are reminded that, unless you have been authorised to do so in School or
specific assessment guidance, you should not access online materials, notes etc.
during this examination or discuss this assessment with others before the end of
its 24 hour window. By submitting this assessment you confirm that you have read
the above Statement and are responsible for understanding and complying with
our academic misconduct regulations (found on Student Hub and here: Academic
Misconduct regulations).
G5035 Compilers and Computer Architecure
1. This question is about lexing, parsing, and CFGs (= context free grammars).
(a) For each of the following statements about ASTs (= abstract syntax
trees), state whether they are true or false. Correct answers are
awarded 2 marks; wrong answers are penalised by 1 mark (to a minimum
of 0 marks for this question). Omitted answers do not contribute
positively or negatively to your grade. [14 marks]
i. The lexer takes as input a list of tokens, representing a program.
ii. The lexer produces an AST from the list of tokens.
iii. The token list is produced in the semantic analysis stage.
iv. The purpose of the lexing phase is to make it easier to adapt a
compiler to new machine architectures (such as moving from Intel
to ARM processors).
v. The purpose of constructing an AST is to represent the structure of
the computer program, to simplify code generation.
vi. The purpose of constructing an AST is to allow the compiler to
generate faster executable machine code.
vii. Dynamically typed languages like Python and Javascript don’t need
to do lexing and parsing.
(b) In this question, we consider CFGs in which we take S to be the initial
variable. For each of the following statements, state whether they are
true or false. Correct answers are awarded 4 marks; wrong answers
are penalised by 1 mark (to a minimum of 0 marks for this question).
Omitted answers do not contribute positively or negatively to your grade.
True or false: the language of this CFG is infinite (meaning: contains
infinitely many strings).
True or false: the language of this CFG is precisely the set of
non-empty strings over {(,)} with balanced brackets, including
e.g. (),(()),(()(())), ...
iii.
True or false: the language of this CFG is precisely the set of
(possibly empty) strings over {(,)} with balanced brackets, including
e.g. (),(()),(()(())), ....
2
Compilers and Computer Architecure G5035
iv. The CFG over the alphabet {a, !} with reductions
S → HSHS
True or false: the CFG is left-recursive.
(c) For this question, you are to provide a formal specification of the
structure of the reduction relations of a CFG, given that a CFG can itself
be described using a sequence of symbols.
Consider a context-free grammar G = (A, V, S, X), with alphabet A =
{a, b, c}, variables V = {P, Q, R, S, T}, and start variable S. Observe that
one may specify the reduction relation X with a string of the following
format:
A single reduction rule has the format “hvari ::= hstringi”, where
– hvari ∈ V , and
– hstringi is either a single symbol ‘epsilon’, or a non-empty string
over the set A ∪ V .
The set of all reduction rules consists either of just a single reduction
rule, or a semicolon-separated list “hrule1i ; hrule2i ; · · · ” in which
each hruleji is a single reduction rule.
Write a formal grammar (involving alphabet symbols ‘ ::= ’, ‘epsilon’, ‘;’ ,
‘a’, ‘b’, ‘c’, ‘P’, ‘Q’, etc.) which accepts precisely the strings with the
above format, for a CFG G = (A, V, S, X) as set out above. (Hint: use
notation which distinguishes the rules of the CFG G, from the rules of
the formal grammar which you use to describe G.) [20 marks]
3 Turn over/
G5035 Compilers and Computer Architecure
2. This question is about code generation. The first two parts make reference
to the following program fragment in a Java-like language:
class MyInt {
private int n;
public MyInt (int j) { n=j; }
public int f (int x) { n=n+1; return n*x; }
public MyInt g (int x) {
int j = x+n;
MyInt r = new MyInt(j);
return r;
}
}
(a) Consider an invocation of the form a.g(z) for variables a (of type MyInt)
and z (of type int). Describe the locations in memory of the variables
x, j, n, and r (making reference to the stack, activation frame, symbol
table, or heap as appropriate), and explain the reason for your answer.
i. Briefly describe the location of the variable x, and the reason for this.
[4 marks]
ii. Describe the location of the variable j. Does it have any simple
relationship to the location of x? Briefly explain your answer.
[8 marks]
iii. Describe the location of the variable n. Does it have any simple
relationship to the location of x or j? Briefly explain your answer.
[8 marks]
iv. Describe the location of the object r. Does it have any simple
relationship to the location of x, j, or n? Briefly explain your answer.
[8 marks]
(b) Explain how the compilation of methods and method invocation in
object-oriented languages, can be reduced to the compilation of
procedures and procedure calls. Your answer should suppose an
approach involving method tables.
i. Write pseudocode representing how MyInt::f would be realised as
a procedure, and how an invocation a.f(x) would be realised as a
procedure invocation for an object a of class MyInt. [6 marks]
ii. Explain briefly how method bodies are stored in memory, and how
these memory locations may be found at run-time in a method
invocation. [10 marks]
iii. Explain briefly what advantage there is to perform such a
conversion, e.g., in a compiler accepting multiple source languages.
[6 marks]
4
Compilers and Computer Architecure G5035
3. This question is about computer architecture.
(a) In most common architectures, a memory access to an odd-valued
address may either fail, or be slower than a memory access to an
address which is a multiple of 4 or 8. Briefly explain why. [10 marks]
(b) Describe the two main issues which apply to the use and availability of
the following for kinds of memory. Describe how these issues apply to
each sort of memory (a very brief description for each). [10 marks]
i. Registers;
ii. Flash memory;
iii. Dynamic RAM (main memory);
iv. Static RAM (cache);
(c) In this question, you will write (short) RISC-V assembly programs for two
different tasks. Your programs may only use 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 .
addi register1 register2 constant add the signed 16-bit value constant
to the value stored in register2 and
and store the result in register1 .
b address jump to the instruction at 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.
5 Turn over/
G5035 Compilers and Computer Architecure
i. Write a program that pushes the value 0 onto the front of the stack.
[10 marks]
ii. Write a RISC-V assembly program to add a sequence of numbers
which are stored on the stack. Assume the following:
The last item on the stack to be added, is at the address which
is pointed to by fp; and that the initial value stored by fp is an
address in memory which is higher than that stored in sp.
In particular: there is at least one item on the stack to be added.
The resulting sum is to be stored at the front of the stack. The first
instruction should have a symbolic address “start”, and the last
instruction should jump to a symbolic address “done”. [20 marks]