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

\usepackage{../slides}

\usepackage{../graphics}

\usepackage{../langs}

\usepackage{../data}

\usepackage{../grammar}

\hfuzz=220pt 

\pgfplotsset{compat=1.11}

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

% beamer stuff 

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

\begin{document}

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

\begin{frame}[t]

\frametitle{%

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

  \\[-3mm]

  \LARGE Compilers and \\[-2mm] 

  \LARGE Formal Languages (5)\\[3mm] 

  \end{tabular}}

  \normalsize

  \begin{center}

  \begin{tabular}{ll}

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

  Office: & N7.07 (North Wing, Bush House)\\

  Slides: & KEATS (also home work is there)\\

  \end{tabular}

  \end{center}

\end{frame}

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

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

% \begin{frame}[c]

% \frametitle{Survey: Thanks!}

% \small

% \begin{itemize}

% \item {\bf My Voice} ``could be a bit louder''

% \item {\bf Writing} ``sometimes a bit difficult to read''

% \item {\bf Recording} ``video caps of blackboard''

% \item ``It's all great''

% \end{itemize}

% \end{frame}

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

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

\begin{frame}[c]

\frametitle{\begin{tabular}{c}Last Week\\[-1mm] 

            Regexes and Values\end{tabular}}

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{$[v_1,\ldots\,v_n]$} \\

  \end{tabular}

\end{column}

\end{columns}

\end{center}

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

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

\begin{textblock}{6}(1,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}

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

\begin{bubble}[2cm]

\small

\begin{tabular}{ll}

\bl{$|v_1|$}: & \bl{$abc$}\\

\bl{$|v_2|$}: & \bl{$bc$}\\

\bl{$|v_3|$}: & \bl{$c$}\\

\bl{$|v_4|$}: & \bl{$[]$}

\end{tabular}

\end{bubble}

\end{textblock}

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Simplification}

\begin{itemize}

\item If we simplify after the derivative, then we are builing the

value for the simplified regular expression, but \emph{not} for the original

regular expression.

\end{itemize}

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

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

\small

\hspace{4.5cm}\bl{$(b \cdot c) + (\ZERO + \ONE)$}

$\mapsto$

\bl{$(b \cdot c) + \ONE$}

\end{frame}

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

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

% \begin{frame}[t]

% \begin{center}

% \bl{$\only<1>{(b \cdot c)}%

%      \only<2-3>{(\underline{b \cdot c})}%

%      \only<1-3>{+}% 

%      \only<1>{(\ZERO + \ONE)}%

%      \only<2-3>{(\underline{\ZERO + \ONE})}$}%

% \only<4->{%

% \bl{$\underline{(b \cdot c) + (\ZERO + \ONE)}$}%

% }

% $\mapsto$

% \bl{$(b \cdot c) + \ONE$}

% \end{center}\bigskip

% \onslide<3->{%

% \begin{center}

% \begin{tabular}{lcl}

% \bl{$f_{s1}$} & \bl{$=$} & \bl{$\lambda v.v$}\\

% \bl{$f_{s2}$} & \bl{$=$} & \bl{$\lambda v. \textit{Right}(v)$}

% \end{tabular}

% \end{center}}

% \only<4>{%

% \begin{center}

% \begin{tabular}{@{}l@{\hspace{1mm}}l@{}}

% \bl{$f_{alt}(f_{s1}, f_{s2}) \dn$}\\

% \quad \bl{$\lambda v.\,$} 

%         case \bl{$v = Left(v')$}: 

%       & return \bl{$Left(f_{s1}(v'))$}\\

% \quad \phantom{$\lambda v.\,$} 

%         case \bl{$v = Right(v')$}: 

%       & return \bl{$Right(f_{s2}(v'))$}\\ 

% \end{tabular}

% \end{center}}%

% \only<5->{%

% \begin{center}

% \begin{tabular}{@{}l@{\hspace{1mm}}l@{}}

% \only<5->{\phantom{\bl{$f_{alt}(f_{s1}, f_{s2}) \dn$}}}\\

% \quad \bl{$\lambda v.\,$} 

%         case \bl{$v = Left(v')$}: 

%       & return \bl{$Left(v')$}\\

% \quad \phantom{$\lambda v.\,$} 

%         case \bl{$v = Right(v')$}: 

%       & return \bl{$Right(Right(v'))$}\\ 

% \end{tabular}

% \end{center}}%

% \only<6->{%

% \begin{center}

% \begin{tabular}{@{}l@{\hspace{4mm}}l@{}}

% \bl{$\textit{mkeps}$} simplified case: &

% \bl{$\textit{Right}(\textit{Empty})$}\\

% rectified case: &

% \bl{$\textit{Right}(\textit{Right}(\textit{Empty}))$}

% \end{tabular}

% \end{center}}%

% \end{frame}

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

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

\begin{frame}[c]

\frametitle{Records}

\begin{itemize}

\item new regex: \bl{$(x:r)$}\hspace{7mm}new value: 

\bl{$Rec(x,v)$}\medskip

\item \bl{$nullable(x:r) \dn nullable(r)$}

\item \bl{$der\,c\,(x:r) \dn der\,c\,r$}

\item \bl{$mkeps(x:r) \dn Rec(x, mkeps(r))$}

\item \bl{$inj\,(x:r)\,c\,v \dn Rec(x, inj\,r\,c\,v)$}

\end{itemize}\bigskip\bigskip

\small

for extracting subpatterns \bl{$(z: ((x:ab) + (y:ba))$}

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Environments}

Obtaining the ``recorded'' parts of a value: 

\begin{center}

\begin{tabular}{lcl}

  \bl{$env(Empty)$}     & \bl{$\dn$} & \bl{$[]$}\\

  \bl{$env(Char(c))$}   & \bl{$\dn$} & \bl{$[]$}\\

  \bl{$env(Left(v))$}   & \bl{$\dn$} & \bl{$env(v)$}\\

  \bl{$env(Right(v))$}  & \bl{$\dn$} & \bl{$env(v)$}\\

  \bl{$env(Seq(v_1,v_2))$}& \bl{$\dn$} & \bl{$env(v_1) \,@\, env(v_2)$}\\

  \bl{$env([v_1,\ldots ,v_n])$} & \bl{$\dn$} & 

     \bl{$env(v_1) \,@\ldots @\, env(v_n)$}\\

  \bl{$env(Rec(x:v))$} & \bl{$\dn$} & \bl{$(x:|v|) :: env(v)$}\\

\end{tabular}

\end{center}

\end{frame}

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

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

\begin{frame}[c]

\frametitle{While Tokens}

\begin{center}

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

\pcode{WHILE\_REGS} & $\dn$ & \raisebox{-1mm}{\large(}\pcode{("k" : KEYWORD)} +\\ 

                  &       & \phantom{(}\pcode{("i" : ID)} +\\ 

                  &       & \phantom{(}\pcode{("o" : OP)} + \\

                  &       & \phantom{(}\pcode{("n" : NUM)} + \\

                  &       & \phantom{(}\pcode{("s" : SEMI)} +\\ 

                  &       & \phantom{(}\pcode{("p" : (LPAREN + RPAREN))} +\\ 

                  &       & \phantom{(}\pcode{("b" : (BEGIN + END))} +\\ 

                  &       & \phantom{(}\pcode{("w" : WHITESPACE)}\raisebox{-1mm}{\large)$^*$}

\end{tabular}

\end{center}

\end{frame}

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

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

\begin{frame}[t]

\consolas

\begin{center}

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

\frametitle{Coursework: Nullable}

\begin{center}

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

  \bl{$nullable([c_1 c_2 \ldots c_n])$}  & \bl{$\dn$} & $?$\\

  \bl{$nullable(r^+)$}                   & \bl{$\dn$} & $?$\\

  \bl{$nullable(r^?)$}                   & \bl{$\dn$} & $?$\\

  \bl{$nullable(r^{\{n\}})$}              & \bl{$\dn$} & $?$\\

  \bl{$nullable(r^{\{n..\}})$}            & \bl{$\dn$} & $?$\\

  \bl{$nullable(r^{\{..n\}})$}            & \bl{$\dn$} & $?$\\

  \bl{$nullable(r^{\{n..m\}})$}           & \bl{$\dn$} & $?$\\

  \bl{$nullable(\sim{}r)$}               & \bl{$\dn$} & $?$\\

\end{tabular}

\end{center}

\end{frame}

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

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

\begin{frame}[c]

%%\frametitle{Coursework: der}

\begin{center}

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

  \bl{$der\, c\, ([c_1 c_2 \ldots c_n])$}  & \bl{$\dn$} & $?$\\

  \bl{$der\, c\, (r^+)$}                   & \bl{$\dn$} & $?$\\

  \bl{$der\, c\, (r^?)$}                   & \bl{$\dn$} & $?$\\

  \bl{$der\, c\, (r^{\{n\}})$}              & \bl{$\dn$} &

     \bl{$if\;n=0\;then\;\ZERO\;else\;(der\,c\,r)\cdot r^{\{n-1\}}$}\\

  \bl{$der\, c\, (r^{\{n..\}})$}            & \bl{$\dn$} &

     \bl{$if\;n=0\;then (der\,c\,r)\cdot r^*$}\\

  & & \bl{$\phantom{if\;n=0\;}else \;(der\,c\,r)\cdot r^{\{n-1..\}}$}\\

  \bl{$der\, c\, (r^{\{..n\}})$}            & \bl{$\dn$} &

     \bl{$if\;n=0\;then\;\ZERO\;else\;(der\,c\,r)\cdot r^{\{..n-1\}}$}\\

  \bl{$der\, c\, (r^{\{n..m\}})$}          & \bl{$\dn$} &

     \bl{$if\;n = 0 \wedge m = 0\;then\;\ZERO\; else$}\\

  \multicolumn{3}{l}{\bl{$if\;n = 0 \wedge m > 0\;then\;(der\,c\,r)\cdot r^{\{..m-1\}}$}}\\

  \multicolumn{3}{l}{\bl{$\phantom{if\;n = 0 \wedge m > 0\;}else

          \;(der\,c\,r)\cdot r^{\{n-1..m-1\}}$}}\\

  \bl{$der\, c\, (\sim{}r)$}              & \bl{$\dn$} & $?$\\

\end{tabular}

\end{center}

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Coursework: CFUN}

\begin{center}

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

  \bl{$nullable(CFUN(\_))$}  & \bl{$\dn$} & \bl{$false$}\\

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

     \bl{$if\;f(c)\;then\;\ONE\;else\;\ZERO$}\bigskip\\

  \bl{$CHAR(c)$}                   & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;c=d)$}\\

  \bl{$CSET([c_1,\ldots,c_n])$} & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;d\in [c_1,\ldots,c_n])$}\\

  \bl{$ALL$}                   & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;true)$}\\                                                      

\end{tabular}

\end{center}

\end{frame}

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

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

\begin{frame}[t]

\frametitle{Lexer, Parser}

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

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

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Regular Languages}

While regular expressions are very useful for lexing, there is

no regular expression that can recognise the language

\bl{$a^nb^n$}.\bigskip

\begin{center}

\bl{$(((()()))())$} \;\;vs.\;\; \bl{$(((()()))()))$}

\end{center}\bigskip\bigskip