% !TEX program = xelatex
\documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer}
\usepackage{../slides}
\usepackage{../langs}
\usepackage{../data}
\usepackage{../graphics}
\usepackage{../grammar}
% beamer stuff
\renewcommand{\slidecaption}{CFL 07, King's College London}
\newcommand{\bl}[1]{\textcolor{blue}{#1}}
\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{%
\begin{tabular}{@ {}c@ {}}
\\[-3mm]
\LARGE Compilers and \\[-2mm]
\LARGE Formal Languages\\[3mm]
\end{tabular}}
\normalsize
\begin{center}
\begin{tabular}{ll}
Email: & christian.urban at kcl.ac.uk\\
%Office Hours: & Thursdays 12 -- 14\\
%Location: & N7.07 (North Wing, Bush House)\\
Slides \& Progs: & KEATS (also homework is there)\\
\end{tabular}
\end{center}
\begin{center}
\begin{tikzpicture}
\node[drop shadow,fill=white,inner sep=0pt]
{\footnotesize\rowcolors{1}{capri!10}{white}
\begin{tabular}{|p{4.8cm}|p{4.8cm}|}\hline
1 Introduction, Languages & 6 While-Language \\
2 Regular Expressions, Derivatives & \cellcolor{blue!50} 7 Compilation, JVM \\
3 Automata, Regular Languages & 8 Compiling Functional Languages \\
4 Lexing, Tokenising & 9 Optimisations \\
5 Grammars, Parsing & 10 LLVM \\ \hline
\end{tabular}%
};
\end{tikzpicture}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Bird's Eye View}
\mbox{}\\[-16mm]\mbox{}
\begin{center}
\begin{tikzpicture}[scale=1,
node/.style={
rectangle,rounded corners=3mm,
very thick,draw=black!50,
minimum height=18mm, minimum width=20mm,
top color=white,bottom color=black!20,drop shadow}]
\node (0) at (-2.3,0) {};
\node (A) at (0,0) [node] {};
\node [below right] at (A.north west) {lexer};
\node (B) at (3,0) [node] {};
\node [below right=1mm] at (B.north west)
{\mbox{}\hspace{-1mm}parser};
\node (C) at (6,0) [node] {};
\node [below right] at (C.north west)
{\mbox{}\hspace{-1mm}code gen};
\node (1) at (8.4,0) {};
\draw [->,line width=4mm] (0) -- (A);
\draw [->,line width=4mm] (A) -- (B);
\draw [->,line width=4mm] (B) -- (C);
\draw [->,line width=4mm] (C) -- (1);
\end{tikzpicture}
\end{center}\pause
\begin{center}
\begin{tikzpicture}[scale=1,font=\bf,
node/.style={
rectangle,rounded corners=3mm,
ultra thick,draw=black!50,minimum height=18mm,
minimum width=20mm,
top color=white,bottom color=black!20}]
\node (0) at (-3,0) {};
\node (A) at (0,0) [node,text width=1.6cm,text centered] {\small{}our compiler};
\node (B) at (3.5,0) [node,text width=1.6cm,text centered] {\small{}Jasmin / Krakatau};
\node (C) at (7.5,0) [node] {JVM};
\draw [->,line width=2.5mm] (0) -- node [above,pos=0.35] {*.while} (A);
\draw [->,line width=2.5mm] (A) -- node [above,pos=0.35] {*.j} (B);
\draw [->,line width=2.5mm] (B) -- node [above,pos=0.35] {*.class} (C);
\end{tikzpicture}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Test Program}
\mbox{}\\[-18mm]\mbox{}
{\lstset{language=While}\fontsize{10}{12}\selectfont
\texttt{\lstinputlisting{../progs/while-tests/loops.while}}}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\begin{textblock}{10}(0.5,0.5)
\LARGE
\fontspec{Hoefler Text Black}
\textcolor{ProcessBlue}{JVM\\ Code}
\\[12mm]
\normalsize
Jasmin\\
Krakatau\\
ASM lib
\end{textblock}
\fontsize{8}{10}\selectfont
%\footnotesize
\mbox{}\\[-13mm]\mbox{}
\begin{columns}
\begin{column}{2cm}
\lstinputlisting[numbers=none]{../progs/appHa.j}
\end{column}
\begin{column}{2cm}
\lstinputlisting[numbers=none]{../progs/appHb.j}
\end{column}
\end{columns}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \begin{frame}[t]
% \begin{center}
% \bl{\begin{tabular}{@{}lcl@{}}
% \\[-12mm]
% \meta{Stmt} & $::=$ & $\texttt{skip}$\\
% & $|$ & \textit{Id}\;\texttt{:=}\;\meta{AExp}\\
% & $|$ & \texttt{if}\; \meta{BExp} \;\texttt{then}\; \meta{Block} \;\texttt{else}\; \meta{Block}\\
% & $|$ & \texttt{while}\; \meta{BExp} \;\texttt{do}\; \meta{Block}\\
% & $|$ & \texttt{read}\;\textit{Id}\\
% & $|$ & \texttt{write}\;\textit{Id}\\
% & $|$ & \texttt{write}\;\textit{String}\medskip\\
% \meta{Stmts} & $::=$ & \meta{Stmt} \;\texttt{;}\; \meta{Stmts}\\
% & $|$ & \meta{Stmt}\medskip\\
% \meta{Block} & $::=$ & \texttt{\{}\,\meta{Stmts}\,\texttt{\}}\\
% & $|$ & \meta{Stmt}\medskip\\
% \meta{AExp} & $::=$ & \ldots\\
% \meta{BExp} & $::=$ & \ldots\\
% \end{tabular}}
% \end{center}
% \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}
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \begin{frame}[c]
% \frametitle{Interpreter}
% \begin{center}
% \bl{\begin{tabular}{@{}lcl@{}}
% $\text{eval}(n, E)$ & $\dn$ & $n$\\
% $\text{eval}(x, E)$ & $\dn$ & $E(x)$ \;\;\;\textcolor{black}{lookup \bl{$x$} in \bl{$E$}}\\
% $\text{eval}(a_1 + a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) + \text{eval}(a_2, E)$\\
% $\text{eval}(a_1 - a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) - \text{eval}(a_2, E)$\\
% $\text{eval}(a_1 * a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) * \text{eval}(a_2, E)$\bigskip\\
% $\text{eval}(a_1 = a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) = \text{eval}(a_2, E)$\\
% $\text{eval}(a_1\,!\!= a_2, E)$ & $\dn$ & $\neg(\text{eval}(a_1, E) = \text{eval}(a_2, E))$\\
% $\text{eval}(a_1 < a_2, E)$ & $\dn$ & $\text{eval}(a_1, E) < \text{eval}(a_2, E)$\
% \end{tabular}}
% \end{center}
% \end{frame}
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \begin{frame}[c]
% \frametitle{Interpreter (2)}
% \begin{center}
% \bl{\begin{tabular}{@{}lcl@{}}
% $\text{eval}(\text{skip}, E)$ & $\dn$ & $E$\\
% $\text{eval}(x:=a, E)$ & $\dn$ & \bl{$E(x \mapsto \text{eval}(a, E))$}\\
% \multicolumn{3}{@{}l@{}}{$\text{eval}(\text{if}\;b\;\text{then}\;cs_1\;\text{else}\;cs_2 , E) \dn$}\\
% \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{if}\;\text{eval}(b,E)\;\text{then}\;
% \text{eval}(cs_1,E)$}\\
% \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\phantom{\text{if}\;\text{eval}(b,E)\;}\text{else}\;\text{eval}(cs_2,E)$}\\
% \multicolumn{3}{@{}l@{}}{$\text{eval}(\text{while}\;b\;\text{do}\;cs, E) \dn$}\\
% \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{if}\;\text{eval}(b,E)$}\\
% \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{then}\;
% \text{eval}(\text{while}\;b\;\text{do}\;cs, \text{eval}(cs,E))$}\\
% \multicolumn{3}{@{}l@{}}{\hspace{2cm}$\text{else}\; E$}\\
% $\text{eval}(\text{write}\; x, E)$ & $\dn$ & $\{\;\text{println}(E(x))\; ;\;E\;\}$\\
% \end{tabular}}
% \end{center}
% \end{frame}
% %%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \begin{frame}[c]
% \frametitle{Test Program}
% \mbox{}\\[-18mm]\mbox{}
% {\lstset{language=While}\fontsize{10}{12}\selectfont
% \texttt{\lstinputlisting{../progs/while-tests/loops.while}}}
% \end{frame}
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \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{Interpreted Code}
%
%\begin{center}
%\begin{tikzpicture}
%\begin{axis}[axis x line=bottom, axis y line=left, xlabel=n, ylabel=secs, legend style=small]
%\addplot+[smooth] file {interpreted.data};
%\end{axis}
%\end{tikzpicture}
%\end{center}
%
%\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[c]
%\frametitle{Java Virtual Machine}
%
%\begin{itemize}
%\item introduced in 1995
%\item is a stack-based VM (like Postscript, CLR of .Net)
%\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 compiled to the JVM: Scala, Clojure\ldots
%\end{itemize}
%
%\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t,fragile]
\frametitle{Compiling AExps}
For example \textbf{\bl{1 + ((2 * 3) + (4 - 3))}}:\medskip
\begin{columns}[T]
\begin{column}{.3\textwidth}
\begin{center}
\bl{\begin{tikzpicture}
\tikzset{level distance=12mm,sibling distance=4mm}
\tikzset{edge from parent/.style={draw,very thick}}
\Tree [.$+$ [.$1$ ] [.$+$ [.$*$ $2$ $3$ ] [.$-$ $4$ $3$ ]]]
\end{tikzpicture}}
\end{center}
\end{column}
\begin{column}{.3\textwidth}
\begin{lstlisting}[language=JVMIS,numbers=none]
ldc 1
ldc 2
ldc 3
imul
ldc 4
ldc 3
isub
iadd
iadd
\end{lstlisting}
\end{column}
\end{columns}\bigskip
\small
Traverse tree in post-order \bl{$\Rightarrow$} code for
stack-machine
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t,fragile]
\frametitle{Compiling AExps}
\liningnums{\textbf{\Large\bl{(1 + 2) + 3}}}
\begin{lstlisting}[language=JVMIS,numbers=none,xleftmargin=6cm]
ldc 1
ldc 2
iadd
ldc 3
iadd
\end{lstlisting}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t,fragile]
\frametitle{Compiling AExps}
\liningnums{\textbf{\Large\bl{1 + (2 + 3)}}}
\begin{lstlisting}[language=JVMIS,numbers=none,xleftmargin=6cm]
ldc 1
ldc 2
ldc 3
iadd
iadd
\end{lstlisting}
\bigskip\pause
\vfill
\textcolor{codepurple}{\textbf{\texttt{dadd}}},
\textcolor{codepurple}{\textbf{\texttt{fadd}}},
\textcolor{codepurple}{\textbf{\texttt{ladd}}}, \ldots
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Compiling AExps}
\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}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t,fragile]
\frametitle{\begin{tabular}{c}Compiling AExps\end{tabular}}
\liningnums{\textbf{\Large\bl{1 $+$ 2 $*$ 3 $+$ (4 $-$ 3)}}}
\begin{lstlisting}[language=JVMIS,numbers=none,xleftmargin=6cm]
ldc 1
ldc 2
ldc 3
imul
ldc 4
ldc 3
isub
iadd
iadd
\end{lstlisting}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Variables}
\liningnums{\textbf{\Large\bl{x $:=$ 5 $+$ y $*$ 2}}}\bigskip\pause
\begin{itemize}
\item lookup: \bl{$\textcolor{codepurple}{\textbf{\texttt{iload}}}\; index$}
\item store: \bl{$\textcolor{codepurple}{\textbf{\texttt{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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Compiling AExps}
\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}
\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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c,fragile]
\frametitle{Compiling Assignments}
\liningnums{\textbf{\Large\bl{x $:=$ x $+$ 1}}}
\begin{lstlisting}[language=JVMIS,numbers=none,xleftmargin=6cm]
iload /*@\bl{$n_x$}@*/
ldc 1
iadd
istore /*@\bl{$n_x$}@*/
\end{lstlisting}\medskip
where \bl{$n_x$} is the index corresponding to the variable~\bl{$x$}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Compiling Ifs}
{\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,fragile]
\frametitle{Conditional Jumps}
\begin{minipage}{1.1\textwidth}
\begin{itemize}
\item \textcolor{codepurple}{\textbf{\texttt{if\_icmpeq}}} \bl{$label$}
if two ints are equal, then jump\medskip
\item \textcolor{codepurple}{\textbf{\texttt{if\_icmpne}}} \bl{$label$}
if two ints aren't equal, then jump\medskip
\item \textcolor{codepurple}{\textbf{\texttt{if\_icmpge}}} \bl{$label$}
if one int is greater or equal then another, then jump
\item[]\ldots
\end{itemize}
\end{minipage}\pause
\begin{lstlisting}[language=JVMIS,numbers=none,xleftmargin=2cm]
/*@\bl{$L_1$:}@*/
if_icmpeq /*@\bl{$L_2$}@*/
iload 1
ldc 1
iadd
if_icmpeq /*@\bl{$L_1$}@*/
/*@\bl{$L_2$:}@*/
\end{lstlisting}
\begin{textblock}{3.5}(11,12)
\only<3>{labels must be unique}
\end{textblock}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c,fragile]
\frametitle{Compiling Ifs}
For example
\begin{lstlisting}[mathescape,numbers=none,language=While]
if 1 = 1 then x := 2 else y := 3
\end{lstlisting}
\begin{center}
\begin{lstlisting}[mathescape,language=JVMIS,numbers=none]
ldc 1
ldc 1
if_icmpne L_ifelse $\quad\tikz[remember picture] \node (C) {\mbox{}};$
ldc 2
istore 0
goto L_ifend $\quad\tikz[remember picture] \node (A) {\mbox{}};$
L_ifelse: $\quad\tikz[remember picture] \node[] (D) {\mbox{}};$
ldc 3
istore 1
L_ifend: $\quad\tikz[remember picture] \node[] (B) {\mbox{}};$
\end{lstlisting}
\end{center}
\begin{tikzpicture}[remember picture,overlay]
\draw[->,very thick] (A) edge [->,to path={-- ++(10mm,0mm)
-- ++(0mm,-17.3mm) |- (\tikztotarget)},line width=1mm] (B.east);
\draw[->,very thick] (C) edge [->,to path={-- ++(10mm,0mm)
-- ++(0mm,-17.3mm) |- (\tikztotarget)},line width=1mm] (D.east);
\end{tikzpicture}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Compiling BExps}
{\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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Compiling Ifs}
{\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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Compiling Whiles}
{\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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Compiling Whiles}
{\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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c,fragile]
\frametitle{Compiling Whiles}
For example
\begin{lstlisting}[mathescape,numbers=none,language=While]
while x <= 10 do x := x + 1
\end{lstlisting}
\begin{center}
\begin{lstlisting}[mathescape,language=JVMIS,numbers=none]
L_wbegin: $\quad\tikz[remember picture] \node[] (LB) {\mbox{}};$
iload 0
ldc 10
if_icmpgt L_wend $\quad\tikz[remember picture] \node (LC) {\mbox{}};$
iload 0
ldc 1
iadd
istore 0
goto L_wbegin $\quad\tikz[remember picture] \node (LA) {\mbox{}};$
L_wend: $\quad\tikz[remember picture] \node[] (LD) {\mbox{}};$
\end{lstlisting}
\end{center}
\begin{tikzpicture}[remember picture,overlay]
\draw[->,very thick] (LA) edge [->,to path={-- ++(12mm,0mm)
-- ++(0mm,17.3mm) |- (\tikztotarget)},line width=1mm] (LB.east);
\draw[->,very thick] (LC) edge [->,to path={-- ++(12mm,0mm)
-- ++(0mm,-17.3mm) |- (\tikztotarget)},line width=1mm] (LD.east);
\end{tikzpicture}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c,fragile]
\frametitle{Compiling Writes}
\small
\begin{lstlisting}[language=JVMIS,mathescape,
numbers=none,xleftmargin=-6mm]
.method public static write(I)V
.limit locals 1
.limit stack 2
getstatic java/lang/System/out
Ljava/io/PrintStream;
iload 0
invokevirtual java/io/PrintStream/println(I)V
return
.end method
iload $E(x)$
invokestatic XXX/XXX/write(I)V
\end{lstlisting}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c,fragile]
\frametitle{Compiling Main}
\footnotesize
\begin{lstlisting}[language=JVMIS,mathescape,
numbers=none,xleftmargin=-6mm]
.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
$\textit{\ldots{}here comes the compiled code\ldots}$
return
.end method
\end{lstlisting}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Next Compiler Phases}
\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
\item jasmin and krakatau are assemblers for jvm code
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Recall: Interpreted Code}
\begin{center}
\begin{tikzpicture}
\begin{axis}[axis x line=bottom, axis y line=left, xlabel=n, ylabel=secs, legend style=small]
\addplot+[smooth] file {interpreted.data};
\end{axis}
\end{tikzpicture}
\end{center}
Loop program
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Compiled Code}
\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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Compiler vs.~Interpreter}
\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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{A ``Compiler'' for BF*** to C}
\begin{center}
\begin{tabular}{lcl}
\bl{\texttt{>}} & $\Rightarrow$ & \texttt{ptr++}\\
\bl{\texttt{<}} & $\Rightarrow$ & \texttt{ptr--}\\
\bl{\texttt{+}} & $\Rightarrow$ & \texttt{(*ptr)++}\\
\bl{\texttt{-}} & $\Rightarrow$ & \texttt{(*ptr)--}\\
\bl{\texttt{.}} & $\Rightarrow$ & \texttt{putchar(*ptr)}\\
\bl{\texttt{,}} & $\Rightarrow$ & \texttt{*ptr = getchar()}\\
\bl{\texttt{[}} & $\Rightarrow$ & \texttt{while(*ptr)\{}\\
\bl{\texttt{]}} & $\Rightarrow$ & \texttt{\}}\medskip\\
& $\Rightarrow$ & ignore everything else\\
\end{tabular}
\end{center}\bigskip
\texttt{char field[30000]\\ char *ptr = \&field[15000]}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c,fragile]
\frametitle{BF***}
we need some big array, say \texttt{arr} and 7 (8) instructions:\medskip
\begin{itemize}
\item \texttt{>} move \texttt{ptr++}
\item \texttt{<} move \texttt{ptr-{}-}
\item \texttt{+} add \texttt{arr[ptr]++}
\item \texttt{-} subtract \texttt{arr[ptr]-{}-}
\item \texttt{.} print out \texttt{arr[ptr]} as ASCII
\item \texttt{[} if \texttt{arr[ptr] == 0} jump just after the corresponding \texttt{]}; otherwise \texttt{ptr++}
\item \texttt{]} if \texttt{arr[ptr] != 0} jump just after the corresponding \texttt{[}; otherwise \texttt{ptr++}
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c,fragile]
\frametitle{Arrays in While}
\begin{itemize}
\item \texttt{new arr[15000]}\medskip
\item \texttt{x := 3 + arr[3 + y]}\medskip
\item \texttt{arr[42 * n] := ...}
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c,fragile]
\frametitle{New Arrays}
\begin{lstlisting}[mathescape,numbers=none,language=While]
new arr[number]
\end{lstlisting}\bigskip\bigskip
\begin{lstlisting}[mathescape,numbers=none,language=JVMIS]
ldc number
newarray int
astore loc_var
\end{lstlisting}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c,fragile]
\frametitle{Array Update}
\begin{lstlisting}[mathescape,numbers=none,language=While]
arr[...] :=
\end{lstlisting}\bigskip\bigskip
\begin{lstlisting}[mathescape,numbers=none,language=JVMIS]
aload loc_var
index_aexp
value_aexp
iastore
\end{lstlisting}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c,fragile]
\frametitle{Array Lookup in AExp}
\begin{lstlisting}[mathescape,numbers=none,language=While]
...arr[...]...
\end{lstlisting}\bigskip\bigskip
\begin{lstlisting}[mathescape,numbers=none,language=JVMIS]
aload loc_var
index_aexp
iaload
\end{lstlisting}
\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 is 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}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: