\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}{AFL 06, King's College London}

\begin{document}

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

\begin{frame}[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}

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

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

\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

\small

\noindent So we cannot find out with regular expressions

whether parentheses are matched or unmatched.

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Hierarchy of Languages}

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

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}

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

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

\begin{frame}[c]

\frametitle{Palindromes}

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

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

\small

Can you find the grammar rules for matched parentheses?

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Arithmetic Expressions}

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

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

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

\begin{frame}[c]

\frametitle{A CFG Derivation}

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

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

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

\begin{frame}[c]

\frametitle{Example Derivation}

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

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

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

\begin{frame}[c]

\frametitle{Example Derivation}

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

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

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

\begin{frame}[c]

\frametitle{Language of a CFG}

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}

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

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

\begin{frame}[c]

\frametitle{Parse Trees}

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

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

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

\begin{frame}[c]

\frametitle{Arithmetic Expressions}

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

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

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

\begin{frame}[c]

\frametitle{Ambiguous Grammars}

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}

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

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

\begin{frame}[c]

\frametitle{Dangling Else}

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}

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

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

\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

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

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

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

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

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

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

\mode<presentation>{

\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}\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{$T \sim + \sim E \Rightarrow \underbrace{f((x,y), z) \Rightarrow x + z}_{\text{semantic action}}$}

\end{center}\pause

Multiplication

\begin{center}

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

\end{center}\pause

Parenthesis

\begin{center}

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