author | Christian Urban <christian.urban@kcl.ac.uk> |
Fri, 29 Nov 2024 18:59:32 +0000 | |
changeset 976 | e9eac62928f5 |
parent 958 | fddf099a82f8 |
permissions | -rw-r--r-- |
208
bd5a8a6b3871
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
1 |
\documentclass{article} |
292
7ed2a25dd115
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
208
diff
changeset
|
2 |
\usepackage{../style} |
7ed2a25dd115
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
208
diff
changeset
|
3 |
\usepackage{../graphics} |
459 | 4 |
\usepackage{../langs} |
906 | 5 |
\usepackage{../grammar} |
208
bd5a8a6b3871
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
6 |
|
bd5a8a6b3871
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
7 |
\begin{document} |
bd5a8a6b3871
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
8 |
|
bd5a8a6b3871
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
9 |
\section*{Homework 9} |
bd5a8a6b3871
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
10 |
|
916 | 11 |
%\HEADER |
359
db106e5b7c4d
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
314
diff
changeset
|
12 |
|
208
bd5a8a6b3871
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
13 |
\begin{enumerate} |
292
7ed2a25dd115
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
208
diff
changeset
|
14 |
\item Describe what is meant by \emph{eliminating tail |
459 | 15 |
recursion}? When can this optimization be applied and |
958 | 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 |
||
459 | 27 |
|
28 |
\item A programming language has arithmetic expression. For an |
|
29 |
arithmetic expression the compiler of this language produces the |
|
30 |
following snippet of JVM code. |
|
31 |
||
32 |
\begin{lstlisting}[language=JVMIS,numbers=none] |
|
33 |
ldc 1 |
|
34 |
ldc 2 |
|
35 |
ldc 3 |
|
36 |
imul |
|
37 |
ldc 4 |
|
38 |
ldc 3 |
|
39 |
isub |
|
40 |
iadd |
|
41 |
iadd |
|
42 |
\end{lstlisting} |
|
43 |
||
44 |
Give the arithmetic expression that produced this code. Make sure |
|
45 |
you give all necessary parentheses. |
|
46 |
||
958 | 47 |
\solution{ |
48 |
$1 + ((2 * 3) + (4 - 3))$ |
|
49 |
} |
|
50 |
||
647 | 51 |
\item Describe what the following JVM instructions do! |
459 | 52 |
|
647 | 53 |
|
54 |
\begin{lstlisting}[language=JVMIS2,numbers=none] |
|
55 |
ldc 3 |
|
459 | 56 |
iload 3 |
57 |
istore 1 |
|
525 | 58 |
ifeq label |
647 | 59 |
if_icmpge label |
459 | 60 |
\end{lstlisting} |
61 |
||
958 | 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 |
||
66 |
||
901 | 67 |
\item What does the following JVM function calculate? |
68 |
||
69 |
\begin{lstlisting}[language=JVMIS2,numbers=none] |
|
70 |
.method public static bar(I)I |
|
71 |
.limit locals 1 |
|
72 |
.limit stack 9 |
|
73 |
iload 0 |
|
74 |
ldc 0 |
|
75 |
if_icmpne If_else_8 |
|
76 |
ldc 0 |
|
77 |
goto If_end_9 |
|
78 |
If_else_8: |
|
79 |
iload 0 |
|
80 |
ldc 1 |
|
81 |
if_icmpne If_else_10 |
|
82 |
ldc 1 |
|
83 |
goto If_end_11 |
|
84 |
If_else_10: |
|
85 |
iload 0 |
|
86 |
ldc 1 |
|
87 |
isub |
|
88 |
invokestatic bar(I)I |
|
89 |
iload 0 |
|
90 |
ldc 2 |
|
91 |
isub |
|
92 |
invokestatic bar(I)I |
|
93 |
iadd |
|
94 |
If_end_11: |
|
95 |
If_end_9: |
|
96 |
ireturn |
|
97 |
.end method |
|
98 |
\end{lstlisting} |
|
577 | 99 |
|
958 | 100 |
\solution{ Fibonacci function..students should be able to read what the instructions do on the stack).} |
101 |
||
703 | 102 |
\item What does the following LLVM function calculate? Give the |
103 |
corresponding arithmetic expression . |
|
648 | 104 |
|
105 |
\begin{lstlisting}[language=LLVM,numbers=none] |
|
106 |
define i32 @foo(i32 %a, i32 %b) { |
|
107 |
%1 = mul i32 %a, %a |
|
108 |
%2 = mul i32 %a, 2 |
|
109 |
%3 = mul i32 %2, %b |
|
110 |
%4 = add i32 %1, %3 |
|
111 |
%5 = mul i32 %b, %b |
|
112 |
%6 = add i32 %5, %4 |
|
113 |
ret i32 %6 |
|
114 |
} |
|
115 |
\end{lstlisting} |
|
116 |
||
958 | 117 |
\solution{ $a^2+a*2*b + b^2$ |
118 |
} |
|
119 |
||
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 |
||
906 | 133 |
|
134 |
\item In an earlier question, we analysed the advantages of having a lexer-phase |
|
135 |
before running the parser (having a lexer is definitely a good thing to have). But you |
|
136 |
might wonder if a lexer can also be implemented by a parser and some simple |
|
137 |
grammar rules. Consider for example: |
|
138 |
||
139 |
\begin{plstx}[margin=1cm] |
|
140 |
: \meta{S\/} ::= (\meta{Kw\/}\mid \meta{Id\/}\mid \meta{Ws\/}) \cdot \meta{S\/} \;\mid\; \epsilon\\ |
|
141 |
: \meta{Kw\/} ::= \texttt{if} \mid \texttt{then} \mid \ldots\\ |
|
142 |
: \meta{Id\/} ::= (\texttt{a} \mid\ldots\mid \texttt{z}) \cdot \meta{Id\/} \;\mid\; \epsilon\\ |
|
143 |
: \meta{Ws\/} ::= \ldots\\ |
|
144 |
\end{plstx} |
|
145 |
||
146 |
What is wrong with implementing a lexer in this way? |
|
147 |
||
958 | 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 |
||
705 | 155 |
\item What is the difference between a parse tree and an abstract |
156 |
syntax tree? Give some simple examples for each of them. |
|
648 | 157 |
|
958 | 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. } |
|
161 |
||
941 | 162 |
\item What are the two main features of code in |
163 |
static single assignment form (SSA)? |
|
577 | 164 |
|
941 | 165 |
\solution{ |
166 |
Variables are only assigned once and all operations are |
|
167 |
primitive (in the sense of simple arithmetic operations, |
|
168 |
function calls and so on). |
|
169 |
} |
|
170 |
||
171 |
||
172 |
%\item Give a description of how the Brzozowski matcher works. |
|
173 |
% The description should be coherent and logical. |
|
174 |
||
175 |
%\item Give a description of how a compiler for the While-language can |
|
176 |
% be implemented. You should assume you are producing code for the JVM. |
|
177 |
% The description should be coherent and logical. |
|
805 | 178 |
|
179 |
||
459 | 180 |
\item \POSTSCRIPT |
208
bd5a8a6b3871
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
181 |
|
314
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
182 |
% \item It is true (I confirmed it) that |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
183 |
% |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
184 |
% \begin{center} if $\varnothing$ does not occur in $r$ |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
185 |
% \;\;then\;\;$L(r) \not= \{\}$ |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
186 |
% \end{center} |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
187 |
% |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
188 |
% \noindent |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
189 |
% holds, or equivalently |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
190 |
% |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
191 |
% \begin{center} |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
192 |
% $L(r) = \{\}$ \;\;implies\;\; $\varnothing$ occurs in $r$. |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
193 |
% \end{center} |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
194 |
% |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
195 |
% \noindent |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
196 |
% You can prove either version by induction on $r$. The best way to |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
197 |
% make more formal what is meant by `$\varnothing$ occurs in $r$', you can define |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
198 |
% the following function: |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
199 |
% |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
200 |
% \begin{center} |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
201 |
% \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
202 |
% $occurs(\varnothing)$ & $\dn$ & $true$\\ |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
203 |
% $occurs(\epsilon)$ & $\dn$ & $f\!alse$\\ |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
204 |
% $occurs (c)$ & $\dn$ & $f\!alse$\\ |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
205 |
% $occurs (r_1 + r_2)$ & $\dn$ & $occurs(r_1) \vee occurs(r_2)$\\ |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
206 |
% $occurs (r_1 \cdot r_2)$ & $\dn$ & $occurs(r_1) \vee occurs(r_2)$\\ |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
207 |
% $occurs (r^*)$ & $\dn$ & $occurs(r)$ \\ |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
208 |
% \end{tabular} |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
209 |
% \end{center} |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
210 |
% |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
211 |
% \noindent |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
212 |
% Now you can prove |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
213 |
% |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
214 |
% \begin{center} |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
215 |
% $L(r) = \{\}$ \;\;implies\;\; $occurs(r)$. |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
216 |
% \end{center} |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
217 |
% |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
218 |
% \noindent |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
219 |
% The interesting cases are $r_1 + r_2$ and $r^*$. |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
220 |
% The other direction is not true, that is if $occurs(r)$ then $L(r) = \{\}$. A counter example |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
221 |
% is $\varnothing + a$: although $\varnothing$ occurs in this regular expression, the corresponding |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
222 |
% language is not empty. The obvious extension to include the not-regular expression, $\sim r$, |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
223 |
% also leads to an incorrect statement. Suppose we add the clause |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
224 |
% |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
225 |
% \begin{center} |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
226 |
% \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
227 |
% $occurs(\sim r)$ & $\dn$ & $occurs(r)$ |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
228 |
% \end{tabular} |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
229 |
% \end{center} |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
230 |
% |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
231 |
% \noindent |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
232 |
% to the definition above, then it will not be true that |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
233 |
% |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
234 |
% \begin{center} |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
235 |
% $L(r) = \{\}$ \;\;implies\;\; $occurs(r)$. |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
236 |
% \end{center} |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
237 |
% |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
238 |
% \noindent |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
239 |
% Assume the alphabet contains just $a$ and $b$, find a counter example to this |
7dd5797a5ffa
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
292
diff
changeset
|
240 |
% property. |
208
bd5a8a6b3871
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
241 |
|
bd5a8a6b3871
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
242 |
\end{enumerate} |
bd5a8a6b3871
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
243 |
|
bd5a8a6b3871
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
244 |
\end{document} |
bd5a8a6b3871
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
245 |
|
bd5a8a6b3871
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
246 |
%%% Local Variables: |
bd5a8a6b3871
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
247 |
%%% mode: latex |
bd5a8a6b3871
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
248 |
%%% TeX-master: t |
bd5a8a6b3871
added
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
249 |
%%% End: |