\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}}
\end{center}\bigskip
\bl{\texttt{if a then if x then y else c}}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: