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


\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 \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$}
\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 \Rightarrow 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{string}
\item output: set of (output\_type, \alert{string})
\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;
then input is a sequence of tokens

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

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

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{Abstract Parser Class}

\mbox{\lstset{language=Scala}\fontsize{10}{12}\selectfont
\texttt{\lstinputlisting{../progs/app7.scala}}}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
{\lstset{language=Scala}\fontsize{10}{12}\selectfont
\texttt{\lstinputlisting{../progs/app8.scala}}}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 


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

Which languages are recognised by the following two grammars?

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

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

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


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

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

\begin{center}
\begin{tikzpicture}[y=.2cm, x=.009cm]
 	%axis
	\draw (0,0) -- coordinate (x axis mid) (1000,0);
    	\draw (0,0) -- coordinate (y axis mid) (0,30);
    	%ticks
    	\foreach \x in {0, 20, 100, 200,...,1000}
     		\draw (\x,1pt) -- (\x,-3pt)
			node[anchor=north] {\small \x};
    	\foreach \y in {0,5,...,30}
     		\draw (1pt,\y) -- (-3pt,\y) 
     			node[anchor=east] {\small\y}; 
	%labels      
	\node[below=0.6cm] at (x axis mid) {\bl{1}s};
	\node[rotate=90, left=1.2cm] at (y axis mid) {secs};

	%plots
	\draw[color=blue] plot[mark=*, mark options={fill=white}] 
		file {s-grammar1.data};
         \only<2->{\draw[color=red] plot[mark=triangle*, mark options={fill=white} ] 
                  file {s-grammar2.data};}
	%legend
	\begin{scope}[shift={(400,20)}] 
	\draw[color=blue] (0,0) -- 
		plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0) 
		node[right]{\small unambiguous};
	\only<2->{\draw[yshift=\baselineskip, color=red] (0,0) -- 
                plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0)
                node[right]{\small ambiguous};}  
	\end{scope}
\end{tikzpicture}
\end{center}

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


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


\begin{center}
\bl{\begin{tabular}{@{}lcl@{}}
$Stmt$ & $\rightarrow$ &  $\text{skip}$\\
              & $|$ & $Id := AExp$\\
              & $|$ & $\text{if}\; B\!Exp \;\text{then}\; Block \;\text{else}\; Block$\\
              & $|$ & $\text{while}\; B\!Exp \;\text{do}\; Block$\medskip\\
$Stmts$ & $\rightarrow$ &  $Stmt \;\text{;}\; Stmts$\\
              & $|$ & $Stmt$\medskip\\
$Block$ & $\rightarrow$ &  $\{ Stmts \}$\\
                & $|$ & $Stmt$\medskip\\
$AExp$ & $\rightarrow$ & \ldots\\
$BExp$ & $\rightarrow$ & \ldots\\
\end{tabular}}
\end{center}


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

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

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


  


\end{document}

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