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}
|
208
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
5 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
6 |
\begin{document}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
7 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
8 |
\section*{Homework 9}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
9 |
|
359
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
10 |
\HEADER
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
11 |
|
208
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
12 |
\begin{enumerate}
|
292
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
13 |
\item Describe what is meant by \emph{eliminating tail
|
459
|
14 |
recursion}? When can this optimization be applied and
|
|
15 |
why is it of benefit?
|
|
16 |
|
|
17 |
\item A programming language has arithmetic expression. For an
|
|
18 |
arithmetic expression the compiler of this language produces the
|
|
19 |
following snippet of JVM code.
|
|
20 |
|
|
21 |
\begin{lstlisting}[language=JVMIS,numbers=none]
|
|
22 |
ldc 1
|
|
23 |
ldc 2
|
|
24 |
ldc 3
|
|
25 |
imul
|
|
26 |
ldc 4
|
|
27 |
ldc 3
|
|
28 |
isub
|
|
29 |
iadd
|
|
30 |
iadd
|
|
31 |
\end{lstlisting}
|
|
32 |
|
|
33 |
Give the arithmetic expression that produced this code. Make sure
|
|
34 |
you give all necessary parentheses.
|
|
35 |
|
647
|
36 |
\item Describe what the following JVM instructions do!
|
459
|
37 |
|
647
|
38 |
|
|
39 |
\begin{lstlisting}[language=JVMIS2,numbers=none]
|
|
40 |
ldc 3
|
459
|
41 |
iload 3
|
|
42 |
istore 1
|
525
|
43 |
ifeq label
|
647
|
44 |
if_icmpge label
|
459
|
45 |
\end{lstlisting}
|
|
46 |
|
577
|
47 |
|
703
|
48 |
\item What does the following LLVM function calculate? Give the
|
|
49 |
corresponding arithmetic expression .
|
648
|
50 |
|
|
51 |
\begin{lstlisting}[language=LLVM,numbers=none]
|
|
52 |
define i32 @foo(i32 %a, i32 %b) {
|
|
53 |
%1 = mul i32 %a, %a
|
|
54 |
%2 = mul i32 %a, 2
|
|
55 |
%3 = mul i32 %2, %b
|
|
56 |
%4 = add i32 %1, %3
|
|
57 |
%5 = mul i32 %b, %b
|
|
58 |
%6 = add i32 %5, %4
|
|
59 |
ret i32 %6
|
|
60 |
}
|
|
61 |
\end{lstlisting}
|
|
62 |
|
705
|
63 |
\item What is the difference between a parse tree and an abstract
|
|
64 |
syntax tree? Give some simple examples for each of them.
|
648
|
65 |
|
|
66 |
|
805
|
67 |
\item Give a description of how the Brzozowski matcher works.
|
|
68 |
The description should be coherent and logical.
|
577
|
69 |
|
805
|
70 |
\item Give a description of how a compiler for the While-language can
|
|
71 |
be implemented. You should assume you are producing code for the JVM.
|
|
72 |
The description should be coherent and logical.
|
|
73 |
|
|
74 |
|
459
|
75 |
\item \POSTSCRIPT
|
208
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
76 |
|
314
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
77 |
% \item It is true (I confirmed it) that
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
78 |
%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
79 |
% \begin{center} if $\varnothing$ does not occur in $r$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
80 |
% \;\;then\;\;$L(r) \not= \{\}$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
81 |
% \end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
82 |
%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
83 |
% \noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
84 |
% holds, or equivalently
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
85 |
%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
86 |
% \begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
87 |
% $L(r) = \{\}$ \;\;implies\;\; $\varnothing$ occurs in $r$.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
88 |
% \end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
89 |
%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
90 |
% \noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
91 |
% 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
|
92 |
% 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
|
93 |
% the following function:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
94 |
%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
95 |
% \begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
96 |
% \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
97 |
% $occurs(\varnothing)$ & $\dn$ & $true$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
98 |
% $occurs(\epsilon)$ & $\dn$ & $f\!alse$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
99 |
% $occurs (c)$ & $\dn$ & $f\!alse$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
100 |
% $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
|
101 |
% $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
|
102 |
% $occurs (r^*)$ & $\dn$ & $occurs(r)$ \\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
103 |
% \end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
104 |
% \end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
105 |
%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
106 |
% \noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
107 |
% Now you can prove
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
108 |
%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
109 |
% \begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
110 |
% $L(r) = \{\}$ \;\;implies\;\; $occurs(r)$.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
111 |
% \end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
112 |
%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
113 |
% \noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
114 |
% The interesting cases are $r_1 + r_2$ and $r^*$.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
115 |
% 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
|
116 |
% 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
|
117 |
% 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
|
118 |
% also leads to an incorrect statement. Suppose we add the clause
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
119 |
%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
120 |
% \begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
121 |
% \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
122 |
% $occurs(\sim r)$ & $\dn$ & $occurs(r)$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
123 |
% \end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
124 |
% \end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
125 |
%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
126 |
% \noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
127 |
% to the definition above, then it will not be true that
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
128 |
%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
129 |
% \begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
130 |
% $L(r) = \{\}$ \;\;implies\;\; $occurs(r)$.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
131 |
% \end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
132 |
%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
133 |
% \noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
134 |
% 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
|
135 |
% property.
|
208
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
136 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
137 |
\end{enumerate}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
138 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
139 |
\end{document}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
140 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
141 |
%%% Local Variables:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
142 |
%%% mode: latex
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
143 |
%%% TeX-master: t
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
144 |
%%% End:
|