Name_______________________________________ Final Examination. COM 1355/3355. Compiler Design. Winter 1997. Each true/false question is worth 3 points. Each multiple choice question is worth 3 points. Each remaining question is worth the number of points indicated within brackets. F 1. Every context-free language is recognized by some deterministic finite automaton. F 2. Every ambiguous grammar is LR(1). T 3. The parser is considered to be part of the front end of a compiler. T 4. Every LL(1) parser runs in O(n) time, where n is the length of the program being parsed. T 5. Every LL(1) grammar is an LR(1) grammar. T 6. Both LL and LR parsers have the correct prefix property. (The correct prefix property is also known as the viable prefix property.) F 7. The lookup operation for compile-time environments cannot be implemented to run in constant time. F 8. In quirk13, a closed type stands for the union of its ground instances. T 9. In quirk13, but not in quirk13c, all objects have unlimited extent (lifetime). F 10. In quirk13, the size of an array can always be determined at compile time. T 11. Boolean evaluation for control can be added to our code generators as a set of peephole optimizations, one for each boolean-valued operation. F 12. It takes at least 8 PowerPC instructions to copy the condition code register into a general register. 13. How many tokens occur in the quirk13 expression while not f() do g() ____ A. 4 ____ B. 6 _XX_ C. 9 ____ D. 12 ____ E. 20 14. Although tokens could be recognized by the context-free parser, a lexical analyzer (scanner) is normally used because ____ A. add instructions cannot use the link register as an operand. _XX_ B. finite state automata are simpler (hence faster) than pushdown automata. ____ C. LALR(1) parsers are simpler than LL(1) parsers. ____ D. strongly left-circular attribute grammars dominate superscalar processor architectures. ____ E. wool insulates better than hydroquinone. 15. Which of the following is an LL(1) grammar equivalent to W --> a | b | W [ W ] | W , W & ____ A. W --> a | b | X X --> a [ W ] | b , W & ____ B. W --> W X X --> a | b | [ W ] | , W & ____ C. W --> a | b | W X X --> [ W ] | , W & ____ D. W --> a X | b X X --> [ W ] X | , W & X _XX_ E. W --> a X | b X X --> | [ W ] X | , W & X Questions 16 and 17 refer to the following grammar: E --> A | A ¤ E | A & A A --> B | B @ A B --> C | B # C | C Æ C C --> D | D % D | D ! D D --> x | ( E ) Figure 1. 16. [14 pts] For each of the seven binary operators used in Figure 1, indicate whether the operator associates to the left, to the right, or not at all: operator association ¤ right & not at all @ right # left Æ not at all % not at all ! not at all 17. According to Figure 1, which of the following expressions should have the same abstract syntax tree as x Æ x @ x ¤ x ? _XX_ A. ( ( x Æ x ) @ x ) ¤ x ____ B. ( x Æ ( x @ x ) ) ¤ x ____ C. ( x Æ x ) @ ( x ¤ x ) ____ D. x Æ ( ( x @ x ) ¤ x ) ____ E. x Æ ( x @ ( x ¤ x ) ) 18. Which of the following operations is parametrically polymorphic but not overloaded in quirk13? ____ A. not ____ B. > _XX_ C. # ____ D. < ____ E. = 19. Which of the following operations is overloaded but not parametrically polymorphic in quirk13? ____ A. @ _XX_ B. + ____ C. & ____ D. := ____ E. . 20. All of the following expressions are syntactically correct in quirk13, but only one will be accepted by the type checker. Which one is type-correct? _XX_ A. if 3 < 4.5 then 99.9 else "one hundred" ____ B. while not 7 do 8 ____ C. { int x = new 0; x := x + 1 } ____ D. (function () -> void { nothing }) (nothing) ____ E. { ref int x = 0; x := x + 1 } 21. Which of the following is a legal declaration in quirk13? _XX_ A. void f () { 24 } ____ B. forall (a) proc () -> a f = function () -> int { 24 } ____ C. float f () { 24 } ____ D. int f () { 24.0 } ____ E. forall (a) a f () { 24 } 22. In the quirk13 expression function (int x, int y) -> int { if g (x) then y else h (i (x), j (y)) } which procedure calls occur in tail-recursive position? ____ A. the calls to g and h ____ B. the call to g _XX_ C. the call to h ____ D. the calls to g, h, i, and j ____ E. the calls to h, i, and j 23. Suppose env is a compile-time environment for code generation in full quirk13, as in the first set of class notes. What is the lexical address of x in env[x:97][+][+] ? ____ A. <0, 99> ____ B. 97 ____ C. <1, 97> _XX_ D. <2, 97> ____ E. 99 24. According to the second set of class notes, the code generated for an assignment operation in quirk13c (the C-like subset) is stw ARG[k+1],0(ARG[k]) or ARG[k],ARG[k+1],ARG[k+1] // second instruction where k = E.reg. Under some circumstances, the compiler could omit the second instruction without changing the behavior of a program. For which one of the following expressions is it safe to omit the second instruction for the assignment operation? ____ A. x := y := z ____ B. (x := y) + (z := w) ____ C. A[x := y] ____ D. f(x := y) _XX_ E. { x := y; z } 25. According to the first set of class notes, the code that is generated for a non-tail-recursive occurrence of "new E1" in full quirk13 has the form [E1.code] bl L_quirk13_alloc_pair stw ARG[k],0-PTAG(r31) or ARG[k],r31,r31 addi r0,r0,0 stw r0,4-PTAG(ARG[k]) // second store instruction What would happen if the second store instruction were omitted? ____ A. The parser would have to insert an old expression to balance the new. _XX_ B. The garbage collector might crash after becoming confused by the uninitialized second field of the newly allocated pair. ____ C. The Load/Store Unit (LSU) might become bored and move to a nearby state. ____ D. The Translation Lookaside Buffer (TLB) would run out of Gallium Arsenide (GAs) and stall. ____ E. Cache hits would become louder. 26. PowerPC general register r2 (RTOC) is normally used ____ A. to hold the result of the most recent comparison ____ B. to point to the current stack frame ____ C. to hold the cache used for branch prediction ____ D. to hold the return address _XX_ E. to address global variables and constants 27. The PowerPC 604 is capable of initiating up to 4 instructions in a single clock cycle. This means the PowerPC 604 ____ A. uses register windows. ____ B. is a bit-sliced processor. _XX_ C. is a superscalar processor. ____ D. uses a 16-stage pipeline to decode instructions. ____ E. employs a 4-way set associative write-through cache. 28. [8 points] Suppose a compiler for quirk13c (the C-like subset) uses the representations for integers that are assumed by the second set of class notes (and most C compilers for the PowerPC actually use). 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 quirk13c compiler might generate for the following code, assuming the target register is r6 and the tail attribute is false. (Hint: It will take at least four instructions.) i - (2 * (j + k + 1)) add r6,r4,r5 addi r6,r6,1 add r6,r6,r6 // 2 * x = x + x subf r6,r6,r3