\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 kind of 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 What are the two main features of code in

  static single assignment form (SSA)?

  \solution{

    Variables are only assigned once and all operations are

    primitive (in the sense of simple arithmetic operations,

    function calls and so on).

  }

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