--- a/slides/slides05.tex Mon Oct 19 15:03:44 2015 +0100
+++ b/slides/slides05.tex Mon Oct 19 23:49:25 2015 +0100
@@ -3,6 +3,7 @@
\usepackage{../graphics}
\usepackage{../langs}
\usepackage{../data}
+\usepackage{../grammar}
\hfuzz=220pt
@@ -38,7 +39,8 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Last Week\\ Regexes and Values\end{tabular}}
+\frametitle{\begin{tabular}{c}Last Week\\[-1mm]
+ Regexes and Values\end{tabular}}
Regular expressions and their corresponding values:
@@ -73,127 +75,6 @@
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-
-\begin{textblock}{10}(3,5)
-\begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}]
-\node (r1) {\bl{$r_1$}};
-\node (r2) [right=of r1] {\bl{$r_2$}};
-\draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};
-\node (r3) [right=of r2] {\bl{$r_3$}};
-\draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};
-\node (r4) [right=of r3] {\bl{$r_4$}};
-\draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};
-\draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};
-\node (v4) [below=of r4] {\bl{$v_4$}};
-\draw[->,line width=1mm] (r4) -- (v4);
-\node (v3) [left=of v4] {\bl{$v_3$}};
-\draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};
-\node (v2) [left=of v3] {\bl{$v_2$}};
-\draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};
-\node (v1) [left=of v2] {\bl{$v_1$}};
-\draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};
-\draw[->,line width=0.5mm] (r3) -- (v3);
-\draw[->,line width=0.5mm] (r2) -- (v2);
-\draw[->,line width=0.5mm] (r1) -- (v1);
-\draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};
-\end{tikzpicture}
-\end{textblock}
-
-\only<2->{
-\begin{textblock}{6}(1,0.8)
-\begin{bubble}[6cm]
-\small
-\begin{tabular}{ll}
-\bl{$r_1$}: & \bl{$a \cdot (b \cdot c)$}\\
-\bl{$r_2$}: & \bl{$\epsilon \cdot (b \cdot c)$}\\
-\bl{$r_3$}: & \bl{$(\varnothing \cdot (b \cdot c)) + (\epsilon \cdot c)$}\\
-\bl{$r_4$}: & \bl{$(\varnothing \cdot (b \cdot c)) + ((\varnothing \cdot c) + \epsilon)$}\\
-\end{tabular}
-\end{bubble}
-\end{textblock}}
-
-\only<2->{
-\begin{textblock}{6}(5,11.4)
-\begin{bubble}[7.6cm]
-\small
-\begin{tabular}{ll}
-\bl{$v_1$}: & \bl{$Seq(Char(a), Seq(Char(b), Char(c)))$}\\
-\bl{$v_2$}: & \bl{$Seq(Empty, Seq(Char(b), Char(c)))$}\\
-\bl{$v_3$}: & \bl{$Right(Seq(Empty, Char(c)))$}\\
-\bl{$v_4$}: & \bl{$Right(Right(Empty))$}\\
-\end{tabular}
-\end{bubble}
-\end{textblock}}
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Mkeps}
-
-Finding a (posix) value for recognising the empty string:
-
-\begin{center}
-\begin{tabular}{lcl}
- \bl{$mkeps\,\epsilon$} & \bl{$\dn$} & \bl{$Empty$}\\
- \bl{$mkeps\,r_1 + r_2$} & \bl{$\dn$} & \bl{if $nullable(r_1)$} \\
- & & \bl{then $Left(mkeps(r_1))$}\\
- & & \bl{else $Right(mkeps(r_2))$}\\
- \bl{$mkeps\,r_1 \cdot r_2$} & \bl{$\dn$} & \bl{$Seq(mkeps(r_1),mkeps(r_2))$}\\
- \bl{$mkeps\,r^*$} & \bl{$\dn$} & \bl{$[]$} \\
-\end{tabular}
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Inject}
-
-Injecting (``Adding'') a character to a value\\
-
-\begin{center}
-\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
- \bl{$inj\,(c)\,c\,Empty$} & \bl{$\dn$} & \bl{$Char\,c$}\\
- \bl{$inj\,(r_1 + r_2)\,c\,Left(v)$} & \bl{$\dn$} & \bl{$Left(inj\,r_1\,c\,v)$}\\
- \bl{$inj\,(r_1 + r_2)\,c\,Right(v)$} & \bl{$\dn$} & \bl{$Right(inj\,r_2\,c\,v)$}\\
- \bl{$inj\,(r_1 \cdot r_2)\,c\,Seq(v_1,v_2)$} & \bl{$\dn$} & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\
- \bl{$inj\,(r_1 \cdot r_2)\,c\,Left(Seq(v_1,v_2))$} & \bl{$\dn$} & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\
- \bl{$inj\,(r_1 \cdot r_2)\,c\,Right(v)$} & \bl{$\dn$} & \bl{$Seq(mkeps(r_1),inj\,r_2\,c\,v)$}\\
- \bl{$inj\,(r^*)\,c\,Seq(v,vs)$} & \bl{$\dn$} & \bl{$inj\,r\,c\,v\,::\,vs$}\\
-\end{tabular}
-\end{center}\bigskip
-
-\footnotesize
-\bl{$inj$}: 1st arg $\mapsto$ a rexp; 2nd arg $\mapsto$ a character; 3rd arg $\mapsto$ a value
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Flatten}
-
-Obtaining the string underlying a value:
-
-\begin{center}
-\begin{tabular}{lcl}
- \bl{$|Empty|$} & \bl{$\dn$} & \bl{$[]$}\\
- \bl{$|Char(c)|$} & \bl{$\dn$} & \bl{$[c]$}\\
- \bl{$|Left(v)|$} & \bl{$\dn$} & \bl{$|v|$}\\
- \bl{$|Right(v)|$} & \bl{$\dn$} & \bl{$|v|$}\\
- \bl{$|Seq(v_1,v_2)|$}& \bl{$\dn$} & \bl{$|v_1| \,@\, |v_2|$}\\
- \bl{$|[v_1,\ldots ,v_n]|$} & \bl{$\dn$} & \bl{$|v_1| \,@\ldots @\, |v_n|$}\\
-\end{tabular}
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
@@ -307,127 +188,17 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
-\frametitle{Rectification}
-
-\begin{center}
-\begin{tabular}{l}
-\bl{$simp(r)$}:\\
-\quad case \bl{$r = r_1 + r_2$}\\
-\qquad let \bl{$(r_{1s}, f_{1s}) = simp(r_1)$}\\
-\qquad \phantom{let} \bl{$(r_{2s}, f_{2s}) = simp(r_2)$}\smallskip\\
-\qquad case \bl{$r_{1s} = \varnothing$}:
- return \bl{$(r_{2s}, \lambda v. \,Right(f_{2s}(v)))$}\\
-\qquad case \bl{$r_{2s} = \varnothing$}:
- return \bl{$(r_{1s}, \lambda v. \,Left(f_{1s}(v)))$}\\
-\qquad case \bl{$r_{1s} = r_{2s}$}:
- return \bl{$(r_{1s}, \lambda v. \,Left(f_{1s}(v)))$}\\
-\qquad otherwise:
- return \bl{$(r_{1s} + r_{2s}, f_{alt}(f_{1s}, f_{2s}))$}\\
-\end{tabular}
-\end{center}
-
-\small
-\begin{center}
-\begin{tabular}{l@{\hspace{1mm}}l}
-\bl{$f_{alt}(f_1, f_2) \dn$}\\
-\qquad \bl{$\lambda v.\,$} case \bl{$v = Left(v')$}:
- & return \bl{$Left(f_1(v'))$}\\
-\qquad \phantom{$\lambda v.\,$} case \bl{$v = Right(v')$}:
- & return \bl{$Right(f_2(v'))$}\\
-\end{tabular}
-\end{center}
-
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Rectification}
-
-\begin{center}
-\begin{tabular}{@{\hspace{-3mm}}l}
-\bl{$simp(r)$}:\ldots\\
-\quad case \bl{$r = r_1 \cdot r_2$}\\
-\qquad let \bl{$(r_{1s}, f_{1s}) = simp(r_1)$}\\
-\qquad \phantom{let} \bl{$(r_{2s}, f_{2s}) = simp(r_2)$}\smallskip\\
-\qquad case \bl{$r_{1s} = \varnothing$}:
- return \bl{$(\varnothing, f_{error})$}\\
-\qquad case \bl{$r_{2s} = \varnothing$}:
- return \bl{$(\varnothing, f_{error})$}\\
-\qquad case \bl{$r_{1s} = \epsilon$}:
-return \bl{$(r_{2s}, \lambda v. \,Seq(f_{1s}(Empty), f_{2s}(v)))$}\\
-\qquad case \bl{$r_{2s} = \epsilon$}:
-return \bl{$(r_{1s}, \lambda v. \,Seq(f_{1s}(v), f_{2s}(Empty)))$}\\
-\qquad otherwise:
- return \bl{$(r_{1s} \cdot r_{2s}, f_{seq}(f_{1s}, f_{2s}))$}\\
-\end{tabular}
-\end{center}
-
-\small
-\begin{center}
-\begin{tabular}{l@{\hspace{1mm}}l}
-\bl{$f_{seq}(f_1, f_2) \dn$}\\
-\qquad \bl{$\lambda v.\,$ case $v = Seq(v_1, v_2)$}:
- & return \bl{$Seq(f_1(v_1), f_2(v_2))$}\\
-\end{tabular}
-\end{center}
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Lexing with Simplification}
-
-\begin{center}
-\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
- \bl{$lex\,r\,[]$} & \bl{$\dn$} & \bl{if $nullable(r)$ then $mkeps(r)$ else $error$}\\
- \bl{$lex\,r\,c::s$} & \bl{$\dn$} & \bl{let $(r', frect) = simp(der(c, r))$}\smallskip\\
- & & \bl{$inj\,r\,c\,(frect(lex(r', s)))$}\\
-\end{tabular}
-\end{center}\bigskip
-
-\begin{center}\small
-\begin{tikzpicture}[node distance=1.1cm,every node/.style={minimum size=7mm}]
-\node (r1) {\bl{$r_1$}};
-\node (r2) [right=of r1] {\bl{$r_2$}};
-\draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};
-\node (r3) [right=of r2] {\bl{$r_3$}};
-\draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};
-\node (r4) [right=of r3] {\bl{$r_4$}};
-\draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};
-\draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};
-\node (v4) [below=of r4] {\bl{$v_4$}};
-\draw[->,line width=1mm] (r4) -- (v4);
-\node (v3) [left=of v4] {\bl{$v_3$}};
-\draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};
-\node (v2) [left=of v3] {\bl{$v_2$}};
-\draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};
-\node (v1) [left=of v2] {\bl{$v_1$}};
-\draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};
-\draw[->,line width=0.5mm] (r3) -- (v3);
-\draw[->,line width=0.5mm] (r2) -- (v2);
-\draw[->,line width=0.5mm] (r1) -- (v1);
-\draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};
-\end{tikzpicture}
-\end{center}
-
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
\frametitle{Records}
\begin{itemize}
-\item new regex: \bl{$(x:r)$}\hspace{7mm}new value: \bl{$Rec(x,v)$}\medskip\pause
+\item new regex: \bl{$(x:r)$}\hspace{7mm}new value:
+\bl{$Rec(x,v)$}\medskip
\item \bl{$nullable(x:r) \dn nullable(r)$}
\item \bl{$der\,c\,(x:r) \dn (x:der\,c\,r)$}
\item \bl{$mkeps(x:r) \dn Rec(x, mkeps(r))$}
\item \bl{$inj\,(x:r)\,c\,v \dn Rec(x, inj\,r\,c\,v)$}
-\end{itemize}\bigskip\bigskip\pause
+\end{itemize}\bigskip\bigskip
\small
for extracting subpatterns \bl{$(z: ((x:ab) + (y:ba))$}
@@ -437,6 +208,29 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
+\frametitle{Environments}
+
+Obtaining the ``recorded'' parts of a value:
+
+\begin{center}
+\begin{tabular}{lcl}
+ \bl{$env(Empty)$} & \bl{$\dn$} & \bl{$[]$}\\
+ \bl{$env(Char(c))$} & \bl{$\dn$} & \bl{$[]$}\\
+ \bl{$env(Left(v))$} & \bl{$\dn$} & \bl{$env(v)$}\\
+ \bl{$env(Right(v))$} & \bl{$\dn$} & \bl{$env(v)$}\\
+ \bl{$env(Seq(v_1,v_2))$}& \bl{$\dn$} & \bl{$env(v_1) \,@\, env(v_2)$}\\
+ \bl{$env([v_1,\ldots ,v_n])$} & \bl{$\dn$} &
+ \bl{$env(v_1) \,@\ldots @\, env(v_n)$}\\
+ \bl{$env(Rec(x:v))$} & \bl{$\dn$} & \bl{$(x:|v|) :: env(v)$}\\
+\end{tabular}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
\frametitle{While Tokens}
\begin{center}
@@ -455,13 +249,14 @@
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[t]
\consolas
\begin{center}
-"if true then then 42 else +"
+\code{"if true then then 42 else +"}
\end{center}
\only<1>{
@@ -492,39 +287,12 @@
OP(+)
\end{tabular}}
-\end{frame}}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
-
-
-There is one small problem with the tokenizer. How should we
-tokenize:
-
-\begin{center}
-{\consolas "x - 3"}
-\end{center}
-
-\consolas
-\begin{tabular}{@{}l}
-OP:\\
-\hspace{5mm}\texttt{"+"}, \texttt{"-"}\\
-NUM:\\
-\hspace{5mm}(NONZERODIGIT $\cdot$ DIGIT$^*$) + {''0''}\\
-NUMBER:\\
-\hspace{5mm}NUM + (\texttt{"-"} $\cdot$ NUM)\\
-\end{tabular}
-
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Two Rules\end{tabular}}
+\frametitle{Two Rules}
\begin{itemize}
\item Longest match rule (``maximal munch rule''): The
@@ -544,30 +312,9 @@
%\item problem with infix operations, for example i-12
-\end{frame}}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Environment}
-
-Obtaining the ``recorded'' parts of a regular expression:
-
-\begin{center}
-\begin{tabular}{lcl}
- \bl{$env(Empty)$} & \bl{$\dn$} & \bl{$[]$}\\
- \bl{$env(Char(c))$} & \bl{$\dn$} & \bl{$[]$}\\
- \bl{$env(Left(v))$} & \bl{$\dn$} & \bl{$env(v)$}\\
- \bl{$env(Right(v))$} & \bl{$\dn$} & \bl{$env(v)$}\\
- \bl{$env(Seq(v_1,v_2))$}& \bl{$\dn$} & \bl{$env(v_1) \,@\, env(v_2)$}\\
- \bl{$env([v_1,\ldots ,v_n])$} & \bl{$\dn$} &
- \bl{$env(v_1) \,@\ldots @\, env(v_n)$}\\
- \bl{$env(Rec(x:v))$} & \bl{$\dn$} & \bl{$(x:|v|) :: env(v)$}\\
-\end{tabular}
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
@@ -623,6 +370,681 @@
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Regular Languages}
+
+While regular expressions are very useful for lexing, there is
+no regular expression that can recognise the language
+\bl{$a^nb^n$}.\bigskip
+
+\begin{center}
+\bl{$(((()()))())$} \;\;vs.\;\; \bl{$(((()()))()))$}
+\end{center}\bigskip\bigskip
+
+\small
+\noindent So we cannot find out with regular expressions
+whether parentheses are matched or unmatched. Also regular
+expressions are not recursive, e.g.~\bl{$(1 + 2) + 3$}.
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Hierarchy of Languages}
+
+\begin{center}
+\begin{tikzpicture}
+[rect/.style={draw=black!50,
+ top color=white,
+ bottom color=black!20,
+ rectangle,
+ very thick,
+ rounded corners}, scale=1.2]
+
+\draw (0,0) node [rect, text depth=39mm, text width=68mm] {all languages};
+\draw (0,-0.4) node [rect, text depth=28.5mm, text width=64mm] {decidable languages};
+\draw (0,-0.85) node [rect, text depth=17mm] {context sensitive languages};
+\draw (0,-1.14) node [rect, text depth=9mm, text width=50mm] {context-free languages};
+\draw (0,-1.4) node [rect] {regular languages};
+\end{tikzpicture}
+
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Grammars}
+
+A (context-free) grammar \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 \textit{rhs}$}
+\end{center}
+
+where \bl{\textit{rhs}} are sequences involving terminals and nonterminals,
+including the empty sequence \bl{$\epsilon$}.\medskip\pause
+
+We also allow rules
+\begin{center}
+\bl{$A \rightarrow \textit{rhs}_1 | \textit{rhs}_2 | \ldots$}
+\end{center}
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Palindromes}
+
+A grammar for palindromes over the alphabet~\bl{$\{a,b\}$}:
+
+\begin{center}
+\bl{\begin{tabular}{lcl}
+$S$ & $\rightarrow$ & $\epsilon$ \\
+$S$ & $\rightarrow$ & $a\cdot S\cdot a$ \\
+$S$ & $\rightarrow$ & $b\cdot S\cdot b$ \\
+\end{tabular}}
+\end{center}\pause
+
+or
+
+\begin{center}
+\bl{\begin{tabular}{lcl}
+$S$ & $\rightarrow$ & $\epsilon \;|\; a\cdot S\cdot a \;|\;b\cdot S\cdot b$ \\
+\end{tabular}}
+\end{center}\pause\bigskip
+
+\small
+Can you find the grammar rules for matched parentheses?
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Arithmetic Expressions}
+
+\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
+
+\bl{\texttt{1 + 2 * 3 + 4}}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{A CFG Derivation}
+
+\begin{enumerate}
+\item Begin with a string containing only the start symbol, say \bl{$S$}\bigskip
+\item Replace any nonterminal \bl{$X$} in the string by the
+right-hand side of some production \bl{$X \rightarrow \textit{rhs}$}\bigskip
+\item Repeat 2 until there are no nonterminals
+\end{enumerate}
+
+\begin{center}
+\bl{$S \rightarrow \ldots \rightarrow \ldots \rightarrow \ldots \rightarrow \ldots $}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Example Derivation}
+
+\begin{center}
+\bl{\begin{tabular}{lcl}
+$S$ & $\rightarrow$ & $\epsilon \;|\; a\cdot S\cdot a \;|\;b\cdot S\cdot b$ \\
+\end{tabular}}
+\end{center}\bigskip
+
+\begin{center}
+\begin{tabular}{lcl}
+\bl{$S$} & \bl{$\rightarrow$} & \bl{$aSa$}\\
+ & \bl{$\rightarrow$} & \bl{$abSba$}\\
+ & \bl{$\rightarrow$} & \bl{$abaSaba$}\\
+ & \bl{$\rightarrow$} & \bl{$abaaba$}\\
+
+
+\end{tabular}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Example Derivation}
+
+\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}\bigskip
+
+
+\begin{center}
+\begin{tabular}{@{}c@{}c@{}}
+\begin{tabular}{l@{\hspace{1mm}}l@{\hspace{1mm}}l}
+\bl{$E$} & \bl{$\rightarrow$} & \bl{$E*E$}\\
+ & \bl{$\rightarrow$} & \bl{$E+E*E$}\\
+ & \bl{$\rightarrow$} & \bl{$E+E*E+E$}\\
+ & \bl{$\rightarrow^+$} & \bl{$1+2*3+4$}\\
+\end{tabular} &\pause
+\begin{tabular}{l@{\hspace{1mm}}l@{\hspace{1mm}}l}
+\bl{$E$} & \bl{$\rightarrow$} & \bl{$E+E$}\\
+ & \bl{$\rightarrow$} & \bl{$E+E+E$}\\
+ & \bl{$\rightarrow$} & \bl{$E+E*E+E$}\\
+ & \bl{$\rightarrow^+$} & \bl{$1+2*3+4$}\\
+\end{tabular}
+\end{tabular}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Context Sensitive Grms}
+
+
+\begin{center}
+\bl{\begin{tabular}{lcl}
+$S$ & $\Rightarrow$ & $bSAA\;|\; \epsilon$\\
+$A$ & $\Rightarrow$ & $a$\\
+$bA$ & $\Rightarrow$ & $Ab$\\
+\end{tabular}}
+\end{center}\pause
+
+\begin{center}
+\bl{$S \Rightarrow\ldots\Rightarrow^? "ababaa"$}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Language of a CFG}
+
+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, because there are no rules for replacing them.
+\item Once generated, terminals are ``permanent''.
+\item Terminals ought to be tokens of the language\\
+(but can also be strings).
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Parse Trees}
+
+\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}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Arithmetic Expressions}
+
+\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{\bf left-recursive} if it has a nonterminal \bl{$E$} such
+that \bl{$E \rightarrow^+ E\cdot \ldots$}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Ambiguous Grammars}
+
+A grammar is \alert{\bf ambiguous} if there is a string that
+has at least two different 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}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Dangling Else}
+
+Another ambiguous grammar:\bigskip
+
+\begin{center}
+\bl{\begin{tabular}{lcl}
+$E$ & $\rightarrow$ & if $E$ then $E$\\
+ & $|$ & if $E$ then $E$ else $E$ \\
+ & $|$ & \ldots
+\end{tabular}}
+\end{center}\bigskip
+
+\bl{\texttt{if a then if x then y else c}}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Parser Combinators}
+
+One of the simplest ways to implement a parser, see
+{\small\url{https://vimeo.com/142341803}}\bigskip
+
+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 atomic parsers
+\item sequencing
+\item alternative
+\item semantic action
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+
+Atomic parsers, for example, number tokens
+
+\begin{center}
+\bl{$\texttt{Num(123)}::rest \;\Rightarrow\; \{(\texttt{Num(123)}, rest)\}$}
+\end{center}\bigskip
+
+\begin{itemize}
+\item you consume one or more token from the\\
+ input (stream)
+\item also works for characters and strings
+\end{itemize}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\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}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\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:\medskip
+\begin{center}
+((output$_1$, output$_2$), unparsed part)
+\end{center}
+\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}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+
+Function parser (code \bl{$p \Rightarrow 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]
+\frametitle{\begin{tabular}{c}Semantic Actions\end{tabular}}
+
+Addition
+
+\begin{center}
+\bl{$T \sim + \sim E \Rightarrow \underbrace{f((x,y), z) \Rightarrow x + z}_{\text{semantic action}}$}
+\end{center}\pause
+
+Multiplication
+
+\begin{center}
+\bl{$F \sim * \sim T \Rightarrow f((x,y), z) \Rightarrow x * z$}
+\end{center}\pause
+
+Parenthesis
+
+\begin{center}
+\bl{$\text{(} \sim E \sim \text{)} \Rightarrow f((x,y), z) \Rightarrow y$}
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Types of Parsers}
+
+\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 \Rightarrow f$} returns results of type
+
+\begin{center}
+\bl{$S$}
+\end{center}
+
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Input Types of Parsers}
+
+\begin{itemize}
+\item input: \alert{token list}
+\item output: set of (output\_type, \alert{token list})
+\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}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Scannerless Parsers}
+
+\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; then input is a sequence of tokens
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Successful Parses}
+
+\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}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Abstract Parser Class}
+
+\small
+\lstinputlisting[language=Scala,xleftmargin=1mm]
+ {../progs/app7.scala}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+
+\small
+\fontsize{10}{12}\selectfont
+\lstinputlisting[language=Scala,xleftmargin=1mm]
+ {../progs/app8.scala}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Two Grammars}
+
+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}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{Ambiguous Grammars}
+
+\begin{center}
+\begin{tikzpicture}
+\begin{axis}[xlabel={\pcode{1}s},ylabel={time in secs},
+ enlargelimits=false,
+ xtick={0,100,...,1000},
+ xmax=1050,
+ ymax=33,
+ ytick={0,5,...,30},
+ scaled ticks=false,
+ axis lines=left,
+ width=11cm,
+ height=7cm,
+ legend entries={unambiguous,ambiguous},
+ legend pos=north east,
+ legend cell align=left,
+ x tick label style={font=\small,/pgf/number format/1000 sep={}}]
+\addplot[blue,mark=*, mark options={fill=white}]
+ table {s-grammar1.data};
+\only<2>{
+ \addplot[red,mark=triangle*, mark options={fill=white}]
+ table {s-grammar2.data};}
+\end{axis}
+\end{tikzpicture}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}
+\frametitle{While-Language}
+\mbox{}\\[-23mm]\mbox{}
+
+\bl{\begin{plstx}[rhs style=,one per line]
: \meta{Stmt} ::= skip
+ | \meta{Id} := \meta{AExp}
+ | if \meta{BExp} then \meta{Block} else \meta{Block}
+ | while \meta{BExp} do \meta{Block}\\
+: \meta{Stmts} ::= \meta{Stmt} ; \meta{Stmts}
+ | \meta{Stmt}\\
+: \meta{Block} ::= \{ \meta{Stmts} \}
+ | \meta{Stmt}\\
+: \meta{AExp} ::= \ldots\\
+: \meta{BExp} ::= \ldots\\
\end{plstx}}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{An Interpreter}
+
+\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{\texttt{eval(stmt, env)}}
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
\end{document}
%%% Local Variables: