208
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
1 |
\documentclass{article}
|
292
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
2 |
\usepackage{../style}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
3 |
\usepackage{../graphics}
|
459
|
4 |
\usepackage{../langs}
|
906
|
5 |
\usepackage{../grammar}
|
208
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
6 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
7 |
\begin{document}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
8 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
9 |
\section*{Homework 9}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
10 |
|
359
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
11 |
\HEADER
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
12 |
|
208
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
13 |
\begin{enumerate}
|
292
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
14 |
\item Describe what is meant by \emph{eliminating tail
|
459
|
15 |
recursion}? When can this optimization be applied and
|
|
16 |
why is it of benefit?
|
|
17 |
|
|
18 |
\item A programming language has arithmetic expression. For an
|
|
19 |
arithmetic expression the compiler of this language produces the
|
|
20 |
following snippet of JVM code.
|
|
21 |
|
|
22 |
\begin{lstlisting}[language=JVMIS,numbers=none]
|
|
23 |
ldc 1
|
|
24 |
ldc 2
|
|
25 |
ldc 3
|
|
26 |
imul
|
|
27 |
ldc 4
|
|
28 |
ldc 3
|
|
29 |
isub
|
|
30 |
iadd
|
|
31 |
iadd
|
|
32 |
\end{lstlisting}
|
|
33 |
|
|
34 |
Give the arithmetic expression that produced this code. Make sure
|
|
35 |
you give all necessary parentheses.
|
|
36 |
|
647
|
37 |
\item Describe what the following JVM instructions do!
|
459
|
38 |
|
647
|
39 |
|
|
40 |
\begin{lstlisting}[language=JVMIS2,numbers=none]
|
|
41 |
ldc 3
|
459
|
42 |
iload 3
|
|
43 |
istore 1
|
525
|
44 |
ifeq label
|
647
|
45 |
if_icmpge label
|
459
|
46 |
\end{lstlisting}
|
|
47 |
|
901
|
48 |
\item What does the following JVM function calculate?
|
|
49 |
|
|
50 |
\begin{lstlisting}[language=JVMIS2,numbers=none]
|
|
51 |
.method public static bar(I)I
|
|
52 |
.limit locals 1
|
|
53 |
.limit stack 9
|
|
54 |
iload 0
|
|
55 |
ldc 0
|
|
56 |
if_icmpne If_else_8
|
|
57 |
ldc 0
|
|
58 |
goto If_end_9
|
|
59 |
If_else_8:
|
|
60 |
iload 0
|
|
61 |
ldc 1
|
|
62 |
if_icmpne If_else_10
|
|
63 |
ldc 1
|
|
64 |
goto If_end_11
|
|
65 |
If_else_10:
|
|
66 |
iload 0
|
|
67 |
ldc 1
|
|
68 |
isub
|
|
69 |
invokestatic bar(I)I
|
|
70 |
iload 0
|
|
71 |
ldc 2
|
|
72 |
isub
|
|
73 |
invokestatic bar(I)I
|
|
74 |
iadd
|
|
75 |
If_end_11:
|
|
76 |
If_end_9:
|
|
77 |
ireturn
|
|
78 |
.end method
|
|
79 |
\end{lstlisting}
|
577
|
80 |
|
703
|
81 |
\item What does the following LLVM function calculate? Give the
|
|
82 |
corresponding arithmetic expression .
|
648
|
83 |
|
|
84 |
\begin{lstlisting}[language=LLVM,numbers=none]
|
|
85 |
define i32 @foo(i32 %a, i32 %b) {
|
|
86 |
%1 = mul i32 %a, %a
|
|
87 |
%2 = mul i32 %a, 2
|
|
88 |
%3 = mul i32 %2, %b
|
|
89 |
%4 = add i32 %1, %3
|
|
90 |
%5 = mul i32 %b, %b
|
|
91 |
%6 = add i32 %5, %4
|
|
92 |
ret i32 %6
|
|
93 |
}
|
|
94 |
\end{lstlisting}
|
|
95 |
|
906
|
96 |
\item As an optimisation technique, a compiler might want to detect `dead code' and
|
|
97 |
not generate anything for this code. Why does this optimisation technique have the
|
|
98 |
potential of speeding up the run-time of a program? (Hint: On what CPUs are programs
|
|
99 |
run nowadays?)
|
|
100 |
|
|
101 |
\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
|
|
103 |
might wonder if a lexer can also be implemented by a parser and some simple
|
|
104 |
grammar rules. Consider for example:
|
|
105 |
|
|
106 |
\begin{plstx}[margin=1cm]
|
|
107 |
: \meta{S\/} ::= (\meta{Kw\/}\mid \meta{Id\/}\mid \meta{Ws\/}) \cdot \meta{S\/} \;\mid\; \epsilon\\
|
|
108 |
: \meta{Kw\/} ::= \texttt{if} \mid \texttt{then} \mid \ldots\\
|
|
109 |
: \meta{Id\/} ::= (\texttt{a} \mid\ldots\mid \texttt{z}) \cdot \meta{Id\/} \;\mid\; \epsilon\\
|
|
110 |
: \meta{Ws\/} ::= \ldots\\
|
|
111 |
\end{plstx}
|
|
112 |
|
|
113 |
What is wrong with implementing a lexer in this way?
|
|
114 |
|
705
|
115 |
\item What is the difference between a parse tree and an abstract
|
|
116 |
syntax tree? Give some simple examples for each of them.
|
648
|
117 |
|
|
118 |
|
805
|
119 |
\item Give a description of how the Brzozowski matcher works.
|
|
120 |
The description should be coherent and logical.
|
577
|
121 |
|
805
|
122 |
\item Give a description of how a compiler for the While-language can
|
|
123 |
be implemented. You should assume you are producing code for the JVM.
|
|
124 |
The description should be coherent and logical.
|
|
125 |
|
|
126 |
|
459
|
127 |
\item \POSTSCRIPT
|
208
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
128 |
|
314
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
129 |
% \item It is true (I confirmed it) that
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
130 |
%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
131 |
% \begin{center} if $\varnothing$ does not occur in $r$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
132 |
% \;\;then\;\;$L(r) \not= \{\}$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
133 |
% \end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
134 |
%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
135 |
% \noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
136 |
% holds, or equivalently
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
137 |
%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
138 |
% \begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
139 |
% $L(r) = \{\}$ \;\;implies\;\; $\varnothing$ occurs in $r$.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
140 |
% \end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
141 |
%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
142 |
% \noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
143 |
% You can prove either version by induction on $r$. The best way to
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
144 |
% make more formal what is meant by `$\varnothing$ occurs in $r$', you can define
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
145 |
% the following function:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
146 |
%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
147 |
% \begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
148 |
% \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
149 |
% $occurs(\varnothing)$ & $\dn$ & $true$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
150 |
% $occurs(\epsilon)$ & $\dn$ & $f\!alse$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
151 |
% $occurs (c)$ & $\dn$ & $f\!alse$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
152 |
% $occurs (r_1 + r_2)$ & $\dn$ & $occurs(r_1) \vee occurs(r_2)$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
153 |
% $occurs (r_1 \cdot r_2)$ & $\dn$ & $occurs(r_1) \vee occurs(r_2)$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
154 |
% $occurs (r^*)$ & $\dn$ & $occurs(r)$ \\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
155 |
% \end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
156 |
% \end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
157 |
%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
158 |
% \noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
159 |
% Now you can prove
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
160 |
%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
161 |
% \begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
162 |
% $L(r) = \{\}$ \;\;implies\;\; $occurs(r)$.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
163 |
% \end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
164 |
%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
165 |
% \noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
166 |
% The interesting cases are $r_1 + r_2$ and $r^*$.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
167 |
% The other direction is not true, that is if $occurs(r)$ then $L(r) = \{\}$. A counter example
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
168 |
% is $\varnothing + a$: although $\varnothing$ occurs in this regular expression, the corresponding
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
169 |
% language is not empty. The obvious extension to include the not-regular expression, $\sim r$,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
170 |
% also leads to an incorrect statement. Suppose we add the clause
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
171 |
%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
172 |
% \begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
173 |
% \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
174 |
% $occurs(\sim r)$ & $\dn$ & $occurs(r)$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
175 |
% \end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
176 |
% \end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
177 |
%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
178 |
% \noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
179 |
% to the definition above, then it will not be true that
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
180 |
%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
181 |
% \begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
182 |
% $L(r) = \{\}$ \;\;implies\;\; $occurs(r)$.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
183 |
% \end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
184 |
%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
185 |
% \noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
186 |
% Assume the alphabet contains just $a$ and $b$, find a counter example to this
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
187 |
% property.
|
208
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
188 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
189 |
\end{enumerate}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
190 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
191 |
\end{document}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
192 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
193 |
%%% Local Variables:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
194 |
%%% mode: latex
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
195 |
%%% TeX-master: t
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
196 |
%%% End:
|