\documentclass{article}
\usepackage{../style}
\usepackage{../graphics}
\usepackage{../langs}

\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 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 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: