12 The purpose of a compiler is to transform a program, a human

    15 

    13 can read and write, into code the machine can run as fast as

    16 The language we looked at in the previous lecture was rather 

    14 possible. The fastest code would be machine code the CPU can

    17 primitive and the compiler rather crude. In this handout

    15 run directly, but it is often enough to improve the speed of a

    18 we like to have a look at a slightly more comfortable

    16 program by just targeting a virtual machine. This produces not

    19 language and a tiny-teeny bit more realistic compiler. A small

    17 the fastest possible code, but code that is fast enough and

    20 collection of programs we want to be able to write and compile

    18 has the advantage that the virtual machine takes care of

    21 is as follows:

    19 things a compiler would normally need to take care of (like

    22 

    20 explicit memory management).

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

    21 

    24 def fib(n) = if n == 0 then 0 

    22 As a first example we will implement a compiler for the very

    25              else if n == 1 then 1 

    23 simple While-language. It will generate code for the Java

    26              else fib(n - 1) + fib(n - 2);

    24 Virtual Machine (JVM). This is a stack-based virtual machine,

    27 

    25 a fact which will make it easy to generate code for arithmetic

    28 def fact(n) = if n == 0 then 1 else n * fact(n - 1);

    26 expressions. For example for generating code for the

    29 

    27 expression $1 + 2$ we need to generate the following three

    30 def ack(m, n) = if m == 0 then n + 1

    28 instructions

    31                 else if n == 0 then ack(m - 1, 1)

    29 

    32                 else ack(m - 1, ack(m, n - 1));

    30 \begin{lstlisting}[numbers=none]

    33                 

    31 ldc 1

    34 def gcd(a, b) = if b == 0 then a else gcd(b, a % b);                

    32 ldc 2

    35 \end{lstlisting}

    33 iadd 

    36 

    34 \end{lstlisting}

    37 \noindent We will still restrict us to just programs about

    35 

    38 integers, that means for example that every function needs to

    36 \noindent The first instruction loads the constant $1$ onto

    39 return an integer. The grammar of the Fun-language is slightly 

    37 the stack, the next one $2$, the third instruction adds both

    40 simpler than the While-language, because almost everything is 

    38 numbers together replacing the top two elements of the stack

    41 an expression. The grammar rules are as follows:

    39 with the result $3$. For simplicity, we will throughout

    42 

    40 consider only integer numbers and results. Therefore we can

    43 

    41 use the JVM instructions \code{iadd}, \code{isub},

    44 \begin{plstx}[rhs style=,margin=1.5cm]

    42 \code{imul}, \code{idiv} and so on. The \code{i} stands for

    45 : \meta{Exp} ::= \meta{Var} | \meta{Num} {\hspace{3cm}}

    43 integer instructions in the JVM (alternatives are \code{d} for

    46              |   \meta{Exp} + \meta{Exp} | ... | (\meta{ExP})

    44 doubles, \code{l} for longs and \code{f} for floats).

    47              |   \code{if} \meta{BExp} \code{then} \meta{Exp} \code{else} \meta{Exp}

    45 

    48              |   \code{write} \meta{Exp} {\hspace{5cm}}

    46 Recall our grammar for arithmetic expressions ($E$ is the

    49              |   \meta{Exp} ; \meta{Exp}  {\hspace{5cm}}

    47 starting symbol):

    50              |   \textit{FunName} (\meta{Exp}, ..., \meta{Exp})\\

    48 

    51 : \meta{BExp} ::= ...\\

    49 

    52 : \meta{Decl} ::= \meta{Def} ; \meta{Decl}

    50 \begin{plstx}[rhs style=, margin=3cm]

    53              | \meta{Exp}\\

    51 : \meta{E} ::= \meta{T} $+$ \meta{E}

    54 : \meta{Def} ::= \code{def} \textit{FunName} ($x_1$, ..., $x_2$)\\               

    52          | \meta{T} $-$ \meta{E}

    53          | \meta{T}\\

    54 : \meta{T} ::= \meta{F} $*$ \meta{T}

    55           | \meta{F} $\backslash$ \meta{T}

    56           | \meta{F}\\

    57 : \meta{F} ::= ( \meta{E} )

    58           | \meta{Id}

    59           | \meta{Num}\\