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

\usepackage{beamerthemeplaincu}

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

\setmonofont{Consolas}

\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

\makeatletter

\lst@CCPutMacro\lst@ProcessOther {"2D}{\lst@ttfamily{-{}}{-{}}}

\@empty\z@\@empty

\makeatother

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

}

\lstdefinelanguage{while}{

  morekeywords={while, if, then. else, read, write},

  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 06, King's College London, 30.~October 2013}

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

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

\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 (6)\\[3mm] 

  \end{tabular}}

  \normalsize

  \begin{center}

  \begin{tabular}{ll}

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

  Office: & 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}Regular Languages\end{tabular}}

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}

\end{frame}}

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

\newcommand{\qq}{\mbox{\texttt{"}}}

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

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}Grammars\end{tabular}}

A (context-free) grammar \bl{$G$} consists of

\begin{itemize}

\item a finite set of nonterminal symbols (upper case)

\item a finite terminal symbols or tokens (lower case)

\item a start symbol (which must be a nonterminal)

\item a set of rules

\begin{center}

\bl{$A \rightarrow \text{rhs}$}

\end{center}

where \bl{rhs} are sequences involving terminals and nonterminals,

including the empty sequence \bl{$\epsilon$}.\medskip\pause

We also allow rules

\begin{center}

\bl{$A \rightarrow \text{rhs}_1 | \text{rhs}_2 | \ldots$}

\end{center}

\end{itemize}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}Palindromes\end{tabular}}

\begin{center}

\bl{\begin{tabular}{lcl}

$S$ & $\rightarrow$ &  $\epsilon$ \\

$S$ & $\rightarrow$ &  $a\cdot S\cdot a$ \\

$S$ & $\rightarrow$ &  $b\cdot S\cdot b$ \\

\end{tabular}}

\end{center}\pause

or

\begin{center}

\bl{\begin{tabular}{lcl}

$S$ & $\rightarrow$ &  $\epsilon \;|\; a\cdot S\cdot a \;|\;b\cdot S\cdot b$ \\

\end{tabular}}

\end{center}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}Arithmetic Expressions\end{tabular}}

\begin{center}

\bl{\begin{tabular}{lcl}

$E$ & $\rightarrow$ &  $num\_token$ \\

$E$ & $\rightarrow$ &  $E \cdot + \cdot E$ \\

$E$ & $\rightarrow$ &  $E \cdot - \cdot E$ \\

$E$ & $\rightarrow$ &  $E \cdot * \cdot E$ \\

$E$ & $\rightarrow$ &  $( \cdot E \cdot )$ 

\end{tabular}}

\end{center}\pause

\bl{\texttt{1 + 2 * 3 + 4}}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}A CFG Derivation\end{tabular}}

\begin{enumerate}

\item Begin with a string containing only the start symbol, say \bl{$S$}\bigskip

\item Replace any nonterminal \bl{$X$} in the string by the
right-hand side of some production \bl{$X \rightarrow \text{rhs}$}\bigskip

\item Repeat 2 until there are no nonterminals

\end{enumerate}

\begin{center}

\bl{$S \rightarrow \ldots \rightarrow \ldots  \rightarrow \ldots  \rightarrow \ldots $}

\end{center}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}Example Derivation\end{tabular}}

\begin{center}

\bl{\begin{tabular}{lcl}

$S$ & $\rightarrow$ &  $\epsilon \;|\; a\cdot S\cdot a \;|\;b\cdot S\cdot b$ \\

\end{tabular}}

\end{center}\bigskip

\begin{center}

\begin{tabular}{lcl}

\bl{$S$} & \bl{$\rightarrow$} & \bl{$aSa$}\\

              & \bl{$\rightarrow$} & \bl{$abSba$}\\

              & \bl{$\rightarrow$} & \bl{$abaSaba$}\\

              & \bl{$\rightarrow$} & \bl{$abaaba$}\\

\end{tabular}

\end{center}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}Example Derivation\end{tabular}}

\begin{center}

\bl{\begin{tabular}{lcl}

$E$ & $\rightarrow$ &  $num\_token$ \\

$E$ & $\rightarrow$ &  $E \cdot + \cdot E$ \\

$E$ & $\rightarrow$ &  $E \cdot - \cdot E$ \\

$E$ & $\rightarrow$ &  $E \cdot * \cdot E$ \\

$E$ & $\rightarrow$ &  $( \cdot E \cdot )$ 

\end{tabular}}

\end{center}\bigskip

\begin{center}

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

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

\bl{$E$} & \bl{$\rightarrow$} & \bl{$E*E$}\\

              & \bl{$\rightarrow$} & \bl{$E+E*E$}\\

              & \bl{$\rightarrow$} & \bl{$E+E*E+E$}\\

              & \bl{$\rightarrow^+$} & \bl{$1+2*3+4$}\\

\end{tabular} &\pause

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

\bl{$E$} & \bl{$\rightarrow$} & \bl{$E+E$}\\

              & \bl{$\rightarrow$} & \bl{$E+E+E$}\\

              & \bl{$\rightarrow$} & \bl{$E+E*E+E$}\\

              & \bl{$\rightarrow^+$} & \bl{$1+2*3+4$}\\

\end{tabular}

\end{tabular}

\end{center}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}Language of a CFG\end{tabular}}

Let \bl{$G$} be a context-free grammar with start symbol \bl{$S$}. 

Then the language \bl{$L(G)$} is:

\begin{center}

\bl{$\{c_1\ldots c_n \;|\; \forall i.\; c_i \in T \wedge S \rightarrow^* c_1\ldots c_n \}$}

\end{center}\pause

\begin{itemize}

\item Terminals, because there are no rules for replacing them.

\item Once generated, terminals are ``permanent''.

\item Terminals ought to be tokens of the language\\

(but can also be strings).

\end{itemize}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}Parse Trees\end{tabular}}

\begin{center}

\bl{\begin{tabular}{lcl}

$E$ & $\rightarrow$ &  $F \;|\; F \cdot * \cdot F$\\

$F$ & $\rightarrow$ & $T \;|\; T \cdot + \cdot T \;|\; T \cdot - \cdot T$\\

$T$ & $\rightarrow$ & $num\_token \;|\; ( \cdot E \cdot )$\\

\end{tabular}}

\end{center}

\begin{center}

\begin{tikzpicture}[level distance=8mm, blue]

  \node {$E$}

    child {node {$F$} 

     child {node {$T$} 

                 child {node {(\,$E$\,)}

                            child {node{$F$ *{} $F$}

                                  child {node {$T$} child {node {2}}}

                                  child {node {$T$} child {node {3}}} 

                               }

                          }

              }

     child {node {+}}

     child {node {$T$}

       child {node {(\,$E$\,)} 

       child {node {$F$}

       child {node {$T$ +{} $T$}

                    child {node {3}}

                    child {node {4}} 

                 }

                 }}

    }};

\end{tikzpicture}

\end{center}

\begin{textblock}{5}(1, 6.5)

\bl{\texttt{(2*3)+(3+4)}}

\end{textblock}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}Arithmetic Expressions\end{tabular}}

\begin{center}

\bl{\begin{tabular}{lcl}

$E$ & $\rightarrow$ &  $num\_token$ \\

$E$ & $\rightarrow$ &  $E \cdot + \cdot E$ \\

$E$ & $\rightarrow$ &  $E \cdot - \cdot E$ \\

$E$ & $\rightarrow$ &  $E \cdot * \cdot E$ \\

$E$ & $\rightarrow$ &  $( \cdot E \cdot )$ 

\end{tabular}}

\end{center}\pause\bigskip

A CFG is \alert{left-recursive} if it has a nonterminal \bl{$E$} such

that \bl{$E \rightarrow^+ E\cdot \ldots$}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}Ambiguous Grammars\end{tabular}}

A grammar is \alert{ambiguous} if there is a string that has at least two different parse trees.

\begin{center}

\bl{\begin{tabular}{lcl}

$E$ & $\rightarrow$ &  $num\_token$ \\

$E$ & $\rightarrow$ &  $E \cdot + \cdot E$ \\

$E$ & $\rightarrow$ &  $E \cdot - \cdot E$ \\

$E$ & $\rightarrow$ &  $E \cdot * \cdot E$ \\

$E$ & $\rightarrow$ &  $( \cdot E \cdot )$ 

\end{tabular}}

\end{center}

\bl{\texttt{1 + 2 * 3 + 4}}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}Dangling Else\end{tabular}}

Another ambiguous grammar:\bigskip

\begin{center}

\bl{\begin{tabular}{lcl}

$E$ & $\rightarrow$ &  if $E$ then $E$\\

 & $|$ &  if $E$ then $E$ else $E$ \\

 & $|$ &  \ldots

\end{tabular}}

\end{center}\bigskip

\bl{\texttt{if a then if x then y else c}}

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