--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/coursework/cw4.tex Fri Nov 07 13:54:50 2014 +0000
@@ -0,0 +1,322 @@
+\documentclass{article}
+\usepackage{hyperref}
+\usepackage{amssymb}
+\usepackage{amsmath}
+\usepackage{../langs}
+
+\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}%
+\begin{document}
+
+\section*{Coursework 3}
+
+\noindent
+This coursework is worth 5\% and is due on 28 November at 16:00. You are asked to
+implement a compiler for the WHILE language that targets the
+assembler language provided by Jasmin. This assembler
+is available from
+
+\begin{center}
+\url{http://jasmin.sourceforge.net}
+\end{center}
+
+\noindent
+There is a user guide for Jasmin
+
+\begin{center}
+\url{http://jasmin.sourceforge.net/guide.html}
+\end{center}
+
+\noindent
+and also a description of some of the instructions that the JVM understands
+
+\begin{center}
+\url{http://jasmin.sourceforge.net/instructions.html}
+\end{center}
+
+\noindent
+If you generated a correct assembler file for Jasmin, for example
+\texttt{loops.j}, you can use
+
+\begin{center}
+\texttt{java -jar jasmin-2.4/jasmin.jar loops.j}
+\end{center}
+
+\noindent
+in order to translate it to Java byte code. The resulting class file can be
+run with
+
+\begin{center}
+\texttt{java loops}
+\end{center}
+
+\noindent
+where you might need to give the correct path to the class file. There
+are also other resources about Jasmin on the Internet, for example
+\mbox{\url{http://goo.gl/Qj8TeK}} and \mbox{\url{http://goo.gl/fpVNyT}}\;.\bigskip
+
+\noindent
+You need to submit a document containing the answers for the two questions
+below. You can do the implementation in any programming language you like, but you need
+to submit the source code with which you answered the questions. Otherwise
+the submission will not be counted. However, the coursework
+will \emph{only} be judged according to the answers. You can submit your answers
+in a txt-file or as pdf.\bigskip
+
+
+\subsection*{Question 1 (marked with 2\%)}
+
+You need to lex and parse WHILE programs and submit the assembler
+instructions for the Fibonacci program and for the program you submitted
+in Coursework 2 in Question 3. The latter should be so modified that
+a user can input the upper bound on the console (in the original question
+it was fixed to 100).
+
+\subsection*{Question 2 (marked with 2\%)}
+
+Extend the syntax of you language so that it contains also \texttt{for}-loops, like
+
+\begin{center}
+\texttt{for} \;\textit{Id} \texttt{:=} \textit{AExp}\; \texttt{upto} \;\textit{AExp}\; \texttt{do} \textit{Block}
+\end{center}
+
+\noindent
+The intended meaning is to first assign the variable \textit{Id} the value of the first arithmetic
+expression, then go through the loop, at the end increase the value of the variable by 1,
+and finally test wether the value is not less or equal to the value of the second
+arithmetic expression. For example the following instance of a \texttt{for}-loop
+is supposed to print out the numbers \texttt{2}, \texttt{3}, \texttt{4}.
+
+
+\begin{center}
+\begin{minipage}{6cm}
+\begin{lstlisting}[language=While,basicstyle=\ttfamily, numbers=none]
+for i := 2 upto 4 do {
+ write i
+}
+\end{lstlisting}
+\end{minipage}
+\end{center}
+
+\noindent
+There are two ways how this can be implemented: one is to adapt the code generation
+part of the compiler and generate specific code for \texttt{for}-loops; the other is to
+translate the abstract syntax tree of \texttt{for}-loops into an abstract syntax tree using
+existing language constructs. For example the loop above could be translated
+to the following \texttt{while}-loop:
+
+\begin{center}
+\begin{minipage}{6cm}
+\begin{lstlisting}[language=While,basicstyle=\ttfamily, numbers=none]
+i := 2;
+while (i <= 4) do {
+ write i;
+ i := i + 1;
+}
+\end{lstlisting}
+\end{minipage}
+\end{center}
+
+\noindent
+In this question you are supposed to give the assembler instructions for the
+program
+
+\begin{center}
+\begin{minipage}{6cm}
+\begin{lstlisting}[language=While,basicstyle=\ttfamily, numbers=none]
+for i := 1 upto 10000 do {
+ for i := 1 upto 10000 do {
+ skip
+ }
+}
+\end{lstlisting}
+\end{minipage}
+\end{center}
+
+
+
+\subsection*{Further Information}
+
+The Java infrastructure unfortunately does not contain an assembler out-of-the-box
+(therefore
+you need to download the additional package Jasmin---see above). But it does contain a
+disassembler, called \texttt{javap}. A dissembler does the ``opposite'' of an assembler: it
+generates readable assembler code from Java byte code. Have a look at the
+following example: Compile using the usual Java compiler the simple Hello World
+program below:
+
+\begin{center}
+\begin{minipage}{10cm}
+\begin{lstlisting}[language=Java,basicstyle=\ttfamily]
+class HelloWorld {
+ public static void main(String[] args) {
+ System.out.println("Hello World!");
+ }
+}
+\end{lstlisting}
+\end{minipage}
+\end{center}
+
+\noindent
+You can use the command
+
+\begin{center}
+\texttt{javap -v HelloWorld}
+\end{center}
+
+\noindent
+to see the assembler instructions of the Java byte code that has been generated for this
+program. You can compare this with the code generated for the Scala
+version of Hello World.
+
+\begin{center}
+\begin{minipage}{10cm}
+\begin{lstlisting}[language=Scala,basicstyle=\ttfamily]
+object HelloWorld {
+ def main(args: Array[String]) {
+ println("Hello World!")
+ }
+}
+\end{lstlisting}
+\end{minipage}
+\end{center}
+
+
+\subsection*{Library Functions}
+
+You need to generate code for the commands \texttt{write} and \texttt{read}. This
+will require the addition of some ``library'' functions to your generated code. The first
+command even needs two versions, because you might want to write out an
+integer or a string. The Java byte code will need two separate functions for this.
+For writing out an integer, you can use the assembler code
+
+\begin{center}
+\begin{minipage}{12cm}
+\begin{lstlisting}[basicstyle=\ttfamily, numbers=none]
+.method public static write(I)V
+ .limit locals 5
+ .limit stack 5
+ iload 0
+ getstatic java/lang/System/out Ljava/io/PrintStream;
+ swap
+ invokevirtual java/io/PrintStream/println(I)V
+ return
+.end method
+\end{lstlisting}
+\end{minipage}
+\end{center}
+
+\noindent
+This function will invoke Java's \texttt{println} function for integers. Then if you need
+to generate code for \texttt{write x} where \texttt{x} is an integer variable, you can generate
+
+\begin{center}
+\begin{minipage}{8cm}
+\begin{lstlisting}[basicstyle=\ttfamily, numbers=none]
+iload n
+invokestatic XXX/XXX/write(I)V
+\end{lstlisting}
+\end{minipage}
+\end{center}
+
+\noindent
+where \texttt{n} is the index where the value of the variable \texttt{x} is
+stored. The \texttt{XXX/XXX} needs to be replaced with the class name
+which you use to generate the code (for example \texttt{fib/fib} in case
+of the Fibonacci numbers).
+
+Writing out a string is similar. The corresponding library function uses strings
+instead of integers:
+
+\begin{center}
+\begin{minipage}{12cm}
+\begin{lstlisting}[basicstyle=\ttfamily, numbers=none]
+.method public static writes(Ljava/lang/String;)V
+ .limit stack 2
+ .limit locals 2
+ getstatic java/lang/System/out Ljava/io/PrintStream;
+ aload 0
+ invokevirtual java/io/PrintStream/println(Ljava/lang/String;)V
+ return
+.end method
+\end{lstlisting}
+\end{minipage}
+\end{center}
+
+\noindent
+The code that needs to be generated for \texttt{write "some\_string"} commands
+is
+
+\begin{center}
+\begin{minipage}{8cm}
+\begin{lstlisting}[basicstyle=\ttfamily, numbers=none]
+ldc "some_string"
+invokestatic XXX/XXX/writes(Ljava/lang/String;)V
+\end{lstlisting}
+\end{minipage}
+\end{center}
+
+\noindent
+Again you need to adjust the \texttt{XXX/XXX} part in each call.
+
+The code for \texttt{read} is more complicated. The reason is that inputting a string
+will need to be transformed into an integer. The code in Figure~\ref{read} does this.
+It can be called with
+
+\begin{center}
+\begin{minipage}{8cm}
+\begin{lstlisting}[basicstyle=\ttfamily, numbers=none]
+invokestatic XXX/XXX/read()I
+istore n
+\end{lstlisting}
+\end{minipage}
+\end{center}
+
+\noindent
+where \texttt{n} is the index of the variable that requires an input.
+
+
+\begin{figure}[p]\small
+\begin{lstlisting}[basicstyle=\ttfamily, numbers=none]
+.method public static read()I
+ .limit locals 10
+ .limit stack 10
+
+ ldc 0
+ istore 1 ; this will hold our final integer
+Label1:
+ getstatic java/lang/System/in Ljava/io/InputStream;
+ invokevirtual java/io/InputStream/read()I
+ istore 2
+ iload 2
+ ldc 10 ; the newline delimiter
+ isub
+ ifeq Label2
+ iload 2
+ ldc 32 ; the space delimiter
+ isub
+ ifeq Label2
+
+ iload 2
+ ldc 48 ; we have our digit in ASCII, have to subtract it from 48
+ isub
+ ldc 10
+ iload 1
+ imul
+ iadd
+ istore 1
+ goto Label1
+Label2:
+ ;when we come here we have our integer computed in Local Variable 1
+ iload 1
+ ireturn
+.end method
+\end{lstlisting}\normalsize
+\caption{Assembler code for reading an integer from the console.\label{read}}
+\end{figure}
+
+\end{document}
+
+%%% Local Variables:
+%%% mode: latex
+%%% TeX-master: t
+%%% End: