Candidate Number
THE UNIVERSITY OF SUSSEX
BSc SECOND YEAR EXAMINATION January 2019 (A1)
Compilers and Computer Architecture
Assessment Period: January 2019 (A1)
G5035
DO NOT TURN OVER UNTIL INSTRUCTED TO BY THE LEAD INVIGILATOR
Candidates should answer TWO questions out of THREE. If all three questions are attempted only the first two answers will be marked.
The time allowed is TWO hours.
Each question is worth 50 marks.
At the end of the examination the question paper and any answer books/answer sheets, used or unused, will be collected from you before you leave the examination room.
G5035 Compilers and Computer Architecture
1. This question is about lexing and parsing.
(a) This question is about ASTs (= abstract syntax trees). For each of the following statements, state whether they are true or false. Each correct answer gives 2 marks, each wrong answer gets -1 mark, omitted answers get 0 marks. Overall marks are capped from below to 0.
[10 marks]
i. The AST is constructed by the lexer.
ii. The AST is constructed by the parser.
iii. The purpose of constructing an AST is to make later compiler phases (e.g. type-checking and code-generation algorithms) simpler.
iv. The purpose of constructing an AST is to allow the compiler to generate faster executable machine code.
v. The AST data type is a list of tokens.
(b) Consider the following finite state automaton with 5 states, one of them initial and another one terminal:
Give a regular expression that accepts the same language as the automaton. Don’t forget to specify the alphabet. [14 marks]
(c) Let A be the alphabet {a, b}. For each of the following statements, state whether they are true or false. Each correct answer gives 1 mark, each wrong answer gets -1 mark, omitted answers get 0 marks. Overall marks are capped from below to 0. [10 marks]
i. The empty string is in the language of aaa(a|b)∗ over A.
ii. The string aa is in the language of aaa(a|b)∗ over A.
iii. The string aaabbbbbbbbbbbbbbbbbbb is in the language of aaa(a|b)∗ over A.
iv. The string aabbbbbbbbbbbbbbbbbbb is in the language of aaa(a|b)∗ over A.
v. The string bbaaaaaaaaaaaaaaaaaaa is in the language of aaa(a|b)∗ over A.
0
Terminal
0
Initial
0
1
1 1 0
1
0
1
2
Compilers and Computer Architecture G5035
vi. aaa(a|b)∗ is a regular expression of the alphabet {a, b, c, d}.
vii. Let R be a regular expression over some alphabet B. Then the
languages of R∗ and (R∗)∗ are different.
viii. Let R be a regular expression over some alphabet B. Then the
languages of R∗ and R∗R∗ are identical.
ix. Let R be a regular expression over some alphabet B. Then the
languages of R+ and R+R+ are identical
x. Thelanguageofwell-bracketedstrings,e.g.ε,(),()(),(()),(()(())),…
can be given by a regular expression R over the alphabet {(, )}.
(d) This question is about CFGs (= context free grammars). For each of the following statements, state whether they are true or false. Each correct answer gives 4 marks, each wrong answer gets -2 marks, omitted answers get 0 marks. Overall marks are capped from below to 0.
Consider the following CFGs. In all cases S is the initial variable.
i. The CFG over the alphabet {(, )} with reductions
S → (S) S → SS
True or false: the language of this CFG are exactly the strings over the alphabet {(,)} that feature only balanced brackets, including e.g. ε, (), ()(), (()), (()(())), ….
ii. The CFG over the alphabet {(, )} with reductions S→(T) | S→TT | S→ε | T →S
True or false: the language of this CFG are exactly the strings over the alphabet {(,)} that feature only balanced brackets, including e.g. ε, (), ()(), (()), (()(())), ….
iii. The CFG over the alphabet {(, ), +, ∗, −, 0, 1} with reductions S → (S)|S+S|S∗S|−S|0|1
True or false: the CFG is ambiguous.
iv. The CFG over the alphabet {(, )} with reductions
S→(T) | S→TT | S→ε | T →S True or false: the CFG is left-recursive.
3 Turn over/
[16 marks]
G5035 Compilers and Computer Architecture
2. This question is about code generation.
(a) When translating conditionals and loops, the generated assembly code (e.g. MIPS, x86 or ARM) contains jumps. For the CPU to be able to execute a jump, the target of a jump must be a valid memory address. However, code generators that emit assembly code typically generate jumps to symbolic addresses. Here are two examples in MIPS assembly:
b exit
beq loop_body
Answer the following questions about symbolic addresses.
i. What are the advantages of using symbolic addresses?
ii. Which program is responsible for translating such symbolic addresses to actual memory addresses?
iii. How does the code generator create symbolic addresses?
[10 marks]
(b) Consider the following program fragment in a Java-like language:
class A {
A f ( int i ) {
int j = i+1;
A a = new A ();
return a;
} }
Can the local variable a in the method f be allocated in the activation record (for invocations) of f? If you think it can, sketch an appropriate layout for the activation record. If you think that’s not possible, explain why not, and where a should be held instead. [10 marks]
(c) In the lectures we used (a variant of) the following simple programming language to explain code-generation.
E ::= n|x|E+E|E−E
P ::= forx = EtoEdoP|P;P|x:=E
Here x ranges over variables, and n over integers. Design a code generator for the simple language above. The target machine architecture for your code generator is the stack machine (as introduced in the lectures). Make sure to explain your design appropriately, including any auxiliary procedures you might be using. Note that your code generator should translate both programs (ranged over by P) and expressions (ranged over by E).
4
Compilers and Computer Architecture G5035
For your help, the commands of the machine language for the stack machine are listed below. [30 marks]
Command Nop
Meaning Does nothing
Removes the top of the stack and stores it in x Pushes the content of the variable x on stack Pushes the number n on stack
Pop x
PushAbs x
PushImm n
CompGreaterThan Pops the top two elements off the stack.
CompEq
Jump l JumpTrue l
Plus
Minus
Times Divide
Negate
If the first one popped is bigger than the second one, pushes a 1 onto the stack, otherwise pushes a 0.
Pops the top two elements off the stack. If both are equal, pushes a 1 onto the stack, otherwise pushes a 0.
Jumps to l
Jumps to address/label l if the top of the stack
is not 0. Top element of stack is removed.
Adds the top two elements of the stack, and
puts result on stack. Both arguments are
removed from stack
Subtracts the second element of the stack from
the top element, and pushes the result on the
after popping the top two elements from the stack Multiplies the top two elements of the stack, and puts result on stack. Both arguments are removed from stack Divides the top element of the stack by the second element on the stack, and puts result on stack.
Both arguments are removed from stack
Negates the top element of the stack.
5 Turn over/
G5035
3. This (a)
(b)
(c) (d)
Compilers and Computer Architecture
question is about garbage collection (GC).
What does GC do? How do languages without GC (for example C and C++) deal with the problem GC solves? [10 marks]
Reachability of memory is an important concept in GC. Explain what it
means.
Explain how a mark-and-sweep garbage collector works. Explain how a stop-and-copy garbage collector works.
[10 marks] [15 marks] [15 marks]
6
End of Paper