\documentclass{article}+ −
\usepackage{../style}+ −
\usepackage{../graphics}+ −
\usepackage{../langs}+ −
\usepackage{../grammar}+ −
+ −
\begin{document}+ −
+ −
\section*{Homework 9}+ −
+ −
\HEADER+ −
+ −
\begin{enumerate}+ −
\item Describe what is meant by \emph{eliminating tail+ −
recursion}? When can this optimization be applied and+ −
why is it of benefit?+ −
+ −
\item A programming language has arithmetic expression. For an+ −
arithmetic expression the compiler of this language produces the+ −
following snippet of JVM code.+ −
+ −
\begin{lstlisting}[language=JVMIS,numbers=none]+ −
ldc 1 + −
ldc 2 + −
ldc 3 + −
imul + −
ldc 4 + −
ldc 3 + −
isub + −
iadd + −
iadd+ −
\end{lstlisting}+ −
+ −
Give the arithmetic expression that produced this code. Make sure+ −
you give all necessary parentheses.+ −
+ −
\item Describe what the following JVM instructions do!+ −
+ −
+ −
\begin{lstlisting}[language=JVMIS2,numbers=none]+ −
ldc 3 + −
iload 3+ −
istore 1+ −
ifeq label+ −
if_icmpge label+ −
\end{lstlisting}+ −
+ −
\item What does the following JVM function calculate?+ −
+ −
\begin{lstlisting}[language=JVMIS2,numbers=none] + −
.method public static bar(I)I+ −
.limit locals 1+ −
.limit stack 9+ −
iload 0+ −
ldc 0+ −
if_icmpne If_else_8+ −
ldc 0+ −
goto If_end_9+ −
If_else_8:+ −
iload 0+ −
ldc 1+ −
if_icmpne If_else_10+ −
ldc 1+ −
goto If_end_11+ −
If_else_10:+ −
iload 0+ −
ldc 1+ −
isub+ −
invokestatic bar(I)I+ −
iload 0+ −
ldc 2+ −
isub+ −
invokestatic bar(I)I+ −
iadd+ −
If_end_11:+ −
If_end_9:+ −
ireturn+ −
.end method + −
\end{lstlisting}+ −
+ −
\item What does the following LLVM function calculate? Give the+ −
corresponding arithmetic expression .+ −
+ −
\begin{lstlisting}[language=LLVM,numbers=none] + −
define i32 @foo(i32 %a, i32 %b) {+ −
%1 = mul i32 %a, %a+ −
%2 = mul i32 %a, 2+ −
%3 = mul i32 %2, %b+ −
%4 = add i32 %1, %3+ −
%5 = mul i32 %b, %b+ −
%6 = add i32 %5, %4+ −
ret i32 %6+ −
}+ −
\end{lstlisting}+ −
+ −
\item As an optimisation technique, a compiler might want to detect `dead code' and+ −
not generate anything for this code. Why does this optimisation technique have the+ −
potential of speeding up the run-time of a program? (Hint: On what CPUs are programs+ −
run nowadays?)+ −
+ −
\item In an earlier question, we analysed the advantages of having a lexer-phase+ −
before running the parser (having a lexer is definitely a good thing to have). But you+ −
might wonder if a lexer can also be implemented by a parser and some simple+ −
grammar rules. Consider for example:+ −
+ −
\begin{plstx}[margin=1cm]+ −
: \meta{S\/} ::= (\meta{Kw\/}\mid \meta{Id\/}\mid \meta{Ws\/}) \cdot \meta{S\/} \;\mid\; \epsilon\\+ −
: \meta{Kw\/} ::= \texttt{if} \mid \texttt{then} \mid \ldots\\+ −
: \meta{Id\/} ::= (\texttt{a} \mid\ldots\mid \texttt{z}) \cdot \meta{Id\/} \;\mid\; \epsilon\\+ −
: \meta{Ws\/} ::= \ldots\\+ −
\end{plstx}+ −
+ −
What is wrong with implementing a lexer in this way?+ −
+ −
\item What is the difference between a parse tree and an abstract+ −
syntax tree? Give some simple examples for each of them.+ −
+ −
+ −
\item Give a description of how the Brzozowski matcher works. + −
The description should be coherent and logical.+ −
+ −
\item Give a description of how a compiler for the While-language can+ −
be implemented. You should assume you are producing code for the JVM.+ −
The description should be coherent and logical.+ −
+ −
+ −
\item \POSTSCRIPT + −
+ −
% \item It is true (I confirmed it) that+ −
% + −
% \begin{center} if $\varnothing$ does not occur in $r$+ −
% \;\;then\;\;$L(r) \not= \{\}$ + −
% \end{center}+ −
% + −
% \noindent+ −
% holds, or equivalently+ −
% + −
% \begin{center}+ −
% $L(r) = \{\}$ \;\;implies\;\; $\varnothing$ occurs in $r$.+ −
% \end{center}+ −
% + −
% \noindent+ −
% You can prove either version by induction on $r$. The best way to+ −
% make more formal what is meant by `$\varnothing$ occurs in $r$', you can define+ −
% the following function:+ −
% + −
% \begin{center}+ −
% \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}+ −
% $occurs(\varnothing)$ & $\dn$ & $true$\\+ −
% $occurs(\epsilon)$ & $\dn$ & $f\!alse$\\+ −
% $occurs (c)$ & $\dn$ & $f\!alse$\\+ −
% $occurs (r_1 + r_2)$ & $\dn$ & $occurs(r_1) \vee occurs(r_2)$\\ + −
% $occurs (r_1 \cdot r_2)$ & $\dn$ & $occurs(r_1) \vee occurs(r_2)$\\+ −
% $occurs (r^*)$ & $\dn$ & $occurs(r)$ \\+ −
% \end{tabular}+ −
% \end{center}+ −
% + −
% \noindent+ −
% Now you can prove + −
% + −
% \begin{center}+ −
% $L(r) = \{\}$ \;\;implies\;\; $occurs(r)$.+ −
% \end{center}+ −
% + −
% \noindent+ −
% The interesting cases are $r_1 + r_2$ and $r^*$.+ −
% The other direction is not true, that is if $occurs(r)$ then $L(r) = \{\}$. A counter example+ −
% is $\varnothing + a$: although $\varnothing$ occurs in this regular expression, the corresponding+ −
% language is not empty. The obvious extension to include the not-regular expression, $\sim r$,+ −
% also leads to an incorrect statement. Suppose we add the clause+ −
% + −
% \begin{center}+ −
% \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}+ −
% $occurs(\sim r)$ & $\dn$ & $occurs(r)$+ −
% \end{tabular}+ −
% \end{center} + −
% + −
% \noindent+ −
% to the definition above, then it will not be true that+ −
% + −
% \begin{center}+ −
% $L(r) = \{\}$ \;\;implies\;\; $occurs(r)$.+ −
% \end{center}+ −
% + −
% \noindent+ −
% Assume the alphabet contains just $a$ and $b$, find a counter example to this+ −
% property.+ −
+ −
\end{enumerate}+ −
+ −
\end{document}+ −
+ −
%%% Local Variables: + −
%%% mode: latex+ −
%%% TeX-master: t+ −
%%% End: + −