1 % !TEX program = xelatex

     2 \documentclass{article}

     3 \usepackage{../style}

     4 \usepackage{../langs}

     5 

     6 \begin{document}

     7 

     8 %https://github.com/Storyyeller/Krakatau

     9 %https://docs.oracle.com/javase/specs/jvms/se7/html/

    10 

    11 % Jasmin Tutorial

    12 %http://saksagan.ceng.metu.edu.tr/courses/ceng444/link/jvm-cpm.html

    13 

    14 \section*{Coursework 4}

    15 

    16 \noindent This coursework is worth 10\% and is due on \cwFOUR{}

    17 at 18:00. You are asked to implement a compiler for

    18 the WHILE language that targets the assembler language

    19 provided by Jasmin or Krakatau (both have very similar

    20 syntax). You can do the implementation in any programming

    21 language you like, but you need to submit the source code with

    22 which you answered the questions, otherwise a mark of 0\% will

    23 be awarded. You should use the lexer and parser from the

    24 previous courseworks. Please package \emph{everything}(!) in

    25 a zip-file that creates a directory with the name

    26 \texttt{YournameYourFamilyname} on my end.

    27 

    28 \subsection*{Disclaimer\alert}

    29 

    30 It should be understood that the work you submit represents

    31 your own effort. You have not copied from anyone else. An

    32 exception is the Scala code I showed during the lectures,

    33 which you can use. You can also use your own code from the

    34 CW~1, CW~2 and CW~3.

    35 

    36 

    37 \subsection*{Jasmin Assembler}

    38 

    39 The Jasmin assembler is available from

    40 

    41 \begin{center}

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

    43 \end{center}

    44 

    45 \noindent

    46 There is a user guide for Jasmin

    47 

    48 \begin{center}

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

    50 \end{center}

    51 

    52 \noindent and also a description of some of the instructions

    53 that the JVM understands

    54 

    55 \begin{center}

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

    57 \end{center}

    58 

    59 \noindent If you generated a correct assembler file for

    60 Jasmin, for example \texttt{loops.j}, you can use

    61 

    62 \begin{center}

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

    64 \end{center}

    65 

    66 \noindent in order to translate it into Java Byte Code. The

    67 resulting class file can be run with

    68 

    69 \begin{center}

    70 \texttt{java loops}

    71 \end{center}

    72 

    73 \noindent where you might need to give the correct path to the

    74 class file. For example:

    75 

    76 \begin{center}

    77 \texttt{java -cp . loops/loops}

    78 \end{center}

    79 

    80 \noindent There are also other resources about Jasmin on the

    81 Internet, for example

    82 

    83 \begin{center}

    84 \small\url{http://www.ceng.metu.edu.tr/courses/ceng444/link/f3jasmintutorial.html}

    85 \end{center}

    86 

    87 \noindent and

    88 

    89 \begin{center}

    90   \small\url{http://www.csc.villanova.edu/~tway/courses/csc4181/s2018/labs/lab4/JVM.pdf}

    91 \end{center}

    92 

    93 \subsection*{Krakatau Assembler}

    94 

    95 The Krakatau assembler is available from

    96 

    97 \begin{center}

    98 \url{https://github.com/Storyyeller/Krakatau}

    99 \end{center}

   100 

   101 \noindent This assembler requires Python and a package called

   102 \pcode{ply} available from

   103 

   104 \begin{center}

   105 \url{https://pypi.python.org/pypi/ply}

   106 \end{center}

   107 

   108 \noindent This assembler is largely compatible with the Jasmin

   109 syntax---that means for the files we are concerned with here,

   110 it understands the same input syntax (no changes to your

   111 compiler need to be made; ok maybe some small syntactic

   112 adjustments are needed). You can generate Java Byte Code by

   113 using 

   114 

   115 \begin{center}

   116 \texttt{python Krakatau-master/assemble.py loops.j}

   117 \end{center}

   118 

   119 \noindent where you may have to adapt the directory where

   120 Krakatau is installed (I just downloaded the zip file from

   121 Github and \pcode{Krakatau-master} was the directory where it

   122 was installed). Again the resulting class-file you can run with

   123 \texttt{java}.

   124 

   125 

   126 %\noindent You need to submit a document containing the answers

   127 %for the two questions below. You can do the implementation in

   128 %any programming language you like, but you need to submit the

   129 %source code with which you answered the questions. Otherwise

   130 %the submission will not be counted. However, the coursework

   131 %will \emph{only} be judged according to the answers. You can

   132 %submit your answers in a txt-file or as pdf.\bigskip

   133 

   134 

   135 \subsection*{Question 1}

   136 

   137 You need to lex and parse WHILE programs, and then generate

   138 Java Byte Code instructions for the Jasmin assembler (or

   139 Krakatau assembler). As solution you need to submit the

   140 assembler instructions for the Fibonacci and Factorial

   141 programs. Both should be so modified that a user can input on

   142 the console which Fibonacci number and which Factorial should

   143 be calculated. The Fibonacci program is given in

   144 Figure~\ref{fibs}. You can write your own program for

   145 calculating factorials. Submit your assembler code as

   146 a file that can be run, not as PDF-text.

   147 

   148 \begin{figure}[t]

   149 \lstinputlisting[language=while]{../progs/while-tests/fib.while}

   150 \caption{The Fibonacci program in the WHILE language.\label{fibs}}

   151 \end{figure}

   152 

   153 \subsection*{Question 2}

   154 

   155 Extend the syntax of your language so that it contains also

   156 \texttt{for}-loops, like

   157 

   158 \begin{center}

   159 \lstset{language=While}

   160 \code{for} \;\textit{Id} \texttt{:=} \textit{AExp}\; \code{upto} 

   161 \;\textit{AExp}\; \code{do} \textit{Block} 

   162 \end{center}

   163 

   164 \noindent The intended meaning is to first assign the variable

   165 \textit{Id} the value of the first arithmetic expression, test

   166 whether this value is less or equal than the value of the

   167 second arithmetic expression. If yes, go through the loop, and

   168 at the end increase the value of the loop variable by 1 and

   169 start again with the test. If no, leave the loop. For example

   170 the following instance of a \code{for}-loop is supposed to

   171 print out the numbers \pcode{2}, \pcode{3}, \pcode{4}.

   172 

   173 

   174 \begin{center}

   175 \begin{minipage}{12cm}

   176 \begin{lstlisting}[language=While, numbers=none]

   177 for i := 2 upto 4 do {

   178     write i	

   179 }

   180 \end{lstlisting}

   181 \end{minipage}

   182 \end{center}

   183 

   184 \noindent There are two ways how this can be implemented: one

   185 is to adapt the code generation part of the compiler and

   186 generate specific code for \code{for}-loops; the other is to

   187 translate the abstract syntax tree of \code{for}-loops into

   188 an abstract syntax tree using existing language constructs.

   189 For example the loop above could be translated to the

   190 following \code{while}-loop:

   191 

   192 \begin{center}

   193 \begin{minipage}{12cm}

   194 \begin{lstlisting}[language=While, numbers=none]

   195 i := 2;

   196 while (i <= 4) do {

   197     write i;

   198     i := i + 1;

   199 }

   200 \end{lstlisting}

   201 \end{minipage}

   202 \end{center}

   203 

   204 \subsection*{Question 3}

   205 

   206 \noindent In this question you are supposed to give the

   207 assembler instructions for the program

   208 

   209 \begin{center}

   210 \begin{minipage}{12cm}

   211 \begin{lstlisting}[language=While, numbers=none]

   212 for i := 1 upto 10 do {

   213   for i := 1 upto 10 do {

   214     write i

   215   }

   216 } 

   217 \end{lstlisting}

   218 \end{minipage}

   219 \end{center}

   220 

   221 \noindent 

   222 Note that in this program the variable \pcode{i} is used

   223 twice. You need to make a decision how it should be compiled?

   224 Explain your decision and indicate what this program would

   225 print out.

   226 

   227 \subsection*{Further Information}

   228 

   229 The Java infrastructure unfortunately does not contain an

   230 assembler out-of-the-box (therefore you need to download the

   231 additional package Jasmin or Krakatau---see above). But it

   232 does contain a disassembler, called \texttt{javap}. A

   233 dissembler does the ``opposite'' of an assembler: it generates

   234 readable assembler code from Java Byte Code. Have a look at

   235 the following example: Compile using the usual Java compiler

   236 the simple Hello World program below:

   237 

   238 \begin{center}

   239 \begin{minipage}{12cm}

   240 \begin{lstlisting}[language=Java,numbers=none]

   241 class HelloWorld {

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

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

   244     }

   245 }

   246 \end{lstlisting}

   247 \end{minipage}

   248 \end{center}

   249 

   250 \noindent

   251 You can use the command

   252 

   253 \begin{center}

   254 \begin{minipage}{12cm}

   255 \begin{lstlisting}[language={},numbers=none]

   256 javap -v HelloWorld

   257 \end{lstlisting}

   258 \end{minipage}

   259 \end{center}

   260 

   261 \noindent to see the assembler instructions of the Java Byte

   262 Code that has been generated for this program. You can compare

   263 this with the code generated for the Scala version of Hello

   264 World.

   265 

   266 \begin{center}

   267 \begin{minipage}{12cm}

   268 \begin{lstlisting}[language=Scala,numbers=none]

   269 object HelloWorld {

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

   271       println("Hello World!")

   272   }

   273 }

   274 \end{lstlisting}

   275 \end{minipage}

   276 \end{center}

   277 

   278 

   279 \subsection*{Library Functions}

   280 

   281 You need to generate code for the commands \texttt{write} and

   282 \texttt{read}. This will require the addition of some

   283 ``library'' functions to your generated code. The first

   284 command even needs two versions, because you need to write out

   285 an integer and string. The Java byte code will need two

   286 separate functions for this. For writing out an integer, you

   287 can use the assembler code

   288 

   289 \begin{center}

   290 \begin{minipage}{12cm}

   291 \begin{lstlisting}[language=JVMIS, numbers=none]

   292 .method public static write(I)V 

   293     .limit locals 1 

   294     .limit stack 2  

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

   296     iload 0

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

   298     return 

   299 .end method

   300 \end{lstlisting}

   301 \end{minipage}

   302 \end{center}

   303 

   304 \noindent This function will invoke Java's \texttt{println}

   305 function for integers. Then if you need to generate code for

   306 \texttt{write x} where \texttt{x} is an integer variable, you

   307 can generate

   308 

   309 \begin{center}

   310 \begin{minipage}{12cm}

   311 \begin{lstlisting}[language=JVMIS, numbers=none]

   312 iload n 

   313 invokestatic XXX/XXX/write(I)V

   314 \end{lstlisting}

   315 \end{minipage}

   316 \end{center}

   317 

   318 \noindent where \texttt{n} is the index where the value of the

   319 variable \texttt{x} is stored. The \texttt{XXX/XXX} needs to

   320 be replaced with the class name which you use to generate the

   321 code (for example \texttt{fib/fib} in case of the Fibonacci

   322 numbers).

   323 

   324 Writing out a string is similar. The corresponding library

   325 function uses strings instead of integers:

   326 

   327 \begin{center}

   328 \begin{minipage}{12cm}

   329 \begin{lstlisting}[language=JVMIS, numbers=none]

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

   331    .limit stack 2

   332    .limit locals 1

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

   334    aload 0

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

   336    return

   337 .end method

   338 \end{lstlisting}

   339 \end{minipage}

   340 \end{center}

   341 

   342 \noindent The code that needs to be generated for \code{write

   343 "some_string"} commands is

   344 

   345 \begin{center}

   346 \begin{minipage}{12cm}

   347 \begin{lstlisting}[language=JVMIS,numbers=none]

   348 ldc "some_string"

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

   350 \end{lstlisting}

   351 \end{minipage}

   352 \end{center}

   353 

   354 \noindent Again you need to adjust the \texttt{XXX/XXX} part

   355 in each call.

   356 

   357 The code for \texttt{read} is more complicated. The reason is

   358 that inputting a string will need to be transformed into an

   359 integer. The code in Figure~\ref{read} does this. It can be

   360 called with

   361 

   362 \begin{center}

   363 \begin{minipage}{12cm}

   364 \begin{lstlisting}[language=JVMIS,numbers=none]

   365 invokestatic XXX/XXX/read()I 

   366 istore n

   367 \end{lstlisting}

   368 \end{minipage}

   369 \end{center}

   370 

   371 \noindent 

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

   373 use Windows you need to take into account that a ``return'' is not just a newline,

   374 \code{'\\10'}, but \code{'\\13\\10'}. This means you need to change line~12 in 

   375 Figure~\ref{read} to \pcode{ldc 13}.  

   376 

   377 

   378 \begin{figure}[t]\small

   379 \begin{lstlisting}[language=JVMIS,numbers=left]

   380 .method public static read()I 

   381       .limit locals 10 

   382       .limit stack 10

   383 

   384       ldc 0 

   385       istore 1  ; this will hold our final integer 

   386 Label1: 

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

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

   389       istore 2 

   390       iload 2 

   391       ldc 10  ; the newline delimiter for Unix (Windows 13)

   392       isub 

   393       ifeq Label2 

   394       iload 2 

   395       ldc 32   ; the space delimiter 

   396       isub 

   397       ifeq Label2

   398       iload 2 

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

   400       isub 

   401       ldc 10 

   402       iload 1 

   403       imul 

   404       iadd 

   405       istore 1 

   406       goto Label1 

   407 Label2: 

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

   409       iload 1 

   410       ireturn 

   411 .end method

   412 \end{lstlisting}\normalsize

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

   414 \end{figure}

   415 

   416 \end{document}

   417 

   418 %%% Local Variables: 

   419 %%% mode: latex

   420 %%% TeX-master: t

   421 %%% End: