Candidate Number
G5035
THE UNIVERSITY OF SUSSEX
BSc SECOND YEAR EXAMINATION 2015 COMPILERS AND COMPUTER ARCHITECTURE
Friday, 16 January 2015 9.30 am – 11.00 am
DO NOT TURN OVER UNTIL INSTRUCTED TO BY THE CHIEF 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 ONE AND A HALF hours. Each question is worth 50 marks.
G5035
1. This (a)
(b)
(c)
(d)
COMPILERS AND COMPUTER ARCHITECTURE
question is about lexing and parsing.
Describe the purposes of lexing and parsing in a compiler. Don’t forget to mention the input and output of lexer and parser. [12 marks]
What does it mean for a CFG to be left-recursive? In what circumstances can left-recursive grammars be problematic? Give an example of a left- recursive CFG grammar G, and convert it into a CFG grammar G′ that is not left-recursive, but accepts the same language. [12 marks]
The lexical structure of programming languages is usually specified by regular expressions. For example most languages use a regular expres- sion like [a − z][a − zA − Z0 − 9]∗ to specify identifiers. However, there is a problem with using pure regular expressions (think of keywords). Explain what the problem is and how it is solved. [12 marks]
Here is a context-free grammar for a hypothetical programming lan- guage that is similar to the language used in the assessed exercises. The starting symbol is PROG.
PROG → DEC → VARDEC → VARDECNE → ID → INT → BLOCK → ENE → E →
DEC | DEC PROG
def ID (VARDEC) = BLOCK ε | VARDECNE
ID | VARDECNE, ID
…
…
{ENE}
E |E;ENE
INT
ARGS → ARGSNE → COMP → BINOP →
ε | ARGSNE
E | ARGSNE, E ==
+
| ID
| if E COMP E then BLOCK else BLOCK
| (E BINOP E)
| BLOCK
| while E COMP E do BLOCK
| ID:=E
| ID(ARGS)
Here ε represents empty productions. The non-terminal INT ranges over integers, and ID over strings. Sketch in Java-like pseudo-code a suitable AST (abstract syntax tree) implementation for this language. No need to detail class constructors. Use the corresponding built-in data structures String and int to represent ID and INT. [14 marks]
2
COMPILERS AND COMPUTER ARCHITECTURE G5035
2. This question is about garbage collection and the compilation of object- oriented languages.
(a) Assume you are being asked to advise two companies on garbage col- lection strategies. They ask you whether they should use a mark-and- sweep collector or a stop-and-copy collector.
• The first company works with embedded devices that have little memory. Hence the most important thing for them is that the col- lector should use the available memory as efficiently as possible.
• The second company cares about data-locality, meaning that the data should be as close together in memory as possible.
Which collector would you recommend in each case? Justify your an-
swer. [10 marks]
(b) Modern garbage-collected programming languages often split the heap into multiple heaps (called generations) with rules how to move data between generations. Explain why. [10 marks]
(c) A characteristic of object-oriented languages is the heavy use of sub- typing. One consequence of subtyping is that the concrete type of data might not be known at compile-time. For example the concrete type of obj might not be known in the following code fragment (which we as- sume to be well-typed).
interface I { … }
class A extends I { … }
class B extends I { … }
…
I obj = if … then new A ( … ) else new B ( … )
obj.x = 17
obj.f( 1, 2, true );
Explain how we compile object-oriented languages with subtyping, yield- ing efficient code. Make sure you explain how method invocation and field access are translated. [17 marks]
(d) Languages like Java and Python provide reflection. Reflection gives you information about the type of an object at run-time. For example the Java command obj.getClass().getName() returns (as a string) the name of the class that object obj is an instance of. Explain how reflection can be implemented in class-based object-oriented languages. [13 marks]
3 Turn over/
G5035 COMPILERS AND COMPUTER ARCHITECTURE
3. This question is about code generation.
(a) In principle a compiler could store procedure arguments and local vari- ables on the heap. In practice, compilers store them on the stack or in registers. Explain why. [10 marks]
(b) In the lectures and tutorials we used (a superset of) the following simple programming language to explain code-generation.
E,E′ ::= n|x|E+E′
P,Q ::= repeatP untilE ≤0|if E >0thenP elseQ|x:=E
Here x ranges over variables, and n over integers. Design a code gen- erator for the simple language above. Design a code generator for the simple language above. The target machine architecture for your code generator is the register machine with an unlimited number of registers (as introduced in the lectures). Make sure to explain your design appro- priately. For your help, the commands of the machine language for the target architecture are listed below. We assume that the registers are named R0, R1, R2, …, and r, r′ range over registers. [30 marks]
Command Nop
Pop r
Push r Load r x
LoadImm r n Store r x
Meaning Does nothing
Removes the top of the stack and stores
it in register r
Pushes the content of the register r on stack Loads the content of memory location x into register r
Loads integer n into register r
Stores the content of register r in memory location x
CompGreaterThan r r’ Compares the content of register r with the content of register r’. Stores 1 in r if former
Jump l JumpTrue r l
Plus r r’ Minus r r’ Times r r’
Divide r r’ Negate r
is bigger than latter, otherwise stores 0 Jumps to l
Jumps to address/label l if the content of register r is not 0
Adds the content of r and r’, stores result in r
Subtracts the content of r’ from r, stores result in r
Multiplies the content of r and r’, stores
result in r
Divides the content of r by r’, stores result in r Negates the content of r and stores result in r
4
COMPILERS AND COMPUTER ARCHITECTURE
(c) Consider the following Java fragment:
class A {
int a_;
A( int a ) { a_ = a; }
A f ( int i ) {
int j = i;
A a1 = new A ( j );
A a2 = new A ( i );
return a1; } }
Describe how you would lay out the activation record for f.
G5035
5 End of Paper
[10 marks]