1 a)
Rules			Director Sets
S    -> S_h S_t		{a, b, c}
S_h  -> B		{b, c}
     -> a B		{a}
S_t  -> a A S_t		{a}
     ->			{$}

A    -> c A		{c}
     -> b		{b}

B    -> A B_h B_t	{c, b}
B_h  -> c A		{c}
     ->			{b, a, $}
B_t  -> b A B_t		{b}
     ->			{a, $}

Marking strategy:
 2 marks for director sets
 10 marks for LL grammar


b) Since the grammar has no left recursion, showing that it is LL(1)
   requires showing that director sets do not have a conflict (5 marks).

   The grammar is not SLR(1) since due to a reduce-reduce conflict
   in the last two rules and their follow sets are the same (5 marks).
   Partial marks were given for saying that there is a reduce-reduce
   conflict, but to get full marks you need to show the follow sets.

c). 3: Both parsers build an AST
          Ensure grammar is LALR(1) - no ambiguities, right recursion, ...
    1: vague statements on changing grammar
    0: nothing


For Question 2(b)
We received the following suggestions:
Add logical NOT
Print location of memory[]
add >, >=, <=, AND
make machine instructions use integers instead of shorts
Add INVN function tat inverts top n elements
PRINTCN - prints the top n elements as characters
Add runtime checking (underflow, overflow)
Add array subscript checks
Better I/O
Better conditional brunches (without popping the stack)
Make true and false to be 1 and -1 so that minus works
Add branch on true
Add operations to increment/decrement mlp for top down
  allocation of heap that can grow/shrink
Add function for decompiling code into readable instructions:  

    PUSH 1
    ADD
    etc.




3 (a). 5: use a hash function. +2 bonus if hash function given
       3: if/else statements
       2: table or array
       0: nothing

  (b). 10: implementation of answer in (a) correct. many possible answers.
        7: almost, but not quite correct.
        5: several errors
        3: many errors
        0: nothing

       -2: some sort of IR (quadruples, assignment machine code, ...) not used.

4 (a). 8:

       first:  X(8) pad(8) Y[6](96) -> 112. no padding needed since 8 divides 112
       smallU: 64 -> R takes lower 32, T takes all 64. needs to be aligned on 64 due to T.

       second: first(112) first(112) z(1) pad(31) S(32) pad(32) smallU(64)
               |          |          |    |       |     |       |
               0          112        224  225     256   288     320

       6: layout mostly correct
       4: several errors
       2: many errors
       0: nothing

  (b). 4 per optimization. for each, -1 if optimization not named.
       optimizations must be correctness preserving, otherwise 0 for the incorrect optimization.
       -1: no final code

       Possible optimizations:
         - common subexpression elimination
         - strength reduction / test replacement
         - code motion
         - loop unrolling
         - dead code elimination
         - useless computation elimination
	 - constant folding


5 a) The given program passes procedures as parammeters, which in general
     requires a special display handling algorithm (see slides 49-50).
     However, in this particular case, procedures only use variables
     declared in their scope, so a simple display handling algorithm
     would work.

  b) We expected to see a simple code in the target language that sets
     the display and branches to the address of 'exec'. Since 'exec'
     does not return any values, no particular epilogue is necessary.



For Question 6:

(a).  The problem can be posed either as backward or as forward.
Both received full marks if carried through correctly and if
an explanation why was included.  Otherwise, one mark.  The
rest of these solutions will assume a forward all-paths problem.

(b).  We use gen - information generated in this block,
             use - information used in this block but not generated
             in  - available information upon entry to the block
             out - available information upon exit
             kill - information goes out of scope (used only for one block)

We do not use "use" in the equations:  this set is used for checking:
for every variable in use, check that it is in "in".  If not, there
is an error.

We handle new scope by renaming variables.

The problem is all-paths.

Equations:  out = gen union in minus kill
            in = intersection out(predecessors)

Marking:
  correct equations:    3
  description of sets:  2
  all paths analysis :  2

(c)

Marking:  
correct graph:                                4
additional variables for dealing with scopes: 2
equations are applied correctly:              6

(d)
There are two problems:
   For x = z, z may not be defined (if we go through the loop the first time)
   For x = y, y is not defined

Marking:
For each problem:   1


For question 7:

Here are some cool answers:
Can Anyone Parse a Language
Could Almost Parse a Language
Complete and Perfect Academic Language
Canonical and Practical Assignment Language

and

Compiling and Parsing are Learnable
Can Anyone Please Analyze this Language
Compiling and Parsing a Language
Compiler and Parser at Last
Compilation Ability Presumed Alltogether Lightening
Clever Algorithms Programmed as Language