% !TEX program = xelatex
\documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer}
\usepackage{../slides}
\usepackage{../graphicss}
\usepackage{../langs}
\usepackage{../data}
\usepackage{../grammar}

% beamer stuff 
\renewcommand{\slidecaption}{CFL 06, King's College London}


\newcommand{\bl}[1]{\textcolor{blue}{#1}}       
%\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions
\newcommand{\qq}{\mbox{\texttt{"}}}

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



\begin{document}
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{%
  \begin{tabular}{@ {}c@ {}}
  \\[-3mm]
  \LARGE Compilers and \\[-1mm] 
  \LARGE Formal Languages\\[-5mm] 
  \end{tabular}}

  \normalsize
  \begin{center}
  \begin{tabular}{ll}
    Email:  & christian.urban at kcl.ac.uk\\
     Office Hour: & Fridays 12 -- 14\\  
  Location: & N7.07 (North Wing, Bush House)\\
  Slides \& Progs: & KEATS\\
  Pollev: & \texttt{\alert{https://pollev.com/cfltutoratki576}}\\  
  \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          & \cellcolor{blue!50} 6 While-Language \\
          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,fragile]
\begin{minipage}{1.1\textwidth}
 \begin{mybox3}{}
   Why the hell did we bother for 4 long weeks with a worse-than-cubic
   lexing algorithm for regular expressions, given the CYK-algorithm
   can decide in cubic time whether a string is matched by a context 
   free grammar? Is the lecturer insane?
 \end{mybox3}
\end{minipage}\bigskip

\begin{itemize}
\item Yes, if we are only after string matching. But we are after lexing where
  we need POSIX matching 
  and calculate POSIX values. You cannot do this with any of the CFG-algorithms.
\item Also it is not so easy to include extended regular expressions like $\sim{}r$
and $r^{\{n\}}$. 
\end{itemize}
\end{frame}

\begin{frame}[t,fragile]
\begin{minipage}{1.1\textwidth}
 \begin{mybox3}{}
   Why the hell did we bother for 4 long weeks with a lexing algorithm 
   generating tokens, given the lecturer explains the parsing algorithm using 
   strings as input? Has the lecturer gone insane?
 \end{mybox3}
\end{minipage}\bigskip

\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
%\begin{frame}[t,fragile]
%\begin{mybox3}{}
%  In CW2, be careful with the order of defining regular expressions:
%
%\begin{verbatim}
%val COMMENT : Rexp = ... ~ EOL
%val EOL : Rexp = "\r\n" |  "\n"
%\end{verbatim}
%\end{mybox3}
%\end{frame}
%
%
%\begin{frame}[t,fragile]
%\begin{mybox3}{}
%  In CW2, what is the derivative of RECD?
%
%\begin{center}
%\bl{$der\;c\;RECD(l, r) \;\;\dn\;\; ???$}
%\end{center}  
%\end{mybox3}
%\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Parser Combinators}

One of the simplest ways to implement a parser, see
{\small\url{https://vimeo.com/142341803}} (by Haoyi Li)\bigskip

\begin{itemize}
\item[$\bullet$] built-in library in Scala
\item[$\bullet$] fastparse (2) library by Haoyi Li; is part of Ammonite
\item[$\bullet$] possible exponential runtime behaviour  
\end{itemize}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Palindromes}

A grammar for palindromes over the alphabet~\bl{$\{a,b\}$}:

\only<1>{%
\bl{\begin{plstx}[margin=1cm]
: \meta{S} ::=  a\cdot \meta{S}\cdot a | b\cdot \meta{S}\cdot b | a | b | \epsilon\\
\end{plstx}}}

%\small
%Can you find the grammar rules for matched parentheses?

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Parser Combinators}

Parser combinators: \bigskip

\begin{minipage}{1.1\textwidth}
\begin{center}
\mbox{}\hspace{-12mm}\mbox{}$\underbrace{\text{list of tokens}}_{\text{input}}$ \bl{$\Rightarrow$} 
$\underbrace{\text{set of (parsed input, unparsed input)}}_{\text{output}}$
\end{center}
\end{minipage}\bigskip

\begin{itemize}
\item atomic parsers
\item sequencing
\item alternative
\item semantic action (map-parser)
\end{itemize}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Abstract Parser Class}

\small
\lstinputlisting[language=Scala,xleftmargin=1mm]
 {../progs/app7.scala}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]

Atomic parsers, for example, number tokens

\begin{center}
\bl{$\texttt{Num(123)}::rest \;\Rightarrow\; \{(\texttt{Num(123)}, rest)\}$} 
\end{center}\bigskip

\begin{itemize}
\item you consume one or more token from the\\ 
  input (stream)
\item also works for characters and strings
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]

Alternative parser (code \bl{$p\;||\;q$})\bigskip

\begin{itemize}
\item apply \bl{$p$} and also \bl{$q$}; then combine 
  the outputs
\end{itemize}

\begin{center}
\large \bl{$p(\text{input}) \cup q(\text{input})$}
\end{center}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]

Sequence parser (code \bl{$p\sim q$})\bigskip

\begin{itemize}
\item apply first \bl{$p$} producing a set of pairs
\item then apply \bl{$q$} to the unparsed parts
\item then combine the results:\medskip 
\begin{center}
((output$_1$, output$_2$), unparsed part)
\end{center}
\end{itemize}

\begin{center}
\begin{tabular}{l}
\large \bl{$\{((o_1, o_2), u_2) \;|\;$}\\[2mm] 
\large\mbox{}\hspace{15mm} \bl{$(o_1, u_1) \in p(\text{input}) \wedge$}\\[2mm]
\large\mbox{}\hspace{15mm} \bl{$(o_2, u_2) \in q(u_1)\}$}
\end{tabular}
\end{center}


\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]

Map-parser (code \bl{$p.map(f)\;$})\bigskip

\begin{itemize}
\item apply \bl{$p$} producing a set of pairs
\item then apply the function \bl{$f$} to each first component
\end{itemize}

\begin{center}
\begin{tabular}{l}
\large \bl{$\{(f(o_1), u_1) \;|\; (o_1, u_1) \in p(\text{input})\}$}
\end{tabular}
\end{center}\bigskip\bigskip\pause

\bl{$f$} is the semantic action (``what to do with the parsed input'')

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{\begin{tabular}{c}Semantic Actions\end{tabular}}

Addition

\begin{center}
\bl{$\meta{T} \sim + \sim \meta{E} \Rightarrow \underbrace{f\,((x,y), z) \Rightarrow x + z}_{\text{semantic action}}$}
\end{center}\pause

Multiplication

\begin{center}
\bl{$\meta{F} \sim * \sim \meta{T} \Rightarrow f\,((x,y), z) \Rightarrow x * z$}
\end{center}\pause

Parenthesis

\begin{center}
\bl{$\text{(} \sim \meta{E} \sim \text{)} \Rightarrow f\,((x,y), z) \Rightarrow y$}
\end{center}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Input Types of Parsers}

\begin{itemize}
\item input: \alert{token list}
\item output: set of (output\_type, \alert{token list})
\end{itemize}\bigskip\pause

actually it can be any input type as long as it is a kind of
sequence (for example a string)

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Scannerless Parsers}

\begin{itemize}
\item input: \alert{string}
\item output: set of (output\_type, \alert{string})
\end{itemize}\bigskip\bigskip

but using lexers is better because whitespaces or comments can be
filtered out; then input is a sequence of tokens

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Abstract Parser Class}

\small
\lstinputlisting[language=Scala,xleftmargin=1mm]
 {../progs/app7.scala}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Successful Parses}

\begin{itemize}
\item input: string
\item output: \alert{set of} (output\_type, string)
\end{itemize}\bigskip

a parse is successful whenever the input has been fully
``consumed'' (that is the second component is empty)

\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}
\frametitle{While-Language}
\mbox{}\\[-23mm]\mbox{}

\bl{\begin{plstx}[rhs style=,one per line]: \meta{Stmt} ::= skip
         | \meta{Id} := \meta{AExp}
         | if \meta{BExp} then \meta{Block} else \meta{Block}
         | while \meta{BExp} do \meta{Block}\\
: \meta{Stmts} ::= \meta{Stmt} ; \meta{Stmts}
          | \meta{Stmt}\\
: \meta{Block} ::= \{ \meta{Stmts} \}
          | \meta{Stmt}\\
: \meta{AExp} ::= \ldots\\
: \meta{BExp} ::= \ldots\\\end{plstx}}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{\begin{tabular}{c}Aexps\end{tabular}}

\begin{center}
\bl{\begin{tabular}{@{}lcl@{}}
$\text{eval}(n)$ & $\dn$ & $n$\\
$\text{eval}(a_1 + a_2)$ & $\dn$ & $\text{eval}(a_1) + \text{eval}(a_2)$\\
$\text{eval}(a_1 - a_2)$ & $\dn$ & $\text{eval}(a_1) - \text{eval}(a_2)$\\
$\text{eval}(a_1 * a_2)$ & $\dn$ & $\text{eval}(a_1) * \text{eval}(a_2)$\bigskip\\
$\text{eval}(x)$ & $\dn$ & $???$\\
\end{tabular}}
\end{center}

\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{\begin{tabular}{c}Interpreter\end{tabular}}

\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{An Interpreter (1)}

\begin{center}
\bl{\begin{tabular}{l}
$\{$\\
\;\;$x := 5 \text{;}$\\
\;\;$y := x * 3\text{;}$\\
\;\;$y := x * 4\text{;}$\\
\;\;$x := u * 3$\\
$\}$
\end{tabular}}
\end{center}

\begin{itemize}
\item the interpreter has to record the value of \bl{$x$} before assigning a value to \bl{$y$}\pause
\item \bl{\texttt{eval(stmt, env)}}
\end{itemize}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{\begin{tabular}{c}Interpreter (2)\end{tabular}}

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[t]
\frametitle{\begin{tabular}{c}Interpreted Code\end{tabular}}

\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}[t,fragile]
%\begin{mybox3}{}
%   In CW3, in the collatz program there is the line write "$\backslash$n" Should this print "/n" or perform the new line command /n ? Also should write be print() or println() ?
%\end{mybox3}
%\end{frame}
%
%
\begin{frame}<1-30>[c]
\end{frame}


\end{document}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{\begin{tabular}{c}Java Virtual Machine\end{tabular}}

\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 compile to the JVM: Scala, Clojure\ldots
\end{itemize}

\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   



% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \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          & \cellcolor{blue!50} 6 While-Language \\
%           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}[c]
% \small
% \mbox{}\\[5mm]
% %\begin{textblock}{10}(3,5)
% \begin{tikzpicture}[scale=1.5,
%                     node distance=1cm,
%                     every node/.style={minimum size=7mm}]
% \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{center}
% \begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
%   \\[-10mm]
%   \bl{$inj\,(c)\,c\,Empty$} & \bl{$\dn$}  & \bl{$Char\,c$}\\
%   \bl{$inj\,(r_1 + r_2)\,c\,Left(v)$} & \bl{$\dn$}  & \bl{$Left(inj\,r_1\,c\,v)$}\\
%   \bl{$inj\,(r_1 + r_2)\,c\,Right(v)$} & \bl{$\dn$}  & \bl{$Right(inj\,r_2\,c\,v)$}\\
%   \bl{$inj\,(r_1 \cdot r_2)\,c\,Seq(v_1,v_2)$} & \bl{$\dn$}  & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\
%   \bl{$inj\,(r_1 \cdot r_2)\,c\,Left(Seq(v_1,v_2))$} & \bl{$\dn$}  & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\
%   \bl{$inj\,(r_1 \cdot r_2)\,c\,Right(v)$} & \bl{$\dn$}  & \bl{$Seq(mkeps(r_1),inj\,r_2\,c\,v)$}\\
%   \bl{$inj\,(r^*)\,c\,Seq(v,vs)$} & \bl{$\dn$}  & \bl{$inj\,r\,c\,v\,::\,vs$}\\
% \end{tabular}
% \end{center}

% \end{frame}
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Starting Symbol}

\bl{\begin{plstx}[margin=1cm]
  : \meta{S} ::= \meta{A}\cdot\meta{S}\cdot\meta{B} |
                 \meta{B}\cdot\meta{S}\cdot\meta{A} | \epsilon\\
  : \meta{A} ::= a | \epsilon\\
  : \meta{B} ::= b\\  
\end{plstx}}


TODO: Testcases for math expressions
\url{https://github.com/ArashPartow/math-parser-benchmark-project}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Hierarchy of Languages}

Recall that languages are sets of strings.

\begin{center}
\begin{tikzpicture}
[rect/.style={draw=black!50, top color=white,bottom color=black!20, rectangle, very thick, rounded corners}]

\draw (0,0) node [rect, text depth=39mm, text width=68mm] {all languages};
\draw (0,-0.4) node [rect, text depth=28.5mm, text width=64mm] {decidable languages};
\draw (0,-0.85) node [rect, text depth=17mm] {context sensitive languages};
\draw (0,-1.14) node [rect, text depth=9mm, text width=50mm] {context-free languages};
\draw (0,-1.4) node [rect] {regular languages};
\end{tikzpicture}

\end{center}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Parser Combinators}
  
Atomic parsers, for example

\begin{center}
\bl{$1::rest \;\Rightarrow\; \{(1, rest)\}$} 
\end{center}\bigskip

\begin{itemize}
\item you consume one or more tokens from the\\ 
  input (stream)
\item also works for characters and strings
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]

Alternative parser (code \bl{$p\;|\;q$})\bigskip

\begin{itemize}
\item apply \bl{$p$} and also \bl{$q$}; then combine 
  the outputs
\end{itemize}

\begin{center}
\large \bl{$p(\text{input}) \cup q(\text{input})$}
\end{center}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]

Sequence parser (code \bl{$p\sim q$})\bigskip

\begin{itemize}
\item apply first \bl{$p$} producing a set of pairs
\item then apply \bl{$q$} to the unparsed parts
\item then combine the results:\medskip 
\begin{center}
((output$_1$, output$_2$), unparsed part)
\end{center}
\end{itemize}

\begin{center}
\begin{tabular}{l}
\large \bl{$\{((o_1, o_2), u_2) \;|\;$}\\[2mm] 
\large\mbox{}\hspace{15mm} \bl{$(o_1, u_1) \in p(\text{input}) \wedge$}\\[2mm]
\large\mbox{}\hspace{15mm} \bl{$(o_2, u_2) \in q(u_1)\}$}
\end{tabular}
\end{center}


\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]

Function parser (code \bl{$p \Rightarrow f\;$})\bigskip

\begin{itemize}
\item apply \bl{$p$} producing a set of pairs
\item then apply the function \bl{$f$} to each first component
\end{itemize}

\begin{center}
\begin{tabular}{l}
\large \bl{$\{(f(o_1), u_1) \;|\; (o_1, u_1) \in p(\text{input})\}$}
\end{tabular}
\end{center}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Types of Parsers}

\begin{itemize}
\item {\bf Sequencing}: if \bl{$p$} returns results of type \bl{$T$}, and \bl{$q$} results of type \bl{$S$},
then \bl{$p \sim q$} returns results of type

\begin{center}
\bl{$T \times S$}
\end{center}\pause

\item {\bf Alternative}: if \bl{$p$} returns results of type \bl{$T$} then  \bl{$q$} \alert{must} also have results of type \bl{$T$},
and \bl{$p \;|\; q$} returns results of type

\begin{center}
\bl{$T$}
\end{center}\pause

\item {\bf Semantic Action}: if \bl{$p$} returns results of type \bl{$T$} and \bl{$f$} is a function from
\bl{$T$} to \bl{$S$}, then
\bl{$p \Rightarrow f$} returns results of type

\begin{center}
\bl{$S$}
\end{center}

\end{itemize}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Two Grammars}

Which languages are recognised by the following two grammars?

\bl{\begin{plstx}[margin=3cm]
: \meta{S} ::= \liningnums{1}\cdot\meta{S}\cdot \meta{S} | \epsilon\\
\end{plstx}}

\bl{\begin{plstx}[margin=3cm]
: \meta{U} ::= \liningnums{1}\cdot\meta{U} | \epsilon\\
\end{plstx}}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Ambiguous Grammars}

\begin{center}
\begin{tikzpicture}
\begin{axis}[xlabel={\pcode{1}s},ylabel={time in secs},
    enlargelimits=false,
    xtick={0,100,...,1000},
    xmax=1050,
    ymax=33,
    ytick={0,5,...,30},
    scaled ticks=false,
    axis lines=left,
    width=11cm,
    height=7cm, 
    legend entries={unambiguous,ambiguous},  
    legend pos=north east,
    legend cell align=left,
    x tick label style={font=\small,/pgf/number format/1000 sep={}}]
\addplot[blue,mark=*, mark options={fill=white}] 
  table {s-grammar1.data};
\only<2>{
  \addplot[red,mark=triangle*, mark options={fill=white}] 
  table {s-grammar2.data};}  
\end{axis}
\end{tikzpicture}
\end{center}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Arithmetic Expressions}

A grammar for arithmetic expressions and numbers:

\bl{\begin{plstx}[margin=1cm]
    : \meta{E} ::= \meta{E} \cdot + \cdot \meta{E}
    | \meta{E} \cdot * \cdot \meta{E}
    | ( \cdot \meta{E} \cdot )  | \meta{N}\\
    : \meta{N} ::= \meta{N} \cdot \meta{N} |
    0 | 1 | \ldots | 9\\
\end{plstx}}

Unfortunately it is left-recursive (and ambiguous).\medskip\\
A problem for \alert{recursive descent parsers} (e.g.~parser
combinators).  \bigskip\pause

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Numbers}

\bl{\begin{plstx}[margin=1cm]
    : \meta{N} ::= \meta{N} \cdot \meta{N} |
    0 | 1 | \ldots | 9\\
\end{plstx}}

A non-left-recursive, non-ambiguous grammar for numbers:

\bl{\begin{plstx}[margin=1cm]
    : \meta{N} ::= 0 \cdot \meta{N} | 1 \cdot \meta{N} | \ldots |
    0 | 1 | \ldots | 9\\
\end{plstx}}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Removing Left-Recursion}

The rule for numbers is directly left-recursive:

\begin{center}
\bl{\begin{tabular}{lcl}
$\meta{N}$ & $::=$ & $\meta{N} \cdot \meta{N} \;|\; 0 \;|\; 1\;\;\;\;(\ldots)$ 
\end{tabular}}
\end{center}

Translate

\begin{center}
\begin{tabular}{ccc}
\bl{\begin{tabular}{lcl}
$\meta{N}$ & $::=$ & $\meta{N} \cdot \alpha$\\
 &  $\;|\;$ & $\beta$\\
 \\ 
\end{tabular}} 
& {\Large$\Rightarrow$} &
\bl{\begin{tabular}{lcl}
$\meta{N}$ & $::=$ & $\beta \cdot \meta{N}'$\\
$\meta{N}'$ & $::=$ & $\alpha \cdot \meta{N}'$\\
 &  $\;|\;$ & $\epsilon$ 
\end{tabular}}
\end{tabular}
\end{center}\pause

Which means in this case:

\begin{center}
\bl{\begin{tabular}{lcl}
$\meta{N}$ & $\rightarrow$ & $0 \cdot \meta{N}' \;|\; 1 \cdot \meta{N}'$\\
$\meta{N}'$ & $\rightarrow$ & $\meta{N} \cdot \meta{N}' \;|\; \epsilon$\\
\end{tabular}}
\end{center}


\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[c]
%\frametitle{Operator Precedences}
%
%
%To disambiguate
%
%\begin{center}
%\bl{\begin{tabular}{lcl}
%$\meta{E}$ & $::=$ &  $\meta{E} \cdot + \cdot \meta{E} \;|\;\meta{E} \cdot * \cdot \meta{E} \;|\;( \cdot \meta{E} \cdot ) \;|\;\meta{N}$ \\
%\end{tabular}}
%\end{center}
%
%Decide on how many precedence levels, say\medskip\\
%highest for \bl{$()$}, medium for \bl{*}, lowest for \bl{+}
%
%\begin{center}
%\bl{\begin{tabular}{lcl}
%$\meta{E}_{low}$ & $::=$ & $\meta{E}_{med} \cdot + \cdot \meta{E}_{low} \;|\; \meta{E}_{med}$ \\
%$\meta{E}_{med}$ & $::=$ & $\meta{E}_{hi} \cdot * \cdot \meta{E}_{med} \;|\; \meta{E}_{hi}$\\
%$\meta{E}_{hi}$ & $::=$ &  $( \cdot \meta{E}_{low} \cdot ) \;|\;\meta{N}$ \\
%\end{tabular}}
%\end{center}\pause
%
%\small What happens with \bl{$1 + 3  + 4$}?
%\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Chomsky Normal Form}

All rules must be of the form

\begin{center}
\bl{$\meta{A} ::= a$}
\end{center}

or

\begin{center}
\bl{$\meta{A} ::= \meta{B}\cdot \meta{C}$}
\end{center}

No rule can contain \bl{$\epsilon$}.

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{\begin{tabular}{c}$\epsilon$-Removal\end{tabular}}

\begin{enumerate}
\item If \bl{$A::= \alpha \cdot B \cdot \beta$} and \bl{$B ::= \epsilon$} are in the grammar,
then add \bl{$A::= \alpha \cdot \beta$} (iterate if necessary).
\item Throw out all \bl{$B ::= \epsilon$}.
\end{enumerate}

\small
\begin{center}
\begin{tabular}{ccc}
\bl{\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
$N$ & $::=$ & $0 \cdot N' \;|\; 1\cdot N'$\\
$N'$ & $::=$ & $N \cdot N'\;|\;\epsilon$\\
\\ 
\\
\\
\\
\\
\end{tabular}} &
\bl{\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
\\
$N$ & $::=$ & $0 \cdot N' \;|\; 1\cdot N'\;|\;0\;|\;1$\\
$N'$ & $::=$ & $N \cdot N'\;|\;N\;|\;\epsilon$\\
\\
$N$ & $::=$ & $0 \cdot N' \;|\; 1\cdot N'\;|\;0\;|\;1$\\
$N'$ & $::=$ & $N \cdot N'\;|\;N$\\
\end{tabular}}
\end{tabular}
\end{center}

\pause\normalsize
\begin{center}
\bl{\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
$N$ & $::=$ & $0 \cdot N\;|\; 1\cdot N\;|\;0\;|\;1$\\
\end{tabular}}

\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{CYK Algorithm}

If grammar is in Chomsky normalform \ldots

\begin{center}
\bl{\begin{tabular}{@ {}lcl@ {}}
$\meta{S}$ & $::=$ &  $\meta{N}\cdot \meta{P}$ \\
$\meta{P}$ & $::=$ &  $\meta{V}\cdot \meta{N}$ \\
$\meta{N}$ & $::=$ &  $\meta{N}\cdot \meta{N}$ \\
$\meta{N}$ & $::=$ &  $\texttt{students} \;|\; \texttt{Jeff} \;|\; \texttt{geometry} \;|\; \texttt{trains} $ \\
$\meta{V}$ & $::=$ &  $\texttt{trains}$ 
\end{tabular}}
\end{center}

\bl{\texttt{Jeff trains geometry students}}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{CYK Algorithm}


\begin{itemize}
\item fastest possible algorithm for recognition problem
\item runtime is \bl{$O(n^3)$}\bigskip
\item grammars need to be transformed into CNF
\end{itemize}

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

  \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}
  
We have a lexer and a parser\ldots
  
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]

\begin{center}
\bl{\begin{tabular}{@{}lcl@{}}
\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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]

??%%\mbox{\lstinputlisting[language=while]{../progs/fib.while}}

\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{An Interpreter}

\begin{center}
\bl{\begin{tabular}{l}
$\{$\\
\;\;$x := 5 \text{;}$\\
\;\;$y := x * 3\text{;}$\\
\;\;$y := x * 4\text{;}$\\
\;\;$x := u * 3$\\
$\}$
\end{tabular}}
\end{center}

\begin{itemize}
\item the interpreter has to record the value of \bl{$x$} before assigning a value to \bl{$y$}\pause
\item \bl{\text{eval}(stmt, env)}
\end{itemize}


\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{An 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{An 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{\begin{tabular}{c}Test Program\end{tabular}}

\mbox{}\\[-18mm]\mbox{}

??
%{\lstset{language=While}%%\fontsize{10}{12}\selectfont
%\texttt{\lstinputlisting{../progs/loops.while}}}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[t]
\frametitle{\begin{tabular}{c}Interpreted Code\end{tabular}}

\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\\
\begin{itemize}
\item From the Cradle to the Holy Graal - the JDK Story
\item \url{https://www.youtube.com/watch?v=h419kfbLhUI}
\end{itemize}
\item is garbage collected $\Rightarrow$ no buffer overflows
\item some languages compile to the JVM: Scala, Clojure\ldots
\end{itemize}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{LLVM}

\begin{itemize}
\item LLVM started by academics in 2000 (University of Illinois in 
Urbana-Champaign)
\item suite of compiler tools
\item SSA-based intermediate language
\item no need to allocate registers
\item source languages: C, C++, Rust, Go, Swift
\item target CPUs: x86, ARM, PowerPC, \ldots
\end{itemize}  
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[c]
%  \frametitle{Coursework: MkEps}
%
%\begin{center}
%\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
%  \bl{$mkeps([c_1 c_2 \ldots c_n])$}  & \bl{$\dn$} & $\bl{undefined}$\\
%  \bl{$mkeps(r^*)$}                   & \bl{$\dn$} & $\bl{Stars\,[]}$\\
%  \bl{$mkeps(r^{\{n\}})$}              & \bl{$\dn$} & $\bl{Stars\,(mkeps(r))^n}$\\
%  \bl{$mkeps(r^{\{n..\}})$}            & \bl{$\dn$} & $\bl{Stars\,(mkeps(r))^n}$\\
%  \bl{$mkeps(r^{\{..n\}})$}            & \bl{$\dn$} & $\bl{Stars\,[]}$\\
%  \bl{$mkeps(r^{\{n..m\}})$}           & \bl{$\dn$} & $\bl{Stars\,(mkeps(r))^n}$\medskip\\
%  
%  \bl{$mkeps(r^+)$}                   & \bl{$\dn$} & \bl{$mkeps(r^{\{1..\}})$}\\
%  \bl{$mkeps(r^?)$}                   & \bl{$\dn$} & \bl{$mkeps(r^{\{..1\}})$}\\
%\end{tabular}
%\end{center}
%
%\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[c]
%  \frametitle{Coursework: Inj}
%
%\begin{center}
%\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
%  \bl{$inj([c_1 c_2 \ldots c_n])\,c\,Empty$}  & \bl{$\dn$} & $\bl{Chr\,c}$\\
%  \bl{$inj(r^*)\,c\;(Seq\,v\,(Stars\,vs))$}                   & \bl{$\dn$} & $\bl{Stars\,(inj\,r\,c\,v::vs)}$\\
%  \bl{$inj(r^{\{n\}})\,c\;(Seq\,v\,(Stars\,vs))$}              & \bl{$\dn$} & $\bl{Stars\,(inj\,r\,c\,v::vs)}$\\
%  \bl{$inj(r^{\{n..\}})\,c\;(Seq\,v\,(Stars\,vs))$}            & \bl{$\dn$} & $\bl{Stars\,(inj\,r\,c\,v::vs)}$\\
%  \bl{$inj(r^{\{..n\}})\,c\;(Seq\,v\,(Stars\,vs))$}            & \bl{$\dn$} & $\bl{Stars\,(inj\,r\,c\,v::vs)}$\\
%  \bl{$inj(r^{\{n..m\}})\,c\;(Seq\,v\,(Stars\,vs))$}           & \bl{$\dn$} & $\bl{Stars\,(inj\,r\,c\,v::vs)}$\medskip\\
%  
%  \bl{$inj(r^+)\,c\,v$}                   & \bl{$\dn$} & \bl{$inj(r^{\{1..\}})\,c\,v$}\\
%  \bl{$inj(r^?)\,c\,v$}                   & \bl{$\dn$} & \bl{$inj(r^{\{..1\}})\,c\,v$}\\
%\end{tabular}
%\end{center}
%
%\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
%




\end{document}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Parser Combinators}

Parser combinators: \bigskip

\begin{minipage}{1.1\textwidth}
\begin{center}
\mbox{}\hspace{-12mm}\mbox{}$\underbrace{\text{list of tokens}}_{\text{input}}$ \bl{$\Rightarrow$} 
$\underbrace{\text{set of (parsed input, unparsed input)}}_{\text{output}}$
\end{center}
\end{minipage}\bigskip

\begin{itemize}
\item atomic parsers
\item sequencing
\item alternative
\item semantic action (map-parser)
\end{itemize}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]

Atomic parsers, for example, number tokens

\begin{center}
\bl{$\texttt{Num(123)}::rest \;\Rightarrow\; \{(\texttt{Num(123)}, rest)\}$} 
\end{center}\bigskip

\begin{itemize}
\item you consume one or more token from the\\ 
  input (stream)
\item also works for characters and strings
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]

Alternative parser (code \bl{$p\;||\;q$})\bigskip

\begin{itemize}
\item apply \bl{$p$} and also \bl{$q$}; then combine 
  the outputs
\end{itemize}

\begin{center}
\large \bl{$p(\text{input}) \cup q(\text{input})$}
\end{center}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]

Sequence parser (code \bl{$p\sim q$})\bigskip

\begin{itemize}
\item apply first \bl{$p$} producing a set of pairs
\item then apply \bl{$q$} to the unparsed part
\item then combine the results:\medskip 
\begin{center}
((output$_1$, output$_2$), unparsed part)
\end{center}
\end{itemize}

\begin{center}
\begin{tabular}{l}
\large \bl{$\{((o_1, o_2), u_2) \;|\;$}\\[2mm] 
\large\mbox{}\hspace{15mm} \bl{$(o_1, u_1) \in p(\text{input}) \wedge$}\\[2mm]
\large\mbox{}\hspace{15mm} \bl{$(o_2, u_2) \in q(u_1)\}$}
\end{tabular}
\end{center}


\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]

Map-parser (code \bl{$p.map(f)\;$})\bigskip

\begin{itemize}
\item apply \bl{$p$} producing a set of pairs
\item then apply the function \bl{$f$} to each first component
\end{itemize}

\begin{center}
\begin{tabular}{l}
\large \bl{$\{(f(o_1), u_1) \;|\; (o_1, u_1) \in p(\text{input})\}$}
\end{tabular}
\end{center}\bigskip\bigskip\pause

\bl{$f$} is the semantic action (``what to do with the parsed input'')

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{\begin{tabular}{c}Semantic Actions\end{tabular}}

Addition

\begin{center}
\bl{$\meta{T} \sim + \sim \meta{E} \Rightarrow \underbrace{f\,((x,y), z) \Rightarrow x + z}_{\text{semantic action}}$}
\end{center}\pause

Multiplication

\begin{center}
\bl{$\meta{F} \sim * \sim \meta{T} \Rightarrow f\,((x,y), z) \Rightarrow x * z$}
\end{center}\pause

Parenthesis

\begin{center}
\bl{$\text{(} \sim \meta{E} \sim \text{)} \Rightarrow f\,((x,y), z) \Rightarrow y$}
\end{center}

\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Types of Parsers}

\begin{itemize}
\item {\bf Sequencing}: if \bl{$p$} returns results of type \bl{$T$}, and \bl{$q$} results of type \bl{$S$},
then \bl{$p \sim q$} returns results of type

\begin{center}
\bl{$T \times S$}
\end{center}\pause

\item {\bf Alternative}: if \bl{$p$} returns results of type \bl{$T$} then  \bl{$q$} \alert{must} also have results of type \bl{$T$},
and \bl{$p \;||\; q$} returns results of type

\begin{center}
\bl{$T$}
\end{center}\pause

\item {\bf Semantic Action}: if \bl{$p$} returns results of type \bl{$T$} and \bl{$f$} is a function from
\bl{$T$} to \bl{$S$}, then
\bl{$p \Rightarrow f$} returns results of type

\begin{center}
\bl{$S$}
\end{center}

\end{itemize}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Input Types of Parsers}

\begin{itemize}
\item input: \alert{token list}
\item output: set of (output\_type, \alert{token list})
\end{itemize}\bigskip\pause

actually it can be any input type as long as it is a kind of
sequence (for example a string)

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Scannerless Parsers}

\begin{itemize}
\item input: \alert{string}
\item output: set of (output\_type, \alert{string})
\end{itemize}\bigskip\bigskip

but using lexers is better because whitespaces or comments can be
filtered out; then input is a sequence of tokens

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Successful Parses}

\begin{itemize}
\item input: string
\item output: \alert{set of} (output\_type, string)
\end{itemize}\bigskip

a parse is successful whenever the input has been fully
``consumed'' (that is the second component is empty)

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Abstract Parser Class}

\small
\lstinputlisting[language=Scala,xleftmargin=1mm]
 {../progs/app7.scala}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]

\small
\fontsize{10}{12}\selectfont
\lstinputlisting[language=Scala,xleftmargin=1mm]
  {../progs/app8.scala}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Two Grammars}

Which languages are recognised by the following two grammars?

\begin{center}
\bl{\begin{tabular}{lcl}
$\meta{S}$ & $\rightarrow$ &  $1 \cdot \meta{S} \cdot \meta{S}$\\
        & $|$ & $\epsilon$
\end{tabular}}
\end{center}\bigskip

\begin{center}
\bl{\begin{tabular}{lcl}
$\meta{U}$ & $\rightarrow$ &  $1 \cdot \meta{U}$\\
        & $|$ & $\epsilon$
\end{tabular}}
\end{center}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Ambiguous Grammars}

\begin{center}
\begin{tikzpicture}
\begin{axis}[xlabel={\pcode{1}s},ylabel={time in secs},
    enlargelimits=false,
    xtick={0,100,...,1000},
    xmax=1050,
    ymax=33,
    ytick={0,5,...,30},
    scaled ticks=false,
    axis lines=left,
    width=11cm,
    height=7cm, 
    legend entries={unambiguous,ambiguous},  
    legend pos=north east,
    legend cell align=left,
    x tick label style={font=\small,/pgf/number format/1000 sep={}}]
\addplot[blue,mark=*, mark options={fill=white}] 
  table {s-grammar1.data};
\only<2>{
  \addplot[red,mark=triangle*, mark options={fill=white}] 
  table {s-grammar2.data};}  
\end{axis}
\end{tikzpicture}
\end{center}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

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




%%% Local Variables:  
%%% mode: latex
%%% TeX-master: t
%%% End: