diff -r bdf84605b6cd -r 6322922aa990 coursework/cw03.tex --- a/coursework/cw03.tex Fri Nov 07 13:54:50 2014 +0000 +++ b/coursework/cw03.tex Fri Nov 07 14:02:38 2014 +0000 @@ -1,69 +1,19 @@ \documentclass{article} -\usepackage{hyperref} -\usepackage{amssymb} -\usepackage{amsmath} +\usepackage{../style} \usepackage{../langs} -\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% \begin{document} \section*{Coursework 3} \noindent -This coursework is worth 5\% and is due on 28 November 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 +This coursework is worth 5\% and is due on 28 November at 16:00. You +are asked to implement a parser for the WHILE language and also +an iterpreter. -\subsection*{Question 1 (marked with 2\%)} + +\subsection*{Question 1 (marked with 1\%)} You need to lex and parse WHILE programs and submit the assembler instructions for the Fibonacci program and for the program you submitted @@ -73,246 +23,11 @@ \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*{Question 3 (marked with 2\%)} -\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}