% !TEX program = xelatex

\documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer}

\usepackage{../slides}

\usepackage{../graphics}

\usepackage{../langs}

\usepackage{../data}

\usepackage{tcolorbox}

\newtcolorbox{mybox}{colback=red!5!white,colframe=red!75!black}

\newtcolorbox{mybox2}[1]{colback=red!5!white,colframe=red!75!black,fonttitle=\bfseries,title=#1}

\newtcolorbox{mybox3}[1]{colback=Cyan!5!white,colframe=Cyan!75!black,fonttitle=\bfseries,title=#1}

\hfuzz=220pt 

\lstset{language=Scala,

        style=mystyle,

        numbersep=0pt,

        numbers=none,

        xleftmargin=0mm}

\pgfplotsset{compat=1.12}

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

% beamer stuff 

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

\begin{document}

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

\begin{frame}[t]

\frametitle{%

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

  \\[-3mm]

  \LARGE Compilers and \\[-1mm] 

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

          \cellcolor{blue!50}

          2 Regular Expressions, Derivatives & 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{

    Let's Implement an Efficient\\[-2mm] 

    Regular Expression Matcher}

\footnotesize

\begin{center}

  {\normalsize Graphs: \bl{$a^{?\{n\}} \cdot a^{\{n\}}$} and strings \bl{$\underbrace{\,a\ldots a\,}_{n}$}}\medskip\\

\begin{tabular}{@{}cc@{}}

\begin{tikzpicture}

\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=5cm,

    height=4.5cm, 

    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=pentagon*, mark options={fill=white}] table {re-ruby.data};  

\end{axis}

\end{tikzpicture}

&

\begin{tikzpicture}

  \begin{axis}[

    xlabel={$n$},

    x label style={at={(1.1,0.05)}},

    ylabel={time in secs},

    enlargelimits=false,

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

    xmax=11500,

    ymax=35,

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

    scaled ticks=false,

    axis lines=left,

    width=5cm,

    height=4.5cm,

    legend entries={Scala V2,Scala V3},

    legend pos=north east,

    legend cell align=left]

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

\end{tabular}

\end{center}

\small

In the handouts is a similar graph for \bl{$(a^*)^* \cdot b$} and Java 8, 

JavaScript and Python.

\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)\bigskip

%\item Evil regular expressions\medskip

%\begin{itemize}

%\item \bl{$a^{?\{n\}} \cdot a^{\{n\}}$}

%\item \bl{$(a^*)^*$}

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

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

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

%\end{itemize}

%

%\item sometimes also called \alert{catastrophic backtracking}\bigskip

%\item \small\ldots I hope you have watched the video by the

%  StackExchange engineer  

%\end{itemize}

%

%\end{frame}

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

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

\begin{frame}[c]

\frametitle{(Basic) Regular Expressions}

Their inductive definition:

\begin{center}

  \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l}

  \bl{$r$} & \bl{$::=$}  & \bl{$\ZERO$}  & nothing\\

         & \bl{$\mid$} & \bl{$\ONE$}       & empty string / \pcode{""} / $[]$\\

         & \bl{$\mid$} & \bl{$c$}                         & character\\

         & \bl{$\mid$} & \bl{$r_1 + r_2$}  & alternative / choice\\

         & \bl{$\mid$} & \bl{$r_1 \cdot r_2$} & sequence\\

         & \bl{$\mid$} & \bl{$r^*$}            & star (zero or more)\\

  \end{tabular}

\end{center}

\vspace{\fill}

%%Q: \;What about \;\bl{$r \cdot 0$} \; ?

\end{frame}

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

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

\begin{frame}[c]

  \frametitle{

   When Are Two Regular\\[-1mm]

   Expressions Equivalent?}

   \begin{bubble}[10cm]

    \large

    Two regular expressions \bl{$r_1$} and \bl{$r_2$} are

    \alert{\bf{}equivalent} 

    provided:\medskip 

    \begin{center}

      \bl{$r_1 \equiv r_2 \;\;\dn\;\; L(r_1) = L(r_2)$}  

    \end{center}\medskip

    \end{bubble}

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Some Concrete Equivalences}

\begin{center}

\bl{\begin{tabular}{rcl}

$(a + b)  + c$ & $\equiv$ & $a + (b + c)$\\

$a + a$        & $\equiv$ & $a$\\

$a + b$        & $\equiv$ & $b + a$\\

$(a \cdot b) \cdot c$ & $\equiv$ & $a \cdot (b \cdot c)$\\

$c \cdot (a + b)$ & $\equiv$ & $(c \cdot a) + (c \cdot b)$\bigskip\bigskip\\\pause

$a \cdot a$       & $\not\equiv$ & $a$\\

$a + (b \cdot c)$ & $\not\equiv$ & $(a + b) \cdot (a + c)$\\

\end{tabular}}

\end{center}

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Some Corner Cases}

\begin{center}

\bl{\begin{tabular}{rcl}

$a \cdot \ZERO$ & $\not\equiv$ & $a$\\

$a + \ONE$ & $\not\equiv$ & $a$\\

$\ONE$ & $\equiv$ & $\ZERO^*$\\

$\ONE^*$ & $\equiv$ & $\ONE$\\

$\ZERO^*$ & $\not\equiv$ & $\ZERO$\\

\end{tabular}}

\end{center}

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Some Simplification Rules}

\begin{center}

\bl{\begin{tabular}{rcl}

$r + \ZERO$  & $\equiv$ & $r$\\

$\ZERO + r$  & $\equiv$ & $r$\\

$r \cdot \ONE$ & $\equiv$ & $r$\\

$\ONE \cdot r$     & $\equiv$ & $r$\\

$r \cdot \ZERO$ & $\equiv$ & $\ZERO$\\

$\ZERO \cdot r$ & $\equiv$ & $\ZERO$\\

$r + r$ & $\equiv$ & $r$

\end{tabular}}

\end{center}

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Simplification Example}

%%Given \bl{$r \dn ((a \cdot b) + b)^*$}, you can simplify as follows

\begin{center}

\def\arraystretch{2}  

\begin{tabular}{@{}lcl}

  \bl{$((\ONE \cdot b) + \ZERO) \cdot r$}

    & \bl{$\Rightarrow$} & \bl{$((\underline{\ONE \cdot b}) + \ZERO) \cdot r$}\\

    & \bl{$=$} & \bl{$(\underline{b + \ZERO}) \cdot r$}\\

    & \bl{$=$} & \bl{$b \cdot r$}\\

\end{tabular}

\end{center}

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Simplification Example}

%%Given \bl{$r \dn ((a \cdot b) + b)^*$}, you can simplify as follows

\begin{center}

\def\arraystretch{2}  

\begin{tabular}{@{}lcl}

  \bl{$((\ZERO \cdot b) + \ZERO) \cdot r$}

    & \bl{$\Rightarrow$} & \bl{$((\underline{\ZERO \cdot b}) + \ZERO) \cdot r$}\\

    & \bl{$=$} & \bl{$(\underline{\ZERO + \ZERO}) \cdot r$}\\

    & \bl{$=$} & \bl{$\ZERO \cdot r$}\\

    & \bl{$=$} & \bl{$\ZERO$}\\

\end{tabular}

\end{center}

\end{frame}

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

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

\begin{frame}[t]

\frametitle{Semantic Derivative\\[5mm]}

\begin{itemize}

\item The \alert{\bf Semantic Derivative} of a 

\underline{language}\\ w.r.t.~to a character \bl{$c$}:

\bigskip

\begin{center}

\bl{$\Der\,c\,A \dn \{ s \;|\;  c\!::\!s \in A\}$ } 

\end{center}\bigskip

For \bl{$A = \{\mathit{foo}, \mathit{bar}, \mathit{frak}\}$} then

\begin{center}

\bl{\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}l}

$\Der\,f\,A$ & $=$ & $\{\mathit{oo}, \mathit{rak}\}$\\

$\Der\,b\,A$ & $=$ &  $\{\mathit{ar}\}$\\  

$\Der\,a\,A$ & $=$ & $\{\}$\pause

\end{tabular}}

\end{center}\medskip

We can extend this definition to strings

\[

\bl{\Ders\,s\,A = \{s'\;|\;s\,@\,s' \in A\}}

\]

\end{itemize}

\end{frame}

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

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

\begin{frame}[c]

\frametitle{The Specification for Matching}

\begin{bubble}[10cm]

\large

A regular expression \bl{$r$} matches a string~\bl{$s$} 

provided:

\begin{center}

\bl{$s \in L(r)$} 

\end{center}\medskip

\end{bubble}

\bigskip\bigskip

\ldots and the point of the this lecture is to decide this problem as

fast as possible (unlike Python, Ruby, Java etc)

\end{frame}

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

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

\begin{frame}[c]

\frametitle{\mbox{Brzozowski's Algorithm (1)}}

\ldots{}whether a regular expression can match the empty string:

\begin{center}

\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}

\bl{$nullable(\ZERO)$}    & \bl{$\dn$} & \bl{\textit{false}}\\

\bl{$nullable(\ONE)$}       & \bl{$\dn$} & \bl{\textit{true}}\\

\bl{$nullable (c)$}             & \bl{$\dn$} & \bl{\textit{false}}\\

\bl{$nullable (r_1 + r_2)$}     & \bl{$\dn$} & \bl{$nullable(r_1) \vee nullable(r_2)$} \\ 

\bl{$nullable (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$nullable(r_1) \wedge nullable(r_2)$} \\

\bl{$nullable (r^*)$}           & \bl{$\dn$} & \bl{\textit{true}}\\

\end{tabular}

\end{center}

\end{frame}

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

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

\begin{frame}[c]

\frametitle{The Derivative of a Rexp}

\large

If \bl{$r$} matches the string \bl{$c\!::\!s$}, what is a regular 

expression that matches just \bl{$s$}?\bigskip\bigskip\bigskip\bigskip

\small

\bl{$\der\,c\,r$} gives the answer, Brzozowski 1964

\end{frame}

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

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

\begin{frame}[c]

\frametitle{The Derivative of a Rexp}

\begin{center}

\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}}

  \bl{$\der\, c\, (\ZERO)$}      & \bl{$\dn$} & \bl{$\ZERO$} & \\

  \bl{$\der\, c\, (\ONE)$}           & \bl{$\dn$} & \bl{$\ZERO$} & \\

  \bl{$\der\, c\, (d)$}                     & \bl{$\dn$} & \bl{if $c = d$ then $\ONE$ else $\ZERO$} & \\

  \bl{$\der\, c\, (r_1 + r_2)$}        & \bl{$\dn$} & \bl{$\der\, c\, r_1 + \der\, c\, r_2$} & \\

  \bl{$\der\, c\, (r_1 \cdot r_2)$}  & \bl{$\dn$}  & \bl{if $nullable (r_1)$}\\

  & & \bl{then $(\der\,c\,r_1) \cdot r_2 + \der\, c\, r_2$}\\ 

  & & \bl{else $(\der\, c\, r_1) \cdot r_2$}\\

  \bl{$\der\, c\, (r^*)$}  & \bl{$\dn$} & \bl{$(\der\,c\,r) \cdot (r^*)$} &\medskip\bigskip\\\pause

  \bl{$\ders\, []\, r$}     & \bl{$\dn$} & \bl{$r$} & \\

  \bl{$\ders\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$\ders\,s\,(\der\,c\,r)$} & \\

  \end{tabular}

\end{center}

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Examples}

Given \bl{$r \dn ((a \cdot b) + b)^*$} what is

\begin{center}

\begin{tabular}{l}

\bl{$\der\,a\,r =\;?$}\\

\bl{$\der\,b\,r =\;?$}\\

\bl{$\der\,c\,r =\;?$}

\end{tabular}

\end{center}

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Derivative Example}

Given \bl{$r \dn ((a \cdot b) + b)^*$} what is

\begin{center}

\def\arraystretch{1.5}  

\begin{tabular}{@{}lcl}

  \bl{$\der\,a\,((a \cdot b) + b)^*$}

    & \bl{$\Rightarrow$}& \bl{$\der\,a\, \underline{((a \cdot b) + b)^*}$}\\

    & \bl{$=$} & \bl{$(der\,a\,(\underline{(a \cdot b) + b})) \cdot r$}\\

    & \bl{$=$} & \bl{$((der\,a\,(\underline{a \cdot b})) + (der\,a\,b)) \cdot r$}\\

    & \bl{$=$} & \bl{$(((der\,a\,\underline{a}) \cdot b) + (der\,a\,b)) \cdot r$}\\

    & \bl{$=$} & \bl{$((\ONE \cdot b) + (der\,a\,\underline{b})) \cdot r$}\\

    & \bl{$=$} & \bl{$((\ONE \cdot b) + \ZERO) \cdot r$}

\end{tabular}

\end{center}

\end{frame}

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

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

\begin{frame}[c]

\frametitle{\mbox{The Brzozowski Algorithm}}

%\begin{center}

%\begin{tabular}{l} 

%\bl{$\textit{matcher}\,r\,s \dn \textit{nullable}(\ders\;s\;r)$}  

%\end{tabular}

%\end{center}

\begin{center}

\begin{mybox3}{}

\centering    

\bl{$\textit{matcher}\,r\,s \dn \textit{nullable}(\ders\;s\;r)$}

\end{mybox3}

\end{center}

\end{frame}

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

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

\begin{frame}[t]

\frametitle{Brzozowski: An Example}

Does \bl{$r_1$} match \bl{$abc$}?

\begin{center}

\begin{tabular}{@{}rl@{}l@{}}

Step 1: & build derivative of \bl{$a$} and \bl{$r_1$} & \bl{$(r_2 = \der\,a\,r_1)$}\smallskip\\

Step 2: & build derivative of \bl{$b$} and \bl{$r_2$} & \bl{$(r_3 = \der\,b\,r_2)$}\smallskip\\

Step 3: & build derivative of \bl{$c$} and \bl{$r_3$} & \bl{$(r_4 = \der\,c\,r_3)$}\smallskip\\

Step 4: & the string is exhausted: & \bl{($nullable(r_4))$}\\

        & test whether \bl{$r_4$} can recognise\\

        & the empty string\medskip\\

Output: & result of the test\\

        & $\Rightarrow \bl{\textit{true}} \,\text{or}\, 

                       \bl{\textit{false}}$\\        

\end{tabular}

\end{center}

\end{frame}

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