1 \documentclass{article}

     2 \usepackage{hyperref}

     3 \usepackage{amssymb}

     4 \usepackage{amsmath}

     5 \usepackage{../langs}

     6 

     7 \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}%

     8 \begin{document}

     9 

    10 \section*{Coursework 3}

    11 

    12 \noindent

    13 This coursework is worth 5\% and is due on 28 November at 16:00. You are asked to 

    14 implement a compiler for the WHILE language that targets the

    15 assembler language provided by Jasmin. This assembler 

    16 is available from

    17 

    18 \begin{center}

    19 \url{http://jasmin.sourceforge.net}

    20 \end{center}

    21 

    22 \noindent

    23 There is a user guide for Jasmin

    24 

    25 \begin{center}

    26 \url{http://jasmin.sourceforge.net/guide.html}

    27 \end{center}

    28 

    29 \noindent

    30 and also a description of some of the instructions that the JVM understands

    31 

    32 \begin{center}

    33 \url{http://jasmin.sourceforge.net/instructions.html}

    34 \end{center}

    35 

    36 \noindent

    37 If you generated a correct assembler file for Jasmin, for example

    38 \texttt{loops.j}, you can use

    39 

    40 \begin{center}

    41 \texttt{java -jar jasmin-2.4/jasmin.jar loops.j}

    42 \end{center}

    43 

    44 \noindent

    45 in order to translate it to Java byte code. The resulting class file can be

    46 run with

    47 

    48 \begin{center}

    49 \texttt{java loops}

    50 \end{center}

    51 

    52 \noindent

    53 where you might need to give the correct path to the class file. There

    54 are also other resources about Jasmin on the Internet, for example

    55 \mbox{\url{http://goo.gl/Qj8TeK}} and \mbox{\url{http://goo.gl/fpVNyT}}\;.\bigskip

    56 

    57 \noindent

    58 You need to submit a document containing the answers for the two questions 

    59 below. You can do the implementation in any programming language you like, but you need 

    60 to submit the source code with which you answered the questions. Otherwise

    61 the submission will not be counted.  However, the coursework 

    62 will \emph{only} be judged according to the answers. You can submit your answers

    63 in a txt-file or as pdf.\bigskip

    64 

    65 

    66 \subsection*{Question 1 (marked with 2\%)}

    67 

    68 You need to lex and parse WHILE programs and submit the assembler 

    69 instructions for the Fibonacci program and for the program you submitted

    70 in Coursework 2 in Question 3. The latter should be so modified that 

    71 a user can input the upper bound on the console (in the original question

    72 it was fixed to 100).

    73 

    74 \subsection*{Question 2 (marked with 2\%)}

    75 

    76 Extend the syntax of you language so that it contains also \texttt{for}-loops, like

    77 

    78 \begin{center}

    79 \texttt{for} \;\textit{Id} \texttt{:=} \textit{AExp}\; \texttt{upto} \;\textit{AExp}\; \texttt{do} \textit{Block} 

    80 \end{center}

    81 

    82 \noindent

    83 The intended meaning is to first assign the variable \textit{Id} the value of the first arithmetic 

    84 expression, then go through the loop, at the end increase the value of the variable by 1, 

    85 and finally test wether the value is not less or equal to the value of the second

    86 arithmetic expression. For example the following instance of a \texttt{for}-loop 

    87 is supposed to print out the numbers \texttt{2}, \texttt{3}, \texttt{4}.

    88 

    89 

    90 \begin{center}

    91 \begin{minipage}{6cm}

    92 \begin{lstlisting}[language=While,basicstyle=\ttfamily, numbers=none]

    93 for i := 2 upto 4 do {

    94     write i	

    95 }

    96 \end{lstlisting}

    97 \end{minipage}

    98 \end{center}

    99 

   100 \noindent

   101 There are two ways how this can be implemented: one is to adapt the code generation 

   102 part of the compiler and generate specific code for \texttt{for}-loops; the other is to

   103 translate the abstract syntax tree of \texttt{for}-loops into an abstract syntax tree using

   104 existing language constructs. For example the loop above could be translated

   105 to the following \texttt{while}-loop:

   106 

   107 \begin{center}

   108 \begin{minipage}{6cm}

   109 \begin{lstlisting}[language=While,basicstyle=\ttfamily, numbers=none]

   110 i := 2;

   111 while (i <= 4) do {

   112     write i;

   113     i := i + 1;

   114 }

   115 \end{lstlisting}

   116 \end{minipage}

   117 \end{center}

   118 

   119 \noindent

   120 In this question you are supposed to give the assembler instructions for the

   121 program

   122 

   123 \begin{center}

   124 \begin{minipage}{6cm}

   125 \begin{lstlisting}[language=While,basicstyle=\ttfamily, numbers=none]

   126 for i := 1 upto 10000 do {

   127   for i := 1 upto 10000 do {

   128   skip

   129   }

   130 } 

   131 \end{lstlisting}

   132 \end{minipage}

   133 \end{center}

   134 

   135 

   136 

   137 \subsection*{Further Information}

   138 

   139 The Java infrastructure unfortunately does not contain an assembler out-of-the-box

   140 (therefore

   141 you need to download the additional package Jasmin---see above). But it does contain a 

   142 disassembler, called \texttt{javap}. A dissembler does the ``opposite'' of an assembler: it

   143 generates readable assembler code from Java byte code. Have a look at the

   144 following example: Compile using the usual Java compiler the simple Hello World 

   145 program below:

   146 

   147 \begin{center}

   148 \begin{minipage}{10cm}

   149 \begin{lstlisting}[language=Java,basicstyle=\ttfamily]

   150 class HelloWorld {

   151     public static void main(String[] args) {

   152         System.out.println("Hello World!");

   153     }

   154 }

   155 \end{lstlisting}

   156 \end{minipage}

   157 \end{center}

   158 

   159 \noindent

   160 You can use the command

   161 

   162 \begin{center}

   163 \texttt{javap -v HelloWorld}

   164 \end{center}

   165 

   166 \noindent

   167 to see the assembler instructions of the Java byte code that has been generated for this

   168 program. You can compare this with the code generated for the Scala

   169 version of Hello World.

   170 

   171 \begin{center}

   172 \begin{minipage}{10cm}

   173 \begin{lstlisting}[language=Scala,basicstyle=\ttfamily]

   174 object HelloWorld {

   175    def main(args: Array[String]) {

   176       println("Hello World!")

   177   }

   178 }

   179 \end{lstlisting}

   180 \end{minipage}

   181 \end{center}

   182 

   183 

   184 \subsection*{Library Functions}

   185 

   186 You need to generate code for the commands \texttt{write} and \texttt{read}. This

   187 will require the addition of some ``library'' functions to your generated code. The first

   188 command even needs two versions, because you might want to write out an

   189 integer or a string. The Java byte code will need two separate functions for this.

   190 For writing out an integer, you can use the assembler code

   191 

   192 \begin{center}

   193 \begin{minipage}{12cm}

   194 \begin{lstlisting}[basicstyle=\ttfamily, numbers=none]

   195 .method public static write(I)V 

   196     .limit locals 5 

   197     .limit stack 5 

   198     iload 0 

   199     getstatic java/lang/System/out Ljava/io/PrintStream; 

   200     swap 

   201     invokevirtual java/io/PrintStream/println(I)V 

   202     return 

   203 .end method

   204 \end{lstlisting}

   205 \end{minipage}

   206 \end{center}

   207 

   208 \noindent 

   209 This function will invoke Java's \texttt{println} function for integers. Then if you need

   210 to generate code for \texttt{write x} where \texttt{x} is an integer variable, you can generate

   211 

   212 \begin{center}

   213 \begin{minipage}{8cm}

   214 \begin{lstlisting}[basicstyle=\ttfamily, numbers=none]

   215 iload n 

   216 invokestatic XXX/XXX/write(I)V

   217 \end{lstlisting}

   218 \end{minipage}

   219 \end{center}

   220 

   221 \noindent

   222 where \texttt{n} is the index where the value of the variable \texttt{x} is

   223 stored. The \texttt{XXX/XXX} needs to be replaced with the class name 

   224 which you use to generate the code (for example \texttt{fib/fib} in case

   225 of the Fibonacci numbers).

   226 

   227 Writing out a string is similar. The corresponding library function uses strings 

   228 instead of integers:

   229 

   230 \begin{center}

   231 \begin{minipage}{12cm}

   232 \begin{lstlisting}[basicstyle=\ttfamily, numbers=none]

   233 .method public static writes(Ljava/lang/String;)V

   234    .limit stack 2

   235    .limit locals 2

   236    getstatic java/lang/System/out Ljava/io/PrintStream;

   237    aload 0

   238    invokevirtual java/io/PrintStream/println(Ljava/lang/String;)V

   239    return

   240 .end method

   241 \end{lstlisting}

   242 \end{minipage}

   243 \end{center}

   244 

   245 \noindent

   246 The code that needs to be generated for \texttt{write "some\_string"} commands 

   247 is

   248 

   249 \begin{center}

   250 \begin{minipage}{8cm}

   251 \begin{lstlisting}[basicstyle=\ttfamily, numbers=none]

   252 ldc "some_string"

   253 invokestatic XXX/XXX/writes(Ljava/lang/String;)V

   254 \end{lstlisting}

   255 \end{minipage}

   256 \end{center}

   257 

   258 \noindent

   259 Again you need to adjust the \texttt{XXX/XXX} part in each call.

   260 

   261 The code for \texttt{read} is more complicated. The reason is that inputting a string

   262 will need to be transformed into an integer. The code in Figure~\ref{read} does this.

   263 It can be called with

   264 

   265 \begin{center}

   266 \begin{minipage}{8cm}

   267 \begin{lstlisting}[basicstyle=\ttfamily, numbers=none]

   268 invokestatic XXX/XXX/read()I 

   269 istore n

   270 \end{lstlisting}

   271 \end{minipage}

   272 \end{center}

   273 

   274 \noindent 

   275 where \texttt{n} is the index of the variable that requires an input.

   276 

   277 

   278 \begin{figure}[p]\small

   279 \begin{lstlisting}[basicstyle=\ttfamily, numbers=none]

   280 .method public static read()I 

   281       .limit locals 10 

   282       .limit stack 10

   283 

   284       ldc 0 

   285       istore 1  ; this will hold our final integer 

   286 Label1: 

   287       getstatic java/lang/System/in Ljava/io/InputStream; 

   288       invokevirtual java/io/InputStream/read()I 

   289       istore 2 

   290       iload 2 

   291       ldc 10   ; the newline delimiter 

   292       isub 

   293       ifeq Label2 

   294       iload 2 

   295       ldc 32   ; the space delimiter 

   296       isub 

   297       ifeq Label2

   298 

   299       iload 2 

   300       ldc 48   ; we have our digit in ASCII, have to subtract it from 48 

   301       isub 

   302       ldc 10 

   303       iload 1 

   304       imul 

   305       iadd 

   306       istore 1 

   307       goto Label1 

   308 Label2: 

   309       ;when we come here we have our integer computed in Local Variable 1 

   310       iload 1 

   311       ireturn 

   312 .end method

   313 \end{lstlisting}\normalsize

   314 \caption{Assembler code for reading an integer from the console.\label{read}}

   315 \end{figure}

   316 

   317 \end{document}

   318 

   319 %%% Local Variables: 

   320 %%% mode: latex

   321 %%% TeX-master: t

   322 %%% End: