# HG changeset patch
# User Christian Urban <christian dot urban at kcl dot ac dot uk>
# Date 1447623091 0
# Node ID 43c0ed4737208d1353e9fcab6291ce1821e608be
# Parent  a9911966c0dfe0dca8e8ceeb5afdc0c927a6e679
updated

diff -r a9911966c0df -r 43c0ed473720 coursework/cw01.pdf
Binary file coursework/cw01.pdf has changed
diff -r a9911966c0df -r 43c0ed473720 coursework/cw02.pdf
Binary file coursework/cw02.pdf has changed
diff -r a9911966c0df -r 43c0ed473720 coursework/cw02.tex
--- a/coursework/cw02.tex	Tue Nov 10 22:27:46 2015 +0000
+++ b/coursework/cw02.tex	Sun Nov 15 21:31:31 2015 +0000
@@ -93,20 +93,40 @@
 \end{center}
 
 \noindent
+Try to design regular expressions to be as small as possible.
 
 \subsection*{Question 2 (marked with 3\%)}
 
 Implement the Sulzmann \& Lu tokeniser from the lectures. For
 this you need to implement the functions $nullable$ and $der$
-(you can use your code from CW 1), as well as $mkeps$ and
+(you can use your code from CW~1), as well as $mkeps$ and
 $inj$. These functions need to be appropriately extended for
-the extended regular expressions from Q1. Also add the record
-regular expression from the lectures and implement a function,
-say \pcode{env}, that returns all assignments from a value
-(such that you can extract easily the tokens from a value). 
+the extended regular expressions from Q1. Write down the 
+clauses for
 
-The functions $mkeps$ and $inj$ return values. Calculate the
-value for your regular expressions from Q1 and the string
+\begin{center}
+\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
+$mkeps([c_1 c_2 \ldots c_n])$  & $\dn$ & $?$\\
+$mkeps(r^+)$                   & $\dn$ & $?$\\
+$mkeps(r^?)$                   & $\dn$ & $?$\\
+$mkeps(r^{\{n\}})$             & $\dn$ & $?$\medskip\\
+$inj\, ([c_1 c_2 \ldots c_n])\,c\,\ldots$  & $\dn$ & $?$\\
+$inj\, (r^+)\,c\,\ldots$                   & $\dn$ & $?$\\
+$inj\, (r^?)\,c\,\ldots$                   & $\dn$ & $?$\\
+$inj\, (r^{\{n\}})\,c\,\ldots$             & $\dn$ & $?$\\
+\end{tabular}
+\end{center}
+
+\noindent where $inj$ takes three arguments: a regular
+expression, a character and a value. Also add the record
+regular expression from the lectures to your tokeniser and
+implement a function, say \pcode{env}, that returns all
+assignments from a value (such that you can extract easily the
+tokens from a value).\medskip 
+
+\noindent
+Fiannly give the tokens for your regular expressions from Q1 and the
+string
 
 \begin{center}
 \code{"read n;"}
diff -r a9911966c0df -r 43c0ed473720 handouts/ho07.tex
--- a/handouts/ho07.tex	Tue Nov 10 22:27:46 2015 +0000
+++ b/handouts/ho07.tex	Sun Nov 15 21:31:31 2015 +0000
@@ -5,9 +5,22 @@
 
 \begin{document}
 
-\section*{Handout 7 (Compiling)}
+\section*{Handout 7 (Compilation)}
 
+The purpose of a compiler is to transform a program, a human
+can write, into code the machine can run as fast as possible.
+The fastest code would be machine code the CPU can run
+directly, but it is often enough to improve the speed of a
+program by just targeting a virtual machine. This produces not
+the fastest possible code, but code that is fast enough and
+has the advantage that the virtual machine care of things a
+compiler would normally need to take care of (like explicit
+memory management).
 
+We will be generating code for the Java Virtual Machine. This
+is a stack-based virtual machine which will make it easy to
+generate code for arithmetic expressions. Recall
+that our
 
 \end{document}
 
diff -r a9911966c0df -r 43c0ed473720 progs/compile.scala
--- a/progs/compile.scala	Tue Nov 10 22:27:46 2015 +0000
+++ b/progs/compile.scala	Sun Nov 15 21:31:31 2015 +0000
@@ -111,9 +111,13 @@
 def compile_aexp(a: AExp, env : Env) : Instrs = a match {
   case Num(i) => List("ldc " + i.toString + "\n")
   case Var(s) => List("iload " + env(s) + "\n")
-  case Aop("+", a1, a2) => compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("iadd\n")
-  case Aop("-", a1, a2) => compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("isub\n")
-  case Aop("*", a1, a2) => compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("imul\n")
+  case Aop("+", a1, a2) => 
+    compile_aexp(a1, env) ++ 
+    compile_aexp(a2, env) ++ List("iadd\n")
+  case Aop("-", a1, a2) => 
+    compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("isub\n")
+  case Aop("*", a1, a2) => 
+    compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("imul\n")
 }
 
 // boolean expression compilation
@@ -121,18 +125,22 @@
   case True => Nil
   case False => List("goto " + jmp + "\n")
   case Bop("=", a1, a2) => 
-    compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("if_icmpne " + jmp + "\n")
+    compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ 
+    List("if_icmpne " + jmp + "\n")
   case Bop("!=", a1, a2) => 
-    compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("if_icmpeq " + jmp + "\n")
+    compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ 
+    List("if_icmpeq " + jmp + "\n")
   case Bop("<", a1, a2) => 
-    compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("if_icmpge " + jmp + "\n")
+    compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ 
+    List("if_icmpge " + jmp + "\n")
 }
 
 // statement compilation
 def compile_stmt(s: Stmt, env: Env) : (Instrs, Env) = s match {
   case Skip => (Nil, env)
   case Assign(x, a) => {
-    val index = if (env.isDefinedAt(x)) env(x) else env.keys.size.toString
+    val index = if (env.isDefinedAt(x)) env(x) else 
+                    env.keys.size.toString
     (compile_aexp(a, env) ++ 
      List("istore " + index + "\n"), env + (x -> index))
   } 
@@ -159,9 +167,11 @@
      List("\n" + loop_end + ":\n\n"), env1)
   }
   case Write(x) => 
-    (List("iload " + env(x) + "\n" + "invokestatic XXX/XXX/write(I)V\n"), env)
+    (List("iload " + env(x) + "\n" + 
+           "invokestatic XXX/XXX/write(I)V\n"), env)
   case Read(x) => {
-    val index = if (env.isDefinedAt(x)) env(x) else env.keys.size.toString
+    val index = if (env.isDefinedAt(x)) env(x) else 
+                    env.keys.size.toString
     (List("invokestatic XXX/XXX/read()I\n" + 
           "istore " + index + "\n"), env + (x -> index))
   }
@@ -191,10 +201,11 @@
        Assign("minus2",Num(1)),         //  minus2 := 1;
        Assign("temp",Num(0)),           //  temp := 0;
        While(Bop("<",Num(0),Var("n")),  //  while n > 0 do  {
-          List(Assign("temp",Var("minus2")),                          //  temp := minus2;
-               Assign("minus2",Aop("+",Var("minus1"),Var("minus2"))), //  minus2 := minus1 + minus2;
-               Assign("minus1",Var("temp")),                          //  minus1 := temp;
-               Assign("n",Aop("-",Var("n"),Num(1))))),                //  n := n - 1 };
+          List(Assign("temp",Var("minus2")),    //  temp := minus2;
+               Assign("minus2",Aop("+",Var("minus1"),Var("minus2"))), 
+                                        //  minus2 := minus1 + minus2;
+               Assign("minus1",Var("temp")), //  minus1 := temp;
+               Assign("n",Aop("-",Var("n"),Num(1))))), //  n := n - 1 };
        Write("minus1"))                 //  write minus1
 
 
diff -r a9911966c0df -r 43c0ed473720 slides/slides07.pdf
Binary file slides/slides07.pdf has changed
diff -r a9911966c0df -r 43c0ed473720 slides/slides07.tex
--- a/slides/slides07.tex	Tue Nov 10 22:27:46 2015 +0000
+++ b/slides/slides07.tex	Sun Nov 15 21:31:31 2015 +0000
@@ -1,14 +1,12 @@
 \documentclass[dvipsnames,14pt,t]{beamer}
 \usepackage{../slides}
-\usepackage{../graphics}
 \usepackage{../langs}
 \usepackage{../data}
-
+\usepackage{../graphics}
 
 % beamer stuff 
 \renewcommand{\slidecaption}{AFL 07, King's College London}
 \newcommand{\bl}[1]{\textcolor{blue}{#1}}       
-%\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions
 
 \begin{document}
 
@@ -18,7 +16,7 @@
   \begin{tabular}{@ {}c@ {}}
   \\[-3mm]
   \LARGE Automata and \\[-2mm] 
-  \LARGE Formal Languages (7)\\[3mm] 
+  \LARGE Formal Languages (8)\\[3mm] 
   \end{tabular}}
 
   \normalsize
@@ -33,322 +31,52 @@
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
 
-
-\newcommand{\qq}{\mbox{\texttt{"}}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
-\frametitle{CFGs}
-
-A \alert{context-free} grammar (CFG) \bl{$G$} consists of:
-
-\begin{itemize}
-\item a finite set of nonterminal symbols (upper case)
-\item a finite terminal symbols or tokens (lower case)
-\item a start symbol (which must be a nonterminal)
-\item a set of rules
-\begin{center}
-\bl{$A \rightarrow \text{rhs}_1 | \text{rhs}_2 | \ldots$}
-\end{center}
-
-where \bl{rhs} are sequences involving terminals and nonterminals (can also be empty).\medskip\pause
-
-\end{itemize}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Hierarchy of Languages\end{tabular}}
-
-Recall that languages are sets of strings.
+\frametitle{Bird's Eye View}
 
 \begin{center}
 \begin{tikzpicture}
-[rect/.style={draw=black!50, top color=white,bottom color=black!20, rectangle, very thick, rounded corners}]
-
-\draw (0,0) node [rect, text depth=39mm, text width=68mm] {all languages};
-\draw (0,-0.4) node [rect, text depth=28.5mm, text width=64mm] {decidable languages};
-\draw (0,-0.85) node [rect, text depth=17mm] {context sensitive languages};
-\draw (0,-1.14) node [rect, text depth=9mm, text width=50mm] {context-free languages};
-\draw (0,-1.4) node [rect] {regular languages};
-\end{tikzpicture}
-
-\end{center}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Arithmetic Expressions\end{tabular}}
-
-A grammar for arithmetic expressions and numbers:
-
-\begin{center}
-\bl{\begin{tabular}{lcl}
-$E$ & $\rightarrow$ &  $E \cdot + \cdot E \;|\;E \cdot * \cdot E \;|\;( \cdot E \cdot ) \;|\;N$ \\
-$N$ & $\rightarrow$ & $N \cdot N \;|\; 0 \;|\; 1 \;|\: \ldots \;|\; 9$ 
-\end{tabular}}
-\end{center}
-
-Unfortunately it is left-recursive (and ambiguous).\medskip\\
-A problem for \alert{recursive descent parsers} (e.g.~parser combinators).
-\bigskip\pause
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[t]
-\frametitle{\begin{tabular}{c}Numbers\end{tabular}}
-
-
-
-\begin{center}
-\bl{\begin{tabular}{lcl}
-$N$ & $\rightarrow$ &  $N \cdot N \;|\; 0 \;|\; 1 \;|\; \ldots \;|\; 9$\\
-\end{tabular}}
-\end{center}
-
-A non-left-recursive, non-ambiguous grammar for numbers:
-
-\begin{center}
-\bl{\begin{tabular}{lcl}
-$N$ & $\rightarrow$ &  $0 \cdot N \;|\;1 \cdot N \;|\;\ldots\;|\; 0 \;|\; 1 \;|\; \ldots \;|\; 9$\\
-\end{tabular}}
-\end{center}
-
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Operator Precedences\end{tabular}}
-
-
-To disambiguate
-
-\begin{center}
-\bl{\begin{tabular}{lcl}
-$E$ & $\rightarrow$ &  $E \cdot + \cdot E \;|\;E \cdot * \cdot E \;|\;( \cdot E \cdot ) \;|\;N$ \\
-\end{tabular}}
-\end{center}
-
-Decide on how many precedence levels, say\medskip\\
-\hspace{5mm}highest for \bl{$()$}, medium for \bl{*}, lowest for \bl{+}
-
-\begin{center}
-\bl{\begin{tabular}{lcl}
-$E_{low}$ & $\rightarrow$ & $E_{med} \cdot + \cdot E_{low} \;|\; E_{med}$ \\
-$E_{med}$ & $\rightarrow$ & $E_{hi} \cdot * \cdot E_{med} \;|\; E_{hi}$\\
-$E_{hi}$ & $\rightarrow$ &  $( \cdot E_{low} \cdot ) \;|\;N$ \\
-\end{tabular}}
-\end{center}\pause
-
-\small What happens with \bl{$1 + 3  + 4$}?
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Removing Left-Recursion\end{tabular}}
-
-The rule for numbers is directly left-recursive:
-
-\begin{center}
-\bl{\begin{tabular}{lcl}
-$N$ & $\rightarrow$ & $N \cdot N \;|\; 0 \;|\; 1\;\;\;\;(\ldots)$ 
-\end{tabular}}
-\end{center}
-
-Translate
-
-\begin{center}
-\begin{tabular}{ccc}
-\bl{\begin{tabular}{lcl}
-$N$ & $\rightarrow$ & $N \cdot \alpha$\\
- &  $\;|\;$ & $\beta$\\
- \\ 
-\end{tabular}} 
-& {\Large$\Rightarrow$} &
-\bl{\begin{tabular}{lcl}
-$N$ & $\rightarrow$ & $\beta \cdot N'$\\
-$N'$ & $\rightarrow$ & $\alpha \cdot N'$\\
- &  $\;|\;$ & $\epsilon$ 
-\end{tabular}}
-\end{tabular}
-\end{center}\pause
-
-Which means
-
-\begin{center}
-\bl{\begin{tabular}{lcl}
-$N$ & $\rightarrow$ & $0 \cdot N' \;|\; 1 \cdot N'$\\
-$N'$ & $\rightarrow$ & $N \cdot N' \;|\; \epsilon$\\
-\end{tabular}}
+\node (rexp)  {\bl{\bf Lexer}};
+\node (nfa) [right=of rexp] {\bl{\bf Parser}};
+\node (dfa) [right=of nfa] 
+ {\bl{\begin{tabular}{c}\bf Machine Code/\\\bf Java Byte Code\end{tabular}}};
+\path[->, red, line width=2mm] (rexp) edge node [above=4mm, black] {\begin{tabular}{c@{\hspace{9mm}}}token\\[-1mm]
+sequence\end{tabular}} (nfa);
+\path[->, red, line width=2mm] (nfa) edge node [above=4mm, black] {\begin{tabular}{c}parse\\[-1mm] tree\end{tabular}}(dfa);
+\end{tikzpicture}\\
 \end{center}
 
-
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
+ 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Chomsky Normal Form\end{tabular}}
-
-All rules must be of the form
-
-\begin{center}
-\bl{$A \rightarrow a$}
-\end{center}
-
-or
-
-\begin{center}
-\bl{$A \rightarrow B\cdot C$}
-\end{center}
-
-No rule can contain \bl{$\epsilon$}.
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}$\epsilon$-Removal\end{tabular}}
-
-\begin{enumerate}
-\item If \bl{$A\rightarrow \alpha \cdot B \cdot \beta$} and \bl{$B \rightarrow \epsilon$} are in the grammar,
-then add \bl{$A\rightarrow \alpha \cdot \beta$} (iterate if necessary).
-\item Throw out all \bl{$B \rightarrow \epsilon$}.
-\end{enumerate}
-
-\small
-\begin{center}
-\begin{tabular}{ccc}
-\bl{\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
-$N$ & $\rightarrow$ & $0 \cdot N' \;|\; 1\cdot N'$\\
-$N'$ & $\rightarrow$ & $N \cdot N'\;|\;\epsilon$\\
-\\ 
-\\
-\\
-\\
-\\
-\end{tabular}} &
-\bl{\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
-\\
-$N$ & $\rightarrow$ & $0 \cdot N' \;|\; 1\cdot N'\;|\;0\;|\;1$\\
-$N'$ & $\rightarrow$ & $N \cdot N'\;|\;N\;|\;\epsilon$\\
-\\
-$N$ & $\rightarrow$ & $0 \cdot N' \;|\; 1\cdot N'\;|\;0\;|\;1$\\
-$N'$ & $\rightarrow$ & $N \cdot N'\;|\;N$\\
-\end{tabular}}
-\end{tabular}
-\end{center}
-
-\pause\normalsize
-\begin{center}
-\bl{\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
-$N$ & $\rightarrow$ & $0 \cdot N\;|\; 1\cdot N\;|\;0\;|\;1$\\
-\end{tabular}}
-
-\end{center}
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}CYK Algorithm\end{tabular}}
+\begin{textblock}{10}(0.5,0.5)
+  \LARGE
+  \fontspec{Hoefler Text Black}
+  \textcolor{ProcessBlue}{JVM\\ Code}
+\end{textblock}
+\fontsize{8}{10}\selectfont
+%\footnotesize
+\mbox{}\\[-8mm]\mbox{}
 
-If grammar is in Chomsky normalform \ldots
-
-\begin{center}
-\bl{\begin{tabular}{@ {}lcl@ {}}
-$S$ & $\rightarrow$ &  $N\cdot P$ \\
-$P$ & $\rightarrow$ &  $V\cdot N$ \\
-$N$ & $\rightarrow$ &  $N\cdot N$ \\
-$N$ & $\rightarrow$ &  $\texttt{students} \;|\; \texttt{Jeff} \;|\; \texttt{geometry} \;|\; \texttt{trains} $ \\
-$V$ & $\rightarrow$ &  $\texttt{trains}$ 
-\end{tabular}}
-\end{center}
-
-\bl{\texttt{Jeff trains geometry students}}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}CYK Algorithm\end{tabular}}
-
-
-\begin{itemize}
-\item fastest possible algorithm for recognition problem
-\item runtime is \bl{$O(n^3)$}\bigskip
-\item grammars need to be transferred into CNF
-\end{itemize}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Hierarchy of Languages\end{tabular}}
+\begin{columns}
+\begin{column}{2cm} 
+\lstinputlisting[numbers=none]{../progs/appHa.j}
+\end{column}
 
-Recall that languages are sets of strings.
-
-\begin{center}
-\begin{tikzpicture}
-[rect/.style={draw=black!50, top color=white,bottom color=black!20, rectangle, very thick, rounded corners}]
+\begin{column}{2cm} 
+\lstinputlisting[numbers=none]{../progs/appHb.j}
+\end{column}
 
-\draw (0,0) node [rect, text depth=39mm, text width=68mm] {all languages};
-\draw (0,-0.4) node [rect, text depth=28.5mm, text width=64mm] {decidable languages};
-\draw (0,-0.85) node [rect, text depth=17mm] {context sensitive languages};
-\draw (0,-1.14) node [rect, text depth=9mm, text width=50mm] {context-free languages};
-\draw (0,-1.4) node [rect] {regular languages};
-\end{tikzpicture}
-
-\end{center}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+\end{columns}
 
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Context Sensitive Grms\end{tabular}}
-
-
-\begin{center}
-\bl{\begin{tabular}{lcl}
-$S$ & $\Rightarrow$ &  $bSAA\;|\; \epsilon$\\
-$A$ & $\Rightarrow$ & $a$\\
-$bA$ & $\Rightarrow$ & $Ab$\\
-\end{tabular}}
-\end{center}\pause
-
-\begin{center}
-\bl{$S \Rightarrow\ldots\Rightarrow^? "ababaa"$}
-\end{center}
-
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
+ 
+ 
+ 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
 \begin{frame}[c]
@@ -370,48 +98,26 @@
 \textit{BExp} & $\rightarrow$ & \ldots\\
 \end{tabular}}
 \end{center}
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-
-\mbox{\lstinputlisting[language=while]{../progs/fib.while}}
 
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Fibonacci Numbers\end{tabular}}
+
+\mbox{}\\[-18mm]\mbox{}
+
+{\lstset{language=While}\fontsize{10}{12}\selectfont
+\texttt{\lstinputlisting{../progs/fib.while}}}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}An Interpreter\end{tabular}}
-
-\begin{center}
-\bl{\begin{tabular}{l}
-$\{$\\
-\;\;$x := 5 \text{;}$\\
-\;\;$y := x * 3\text{;}$\\
-\;\;$y := x * 4\text{;}$\\
-\;\;$x := u * 3$\\
-$\}$
-\end{tabular}}
-\end{center}
-
-\begin{itemize}
-\item the interpreter has to record the value of \bl{$x$} before assigning a value to \bl{$y$}\pause
-\item \bl{\text{eval}(stmt, env)}
-\end{itemize}
-
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Interpreter\end{tabular}}
+\frametitle{Interpreter}
 
 \begin{center}
 \bl{\begin{tabular}{@{}lcl@{}}
@@ -426,12 +132,12 @@
 \end{tabular}}
 \end{center}
 
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}Interpreter (2)\end{tabular}}
+\frametitle{Interpreter (2)}
 
 \begin{center}
 \bl{\begin{tabular}{@{}lcl@{}}
@@ -450,27 +156,42 @@
 \end{tabular}}
 \end{center}
 
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
-
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}Test Program\end{tabular}}
+\frametitle{Test Program}
 
 \mbox{}\\[-18mm]\mbox{}
 
-{\lstset{language=While}%%\fontsize{10}{12}\selectfont
+{\lstset{language=While}\fontsize{10}{12}\selectfont
 \texttt{\lstinputlisting{../progs/loops.while}}}
 
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
+\begin{frame}[c]
+\fontsize{7}{9}\selectfont
+
+
+\begin{columns}
+\begin{column}{7cm} 
+\lstinputlisting[numbers=none]{../progs/appHa.j}
+\end{column}
+
+\begin{column}{7cm} 
+\lstinputlisting[numbers=none]{../progs/appHb.j}
+\end{column}
+\end{columns}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+ 
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[t]
-\frametitle{\begin{tabular}{c}Interpreted Code\end{tabular}}
+\frametitle{Interpreted Code}
 
 \begin{center}
 \begin{tikzpicture}
@@ -480,13 +201,12 @@
 \end{tikzpicture}
 \end{center}
 
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}Java Virtual Machine\end{tabular}}
+\frametitle{Java Virtual Machine}
 
 \begin{itemize}
 \item introduced in 1995
@@ -494,12 +214,595 @@
 \item contains a JIT compiler
 \item many languages take advantage of JVM's infrastructure (JRE)
 \item is garbage collected $\Rightarrow$ no buffer overflows
-\item some languages compile to the JVM: Scala, Clojure\ldots
+\item some languages compiled to the JVM: Scala, Clojure\ldots
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{Compiling AExps}
+
+{\Large\bl{1 + 2}}
+
+\begin{center}
+\bl{\begin{tabular}{l}
+ldc 1\\
+ldc 2\\
+iadd\\
+\end{tabular}}
+\end{center}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[t]
+\frametitle{\begin{tabular}{c}Compiling AExps\end{tabular}}
+
+{\Large\bl{1 + 2 + 3}}
+
+\begin{center}
+\bl{\begin{tabular}{l}
+ldc 1\\
+ldc 2\\
+iadd\\
+ldc 3\\
+iadd\\
+\end{tabular}}
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[t]
+\frametitle{\begin{tabular}{c}Compiling AExps\end{tabular}}
+
+{\Large\bl{1 + (2 + 3)}}
+
+\begin{center}
+\bl{\begin{tabular}{l}
+ldc 1\\
+ldc 2\\
+ldc 3\\
+iadd\\
+iadd\\
+\end{tabular}}
+\end{center}\bigskip\pause
+\vfill
+
+\bl{dadd, fadd, ladd, \ldots}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[t]
+\frametitle{\begin{tabular}{c}Compiling AExps\end{tabular}}
+
+\begin{center}
+\bl{\begin{tabular}{@{}lcl@{}}
+$\text{compile}(n)$ & $\dn$ & $\text{ldc}\;n$\\
+$\text{compile}(a_1 + a_2)$ & $\dn$\\ 
+\multicolumn{3}{l}{$\qquad\text{compile}(a_1) \;@\;\text{compile}(a_2)\;@\; \text{iadd}$}\smallskip\\
+$\text{compile}(a_1 - a_2)$ & $\dn$\\ 
+\multicolumn{3}{l}{$\qquad\text{compile}(a_1) \;@\; \text{compile}(a_2)\;@\; \text{isub}$}\smallskip\\
+$\text{compile}(a_1 * a_2)$ & $\dn$\\ 
+\multicolumn{3}{l}{$\qquad\text{compile}(a_1) \;@\; \text{compile}(a_2)\;@\; \text{imul}$}\smallskip\\
+\end{tabular}}
+\end{center}\pause
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[t]
+\frametitle{\begin{tabular}{c}Compiling AExps\end{tabular}}
+
+{\Large\bl{1 + 2 * 3 + (4 - 3)}}
+
+\begin{center}
+\bl{\begin{tabular}{l}
+ldc 1\\
+ldc 2\\
+ldc 3\\
+imul\\
+ldc 4\\
+ldc 3\\
+isub\\
+iadd\\
+iadd\\
+\end{tabular}}
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[t]
+\frametitle{\begin{tabular}{c}Variables\end{tabular}}
+
+{\Large\bl{$x := 5 + y * 2$}}\bigskip\pause   
+
+\begin{itemize}
+\item lookup: \bl{$\text{iload}\; index$}
+\item store: \bl{$\text{istore}\; index$}
+\end{itemize}\bigskip\pause
+
+while compilating we have to maintain a map between our identifiers and the
+Java bytecode indices
+
+\begin{center}
+\bl{$\text{compile}(a, E)$}
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[t]
+\frametitle{\begin{tabular}{c}Compiling AExps\end{tabular}}
+
+\begin{center}
+\bl{\begin{tabular}{@{}lcl@{}}
+$\text{compile}(n, E)$ & $\dn$ & $\text{ldc}\;n$\\
+$\text{compile}(a_1 + a_2, E)$ & $\dn$\\ 
+\multicolumn{3}{l}{$\qquad\text{compile}(a_1, E) \;@\;\text{compile}(a_2. E)\;@\; \text{iadd}$}\smallskip\\
+$\text{compile}(a_1 - a_2, E)$ & $\dn$\\ 
+\multicolumn{3}{l}{$\qquad\text{compile}(a_1, E) \;@\; \text{compile}(a_2, E)\;@\; \text{isub}$}\smallskip\\
+$\text{compile}(a_1 * a_2, E)$ & $\dn$\\ 
+\multicolumn{3}{l}{$\qquad\text{compile}(a_1, E) \;@\; \text{compile}(a_2, E)\;@\; \text{imul}$}\bigskip\\
+$\text{compile}(x, E)$ & $\dn$ & $\text{iload}\;E(x)$\\
+\end{tabular}}
+\end{center}\pause
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{Compiling Statements}
+
+We return a list of instructions and an environment for the
+variables
+
+\begin{center}
+\bl{\begin{tabular}{@{}l@{\hspace{1mm}}c@{\hspace{1mm}}l@{}}
+$\text{compile}(\text{skip}, E)$ & $\dn$ & $(\textit{Nil}, E)$\bigskip\\
+$\text{compile}(x := a, E)$ & $\dn$\\
+\multicolumn{3}{l}{$(\text{compile}(a, E) \;@\;\text{istore}\;index, E(x\mapsto index))$}\\
+\end{tabular}}
+\end{center}\medskip
+
+where \bl{$index$} is \bl{$E(x)$} if it is already defined, 
+or if it is not then the largest index not yet seen
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[t]
+\frametitle{\begin{tabular}{c}Compiling AExps\end{tabular}}
+
+{\Large\bl{$x := x + 1$}}
+
+\begin{center}
+\bl{\begin{tabular}{l}
+iload $n_x$\\
+ldc 1\\
+iadd\\
+istore $n_x$\\
+\end{tabular}}
+\end{center}
+
+where \bl{$n_x$} is the index corresponding to the variable \bl{$x$}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c, fragile]
+\frametitle{Mathematical Functions}
+
+Compilation of some mathematical functions:
+
+\begin{center}
+\begin{tabular}{lcl}
+\texttt{Aop("+", a1, a2)} & $\Rightarrow$ & \texttt{...iadd}\\
+\texttt{Aop("-", a1, a2)} & $\Rightarrow$ & \texttt{...isub}\\
+\texttt{Aop("*", a1, a2)} & $\Rightarrow$ & \texttt{...imul}\\
+\texttt{Aop("/", a1, a2)} & $\Rightarrow$ & \texttt{...idiv}\\
+\texttt{Aop("\%", a1, a2)} & $\Rightarrow$ & \texttt{...irem}\\
+\end{tabular}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[t]
+\frametitle{\begin{tabular}{c}Compiling Ifs\end{tabular}}
+
+{\Large\bl{$\text{if}\;b\;\text{then}\;cs_1\;\text{else}\;cs_2$}}\bigskip\bigskip
+
+\onslide<2->{Case }\only<2>{{\bf True}:}\only<3>{{\bf False}:}
+
+\begin{center}
+\begin{tikzpicture}[node distance=2mm and 4mm,
+ block/.style={rectangle, minimum size=1cm, draw=black, line width=1mm},
+ point/.style={rectangle, inner sep=0mm, minimum size=0mm, fill=red},
+ skip loop/.style={red, line width=1mm, to path={-- ++(0,-10mm) -| (\tikztotarget)}}]
+\node (A1) [point] {};
+\node (b) [block, right=of A1] {code of \bl{$b$}};
+\node (A2) [point, right=of b] {};
+\node (cs1) [block, right=of A2] {code of \bl{$cs_1$}};
+\node (A3) [point, right=of cs1] {};
+\node (cs2) [block, right=of A3] {code of \bl{$cs_2$}};
+\node (A4) [point, right=of cs2] {};
+
+\only<2>{
+\draw (A1) edge [->, red, line width=1mm] (b);
+\draw (b) edge [->, red, line width=1mm] (cs1);
+\draw (cs1) edge [->, red, line width=1mm] (A3);
+\draw (A3) edge [->,skip loop] (A4);
+\node [below=of cs2] {\raisebox{-5mm}{\small{}jump}};}
+\only<3>{
+\draw (A1) edge [->, red, line width=1mm] (b);
+\draw (b) edge [->, red, line width=1mm] (A2);
+\draw (A2) edge [skip loop] (A3);
+\draw (A3) edge [->, red, line width=1mm] (cs2);
+\draw (cs2) edge [->,red, line width=1mm] (A4);
+\node [below=of cs1] {\raisebox{-5mm}{\small{}conditional jump}};}
+\end{tikzpicture}
+\end{center}
+
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{Conditional Jumps}
+
+\begin{minipage}{1.1\textwidth}
+\begin{itemize}
+\item \bl{if\_icmpeq $label$} if two ints are equal, then jump\medskip
+\item \bl{if\_icmpne $label$} if two ints aren't equal, then jump\medskip
+\item \bl{if\_icmpge $label$} if one int is greater or equal then another, then jump
+\item[]\ldots
+\end{itemize}
+\end{minipage}\pause
+
+
+\begin{center}
+\bl{\begin{tabular}{l}
+$L_1$:\\
+\hspace{5mm}if\_icmpeq\;$L_2$\\
+\hspace{5mm}iload 1\\
+\hspace{5mm}ldc 1\\
+\hspace{5mm}iadd\\
+\hspace{5mm}if\_icmpeq\;$L_1$\\
+$L_2$:
+\end{tabular}}
+\end{center}
+
+\begin{textblock}{3.5}(11,12)
+\only<3>{labels must be unique}
+\end{textblock}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[t]
+\frametitle{\begin{tabular}{c}Compiling BExps\end{tabular}}
+
+{\Large\bl{$a_1 = a_2$}}
+
+\begin{center}
+\bl{\begin{tabular}{lcl}
+$\text{compile}(a_1 = a_2, E, lab)$ & $\dn$\\ 
+\multicolumn{3}{l}{$\quad\text{compile}(a_1, E) \;@\;\text{compile}(a_2, E)\;@\; \text{if\_icmpne}\;lab$}
+\end{tabular}}
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c, fragile]
+\frametitle{Boolean Expressions}
+
+Compilation of boolean expressions:
+
+\begin{center}
+\begin{tikzpicture}[node distance=2mm and 4mm,
+ block/.style={rectangle, minimum size=1cm, draw=black, line width=1mm},
+ point/.style={rectangle, inner sep=0mm, minimum size=0mm, fill=red},
+ skip loop/.style={red, line width=1mm, to path={-- ++(0,-10mm) -| (\tikztotarget)}}]
+\node (A1) [point] {};
+\node (b) [block, right=of A1] {code of \bl{$b$}};
+\node (A2) [point, right=of b] {};
+\node (cs1) [block, right=of A2] {code of \bl{$cs_1$}};
+\node (A3) [point, right=of cs1] {};
+\node (cs2) [block, right=of A3] {code of \bl{$cs_2$}};
+\node (A4) [point, right=of cs2] {};
+
+\only<1>{
+\draw (A1) edge [->, red, line width=1mm] (b);
+\draw (b) edge [->, red, line width=1mm] (A2);
+\draw (A2) edge [skip loop] (A3);
+\draw (A3) edge [->, red, line width=1mm] (cs2);
+\draw (cs2) edge [->,red, line width=1mm] (A4);
+\node [below=of cs1] {\raisebox{-5mm}{\small{}conditional jump}};}
+\end{tikzpicture}
+\end{center}
+
+\begin{center}
+\begin{tabular}{lcl}
+\texttt{Bop("==", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpne...}\\
+\texttt{Bop("!=", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpeq...}\\
+\texttt{Bop("<", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpge...}\\
+\texttt{Bop("<=", a1, a2)} & $\Rightarrow$ & \texttt{...if\_icmpgt...}\\
+\end{tabular}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[t]
+\frametitle{\begin{tabular}{c}Compiling Ifs\end{tabular}}
+
+{\Large\bl{if $b$ then $cs_1$ else $cs_2$}}
+
+\begin{center}
+\bl{\begin{tabular}{lcl}
+$\text{compile}(\text{if}\;b\;\text{then}\; cs_1\;\text{else}\; cs_2, E)$ & $\dn$\\ 
+\multicolumn{3}{l}{$\quad l_{ifelse}\;$ \textcolor{black}{(fresh label)}}\\
+\multicolumn{3}{l}{$\quad l_{ifend}\;$ \textcolor{black}{(fresh label)}}\\
+\multicolumn{3}{l}{$\quad (is_1, E') = \text{compile}(cs_1, E)$}\\
+\multicolumn{3}{l}{$\quad (is_2, E'') = \text{compile}(cs_2, E')$}\\
+\multicolumn{3}{l}{$\quad(\text{compile}(b, E, l_{ifelse})$}\\
+\multicolumn{3}{l}{$\quad\phantom{(}@\;is_1$}\\
+\multicolumn{3}{l}{$\quad\phantom{(}@\; \text{goto}\;l_{ifend}$}\\
+\multicolumn{3}{l}{$\quad\phantom{(}@\;l_{ifelse}:$}\\
+\multicolumn{3}{l}{$\quad\phantom{(}@\;is_2$}\\
+\multicolumn{3}{l}{$\quad\phantom{(}@\;l_{ifend}:, E'')$}\\
+\end{tabular}}
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[t]
+\frametitle{\begin{tabular}{c}Compiling Whiles\end{tabular}}
+
+{\Large\bl{$\text{while}\;b\;\text{do}\;cs$}}\bigskip\bigskip
+
+\onslide<2->{Case }\only<2>{{\bf True}:}\only<3>{{\bf False}:}
+
+\begin{center}
+\begin{tikzpicture}[node distance=2mm and 4mm,
+ block/.style={rectangle, minimum size=1cm, draw=black, line width=1mm},
+ point/.style={rectangle, inner sep=0mm, minimum size=0mm, fill=red},
+ skip loop/.style={red, line width=1mm, to path={-- ++(0,-10mm) -| (\tikztotarget)}}]
+\node (A0) [point, left=of A1] {};
+\node (A1) [point] {};
+\node (b) [block, right=of A1] {code of \bl{$b$}};
+\node (A2) [point, right=of b] {};
+\node (cs1) [block, right=of A2] {code of \bl{$cs$}};
+\node (A3) [point, right=of cs1] {};
+\node (A4) [point, right=of A3] {};
+
+\only<2>{
+\draw (A0) edge [->, red, line width=1mm] (b);
+\draw (b) edge [->, red, line width=1mm] (cs1);
+\draw (cs1) edge [->, red, line width=1mm] (A3);
+\draw (A3) edge [->,skip loop] (A1);}
+\only<3>{
+\draw (A0) edge [->, red, line width=1mm] (b);
+\draw (b) edge [->, red, line width=1mm] (A2);
+\draw (A2) edge [skip loop] (A3);
+\draw (A3) edge [->, red, line width=1mm] (A4);}
+\end{tikzpicture}
+\end{center}
+
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[t]
+\frametitle{\begin{tabular}{c}Compiling Whiles\end{tabular}}
+
+{\Large\bl{while $b$ do $cs$}}
+
+\begin{center}
+\bl{\begin{tabular}{lcl}
+$\text{compile}(\text{while}\; b\; \text{do} \;cs, E)$ & $\dn$\\ 
+\multicolumn{3}{l}{$\quad l_{wbegin}\;$ \textcolor{black}{(fresh label)}}\\
+\multicolumn{3}{l}{$\quad l_{wend}\;$ \textcolor{black}{(fresh label)}}\\
+\multicolumn{3}{l}{$\quad (is, E') = \text{compile}(cs_1, E)$}\\
+\multicolumn{3}{l}{$\quad(l_{wbegin}:$}\\
+\multicolumn{3}{l}{$\quad\phantom{(}@\;\text{compile}(b, E, l_{wend})$}\\
+\multicolumn{3}{l}{$\quad\phantom{(}@\;is$}\\
+\multicolumn{3}{l}{$\quad\phantom{(}@\; \text{goto}\;l_{wbegin}$}\\
+\multicolumn{3}{l}{$\quad\phantom{(}@\;l_{wend}:, E')$}\\
+\end{tabular}}
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[t]
+\frametitle{\begin{tabular}{c}Compiling Writes\end{tabular}}
+
+{\Large\bl{write $x$}}
+
+\begin{center}
+\small\bl{\begin{tabular}{l}
+.method public static write(I)V\hspace{1cm}\textcolor{black}{(library function)}\\ 
+\;\;    .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\bigskip\bigskip\\
+%
+\normalsize
+iload $E(x)$\\
+invokestatic write(I)V\\
+\end{tabular}}
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+
+\begin{center}
+\small\bl{\begin{tabular}{l}
+.class public XXX.XXX\\
+.super java/lang/Object\\
+\\
+.method public <init>()V\\
+\;\;     aload\_0\\
+\;\;     invokenonvirtual java/lang/Object/<init>()V\\
+ \;\;    return\\
+.end method\\
+\\
+.method public static main([Ljava/lang/String;)V\\
+\;\;   .limit locals 200\\
+\;\;     .limit stack 200\\
+\\
+   \textcolor{black}{(here comes the compiled code)}\\
+\\
+\;\;     return\\
+.end method\\
+\end{tabular}}
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Next Compiler Phases\end{tabular}}
+
+\begin{itemize}
+\item assembly $\Rightarrow$ byte code (class file)
+\item labels $\Rightarrow$ absolute or relative jumps\bigskip\bigskip
+\item \texttt{javap} is a disassembler for class files
 \end{itemize}
 
 \end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[t]
+\frametitle{\begin{tabular}{c}Compiled Code\end{tabular}}
+
+\begin{center}
+\begin{tikzpicture}
+\begin{axis}[axis x line=bottom, axis y line=left, xlabel=n, ylabel=secs, legend style=small]
+\addplot+[smooth] file {compiled.data};
+\end{axis}
+\end{tikzpicture}
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[t]
+\frametitle{\begin{tabular}{c}Compiler vs.~Interpreter\end{tabular}}
+
+\begin{center}
+\begin{tikzpicture}
+\begin{axis}[axis x line=bottom, axis y line=left, ylabel=secs,
+    xlabel=n,
+    enlargelimits=0.05,
+    ybar interval=0.7, legend style=small]
+\addplot file {interpreted2.data};
+\addplot file {compiled2.data};
+%\legend{interpreted, compiled}
+\end{axis}
+\end{tikzpicture}
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{Backend}
+
+\begin{center}
+\begin{tikzpicture}
+\node (rexp)  {\bl{\bf Lexer}};
+\node (nfa) [right=of rexp] {\bl{\bf Parser}};
+\node (dfa) [right=of nfa] {\bl{\begin{tabular}{c}\bf Optimizations\end{tabular}}};
+\path[->, red, line width=2mm] (rexp) edge node [above=4mm, black] {\begin{tabular}{c@{\hspace{9mm}}}token\\[-1mm]
+sequence\end{tabular}} (nfa);
+\node (final) [below=of dfa] {\bl{\begin{tabular}{c}\bf Machine Code/\\\bf Byte Code\end{tabular}}};
+\path[->, red, line width=2mm] (nfa) edge node [above=4mm, black] {\begin{tabular}{c}parse\\[-1mm] tree
+\end{tabular}}(dfa);
+\path[->, red, line width=2mm] (dfa) edge (final);
+\end{tikzpicture}\\
+\end{center}
+
+\end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[t]
+\frametitle{\begin{tabular}{c}What Next\end{tabular}}
+
+\begin{itemize}
+\item register spilling
+\item dead code removal
+\item loop optimisations
+\item instruction selection
+\item type checking
+\item concurrency
+\item fuzzy testing
+\item verification\bigskip\\
+
+\item GCC, LLVM, tracing JITs
+\end{itemize}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
+
 
 \end{document}