--- a/coursework/cw04.tex Fri Nov 27 12:09:54 2015 +0000
+++ b/coursework/cw04.tex Mon Dec 07 01:35:42 2015 +0000
@@ -12,11 +12,12 @@
\noindent This coursework is worth 10\% and is due on 11
December at 16:00. You are asked to implement a compiler for
the WHILE language that targets the assembler language
-provided by Jasmin or Krakatau. 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.
+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.
\subsection*{Disclaimer}
@@ -27,7 +28,7 @@
CW~1, CW~2 and CW~3.
-\subsection*{Assemblers}
+\subsection*{Jasmin Assembler}
The Jasmin assembler is available from
@@ -42,66 +43,98 @@
\url{http://jasmin.sourceforge.net/guide.html}
\end{center}
-\noindent
-and also a description of some of the instructions that the JVM understands
+\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
+\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
+\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:
+\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
+\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/csc8505/s2011/handouts/JVM%20and%20Jasmin.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{http://www.ceng.metu.edu.tr/courses/ceng444/link/f3jasmintutorial.html}
+\url{https://pypi.python.org/pypi/ply}
+\end{center}
-and
+\noindent This assembler is largely compatible with the Jasmin
+syntax---that means for the files we look are concerned with,
+it understands the same input syntax (no changes to your
+compiler need to be made). You can generate Java Byte Code by
+using
-\url{http://www.csc.villanova.edu/~tway/courses/csc8505/s2011/handouts/JVM%20and%20Jasmin.pdf}
+\begin{center}
+\texttt{python Krakatau-master/assemble.py loops.j}
\end{center}
-\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
+\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).
+
+
+%\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 5\%)}
-You need to lex and parse WHILE programs, and then generate Java Byte
-Code instructions for the Jasmin 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
-calculated. The Fibonacci program is given in Figure~\ref{fibs}. You
-can write your own program for calculating factorials.
+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.
\begin{figure}[t]
\lstinputlisting[language=while]{../progs/fib.while}
@@ -110,23 +143,26 @@
\subsection*{Question 2 (marked with 4\%)}
-Extend the syntax of you language so that it contains also \texttt{for}-loops, like
+Extend the syntax of your 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}.
+\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 (in
+case it is greater, you should leave the loop). 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]
+\begin{minipage}{12cm}
+\begin{lstlisting}[language=While, numbers=none]
for i := 2 upto 4 do {
write i
}
@@ -134,16 +170,17 @@
\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:
+\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]
+\begin{minipage}{12cm}
+\begin{lstlisting}[language=While, numbers=none]
i := 2;
while (i <= 4) do {
write i;
@@ -155,13 +192,12 @@
\subsection*{Question 3 (marked with 1\%)}
-\noindent
-In this question you are supposed to give the assembler instructions for the
-program
+\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]
+\begin{minipage}{12cm}
+\begin{lstlisting}[language=While, numbers=none]
for i := 1 upto 10 do {
for i := 1 upto 10 do {
write i
@@ -174,21 +210,22 @@
\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 you decision and indicate what this program would
+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---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:
+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}{10cm}
+\begin{minipage}{12cm}
\begin{lstlisting}[language=Java,numbers=none]
class HelloWorld {
public static void main(String[] args) {
@@ -203,16 +240,20 @@
You can use the command
\begin{center}
-\texttt{javap -v HelloWorld}
+\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
+\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{minipage}{12cm}
\begin{lstlisting}[language=Scala,numbers=none]
object HelloWorld {
def main(args: Array[String]) {
@@ -249,12 +290,13 @@
\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
+\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{minipage}{12cm}
\begin{lstlisting}[language=JVMIS, numbers=none]
iload n
invokestatic XXX/XXX/write(I)V
@@ -262,21 +304,21 @@
\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).
+\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:
+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 2
+ .limit locals 1
getstatic java/lang/System/out Ljava/io/PrintStream;
aload 0
invokevirtual java/io/PrintStream/println(Ljava/lang/String;)V
@@ -286,12 +328,11 @@
\end{minipage}
\end{center}
-\noindent
-The code that needs to be generated for \code{write "some_string"} commands
-is
+\noindent The code that needs to be generated for \code{write
+"some_string"} commands is
\begin{center}
-\begin{minipage}{8cm}
+\begin{minipage}{12cm}
\begin{lstlisting}[language=JVMIS,numbers=none]
ldc "some_string"
invokestatic XXX/XXX/writes(Ljava/lang/String;)V
@@ -299,15 +340,16 @@
\end{minipage}
\end{center}
-\noindent
-Again you need to adjust the \texttt{XXX/XXX} part in each call.
+\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
+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{minipage}{12cm}
\begin{lstlisting}[language=JVMIS,numbers=none]
invokestatic XXX/XXX/read()I
istore n