\documentclass[dvipsnames,14pt,t,xelatex]{beamer}

\usepackage{../slides}

\usepackage{../graphics}

\usepackage{../langs}

\usepackage{../data}

\hfuzz=220pt 

\lstset{language=Scala,

        style=mystyle,

        numbersep=0pt,

        numbers=none,

        xleftmargin=0mm}

\newcommand{\bl}[1]{\textcolor{blue}{#1}}     

% beamer stuff 

\renewcommand{\slidecaption}{CFL 01, King's College London}

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[t]

\frametitle{%  

  \begin{tabular}{@ {}c@ {}}

  \\[-3mm]

  \LARGE Compilers and \\[-1mm] 

  \LARGE Formal Languages (1)\\[-3mm] 

  \end{tabular}}

  \begin{center}

  %\includegraphics[scale=0.3]{pics/ante1.jpg}\hspace{5mm}

  %\includegraphics[scale=0.31]{pics/ante2.jpg}\\

  %\footnotesize\textcolor{gray}{Antikythera automaton, 100 BC (Archimedes?)}

  \end{center}

  \normalsize

  \begin{center}

  \begin{tabular}{ll}

  Email:  & christian.urban at kcl.ac.uk\\

  Office: & N\liningnums{7.07} (North Wing, Bush House)\\

  Slides: & KEATS

  \end{tabular}

  \end{center}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[t]

\frametitle{Why Study Compilers?}

John Regehr {\small(Univ.~Utah, LLVM compiler hacker)}\smallskip\\

\begin{bubble}[10.5cm]

  \bf ``\ldots{}It’s effectively a perpetual

  employment act for solid compiler hackers.''

\end{bubble}

\onslide<1->{

\only<2>{

\begin{itemize}

\item {\bf Hardware is getting weirder

  rather than getting clocked faster}

\begin{itemize}

\item  Almost all processors are

  multicores nowadays and it looks like there is increasing asymmetry in

  resources across cores. Processors come with vector units, crypto

  accelerators etc. We have DSPs, GPUs,

  ARM big.little, and Xeon Phi. This is only scratching the

  surface.

\end{itemize}  

\end{itemize}}

\only<3>{

\begin{itemize}

\item {\bf We’re getting tired of low-level languages and

    their associated security disasters}

\begin{itemize}

\item 

  We want to write new code, to

  whatever extent possible, in safer, higher-level

  languages. Compilers are caught right in the middle of these

  opposing trends: one of their main jobs is to help bridge the large

  and growing gap between increasingly high-level languages and

  increasingly wacky platforms.

\end{itemize}  

\end{itemize}}}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\frametitle{Why Bother?}

\begin{columns}[t]

\begin{column}{.5\textwidth}

Ruby, Python, Java 8\medskip\\

\begin{tikzpicture}\footnotesize

\begin{axis}[

    xlabel={$n$},

    x label style={at={(1.05,0.0)}},

    ylabel={time in secs},

    enlargelimits=false,

    xtick={0,5,...,30},

    xmax=33,

    ymax=35,

    ytick={0,5,...,30},

    scaled ticks=false,

    axis lines=left,

    width=5.5cm,

    height=4cm, 

    legend entries={Python,Ruby},  

    legend pos=north west,

    legend cell align=left]

\addplot[blue,mark=*, mark options={fill=white}] table {re-python.data};

\addplot[brown,mark=triangle*, mark options={fill=white}] table {re-ruby.data};

\end{axis}

\end{tikzpicture}

\begin{tikzpicture}\footnotesize

\begin{axis}[

    xlabel={$n$},

    x label style={at={(1.05,0.0)}},

    ylabel={time in secs},

    enlargelimits=false,

    xtick={0,5,...,30},

    xmax=33,

    ymax=35,

    ytick={0,5,...,30},

    scaled ticks=false,

    axis lines=left,

    width=5.5cm,

    height=4cm, 

    legend entries={Python, Java 8},  

    legend pos=north west,

    legend cell align=left]

\addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};   

\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};

\end{axis}

\end{tikzpicture}

\end{column}

\begin{column}{.5\textwidth}

Us (after next lecture)\medskip\\

\begin{tikzpicture}\footnotesize

\begin{axis}[

    xlabel={$n$},

    x label style={at={(1.07,0.0)}},

    ylabel={time in secs},

    enlargelimits=false,

    xtick={0,5000,...,10000},

    xmax=11000,

    ymax=35,

    ytick={0,5,...,30},

    scaled ticks=false,

    axis lines=left,

    width=5.5cm,

    height=4cm]

\addplot[green,mark=square*,mark options={fill=white}] table {re2.data};

\addplot[black,mark=square*,mark options={fill=white}] table {re3.data};

\end{axis}

\end{tikzpicture}

\begin{tikzpicture}\footnotesize

\begin{axis}[

    xlabel={$n$},

    x label style={at={(1.07,0.0)}},

    ylabel={time in secs},

    enlargelimits=false,

    ymax=35,

    ytick={0,5,...,30},

    scaled ticks=false,

    axis lines=left,

    width=5.5cm,

    height=4cm]

\addplot[black,mark=square*,mark options={fill=white}] table {re3a.data};

\end{axis}

\end{tikzpicture}

\end{column}

\end{columns}\bigskip

\small\centering

matching \texttt{[a?]\{n\}[a]\{n\}} and \texttt{(a*)*b}

against $\underbrace{\texttt{a}...\texttt{a}}_n$

\end{frame} 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\frametitle{Evil Regular Expressions}

\begin{itemize}

\item \alert{R}egular \alert{e}xpression \alert{D}enial \alert{o}f \alert{S}ervice (ReDoS)\medskip

\item Evil regular expressions\medskip

\begin{itemize}

\item \bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$}

\item \bl{$(a^*)^*\cdot b$}

\item \bl{$([a$\,-\,$z]^+)^*$}

\item \bl{$(a + a \cdot a)^*$}

\item \bl{$(a + a^?)^*$}

\end{itemize}

\item sometimes also called \alert{catastrophic backtracking}

\item this is a problem for \alert{N}etwork \alert{I}ntrusion

  \alert{D}etection systems, StackExchange, Atom editor

\item \url{https://vimeo.com/112065252}  

\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\frametitle{The Goal of this Module}

\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}]

  \node at (3.05, 1.8) {\Large\bf write a compiler};

  \node (0) at (-2.3,0) {};  

  \node [above=5mm of 0]

  {\makebox[0mm]{\footnotesize

      \begin{tabular}{@{}l@{}}input\\[-1mm]program\end{tabular}}}; 

  \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) {};

  \node [above=5mm of 1]

  {\makebox[0mm]{\footnotesize

      \begin{tabular}{@{}r@{}}binary\\[-1mm]code\end{tabular}}};

  \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}

\only<2,3,4>{

\begin{textblock}{1}(1,2.1)

\begin{bubble}[9.8cm]

\normalsize

lexer input: a string\smallskip\\

\hspace{5mm}\code{"read(n);"}\medskip\\

lexer output: a sequence of tokens\smallskip\\

\hspace{5mm}\code{key(read) lpar id(n) rpar semi}

\end{bubble}

\end{textblock}}

\only<3,4>{

\begin{textblock}{1}(6,7.8)

\begin{tabular}{c}

\includegraphics[scale=0.2]{../pics/rosetta.jpg}\\[-2mm]

\footnotesize lexing $\Rightarrow$ recognising words (Stone of Rosetta)

\end{tabular}

\end{textblock}}

\only<4>{

\begin{textblock}{1}(0.5,12)\small

\begin{tabular}{l@{}c@{}l}

  \pcode{if}    & $\;\Rightarrow\;$ & keyword\\

  \pcode{iffoo} & $\;\Rightarrow\;$ & identifier\\

\end{tabular}  

\end{textblock}}

\only<5>{

\begin{textblock}{1}(1,1.5)

\begin{bubble}[8.5cm]

\normalsize

parser input: a sequence of tokens\smallskip\\

{\small\hspace{5mm}\code{key(read) lpar id(n) rpar semi}}\smallskip\\

parser output: an abstract syntax tree\smallskip\\

\footnotesize

\hspace{2cm}\begin{tikzpicture}

  \node {\code{read}}

    child {node {\code{lpar}}}

    child {node {\code{n}}}

    child {node {\code{rpar}}};

\end{tikzpicture}

\end{bubble}

\end{textblock}}

\only<6,7>{

\begin{textblock}{1}(1,1.5)

\begin{bubble}[4cm]

\normalsize

code generator:\smallskip\\

\hspace{5mm}\code{istore 2}\\ 

\hspace{5mm}\code{iload 2}\\ 

\hspace{5mm}\code{ldc 10}\\

\hspace{5mm}\code{isub}\\

\hspace{5mm}\code{ifeq Label2}\\ 

\hspace{5mm}\code{iload 2}\\

\hspace{5mm}\code{...}\\

\end{bubble}

\end{textblock}}

\only<7>{

\begin{textblock}{6}(8.4,7)

\begin{bubble}[5cm]

\mbox{\begin{tikzpicture}[scale=0.58,rounded corners=0mm]

\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{bubble}

\end{textblock}}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\frametitle{The Acad.~Subject is Mature}

\begin{itemize}

\item Turing Machines, 1936

\item Regular Expressions, 1956\\

\item The first compiler for COBOL, 1957\\ (Grace Hopper)

\item But surprisingly research papers are still published nowadays\\

\item ``Parsing: The Solved Problem That Isn't''

\end{itemize}

\begin{flushright}

\includegraphics[scale=0.3]{pics/hopper.jpg}\\

\footnotesize\textcolor{gray}{Grace Hopper}

\end{flushright}

\begin{flushright}

\mbox{}\\[-6mm]

{\footnotesize\textcolor{gray}{(she made it to David Letterman's Tonight Show,\\[-2mm]

 \url{http://www.youtube.com/watch?v=aZOxtURhfEU})}}

\end{flushright}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\frametitle{Lectures 1 - 5}

transforming strings into structured data\\[10mm]

{\LARGE\bf Lexing} {\hfill{}based on regular expressions}\medskip\\

\hspace{5mm}(recognising ``words'')\\[6mm]

{\LARGE\bf Parsing}\medskip\\

\hspace{5mm}(recognising ``sentences'')

\begin{textblock}{1}(10,9.1)

\begin{tabular}{c}

\includegraphics[scale=0.1]{../pics/rosetta.jpg}\\[-2mm]

\footnotesize Stone of Rosetta

\end{tabular}

\end{textblock}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[t]

\frametitle{Familiar Regular Expr.}

\small

\begin{center}

\texttt{[a-z0-9\_$\backslash{}$.-]+ @ [a-z0-9$\backslash{}$.-]+ . [a-z$\backslash{}$.]\{2,6\}}

\end{center}\smallskip

\begin{center}

\begin{tabular}{@{}lp{8.5cm}@{}}

\pcode{re*} & matches 0 or more times\\

\pcode{re+} & matches 1 or more times\\

\pcode{re?} & matches 0 or 1 times\\

\pcode{re\{n\}}	& matches exactly \pcode{n} number of times\\

\pcode{re\{n,m\}} & matches at least \pcode{n} and at most {\tt m} times\\

\pcode{[...]} & matches any single character inside the brackets\\

\pcode{[^...]} & matches any single character not inside the 

brackets\\

\pcode{a-z A-Z} & character ranges\\

\pcode{\\d} & matches digits; equivalent to \pcode{[0-9]}\\

\pcode{.} & matches every character except newline\\

\pcode{(re)}	& groups regular expressions and remembers 

the matched text

\end{tabular}

\end{center}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\frametitle{Today}

\begin{itemize}

\item While the ultimate goal is to implement a small compiler for the JVM

  \ldots\bigskip

\end{itemize}

Let's start with:

\begin{itemize}

\item a web-crawler

\item an email harvester

%\item \textcolor{gray}{(a web-scraper)}

\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[t]

\frametitle{A Web-Crawler}

\mbox{}\\[10mm]

\begin{enumerate}

\item given an URL, read the corresponding webpage

\item extract all links from it

\item call the web-crawler again for all these links

\end{enumerate}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[t]

\frametitle{A Web-Crawler}

\mbox{}\\[10mm]

\begin{enumerate}

\item given an URL, read the corresponding webpage

\item if not possible print, out a problem

\item if possible, extract all links from it

\item call the web-crawler again for all these links

\end{enumerate}\bigskip\pause

\small (we need a bound for the number of recursive calls)

\small (the purpose is to check all links on my own webpage)

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\begin{textblock}{1}(2,5)

\begin{tabular}{c}

\includegraphics[scale=0.15]{pics/servers.png}\\[-2mm]

\small Server

\end{tabular}

\end{textblock}

\begin{textblock}{1}(5.6,4)

  \begin{tikzpicture}[scale=1.1]

  \draw[white] (0,1) node (X) {};

  \draw[white] (2,1) node (Y) {};

   \draw[white] (0,0) node (X1) {};

  \draw[white] (2,0) node (Y1) {};

   \draw[white] (0,-1) node (X2) {};

  \draw[white] (2,-1) node (Y2) {};

  \draw[red, <-, line width = 2mm] (X) -- (Y);