\documentclass{article}+ −
\usepackage{../style}+ −
\usepackage{../langs}+ −
+ −
\begin{document}+ −
+ −
\section*{Coursework 4 (Strand 1)}+ −
+ −
\noindent This coursework is worth 10\% and is due on 12th+ −
December at 16:00. You are asked to implement a compiler for+ −
the WHILE language that targets the assembler language+ −
provided by Jasmin. This 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 to 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. There+ −
are also other resources about Jasmin on the Internet, for example+ −
\mbox{\url{http://goo.gl/Qj8TeK}} and \mbox{\url{http://goo.gl/fpVNyT}}\;.\bigskip+ −
+ −
\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 (marked with 2\%)}+ −
+ −
You need to lex and parse WHILE programs and submit the assembler + −
instructions for the Fibonacci program and for the program you submitted+ −
in Coursework 2 in Question 3. The latter should be so modified that + −
a user can input the upper bound on the console (in the original question+ −
it was fixed to 100).+ −
+ −
\subsection*{Question 2 (marked with 2\%)}+ −
+ −
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}+ −
+ −
\noindent+ −
The 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 second+ −
arithmetic 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}+ −
+ −
\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 \texttt{for}-loops; the other is to+ −
translate the abstract syntax tree of \texttt{for}-loops into an abstract syntax tree using+ −
existing language constructs. For example the loop above could be translated+ −
to 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}+ −
+ −
\noindent+ −
In this question you are supposed to give the assembler instructions for the+ −
program+ −
+ −
\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}+ −
+ −
+ −
+ −
\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---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}{10cm}+ −
\begin{lstlisting}[language=Java,basicstyle=\ttfamily]+ −
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}+ −
\texttt{javap -v HelloWorld}+ −
\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}{10cm}+ −
\begin{lstlisting}[language=Scala,basicstyle=\ttfamily]+ −
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 might want to write out an+ −
integer or a 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}[basicstyle=\ttfamily, 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 need+ −
to generate code for \texttt{write x} where \texttt{x} is an integer variable, you can generate+ −
+ −
\begin{center}+ −
\begin{minipage}{8cm}+ −
\begin{lstlisting}[basicstyle=\ttfamily, 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}[basicstyle=\ttfamily, 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}+ −
+ −
\noindent+ −
The code that needs to be generated for \texttt{write "some\_string"} commands + −
is+ −
+ −
\begin{center}+ −
\begin{minipage}{8cm}+ −
\begin{lstlisting}[basicstyle=\ttfamily, 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}{8cm}+ −
\begin{lstlisting}[basicstyle=\ttfamily, 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}[basicstyle=\ttfamily, 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: + −