1. This question is about the compiler frontend.

(a) Why does the parsing phase construct an abstract syntax tree (AST)? What is the relationship between the program under compilation and this AST?                                                                                           [10 marks]

(b)  For each of the following statements, state whether they are true or false. All regular expressions are over the alphabet {a, b, c, d}.  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 0.

ii. The empty string is not in the language of e.

iii. The empty string is not in the language of (aabaccdddddaccaaa)* .

iv. The empty string is not in the language of aabaccdddddaccaa(a* ).

v. The languages of (a* )I(b* ) and (aIb)*  are identical.

vi. The languages of (bcA* )+  and (bcA* )(bcA* )*  are different.

vii. The languages of A*  and (A* )*  are distinct.

viii. The languages of A+  and (A+ )+  are identical

ix. The languages of (abc)*  and (cba)*  are identical.

x. The languages of (abc)+  and (cba)+  are distinct.

(c)  For  each  of  the  following  context-free  grammars  (CFGs)  over  the alphabet {a, b, c, d}, describe the language given by the grammar. Recall our conventions like grouping transitions, and variables being capitalised while elements of the alphabet are lower-case characters.  In all cases S is the initial variable.

i. Transitions: S - SSSTSSS and T - SSS .

ii. Transitions: S - SSSTSSS and T - SSS and T - e.

iii. Transitions: S - TTTTTTT and T - SSS and T - e.

iv. Transitions: S - SS  I  ScScScScScS  I  a  I  b  I  d  I  e.

v. Transitions: S - SS  I  aSb  I  bSa  I  c  I  d  I  e.

First three are worth 2 marks each, the fourth is worth 4 marks, while the last is worth 5 marks.                                                           [15 marks]

(d) Assume you are given a deterministic finite state automaton A as a two- dimensional table (array) T, together with an initial state and a list of final states.  The array is indexed by a state and a character.  For simplicity assume that A has a unique accepting state. Sketch (in Java-like pseudo code) an algorithm scan deciding the language of A by using T.   In other words, scan takes as input a string (e.g. represented as an array of characters), and returns a Boolean. More precisely, scan(s) returns true exactly when the string s is in the language of A.           [15 marks]

2. This question is about code generation.

(a)  Real CPUs have a small number of fast registers, typically between 8  and  256.     Explain  why  this  small  number  of  registers  makes compilation more complicated in comparison with compilation to stack or accumulator machines.  Outline a strategy for compiling machines with a finite number of registers.  Explain the key features of this strategy. You don’t  have to  present a full code generator, just the  key  ideas.

[10 marks]

(b)  Imagine you are being asked to write a compiler for a new programming language L. Your compiler should target multiple CPUs, such as Intel’s x86,  MIPS and different ARM CPUs.   What key idea would you use to maximise the amount of code-sharing between the compilers for the different CPU architectures?                                                     [10 marks]

(c)  In the lectures we used (a variant of) the following simple programming language to explain code-generation.

E   ::=   n I x I E + E

P   ::=   repeat P until=0  E I while>0  E do P I x = E I if0 E then P else P

Here x  ranges over variables,  and n over  integers.   The statement repeat P until=0 E executes P repeatedly, until E evaluates to 0. Likewise if0 E then P else P\  evaluates E and whenever that evaluation yields 0 then P is executed, otherwise P\  is run. The command while>0  E do P executes  P  as  long  as  the  evaluation  of  E  is  above  0.    Design  a code generator for the simple language above.   The target machine architecture  for  your  code  generator  is  the  accumulator  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).

As  a  reminder,  the  commands  of  the  machine  language  for  the accumulator machine are listed on the next page.                   [30 marks]