\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 07, King's College London, 14.~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}{re-python.data}

1 0.029

5 0.029

10 0.029

15 0.032

16 0.042

17 0.042

18 0.055

19 0.084

20 0.136

21 0.248

22 0.464

23 0.899

24 1.773

25 3.505

26 6.993

27 14.503

28 29.307

#29 58.886

\end{filecontents}

\begin{filecontents}{re-ruby.data}

1 0.00006

2 0.00003

3 0.00001

4 0.00001

5 0.00001

6 0.00002

7 0.00002

8 0.00004

9 0.00007

10 0.00013

11 0.00026

12 0.00055

13 0.00106

14 0.00196

15 0.00378

16 0.00764

17 0.01606

18 0.03094

19 0.06508

20 0.12420

21 0.25393

22 0.51449

23 1.02174

24 2.05998

25 4.22514

26 8.42479

27 16.88678

28 34.79653

\end{filecontents}

\begin{filecontents}{re1.data}

1 0.00179

2 0.00011

3 0.00014

4 0.00026

5 0.00050

6 0.00095

7 0.00190

8 0.00287

9 0.00779

10 0.01399

11 0.01894

12 0.03666

13 0.07994

14 0.08944

15 0.02377

16 0.07392

17 0.22798

18 0.65310

19 2.11360

20 6.31606

21 21.46013

\end{filecontents}

\begin{filecontents}{re2.data}

1  0.00240

2  0.00013

3  0.00020

4  0.00030

5  0.00049

6  0.00083

7  0.00146

8  0.00228

9  0.00351

10  0.00640

11  0.01217

12  0.02565

13  0.01382

14  0.02423

15  0.05065 

16  0.06522

17  0.02140

18  0.05176

19  0.18254

20  0.51898

21  1.39631

22  2.69501

23  8.07952

\end{filecontents}

\begin{filecontents}{re-internal.data}

1 0.00069

301 0.00700

601 0.00297

901 0.00470

1201 0.01301

1501 0.01175

1801 0.01761

2101 0.01787

2401 0.02717

2701 0.03932

3001 0.03470

3301 0.04349

3601 0.05411

3901 0.06181

4201 0.07119

4501 0.08578

\end{filecontents}

\begin{filecontents}{re3.data}

1 0.001605

501 0.131066

1001 0.057885

1501 0.136875

2001 0.176238

2501 0.254363

3001 0.37262

3501 0.500946

4001 0.638384

4501 0.816605

5001 1.00491

5501 1.232505

6001 1.525672

6501 1.757502

7001 2.092784

7501 2.429224

8001 2.803037

8501 3.463045

9001 3.609

9501 4.081504

10001 4.54569

\end{filecontents}

\begin{document}

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

\mode<presentation>{

\begin{frame}<1>[t]

\frametitle{%

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

  \\[-3mm]

  \LARGE Automata and \\[-2mm] 

  \LARGE Formal Languages (7)\\[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}[t]

\frametitle{\begin{tabular}{c}\bl{$(a?\{n\})a\{n\}$}\end{tabular}}

\mbox{}\\[-13mm]

\begin{tikzpicture}[y=.2cm, x=.3cm]

 	%axis

	\draw (0,0) -- coordinate (x axis mid) (30,0);

    	\draw (0,0) -- coordinate (y axis mid) (0,30);

    	%ticks

    	\foreach \x in {0,5,...,30}

     		\draw (\x,1pt) -- (\x,-3pt)

			node[anchor=north] {\x};

    	\foreach \y in {0,5,...,30}

     		\draw (1pt,\y) -- (-3pt,\y) 

     			node[anchor=east] {\y}; 

	%labels      

	\node[below=0.6cm] at (x axis mid) {\bl{a}s};

	\node[rotate=90, left=1.2cm] at (y axis mid) {secs};

	%plots

	\draw[color=blue] plot[mark=*, mark options={fill=white}] 

		file {re-python.data};

	\draw[color=red] plot[mark=triangle*, mark options={fill=white} ] 

		file {re1.data};

         \draw[color=green] plot[mark=square*, mark options={fill=white} ] 

		file {re2.data};

         \draw[color=brown] plot[mark=pentagon*, mark options={fill=white} ] 

		file {re-ruby.data};

	%legend

	\begin{scope}[shift={(4,20)}] 

	\draw[color=blue] (0,0) -- 

		plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0) 

		node[right]{\small Python};

	\draw[yshift=-\baselineskip, color=brown] (0,0) -- 

		plot[mark=pentagon*, mark options={fill=white}] (0.25,0) -- (0.5,0)

		node[right]{\small Ruby (Daniel Baldwin)};

         \draw[yshift=\baselineskip, color=red] (0,0) -- 

		plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0)

		node[right]{\small Scala V1};	

	 \draw[yshift=2\baselineskip, color=green] (0,0) -- 

		plot[mark=square*, mark options={fill=white}] (0.25,0) -- (0.5,0)

		node[right]{\small Scala V2 with simplifications};

	\end{scope}

\end{tikzpicture}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[t]

\begin{tikzpicture}[y=.7cm, x=.0009cm]

 	%axis

	\draw (0,0) -- coordinate (x axis mid) (10000,0);

    	\draw (0,0) -- coordinate (y axis mid) (0,6);

    	%ticks

    	\foreach \x in {0,2000,...,10000}

     		\draw (\x,1pt) -- (\x,-3pt)

			node[anchor=north] {\x};

    	\foreach \y in {0,1,...,6}

     		\draw (1pt,\y) -- (-3pt,\y) 

     			node[anchor=east] {\y}; 

	%labels      

	\node[below=0.6cm] at (x axis mid) {\bl{a}s};

	\node[rotate=90, left=1.2cm] at (y axis mid) {secs};

	%plots

	\draw[color=blue] plot[mark=*, mark options={fill=white}] 

		file {re-internal.data};

	\only<1->{	 

         \draw[color=red] plot[mark=triangle*, mark options={fill=white} ] 

		file {re3.data};}

	%legend

	\begin{scope}[shift={(2000,4)}] 

	\draw[color=blue] (0,0) -- 

		plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0) 

		node[right]{\small Scala Internal};

        \only<1->{

	\draw[yshift=\baselineskip, color=red] (0,0) -- 

		plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0)

		node[right]{\small Scala V3 with explicit $\_\{\_\}$};}

	\end{scope}

\end{tikzpicture}

\begin{center}

\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}}

  \\[-8mm]

  \bl{der c (r$_1$ $\cdot$ r$_2$)} & \bl{$\dn$}  & \bl{if nullable r$_1$}\\

  & & \bl{then ((der c r$_1$) $\cdot$ r$_2$) + (der c r$_2$)}\\ 

  & & \bl{else (der c r$_1$) $\cdot$ r$_2$}\\

  \bl{der c (r$\{n\}$)} & \bl{$\dn$} & \bl{if $n = 0$ then $\varnothing$}\\

  & & \bl{else (der c r) $\cdot$ r$\{n - 1\}$}

  \end{tabular}

\end{center}

\end{frame}}

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

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

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

\mode<presentation>{

\begin{frame}[c]

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

A \alert{context-free} grammar (CFG) \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 (can also be empty).\medskip\pause

We can 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}A CFG Derivation\end{tabular}}

\begin{enumerate}

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

\item Replace any non-terminal \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 non-terminals

\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}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 are so-called because there are no rules for replacing them

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

\item Terminals ought to be tokens of the language (at least in this course)

\end{itemize}

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

A CFG is \alert{ambiguous} if there is a string that has at least 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$ \\

 & $|$ &  id 

\end{tabular}}