--- a/slides09.tex Sat Nov 24 07:08:51 2012 +0000
+++ b/slides09.tex Sat Nov 24 14:58:27 2012 +0000
@@ -20,6 +20,8 @@
\usetikzlibrary{calc}
\usetikzlibrary{plotmarks}
\usepackage{graphicx}
+\usepackage{pgfplots}
+
\definecolor{javared}{rgb}{0.6,0,0} % for strings
\definecolor{javagreen}{rgb}{0.25,0.5,0.35} % comments
@@ -57,6 +59,7 @@
morestring=[b]"""
}
+
\lstset{language=Scala,
basicstyle=\ttfamily,
keywordstyle=\color{javapurple}\bfseries,
@@ -71,6 +74,29 @@
showspaces=false,
showstringspaces=false}
+\lstdefinelanguage{while}{
+ morekeywords={if,then,else,while,do,true,false},
+ otherkeywords={=,!=,:=,<,>},
+ sensitive=true,
+ morecomment=[n]{/*}{*/},
+}
+
+
+\lstset{language=While,
+ 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 09, King's College London, 28.~November 2012}
\newcommand{\bl}[1]{\textcolor{blue}{#1}}
@@ -78,48 +104,18 @@
% The data files, written on the first run.
-\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
+\begin{filecontents}{compiled.data}
+1 0.0207
+5000 0.0217
+10000 0.0297
+50000 0.1034
+100000 0.3873
+500000 1.27949
+1000000 5. 35424
\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
+\begin{filecontents}{interpreted.data}
+
\end{filecontents}
@@ -144,45 +140,54 @@
\end{tabular}
\end{center}
-
\end{frame}}
- %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Building a ``Web Browser''\end{tabular}}
+\frametitle{\begin{tabular}{c}While-Language\end{tabular}}
-Using a lexer: assume the following regular expressions
\begin{center}
-\bl{\begin{tabular}{lcl}
-$SY\!M$ & $\dn$ & $(\text{a}..\text{zA}..\text{Z0}..\text{9}..)$\\
-$W\!O\!RD$ & $\dn$ & $SY\!M^+$\\
-$BT\!AG$ & $\dn$ & $<\!W\!O\!RD\!>$\\
-$ET\!AG$ & $\dn$ & $<\!/W\!O\!RD\!>$\\
-$W\!HIT\!E$ & $\dn$ & $\texttt{" "} + \texttt{"}\slash{}n\texttt{"}$\\
+\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$\\
+ & $|$ & $\alert{\text{write}\; Id}$\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}Interpreting a List of Tokens\end{tabular}}
+\frametitle{\begin{tabular}{c}Fibonacci Numbers\end{tabular}}
+
+\mbox{}\\[-18mm]\mbox{}
+
+{\lstset{language=While}\fontsize{10}{12}\selectfont
+\texttt{\lstinputlisting{app9.while}}}
-\begin{itemize}
-\item the text should be formatted consistently up to a specified width, say 60 characters
-\item potential linebreaks are inserted by the formatter (not the input)
-\item repeated whitespaces are ``condensed'' to a single whitepace
-\item \bl{$<\!p\!>$} \bl{$<\!\slash{}p\!>$} start/end paragraph
-\item \bl{$<\!b\!>$} \bl{$<\!\slash{}b\!>$} start/end bold
-\item \bl{$<\!red\!>$} \bl{$<\!\slash{}red\!>$} start/end red (cyan, etc)
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Interpreter\end{tabular}}
-\end{itemize}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -497,87 +502,39 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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]
-{\lstset{language=Scala}\fontsize{10}{12}\selectfont
-\texttt{\lstinputlisting{app7.scala}}}
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-{\lstset{language=Scala}\fontsize{10}{12}\selectfont
-\texttt{\lstinputlisting{app7.scala}}}
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-{\lstset{language=Scala}\fontsize{10}{12}\selectfont
-\texttt{\lstinputlisting{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{frame}[t]
+\frametitle{\begin{tabular}{c}Compiled vs.~Interpreted Code\end{tabular}}
\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}}
+\begin{tikzpicture}
+\begin{axis}[axis x line=bottom, axis y line=left, xlabel=n, ylabel=mins]
+\addplot file {compiled.data};
+\end{axis}
+\end{tikzpicture}
\end{center}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[t]
-\frametitle{\begin{tabular}{c}Ambiguous Grammars\end{tabular}}
+\frametitle{\begin{tabular}{c}Compiled vs.~Interpreted Code\end{tabular}}
\mbox{}\\[-25mm]\mbox{}
\begin{center}
-\begin{tikzpicture}[y=.2cm, x=.009cm]
+\begin{tikzpicture}[y=.4cm, x=.00000009cm]
%axis
- \draw (0,0) -- coordinate (x axis mid) (1000,0);
- \draw (0,0) -- coordinate (y axis mid) (0,30);
+ \draw (0,0) -- coordinate (x axis mid) (5,0);
+ \draw (0,0) -- coordinate (y axis mid) (0,5);
%ticks
- \foreach \x in {0, 20, 100, 200,...,1000}
+ \foreach \x in {0, 1000,...,10000}
\draw (\x,1pt) -- (\x,-3pt)
- node[anchor=north] {\small \x};
- \foreach \y in {0,5,...,30}
+ node[anchor=north] {\small \x{}00};
+ \foreach \y in {0,0.5,1, ..., 5.5}
\draw (1pt,\y) -- (-3pt,\y)
node[anchor=east] {\small\y};
%labels
@@ -585,88 +542,29 @@
\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};}
+ %\draw[color=blue] plot[mark=*, mark options={fill=white}]
+ % file {compiled.data};
+ %\only<2->{\draw[color=red] plot[mark=triangle*, mark options={fill=white} ]
+ % file {interpreted.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}
+ %\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}What about Left-Recursion?\end{tabular}}
-
-\begin{itemize}
-\item we record when we recursively called a parser\bigskip
-\item whenever the is a recursion, the parser must have consumed something --- so
-we can decrease the input string/list of token by one (at the end)
-\end{itemize}
-\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: