\documentclass{article}

\usepackage{../style}

\usepackage{../langs}

\begin{document}

\section*{Coursework 4 (Strand 1)}

\noindent This coursework is worth 10\% and is due on 11

December 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. 

For example:

\begin{center}

\texttt{java -cp . loops/loops}

\end{center}

\noindent 

There are also other resources about Jasmin on the Internet, for example

\begin{center}

\url{http://www.ceng.metu.edu.tr/courses/ceng444/link/f3jasmintutorial.html}

and

\url{http://www.csc.villanova.edu/~tway/courses/csc8505/s2011/handouts/JVM%20and%20Jasmin.pdf}

\end{center}

\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 5\%)}

You need to lex and parse WHILE programs, and then generate Java Byte

Code instructions for the Jasmin assembler. As solution you need to

submit the assembler instructions for the Fibonacci and Factorial

programs. Both should be so modified that a user can input on the

console which Fibonacci number and which Factorial should

calculated. The Fibonacci program is given in Figure~\ref{fibs}. You

can write your own program for calculating factorials.

\begin{figure}[t]

\lstinputlisting[language=while]{../progs/fib.while}

\caption{The Fibonacci program in the WHILE language.\label{fibs}}

\end{figure}

\subsection*{Question 2 (marked with 4\%)}

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}

\subsection*{Question 3 (marked with 1\%)}

\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 10 do {

  for i := 1 upto 10 do {

    write i

  }

} 

\end{lstlisting}

\end{minipage}

\end{center}

\noindent 

Note that in this program the variable \pcode{i} is used

twice. You need to make a decision how it should be compiled?

Explain you decision and indicate what this program would

print out.

\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,numbers=none]

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,numbers=none]

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 need to write out

an integer and 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}[language=JVMIS, 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}[language=JVMIS, 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}[language=JVMIS, 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 \code{write "some_string"} commands 

is

\begin{center}

\begin{minipage}{8cm}

\begin{lstlisting}[language=JVMIS,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}[language=JVMIS,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. If you

use Windows you need to take into account that a ``return'' is not just a newline,

\code{'\\10'}, but \code{'\\13\\10'}. This means you need to change line~12 in 

Figure~\ref{read} to \pcode{ldc 13}.  

\begin{figure}[t]\small

\begin{lstlisting}[language=JVMIS]

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