equal
deleted
inserted
replaced
11 %\HEADER |
11 %\HEADER |
12 |
12 |
13 \begin{enumerate} |
13 \begin{enumerate} |
14 \item Describe what is meant by \emph{eliminating tail |
14 \item Describe what is meant by \emph{eliminating tail |
15 recursion}? When can this optimization be applied and |
15 recursion}? When can this optimization be applied and |
16 why is it of benefit? |
16 why is it of benefit? |
|
17 |
|
18 \solution{ Tail-call optimisation replaces a recursive call (in |
|
19 tail-call position) by a jump to the beginning of a function. |
|
20 In this way a recursion is replaced by a loop. This saves stack |
|
21 space because no new stack space needs to be allocated when a |
|
22 function is called recursively. |
|
23 |
|
24 Tail-call optimisation can be applied when the recursive call is |
|
25 the last instruction that is run in the function.} |
|
26 |
17 |
27 |
18 \item A programming language has arithmetic expression. For an |
28 \item A programming language has arithmetic expression. For an |
19 arithmetic expression the compiler of this language produces the |
29 arithmetic expression the compiler of this language produces the |
20 following snippet of JVM code. |
30 following snippet of JVM code. |
21 |
31 |
32 \end{lstlisting} |
42 \end{lstlisting} |
33 |
43 |
34 Give the arithmetic expression that produced this code. Make sure |
44 Give the arithmetic expression that produced this code. Make sure |
35 you give all necessary parentheses. |
45 you give all necessary parentheses. |
36 |
46 |
|
47 \solution{ |
|
48 $1 + ((2 * 3) + (4 - 3))$ |
|
49 } |
|
50 |
37 \item Describe what the following JVM instructions do! |
51 \item Describe what the following JVM instructions do! |
38 |
52 |
39 |
53 |
40 \begin{lstlisting}[language=JVMIS2,numbers=none] |
54 \begin{lstlisting}[language=JVMIS2,numbers=none] |
41 ldc 3 |
55 ldc 3 |
42 iload 3 |
56 iload 3 |
43 istore 1 |
57 istore 1 |
44 ifeq label |
58 ifeq label |
45 if_icmpge label |
59 if_icmpge label |
46 \end{lstlisting} |
60 \end{lstlisting} |
|
61 |
|
62 \solution{ |
|
63 (1) load the constant 3 onto the stack. (2) load the 4th local variable onto the stack. (3) store the top of the stack into the 2nd local variable (deleting the top element from the stack) (4) tests whether the top of the stack is equal to zero (if yes, then jump to label; delete top of the stack) (5) compares the top 2 elements of the stack whether they are greater or equal (if yes jump to label; delete two topmost elements from the stack) |
|
64 } |
|
65 |
47 |
66 |
48 \item What does the following JVM function calculate? |
67 \item What does the following JVM function calculate? |
49 |
68 |
50 \begin{lstlisting}[language=JVMIS2,numbers=none] |
69 \begin{lstlisting}[language=JVMIS2,numbers=none] |
51 .method public static bar(I)I |
70 .method public static bar(I)I |
75 If_end_11: |
94 If_end_11: |
76 If_end_9: |
95 If_end_9: |
77 ireturn |
96 ireturn |
78 .end method |
97 .end method |
79 \end{lstlisting} |
98 \end{lstlisting} |
|
99 |
|
100 \solution{ Fibonacci function..students should be able to read what the instructions do on the stack).} |
80 |
101 |
81 \item What does the following LLVM function calculate? Give the |
102 \item What does the following LLVM function calculate? Give the |
82 corresponding arithmetic expression . |
103 corresponding arithmetic expression . |
83 |
104 |
84 \begin{lstlisting}[language=LLVM,numbers=none] |
105 \begin{lstlisting}[language=LLVM,numbers=none] |
91 %6 = add i32 %5, %4 |
112 %6 = add i32 %5, %4 |
92 ret i32 %6 |
113 ret i32 %6 |
93 } |
114 } |
94 \end{lstlisting} |
115 \end{lstlisting} |
95 |
116 |
96 \item As an optimisation technique, a compiler might want to detect `dead code' and |
117 \solution{ $a^2+a*2*b + b^2$ |
97 not generate anything for this code. Why does this optimisation technique have the |
118 } |
98 potential of speeding up the run-time of a program? (Hint: On what kind of CPUs are programs |
119 |
99 run nowadays?) |
120 |
|
121 \item As an optimisation technique, a compiler might want to detect |
|
122 `dead code' and not generate anything for this code. Why does this |
|
123 optimisation technique have the potential of speeding up the |
|
124 run-time of a program? (Hint: On what kind of CPUs are programs run |
|
125 nowadays?) |
|
126 |
|
127 \solution{ Modern CPUs use predictive branching (guessing which |
|
128 code-branch is run) and use the cache extensively...any code that |
|
129 isn't in the program helps with guessing the right branch and does |
|
130 not occupy anything in the cache. So in effect the code will run |
|
131 faster. } |
|
132 |
100 |
133 |
101 \item In an earlier question, we analysed the advantages of having a lexer-phase |
134 \item In an earlier question, we analysed the advantages of having a lexer-phase |
102 before running the parser (having a lexer is definitely a good thing to have). But you |
135 before running the parser (having a lexer is definitely a good thing to have). But you |
103 might wonder if a lexer can also be implemented by a parser and some simple |
136 might wonder if a lexer can also be implemented by a parser and some simple |
104 grammar rules. Consider for example: |
137 grammar rules. Consider for example: |
110 : \meta{Ws\/} ::= \ldots\\ |
143 : \meta{Ws\/} ::= \ldots\\ |
111 \end{plstx} |
144 \end{plstx} |
112 |
145 |
113 What is wrong with implementing a lexer in this way? |
146 What is wrong with implementing a lexer in this way? |
114 |
147 |
|
148 \solution { There is no problem in terms of which strings are |
|
149 matched (the grammar can be defined such that it matches exactly |
|
150 the same strings. However, CFG do not obey the POSIX rules, |
|
151 meaning they cannot implement ``how regular expressions matc a |
|
152 string'' (for example longest match rule; rule priority). } |
|
153 |
|
154 |
115 \item What is the difference between a parse tree and an abstract |
155 \item What is the difference between a parse tree and an abstract |
116 syntax tree? Give some simple examples for each of them. |
156 syntax tree? Give some simple examples for each of them. |
|
157 |
|
158 \solution { Parse-trees follow the grammar rules, therefore the |
|
159 inner nodes correspond to the non-terminal symbols in CFGs. ASTs |
|
160 represent the tree-structure of the programs. } |
117 |
161 |
118 \item What are the two main features of code in |
162 \item What are the two main features of code in |
119 static single assignment form (SSA)? |
163 static single assignment form (SSA)? |
120 |
164 |
121 \solution{ |
165 \solution{ |