\documentclass{article}\usepackage{../style}\usepackage{../langs}\begin{document}\section*{Coursework 4 (Strand 1)}\noindent This coursework is worth 10\% and is due on 12thDecember at 16:00. You are asked to implement a compiler forthe WHILE language that targets the assembler languageprovided by Jasmin. This assembler is available from\begin{center}\url{http://jasmin.sourceforge.net}\end{center}\noindentThere is a user guide for Jasmin\begin{center}\url{http://jasmin.sourceforge.net/guide.html}\end{center}\noindentand also a description of some of the instructions that the JVM understands\begin{center}\url{http://jasmin.sourceforge.net/instructions.html}\end{center}\noindentIf 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}\noindentin order to translate it to Java byte code. The resulting class file can berun with\begin{center}\texttt{java loops}\end{center}\noindentwhere you might need to give the correct path to the class file. Thereare 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}\noindentYou 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. Otherwisethe submission will not be counted. However, the coursework will \emph{only} be judged according to the answers. You can submit your answersin a txt-file or as pdf.\bigskip\subsection*{Question 1 (marked with 5\%)}You need to lex and parse WHILE programs, and then generateJava Byte Code instructions for the Jasmin assmebler. Assolution you need to submit the assembler instructions for theFibonacci and Factorial programs. Both should be so modifiedthat a user can input on the console which Fibonacci number and which Factorial should calculated. The Fibonacci programis given in Figure~\ref{fibs}.\begin{figure}[t]\lstinputlisting[language=while]{../progs/fib.while}\caption{The Fibonacci program in the WHILE language.}\end{figure}\subsection*{Question 2 (marked with 5\%)}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}\noindentThe 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 secondarithmetic 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}\noindentThere 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 totranslate the abstract syntax tree of \texttt{for}-loops into an abstract syntax tree usingexisting language constructs. For example the loop above could be translatedto 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}\noindentIn this question you are supposed to give the assembler instructions for theprogram\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}\noindent Note that in this program the variable \pcode{i} is usedtwice. You need to make a decision how it should be compiled?\subsection*{Further Information}The Java infrastructure unfortunately does not contain an assembler out-of-the-box(thereforeyou 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: itgenerates readable assembler code from Java byte code. Have a look at thefollowing 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}\noindentYou can use the command\begin{center}\texttt{javap -v HelloWorld}\end{center}\noindent to see the assembler instructions of the Java bytecode that has been generated for this program. You can comparethis with the code generated for the Scala version of HelloWorld.\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 firstcommand even needs two versions, because you need to write outan integer and string. The Java byte code will need twoseparate functions for this. For writing out an integer, youcan 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 needto 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}\noindentwhere \texttt{n} is the index where the value of the variable \texttt{x} isstored. 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 caseof 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}\noindentThe 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}\noindentAgain 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 stringwill 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.\begin{figure}[p]\small\begin{lstlisting}[language=JVMIS,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: