--- a/slides08.tex Sat Jun 15 09:11:11 2013 -0400
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,676 +0,0 @@
-\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:
-