diff -r 4b208d81e002 -r c0bdd4ad69ca coursework/cw04.tex --- a/coursework/cw04.tex Tue Sep 01 15:57:55 2020 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,421 +0,0 @@ -% !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} - -\noindent This coursework is worth 10\% and is due on \cwFOUR{} -at 18:00. You are asked to implement a compiler for -the WHILE language that targets the assembler language -provided by Jasmin or Krakatau (both have very similar -syntax). 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 a mark of 0\% will -be awarded. You should use the lexer and parser from the -previous courseworks. Please package \emph{everything}(!) in -a zip-file that creates a directory with the name -\texttt{YournameYourFamilyname} on my end. - -\subsection*{Disclaimer\alert} - -It should be understood that the work you submit represents -your own effort. You have not copied from anyone else. An -exception is the Scala code I showed during the lectures, -which you can use. You can also use your own code from the -CW~1, CW~2 and CW~3. - - -\subsection*{Jasmin Assembler} - -The Jasmin 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 into 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} -\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 Jasmin -syntax---that means for the files we are concerned with here, -it understands the same input syntax (no changes to your -compiler need to be made; ok maybe some small syntactic -adjustments are needed). You can generate Java Byte Code by -using - -\begin{center} -\texttt{python Krakatau-master/assemble.py loops.j} -\end{center} - -\noindent where you may have to adapt the directory where -Krakatau is installed (I just downloaded the zip file from -Github and \pcode{Krakatau-master} was the directory where it -was 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 generate -Java Byte Code instructions for the Jasmin assembler (or -Krakatau 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 -be calculated. The Fibonacci program is given in -Figure~\ref{fibs}. You can write your own program for -calculating factorials. Submit your assembler code as -a file that can be run, not as PDF-text. - -\begin{figure}[t] -\lstinputlisting[language=while]{../progs/while-tests/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, test -whether this value is less or equal than the value of the -second arithmetic expression. If yes, go through the loop, and -at the end increase the value of the loop variable by 1 and -start again with the test. If no, leave the loop. For example -the following instance of a \code{for}-loop is supposed to -print 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: one -is to adapt the code generation part of the compiler and -generate specific code for \code{for}-loops; the other is to -translate the abstract syntax tree of \code{for}-loops into -an abstract syntax tree using existing language constructs. -For example the loop above could be translated to the -following \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 the -assembler 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 used -twice. You need to make a decision how it should be compiled? -Explain your 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 or Krakatau---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}{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} - -\noindent -You 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 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}{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 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 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, you -can 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 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 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} 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}{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 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,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: