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