Name_______________________________________

Final Examination.
COM 3355.  Compiler Design.
Winter 2002.

Each true/false question is worth 3 points.  Each multiple choice
question is worth 4 points.  Each remaining question is worth the
number of points indicated within brackets.


T   F   %.   The parser is considered to be part of the front end
             of a compiler.

T   F   %.   A grammar is unambiguous if and only if some terminal
             string has more than one leftmost derivation.

T   F   %.   Every context-free language is recognized by some
             deterministic pushdown automaton.

T   F   %.   Every LALR(1) grammar is an LR(1) grammar.

T   F   %.   Every LL(1) parser runs in O(n) time, where n is the
             length of the program being parsed.

T   F   %.   LR parsers have the viable prefix property, and so
             do LL parsers.

T   F   %.   In quirk19, the size of an array cannot always be
             determined at compile time.

T   F   %.   It is not necessary to pass an environment to a C
             function, because all C functions are global.


%%.  How many tokens occur in the quirk19 statement

          wordcount[wd] = wordcount[wd] + 1;

     ____ A.  6

     ____ B.  8

     ____ C.  10

     ____ D.  12

     ____ E.  14


%%.  Although tokens could be recognized by the context-free parser,
     a lexical analyzer (scanner) is normally used because

     ____ #.  not all syntax is context-free.

     ____ #.  most programming languages are object-oriented.

     ____ #.  LR(1) parsers are simpler than LL(1) parsers.

     ____ #.  every LALR(1) grammar is ambiguous.

     ____ #.  finite state automata are simpler (hence faster) than
              pushdown automata.


%%.  The set of languages that are recognized by some deterministic
     finite automaton is the set of

     ____ #.  type 0 languages

     ____ #.  type 1 languages

     ____ #.  type 2 languages

     ____ #.  type 3 languages

     ____ #.  type 4 languages


%%.  Suppose print1 is an action routine that prints 1, print2 is an
     action routine that prints 2, and so on.  What sequence of integers
     will be printed when an LL(1) parser that is generated from the
     following ParseGen grammar is used to parse

                if true
                  then until true do skip
                  else stumble

     *terminals

     skip stumble if then else until do true

     *productions

     <stmt>  ::=  skip                                      #print1
             ::=  stumble                                   #print2
             ::=  if <boolexpr> then <stmt> else <stmt>     #print3
             ::=  until <boolexpr> do <stmt>                #print4

     <boolexpr>  ::=  true                                  #print5

     *end


     ____  #.  5 5 1 4 2 3

     ____  #.  3 2 4 1 5 5

     ____  #.  3 5 4 5 1 2

     ____  #.  2 1 5 4 5 3

     ____  #.  1 3 4 2 5 5


Questions %% and %% refer to the following grammar:

     E  -->  A  |  A ! E
     A  -->  B  |  B : A  |  C * C
     B  -->  C  |  B @ C                             (Figure 1)
     C  -->  D  |  C % D  |  C $ D
     D  -->  x  |  ( E )

%%.  [6 points]  For each of the six binary operators used in
     Figure 1, indicate whether the operator associates to the
     left, to the right, or not at all:

            operator                 association

               !               left      right      not at all

               :               left      right      not at all

               *               left      right      not at all

               @               left      right      not at all

               %               left      right      not at all

               $               left      right      not at all


%%.  According to Figure 1, which of the following expressions
     should have the same abstract syntax tree as  x Æ x % x ¤ x  ?

     ____ #.  ( ( x Æ x ) % x ) ¤ x

     ____ #.  ( x Æ ( x % x ) ) ¤ x

     ____ #.  ( x Æ x ) % ( x ¤ x )

     ____ #.  x Æ ( ( x % x ) ¤ x )

     ____ #.  x Æ ( x % ( x ¤ x ) )


%%.  Which of the following is a legal declaration in quirk19?

     ____ #.  var p := array [10] initially 0

     ____ #.  type strings = { s: string, rest: strings }

     ____ #.  var x = nil

     ____ #.  function null = nil

     ____ #.  function g (n: int) { g (n-1, n) }
%%.  All of the following expressions are syntactically correct
     in quirk19, but only one will be accepted by the type checker.
     Which one is type-correct?

     ____ #.  let function f () : string = 17 in f () end

     ____ #.  let type T = string in T { a = 7 } end

     ____ #.  "0" + 1

     ____ #.  if 13 then 99 else not (3 < 4)

     ____ #.  while chr(64) do 88


%%.  In the quirk19 function declaration

          function f (x: int, y: int) : int =
              if i (x)
                  then y
                  else f (g (x), h (y))

     which function calls occur in tail-recursive position?

     ____  #.  the calls to f, g, h, and i

     ____  #.  the call to i

     ____  #.  the call to f

     ____  #.  the calls to g and h

     ____  #.  the calls to g, h, and i


%%.  In the quirk19 program in question 18 on the next page, which
     of the following expressions allocate heap storage?

     ____  #.  print (x.head)

     ____  #.  z.tail

     ____  #.  z.head

     ____  #.  list { head = " world\n", tail = nil }

     ____  #.  z = nil


%%.  What does the following quirk19 program print?

          let type list = { head : string, tail : list }
              function copy (z : list) : list =
                  if z = nil
                      then z
                      else list { head = z.head, tail = copy (z.tail) }
              var x := list { head = "Hello",
                              tail = list { head = " world\n",
                                            tail = nil } }
          in
              for i := 0 to 100000000 do x := copy (x);
              print (x.head)
          end

     ____  #.  one hundred million lines that say "Hello world"

     ____  #.  a line consisting of a space followed by the word "world"

     ____  #.  a line that says "Hello world"

     ____  #.  one hundred million repetitions of the word "Hello"

     ____  #.  the word "Hello"


%%.  Which of the following is an LL(1) grammar equivalent to

          E  -->  a  |  b  |  b c  |  { E }  |  E [ E ]

     ____ #.  E  -->  a G  |  b F G  |  { E } G
              F  -->  <empty>  |  c
              G  -->  <empty>  |  [ E ] G

     ____ #.  E  -->  a  |  b T  |  { E }  |  E [ E ]
              T  -->  <empty>  |  c

     ____ #.  E  -->  a  |  b  |  b c  |  { E }  |  E X
              X  -->  <empty>  |  [ E ] X

     ____ #.  E  -->  a Z  |  b Y Z
              Y  -->  <empty>  |  c
              Z  -->  { E }  |  [ E ] Z

     ____ #.  E  -->  a H  |  b H  |  b c H  |  { E } H
              H  -->  [ E ] H


%%.  The write barrier of a generational garbage collector

     ____ #.  may be bypassed when the compiler knows that the
              right-hand side of an assignment is not a pointer.

     ____ #.  is likely to make some assignments more expensive.

     ____ #.  may be bypassed when initializing a newly allocated
              object.

     ____ #.  maintains the remembered set, which allows garbage
              to be collected without scanning the entire heap.

     ____ #.  all of the above.


%%.  Block-structured programming languages that were designed to
     be used without requiring garbage collection usually perform
     an assignment by copying the R-value of the right-hand side
     before storing the copy into the L-value of the left-hand side.
     One purpose of this copying is

     ____ #.  to make assignments execute more quickly.

     ____ #.  to avoid dangling pointers.

     ____ #.  to make it easier for data to share substructure.

     ____ #.  to touch memory less often.

     ____ #.  to decrease the size of the code for assignments.


%%.  What single PowerPC instruction is equivalent to the 2-instruction
     sequence

            stw     r1,-32(r1)
            addi    r1,r1,-32

     ____  #.  stwu    r1,-32(r1)

     ____  #.  stw     r1,-64(r1)

     ____  #.  rlwinm  r1,r1,6,0,25

     ____  #.  addi    r1,r1,-64

     ____  #.  stwx    r1,r1,r1


%%.  The PowerPC 750 features speculative execution based on dynamic
     branch prediction.  Its functional units include two integer units,
     a load/store unit, a branch processing unit, and two other units
     that are irrelevant to this question.  Under ideal conditions, a
     PowerPC can execute 3 instructions per clock cycle; for this to
     happen, one of the 3 instructions must be a branch of some sort.
     Under ideal conditions, which of the following loops might a 250 MHz
     PowerPC 750 be able to execute at its peak rate of 750 MIPS?

     ____  #.  L1:  stwu    r0,4(r4)
                    stwu    r0,4(r4)
                    addic.  r5,r5,-1
                    bgt     cr0,L1

     ____  #.  L1:  stwu    r0,4(r4)
                    addic.  r5,r5,-1
                    bgt     cr0,L1

     ____  #.  L1:  addic.  r5,r5,-1
                    bgt     cr0,L1

     ____  #.  L1:  lwz     r0,0(r4)
                    stwu    r0,4(r4)
                    cmpw    cr0,r0,r5
                    bgt     cr0,L1

     ____  #.  L1:  stw     r0,4(r4)
                    addi    r4,r4,4
                    addi    r5,r5,-1
                    cmpwi   cr0,r5,0
                    bgt     cr0,L1


%%.  Suppose the R-value of x is stored at lexical address <2, 40>,
     register r3 holds the run-time environment, and the static link
     (to the next rib) is stored at offset 24.  Which of the following
     code sequences will fetch the R-value of x into r4?

     ____  #.  lwz     r4,40(r3)
               lwz     r4,24(r4)
               lwz     r4,24(r4)

     ____  #.  lwz     r4,40(r3)
               lwz     r4,24(r4)

     ____  #.  lwz     r4,24(r4)
               lwz     r4,40(r3)

     ____  #.  addi    r4,r3,24
               addi    r4,r4,40
               lwz     r4,24(r4)
               lwz     r4,0(r4)

     ____  #.  lwz     r4,24(r3)
               lwz     r4,24(r4)
               lwz     r4,40(r4)


%%.  Suppose the lexical address for a function f is <0, L1000>, and
     the target register for the expression f (1 + f (10)) is r4.
     What is wrong with the following code for that expression?

        addi    r4,r0,4
        addi    r4,r0,40
        bl      L1000
        or      r5,r3,r3
        add     r4,r4,r5
        bl      L1000
        or      r4,r3,r3

     ____ #.  It doesn't move the result of each call to f to the
              target register for the call.

     ____ #.  It doesn't preserve the live registers across the
              calls to f.

     ____ #.  The branch and link (bl) instructions should be
              unconditional branch (b) instructions.

     ____ #.  It doesn't multiply the integer constants by 4.

     ____ #.  It doesn't pop the stack after each call to f.


%%.  With our calling conventions for quirk19, which of the following
     is correct code for the body of

        function f (m : int, n : int) : int =
            if m = 0
                then n
                else f (m - 1, m + n)

     ____  #.  L0: cmpwi   cr0,r4,0
                   bne     cr0,L1
                   or      r3,r5,r5
               L1: addi    r4,r4,-4
                   add     r5,r4,r5
                   b       L0

     ____  #.  L0: cmpwi   cr0,r4,0
                   bne     cr0,L1
                   or      r3,r5,r5
                   blr
               L1: add     r5,r4,r5
                   addi    r4,r4,-4
                   b       L0

     ____  #.  L0: cmpwi   cr0,r4,0
                   bne     cr0,L1
                   blr
               L1: addi    r4,r4,-4
                   add     r5,r4,r5
                   b       L0

     ____  #.  L0: cmpwi   cr0,r4,0
                   bne     cr0,L1
                   or      r3,r5,r5
                   mtlr    r0
                   blr
               L1: addi    r6,r4,-4
                   add     r4,r4,r5
                   or      r5,r6,r6
                   b       L0

     ____  #.  L0: cmpwi   cr0,r4,0
                   bne     cr0,L1
                   or      r3,r5,r5
                   mtlr    r0
                   blr
               L1: addi    r4,r4,-4
                   add     r5,r4,r5
                   b       L0


%%.  What is the value of r4 after executing

            addi    r4,r0,5
            rlwinm  r4,r4,3,16,30

     ____  #.  8

     ____  #.  15

     ____  #.  21

     ____  #.  40

     ____  #.  54


%%.  [6 points]  Suppose i, j, and k are of type int and

          i    is in register r3
          j    is in register r4
          k    is in register r5

     Write a sequence of PowerPC code that a quirk19 compiler might
     generate for the following code, assuming the target register
     is r6.  (Hint: It will take at least four instructions.)

          2 * (i - (j + k - 3))




%%.  [25 points]  Write a sequence of MacScheme machine assembly
     code that a quirk19 compiler (perhaps a better one than we
     wrote this term!) might generate for the body of the forEach
     procedure defined below.  Please assume that this procedure
     and the procedures that it calls are defined within the List
     class.

          static void forEach (function void () f, List x) {
              if (! isEmpty (x)) {
                  int n = hd (x);
                  List y = tl (x);
                  f (n);
                  forEach (f, y);
              }
          }