\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 08, King's College London, 21.~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}{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 (8)\\[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}[c]
\frametitle{\begin{tabular}{c}Building a ``Web Browser''\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{"}$\\
\end{tabular}}
\end{center}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{\begin{tabular}{c}Interpreting a List of Tokens\end{tabular}}
\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{itemize}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{\begin{tabular}{c}Interpreting a List of Tokens\end{tabular}}
The lexer cannot prevent errors like
\begin{center}
\bl{$<\!b\!>$} \ldots \bl{$<\!p\!>$} \ldots \bl{$<\!\slash{}b\!>$} \ldots \bl{$<\!\slash{}p\!>$}
\end{center}
or
\begin{center}
\bl{$<\!\slash{}b\!>$} \ldots \bl{$<\!b\!>$}
\end{center}
\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 \Longrightarrow 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]
Token parser:\bigskip
\begin{itemize}
\item if the input is
\begin{center}
\large \bl{$tok_1:: tok_2 :: \ldots :: tok_n$}
\end{center}
then return
\begin{center}
\large \bl{$\{(tok_1,\; tok_2 :: \ldots :: tok_n)\}$}
\end{center}
or
\begin{center}
\large \bl{$\{\}$}
\end{center}
if \bl{$tok_1$} is not the right token we are looking for
\end{itemize}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
Number-Token parser:\bigskip
\begin{itemize}
\item if the input is
\begin{center}
\large \bl{$num\_tok(42):: tok_2 :: \ldots :: tok_n$}
\end{center}
then return
\begin{center}
\large \bl{$\{(42,\; tok_2 :: \ldots :: tok_n)\}$}
\end{center}
or
\begin{center}
\large \bl{$\{\}$}
\end{center}
if \bl{$tok_1$} is not the right token we are looking for
\end{itemize}\pause
\begin{center}
list of tokens \bl{$\Rightarrow$} set of (\alert{int}, list of tokens)
\end{center}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\begin{itemize}
\item if the input is
\begin{center}
\begin{tabular}{l}
\large \bl{$num\_tok(42)::$}\\
\hspace{7mm}\large \bl{$num\_tok(3) ::$}\\
\hspace{14mm}\large \bl{$tok_3 :: \ldots :: tok_n$}
\end{tabular}
\end{center}
and the parser is
\begin{center}
\bl{$ntp \sim ntp$}
\end{center}
the successful output will be
\begin{center}
\large \bl{$\{((42, 3),\; tok_2 :: \ldots :: tok_n)\}$}
\end{center}\pause
Now we can form
\begin{center}
\bl{$(ntp \sim ntp) \Longrightarrow f$}
\end{center}
where \bl{$f$} is the semantic action (``what to do with the pair'')
\end{itemize}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{\begin{tabular}{c}Semantic Actions\end{tabular}}
Addition
\begin{center}
\bl{$T \sim + \sim E \Longrightarrow \underbrace{f((x,y), z) \Rightarrow x + z}_{\text{semantic action}}$}
\end{center}\pause
Multiplication
\begin{center}
\bl{$F \sim * \sim T \Longrightarrow f((x,y), z) \Rightarrow x * z$}
\end{center}\pause
Parenthesis
\begin{center}
\bl{$\text{(} \sim E \sim \text{)} \Longrightarrow 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 \Longrightarrow 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{list of tokens}
\item output: set of (output\_type, \alert{list of tokens})
\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
\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]
{\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{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}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:
%%% mode: latex
%%% TeX-master: t
%%% End: