% !TEX program = xelatex

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

\usepackage{../slides}

\usepackage{../graphics}

\usepackage{../langs}

\usepackage{../data}

\hfuzz=220pt 

\pgfplotsset{compat=1.11}

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

% a hand written lexer for SML

% https://ponyo.org/

% https://github.com/eatonphil/ponyo/blob/master/src/Sml/Lexer.sml

\beamertemplateballitem

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

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

\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 & 7 Compilation, JVM \\

          3 Automata, Regular Languages      & 8 Compiling Functional Languages \\

          \cellcolor{blue!50}

          4 Lexing, Tokenising               & 9 Optimisations \\

          5 Grammars, Parsing                & 10 LLVM \\ \hline

        \end{tabular}%

      };

    \end{tikzpicture}

  \end{center}

\end{frame}

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

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

%\begin{frame}[c]

%\frametitle{Coursework}

%

%\begin{itemize}

%\item \bl{$\der\,c\,(r^+) \dn \der\,c (r\cdot r^*)$}\quad given

%that \bl{$r^+ \dn r\cdot r^*$}

%\end{itemize}\bigskip\pause

%\begin{center}

%\begin{tabular}{lcl}

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

%\only<2-4>{if \bl{$nullable\,r$}}%

%\only<5>{\bl{$(\der\,c\,r)\cdot r^*$}}\\

% & & 

% \only<2>{then \bl{$(\der\,c\,r)\cdot r^* \,+\, \der\,c\,(r^*)$}}%

% \only<3>{then \bl{$(\der\,c\,r)\cdot r^* \,+\, (\der\,c\,r)\cdot r^*$}}%

% \only<4>{then \bl{$(\der\,c\,r)\cdot r^*$}}\\

% & & \only<2-4>{else \bl{$(\der\,c\,r)\cdot r^*$}}

%\end{tabular}  

%\end{center}  

%\end{frame}

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

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

%\begin{frame}[c]

%  \frametitle{Coursework (2)}

%  

%  \begin{itemize}

%  \item \bl{\texttt{CFUN(f: Char => Boolean)}}

%  \end{itemize}\medskip

%

%  \begin{center}

%  \begin{tabular}{l}

%  \bl{\texttt{CHAR(c: Char)}} \bl{$\dn$}\\

%     \quad\bl{\texttt{CFUN(\_ == c)}}\medskip\\

%  \bl{\texttt{RANGE(cs: Set[Char])}} \bl{$\dn$}\\

%     \quad\bl{\texttt{CFUN(cs.contains(\_))}}\medskip\\

%  \bl{\texttt{ALL}} \bl{$\dn$}\\

%     \quad\bl{\texttt{CFUN((c: Char) => true)}}\\

%  \end{tabular}  

%  \end{center}  

%\end{frame}

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

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

\begin{frame}[c]

\frametitle{The Goal of this Course}

\mbox{}\\[-26mm]\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 at (3.05, 1.8) {\Large\bf Write a compiler};

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

Today a lexer.  

\only<2>{

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

\begin{tabular}{c}

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

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

\end{tabular}

\end{textblock}}

\end{frame}

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

\begin{frame}[c]

\frametitle{Regular Expressions}

In programming languages they are often used to recognise:\medskip

\begin{itemize}

\item operands, digits

\item identifiers

\item numbers (non-leading zeros)

\item keywords

\item comments

\end{itemize}\bigskip

\mbox{}\hfill\bl{\url{http://www.regexper.com}}

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Lexing: Test Case}

\mbox{\lstinputlisting[language=While]{../progs/while-tests/fib.while}}

\end{frame}

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

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

%\begin{frame}[c]

%\frametitle{?? Test Case}

%

%\mbox{\lstinputlisting[language=While]{../progs/collatz.while}}

%

%\end{frame}

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

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

\begin{frame}[t]

\tt

\begin{center}\large

\code{"if true then then 42 else +"}

\end{center}

\begin{tabular}{@{}l}

KEYWORD: \\

\hspace{5mm}{if}, {then}, {else},\\ 

WHITESPACE:\\

\hspace{5mm}{" "}, {$\backslash$n},\\ 

IDENTIFIER:\\

\hspace{5mm}LETTER $\cdot$ (LETTER + DIGIT + {\_})$^*$\\ 

NUM:\\

\hspace{5mm}(NONZERODIGIT $\cdot$ DIGIT$^*$) + {0}\\

OP:\\

\hspace{5mm}+, -, *, \%, <, <=\\

COMMENT:\\

\hspace{5mm}{$\slash$*} $\cdot$ $\sim$(ALL$^*$ $\cdot$ (*$\slash$) $\cdot$ ALL$^*$) $\cdot$ {*$\slash$}

\end{tabular}

\end{frame}

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

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

\begin{frame}[t]

\tt

\begin{center}\large

\code{"if true then then 42 else +"}

\end{center}

\only<1>{

\small\begin{tabular}{l}

KEYWORD(if),\\ 

WHITESPACE,\\ 

IDENT(true),\\ 

WHITESPACE,\\ 

KEYWORD(then),\\ 

WHITESPACE,\\ 

KEYWORD(then),\\ 

WHITESPACE,\\ 

NUM(42),\\ 

WHITESPACE,\\ 

KEYWORD(else),\\ 

WHITESPACE,\\ 

OP(+)

\end{tabular}}

\only<2>{

\small\begin{tabular}{l}

KEYWORD(if),\\ 

IDENT(true),\\ 

KEYWORD(then),\\ 

KEYWORD(then),\\ 

NUM(42),\\ 

KEYWORD(else),\\ 

OP(+)

\end{tabular}}

\end{frame}

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

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

\begin{frame}[c]

There is one small problem with the tokenizer. How should we 

tokenize\ldots?

\begin{center}

\large\code{"x-3"}

\end{center}

\tt

\begin{tabular}{@{}l}

ID: \ldots\\

OP:\\

\hspace{5mm}\texttt{"+"}, \texttt{"-"}\\

NUM:\\

\hspace{5mm}(NONZERODIGIT $\cdot$ DIGIT$^*$) + {''0''}\\

NUMBER:\\

\hspace{5mm}NUM +  (\texttt{"-"} $\cdot$ NUM)\\

\end{tabular}

\end{frame}

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

\begin{frame}[c]

The same problem with\medskip

\[

\bl{(ab + a) \cdot (c + bc)}

\]\medskip

and the string $\bl{abc}$.\pause\bigskip

Or, keywords are \code{if} etc and identifiers are 

letters followed by ``letters + numbers + \_''$^*$

\[

\bl{\texttt{if}}\qquad\bl{\texttt{iffoo}}

\]

\end{frame}

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

\begin{frame}[c]

\frametitle{POSIX: Two Rules}

\begin{itemize}

\item Longest match rule (``maximal munch rule''): The 

longest initial substring matched by any regular expression is taken

as the next token.\bigskip

\item Rule priority:

For a particular longest initial substring, the first regular

expression that can match determines the token.

\end{itemize}\bigskip\bigskip\pause

\small

\hfill most posix matchers are buggy\\

\footnotesize

\hfill 

\url{http://www.haskell.org/haskellwiki/Regex_Posix}

\smallskip\pause

\hfill \small traditional lexers are fast, but hairy

%\url{http://www.technologyreview.com/tr10/?year=2011}  

%finite deterministic automata/ nondeterministic automaton

%\item problem with infix operations, for example i-12

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Sulzmann \& Lu Matcher}

We want to match the string \bl{$abc$} using \bl{$r_1$}:

\begin{center}

\begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}]

\node (r1)  {\bl{$r_1$}};

\node (r2) [right=of r1] {\bl{$r_2$}};

\draw[->,line width=1mm]  (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};\pause

\node (r3) [right=of r2] {\bl{$r_3$}};

\draw[->,line width=1mm]  (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};\pause

\node (r4) [right=of r3] {\bl{$r_4$}};

\draw[->,line width=1mm]  (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};\pause

\draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable?$}}};\pause

\node (v4) [below=of r4] {\bl{$v_4$}};

\draw[->,line width=1mm]  (r4) -- (v4);\pause

\node (v3) [left=of v4] {\bl{$v_3$}};

\draw[->,line width=1mm]  (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};\pause

\node (v2) [left=of v3] {\bl{$v_2$}};

\draw[->,line width=1mm]  (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};\pause

\node (v1) [left=of v2] {\bl{$v_1$}};

\draw[->,line width=1mm]  (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};\pause

\draw[->,line width=0.5mm]  (r3) -- (v3);

\draw[->,line width=0.5mm]  (r2) -- (v2);

\draw[->,line width=0.5mm]  (r1) -- (v1);

\draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};

\end{tikzpicture}

\end{center}

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Regexes and Values}

Regular expressions and their corresponding values:

\begin{center}

\begin{columns}

\begin{column}{3cm}

\begin{tabular}{@{}rrl@{}}

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

           & \bl{$\mid$} & \bl{$\ONE$}   \\

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

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

           & \bl{$\mid$} & \bl{$r_1 + r_2$}   \\

  \\

           & \bl{$\mid$} & \bl{$r^*$}         \\

  \\

  \end{tabular}

\end{column}

\begin{column}{3cm}

\begin{tabular}{@{\hspace{-7mm}}rrl@{}}

  \bl{$v$} & \bl{$::=$}  & \\

           &             & \bl{$Empty$}   \\

           & \bl{$\mid$} & \bl{$Char(c)$}          \\

           & \bl{$\mid$} & \bl{$Seq(v_1,v_2)$}\\

           & \bl{$\mid$} & \bl{$Left(v)$}   \\

           & \bl{$\mid$} & \bl{$Right(v)$}  \\

           & \bl{$\mid$} & \bl{$Stars\,[]$}      \\

           & \bl{$\mid$} & \bl{$Stars\,[v_1,\ldots\,v_n]$} \\

  \end{tabular}

\end{column}

\end{columns}

\end{center}

\end{frame}

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

\begin{frame}[c]

\small

{\small\lstinputlisting[language=Scala,numbers=none,

xleftmargin=-5mm] {../progs/app01.scala}}

{\small\lstinputlisting[language=Scala,numbers=none,

xleftmargin=-5mm] {../progs/app02.scala}}

\end{frame}

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

\begin{frame}[c]

\begin{textblock}{10}(3,5)

\begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}]

\node (r1)  {\bl{$r_1$}};

\node (r2) [right=of r1] {\bl{$r_2$}};

\draw[->,line width=1mm]  (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};

\node (r3) [right=of r2] {\bl{$r_3$}};

\draw[->,line width=1mm]  (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};

\node (r4) [right=of r3] {\bl{$r_4$}};

\draw[->,line width=1mm]  (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};

\draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};

\node (v4) [below=of r4] {\bl{$v_4$}};

\draw[->,line width=1mm]  (r4) -- (v4);

\node (v3) [left=of v4] {\bl{$v_3$}};

\draw[->,line width=1mm]  (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};

\node (v2) [left=of v3] {\bl{$v_2$}};

\draw[->,line width=1mm]  (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};

\node (v1) [left=of v2] {\bl{$v_1$}};

\draw[->,line width=1mm]  (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};

\draw[->,line width=0.5mm]  (r3) -- (v3);

\draw[->,line width=0.5mm]  (r2) -- (v2);

\draw[->,line width=0.5mm]  (r1) -- (v1);

\draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};

\end{tikzpicture}

\end{textblock}

\only<1->{

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

\begin{bubble}[6cm]

\small

\begin{tabular}{ll}

\bl{$r_1$}: & \bl{$a \cdot (b \cdot c)$}\\

\bl{$r_2$}: & \bl{$\ONE \cdot (b \cdot c)$}\\

\bl{$r_3$}: & \bl{$(\ZERO \cdot (b \cdot c)) + (\ONE \cdot c)$}\\

\bl{$r_4$}: & \bl{$(\ZERO \cdot (b \cdot c)) + ((\ZERO \cdot c) + \ONE)$}\\

\end{tabular}

\end{bubble}

\end{textblock}}

\only<2->{

\begin{textblock}{6}(5,11.4)

\begin{bubble}[7.6cm]

\small

\begin{tabular}{ll}

\bl{$v_1$}: & \bl{$Seq(Char(a), Seq(Char(b), Char(c)))$}\\

\bl{$v_2$}: & \bl{$Seq(Empty, Seq(Char(b), Char(c)))$}\\

\bl{$v_3$}: & \bl{$Right(Seq(Empty, Char(c)))$}\\

\bl{$v_4$}: & \bl{$Right(Right(Empty))$}\\

\end{tabular}

\end{bubble}

\end{textblock}}

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Flatten}

Obtaining the string underlying a value:

\begin{center}

\begin{tabular}{lcl}

  \bl{$|Empty|$}     & \bl{$\dn$} & \bl{$[]$}\\