% !TEX program = xelatex\documentclass{article}\usepackage{../style}\usepackage{../langs}\begin{document}%https://github.com/Storyyeller/Krakatau%https://docs.oracle.com/javase/specs/jvms/se7/html/% Jasmin Tutorial%http://saksagan.ceng.metu.edu.tr/courses/ceng444/link/jvm-cpm.html\section*{Coursework 4 (Strand 1)}\noindent This coursework is worth 6\% and is due on \cwFOUR{}at 18:00. You are asked to implement a compiler forthe WHILE language that targets the assembler languageprovided by Jasmin or Krakatau (both have very similarsyntax). You can do the implementation in any programminglanguage you like, but you need to submit the source code withwhich you answered the questions, otherwise a mark of 0\% willbe awarded. You should use the lexer and parser from theprevious courseworks. Please package \emph{everything}(!) ina zip-file that creates a directory with the name\texttt{YournameYourFamilyname} on my end.\subsection*{Disclaimer}It should be understood that the work you submit representsyour own effort. You have not copied from anyone else. Anexception is the Scala code I showed during the lectures,which you can use. You can also use your own code from theCW~1, CW~2 and CW~3.\subsection*{Jasmin Assembler}The Jasmin 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}\noindent and also a description of some of the instructionsthat the JVM understands\begin{center}\url{http://jasmin.sourceforge.net/instructions.html}\end{center}\noindent If you generated a correct assembler file forJasmin, 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 into Java Byte Code. Theresulting class file can be run with\begin{center}\texttt{java loops}\end{center}\noindent where you might need to give the correct path to theclass file. For example:\begin{center}\texttt{java -cp . loops/loops}\end{center}\noindent There are also other resources about Jasmin on theInternet, for example\begin{center}\small\url{http://www.ceng.metu.edu.tr/courses/ceng444/link/f3jasmintutorial.html}\end{center}\noindent and\begin{center} \small\url{http://www.csc.villanova.edu/~tway/courses/csc4181/s2018/labs/lab4/JVM.pdf}\end{center}\subsection*{Krakatau Assembler}The Krakatau assembler is available from\begin{center}\url{https://github.com/Storyyeller/Krakatau}\end{center}\noindent This assembler requires Python and a package called\pcode{ply} available from\begin{center}\url{https://pypi.python.org/pypi/ply}\end{center}\noindent This assembler is largely compatible with the Jasminsyntax---that means for the files we are concerned with here,it understands the same input syntax (no changes to yourcompiler need to be made; ok maybe some small syntacticadjustments are needed). You can generate Java Byte Code byusing \begin{center}\texttt{python Krakatau-master/assemble.py loops.j}\end{center}\noindent where you may have to adapt the directory whereKrakatau is installed (I just downloaded the zip file fromGithub and \pcode{Krakatau-master} was the directory where itwas installed). Again the resulting class-file you can run with\texttt{java}.%\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}You need to lex and parse WHILE programs, and then generateJava Byte Code instructions for the Jasmin assembler (orKrakatau assembler). As solution you need to submit theassembler instructions for the Fibonacci and Factorialprograms. Both should be so modified that a user can input onthe console which Fibonacci number and which Factorial shouldbe calculated. The Fibonacci program is given inFigure~\ref{fibs}. You can write your own program forcalculating factorials. Submit your assembler code asa file that can be run, not as PDF-text.\begin{figure}[t]\lstinputlisting[language=while]{../progs/fib.while}\caption{The Fibonacci program in the WHILE language.\label{fibs}}\end{figure}\subsection*{Question 2}Extend the syntax of your language so that it contains also\texttt{for}-loops, like\begin{center}\lstset{language=While}\code{for} \;\textit{Id} \texttt{:=} \textit{AExp}\; \code{upto} \;\textit{AExp}\; \code{do} \textit{Block} \end{center}\noindent The intended meaning is to first assign the variable\textit{Id} the value of the first arithmetic expression, testwhether this value is less or equal than the value of thesecond arithmetic expression. If yes, go through the loop, andat the end increase the value of the loop variable by 1 andstart again with the test. If no, leave the loop. For examplethe following instance of a \code{for}-loop is supposed toprint out the numbers \pcode{2}, \pcode{3}, \pcode{4}.\begin{center}\begin{minipage}{12cm}\begin{lstlisting}[language=While, 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: oneis to adapt the code generation part of the compiler andgenerate specific code for \code{for}-loops; the other is totranslate the abstract syntax tree of \code{for}-loops intoan abstract syntax tree using existing language constructs.For example the loop above could be translated to thefollowing \code{while}-loop:\begin{center}\begin{minipage}{12cm}\begin{lstlisting}[language=While, numbers=none]i := 2;while (i <= 4) do { write i; i := i + 1;}\end{lstlisting}\end{minipage}\end{center}\subsection*{Question 3}\noindent In this question you are supposed to give theassembler instructions for the program\begin{center}\begin{minipage}{12cm}\begin{lstlisting}[language=While, 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 usedtwice. You need to make a decision how it should be compiled?Explain your decision and indicate what this program wouldprint out.\subsection*{Further Information}The Java infrastructure unfortunately does not contain anassembler out-of-the-box (therefore you need to download theadditional package Jasmin or Krakatau---see above). But itdoes contain a disassembler, called \texttt{javap}. Adissembler does the ``opposite'' of an assembler: it generatesreadable assembler code from Java Byte Code. Have a look atthe following example: Compile using the usual Java compilerthe simple Hello World program below:\begin{center}\begin{minipage}{12cm}\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}\begin{minipage}{12cm}\begin{lstlisting}[language={},numbers=none]javap -v HelloWorld\end{lstlisting}\end{minipage}\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}{12cm}\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 1 .limit stack 2 getstatic java/lang/System/out Ljava/io/PrintStream; iload 0 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, youcan generate\begin{center}\begin{minipage}{12cm}\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 thevariable \texttt{x} is stored. The \texttt{XXX/XXX} needs tobe replaced with the class name which you use to generate thecode (for example \texttt{fib/fib} in case of the Fibonaccinumbers).Writing out a string is similar. The corresponding libraryfunction 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 1 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}{12cm}\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} partin each call.The code for \texttt{read} is more complicated. The reason isthat inputting a string will need to be transformed into aninteger. The code in Figure~\ref{read} does this. It can becalled with\begin{center}\begin{minipage}{12cm}\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 youuse 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,numbers=left].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 for Unix (Windows 13) 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: