% !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 15\% and is due on \cwFOUR{}+ −
at 16:00. You are asked to implement a compiler for+ −
the WHILE language that targets the assembler language+ −
provided by Jasmin or Krakatau (both have a very similar+ −
syntax). Please submit your answers to the questions+ −
below as PDF. 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. But do not+ −
be tempted to ask Github Copilot for help or do any other+ −
shenanigans like this!+ −
+ −
+ −
\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. If needed, you+ −
need to give the path to the Jasmin jar-file. 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{https://saksagan.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/s2022/labs/finalproject/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 0 (Unmarked)}+ −
+ −
Please include in the PDF at the beginning your email address, your student+ −
number and whether you are BSc / MSci student and for the latter in which+ −
year your are in. Thanks! + −
+ −
\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]{../cwtests/cw04/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*{Question 4 (Advanced)}+ −
+ −
Extend the lexer and parser in order to add a \texttt{break} keyword.+ −
Modify the compiler such that when a \texttt{break} is encountered the+ −
code should jump out of the ``enclosing'' while loop, or in case it+ −
is not inside a while loop to the end of the+ −
program.+ −
+ −
\bigskip\noindent+ −
\textcolor{red}{ADD EXAMPLE PROGRAMS}+ −
+ −
\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: + −