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

\usepackage{beamerthemeplainculight}

\usepackage[T1]{fontenc}

\usepackage[latin1]{inputenc}

\usepackage{mathpartir}

\usepackage[absolute,overlay]{textpos}

\usepackage{ifthen}

\usepackage{tikz}

\usepackage{pgf}

\usepackage{calc} 

\usepackage{ulem}

\usepackage{courier}

\usepackage{listings}

\renewcommand{\uline}[1]{#1}

\usetikzlibrary{arrows}

\usetikzlibrary{automata}

\usetikzlibrary{shapes}

\usetikzlibrary{shadows}

\usetikzlibrary{positioning}

\usetikzlibrary{calc}

\usetikzlibrary{plotmarks}

\usepackage{graphicx} 

\definecolor{javared}{rgb}{0.6,0,0} % for strings

\definecolor{javagreen}{rgb}{0.25,0.5,0.35} % comments

\definecolor{javapurple}{rgb}{0.5,0,0.35} % keywords

\definecolor{javadocblue}{rgb}{0.25,0.35,0.75} % javadoc

\lstset{language=Java,

	basicstyle=\ttfamily,

	keywordstyle=\color{javapurple}\bfseries,

	stringstyle=\color{javagreen},

	commentstyle=\color{javagreen},

	morecomment=[s][\color{javadocblue}]{/**}{*/},

	numbers=left,

	numberstyle=\tiny\color{black},

	stepnumber=1,

	numbersep=10pt,

	tabsize=2,

	showspaces=false,

	showstringspaces=false}

\lstdefinelanguage{scala}{

  morekeywords={abstract,case,catch,class,def,%

    do,else,extends,false,final,finally,%

    for,if,implicit,import,match,mixin,%

    new,null,object,override,package,%

    private,protected,requires,return,sealed,%

    super,this,throw,trait,true,try,%

    type,val,var,while,with,yield},

  otherkeywords={=>,<-,<\%,<:,>:,\#,@},

  sensitive=true,

  morecomment=[l]{//},

  morecomment=[n]{/*}{*/},

  morestring=[b]",

  morestring=[b]',

  morestring=[b]"""

}

\lstset{language=Scala,

	basicstyle=\ttfamily,

	keywordstyle=\color{javapurple}\bfseries,

	stringstyle=\color{javagreen},

	commentstyle=\color{javagreen},

	morecomment=[s][\color{javadocblue}]{/**}{*/},

	numbers=left,

	numberstyle=\tiny\color{black},

	stepnumber=1,

	numbersep=10pt,

	tabsize=2,

	showspaces=false,

	showstringspaces=false}

% beamer stuff 

\renewcommand{\slidecaption}{AFL 08, King's College London, 21.~November 2012}

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

\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions

% The data files, written on the first run.

\begin{filecontents}{s-grammar1.data}

1 0.01152

51 0.07973

101 0.09726

151 0.09320

201 0.10010

251 0.16997

301 0.26662

351 0.46118

401 0.62516

451 0.87247

501 1.16334

551 1.71152

601 2.10958

651 2.44360

701 2.98488

751 3.50326

801 4.11036

851 4.93394

901 5.77465

951 7.39123

\end{filecontents}

\begin{filecontents}{s-grammar2.data}

1 0.01280

2 0.00064

3 0.00173

4 0.00355

5 0.00965

6 0.02674

7 0.06953

8 0.11166

9 0.18707

10 0.09189

11 0.12724

12 0.24337

13 0.59304

14 1.53594

15 4.01195

16 10.73582

17 29.51587

#18 73.14163

\end{filecontents}

\begin{document}

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

\mode<presentation>{

\begin{frame}<1>[t]

\frametitle{%

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

  \\[-3mm]

  \LARGE Automata and \\[-2mm] 

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

  \end{tabular}}

  \normalsize

  \begin{center}

  \begin{tabular}{ll}

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

  Of$\!$fice: & S1.27 (1st floor Strand Building)\\

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

  \end{tabular}

  \end{center}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}Building a ``Web Browser''\end{tabular}}

Using a lexer: assume the following regular expressions

\begin{center}

\bl{\begin{tabular}{lcl}

$SY\!M$ & $\dn$ & $(\text{a}..\text{zA}..\text{Z0}..\text{9}..)$\\

$W\!O\!RD$ & $\dn$ & $SY\!M^+$\\

$BT\!AG$ & $\dn$ & $<\!W\!O\!RD\!>$\\

$ET\!AG$ & $\dn$ & $<\!/W\!O\!RD\!>$\\

$W\!HIT\!E$ & $\dn$ & $\texttt{" "} + \texttt{"}\slash{}n\texttt{"}$\\

\end{tabular}}

\end{center}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}Interpreting a List of Tokens\end{tabular}}

\begin{itemize}

\item the text should be formatted consistently up to a specified width, say 60 characters 

\item potential linebreaks are inserted by the formatter (not the input)

\item repeated whitespaces are ``condensed'' to a single whitepace

\item \bl{$<\!p\!>$} \bl{$<\!\slash{}p\!>$}  start/end paragraph

\item \bl{$<\!b\!>$} \bl{$<\!\slash{}b\!>$}  start/end bold

\item \bl{$<\!red\!>$} \bl{$<\!\slash{}red\!>$}  start/end red (cyan, etc)

\end{itemize}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}Interpreting a List of Tokens\end{tabular}}

The lexer cannot prevent errors like

\begin{center}

\bl{$<\!b\!>$} \ldots \bl{$<\!p\!>$} \ldots \bl{$<\!\slash{}b\!>$} \ldots \bl{$<\!\slash{}p\!>$} 

\end{center}

or

\begin{center}

\bl{$<\!\slash{}b\!>$} \ldots \bl{$<\!b\!>$}

\end{center}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}Parser Combinators\end{tabular}}

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 sequencing

\item alternative

\item semantic action

\end{itemize}

\end{frame}}

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

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

\mode<presentation>{

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

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

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

\mode<presentation>{

\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:\\ \mbox{}\;\;((output$_1$, output$_2$), unparsed part)

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

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

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

\mode<presentation>{

\begin{frame}[c]

Function parser (code \bl{$p \Longrightarrow 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]

Token parser:\bigskip

\begin{itemize}

\item if the input is

\begin{center}

\large \bl{$tok_1:: tok_2 :: \ldots :: tok_n$}

\end{center}

then return

\begin{center}

\large \bl{$\{(tok_1,\; tok_2 :: \ldots :: tok_n)\}$}

\end{center}

or

\begin{center}

\large \bl{$\{\}$}

\end{center}

if \bl{$tok_1$} is not the right token we are looking for

\end{itemize}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

Number-Token parser:\bigskip

\begin{itemize}

\item if the input is

\begin{center}

\large \bl{$num\_tok(42):: tok_2 :: \ldots :: tok_n$}

\end{center}

then return

\begin{center}

\large \bl{$\{(42,\; tok_2 :: \ldots :: tok_n)\}$}

\end{center}

or

\begin{center}

\large \bl{$\{\}$}

\end{center}

if \bl{$tok_1$} is not the right token we are looking for

\end{itemize}\pause

\begin{center}

list of tokens \bl{$\Rightarrow$} set of (\alert{int}, list of tokens)

\end{center}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

\begin{itemize}

\item if the input is

\begin{center}

\begin{tabular}{l}

\large \bl{$num\_tok(42)::$}\\

\hspace{7mm}\large \bl{$num\_tok(3) ::$}\\

\hspace{14mm}\large \bl{$tok_3 :: \ldots :: tok_n$}

\end{tabular}

\end{center}

and the parser is 

\begin{center}

\bl{$ntp \sim ntp$}

\end{center}

the successful output will be

\begin{center}

\large \bl{$\{((42, 3),\; tok_2 :: \ldots :: tok_n)\}$}

\end{center}\pause

Now we can form

\begin{center}

\bl{$(ntp \sim ntp) \Longrightarrow f$}

\end{center}

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

\end{itemize}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}Semantic Actions\end{tabular}}

Addition

\begin{center}

\bl{$T \sim + \sim E \Longrightarrow \underbrace{f((x,y), z) \Rightarrow x + z}_{\text{semantic action}}$}

\end{center}\pause

Multiplication

\begin{center}

\bl{$F \sim * \sim T \Longrightarrow f((x,y), z) \Rightarrow x * z$}

\end{center}\pause

Parenthesis

\begin{center}

\bl{$\text{(} \sim E \sim \text{)} \Longrightarrow f((x,y), z) \Rightarrow y$}

\end{center}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}Types of Parsers\end{tabular}}

\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 \Longrightarrow f$} returns results of type

\begin{center}

\bl{$S$}

\end{center}

\end{itemize}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}Input Types of Parsers\end{tabular}}

\begin{itemize}

\item input: \alert{list of tokens}

\item output: set of (output\_type, \alert{list of tokens})

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

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

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

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}Scannerless Parsers\end{tabular}}

\begin{itemize}

\item input: \alert{string}

\item output: set of (output\_type, \alert{string})

\end{itemize}\bigskip

but lexers are better when whitespaces or comments need to be filtered out

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}Successful Parses\end{tabular}}

\begin{itemize}

\item input: string