--- a/slides/slides06.tex Sat Nov 01 16:19:05 2014 +0000
+++ b/slides/slides06.tex Sun Nov 02 09:10:15 2014 +0000
@@ -1,42 +1,25 @@
\documentclass[dvipsnames,14pt,t]{beamer}
-\usepackage{beamerthemeplaincu}
-\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}
+\usepackage{../slides}
+\usepackage{../graphics}
\usepackage{../langs}
\usepackage{../data}
+\usepackage{../grammar}
+\hfuzz=220pt
-\makeatletter
-\lst@CCPutMacro\lst@ProcessOther {"2D}{\lst@ttfamily{-{}}{-{}}}
-\@empty\z@\@empty
-\makeatother
+\pgfplotsset{compat=1.11}
+\newcommand{\bl}[1]{\textcolor{blue}{#1}}
% beamer stuff
-\renewcommand{\slidecaption}{AFL 06, King's College London, 30.~October 2013}
-\newcommand{\bl}[1]{\textcolor{blue}{#1}}
-\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions
+\renewcommand{\slidecaption}{AFL 06, King's College London}
\begin{document}
+
+
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}<1>[t]
+\begin{frame}[t]
\frametitle{%
\begin{tabular}{@ {}c@ {}}
\\[-3mm]
@@ -53,31 +36,56 @@
\end{tabular}
\end{center}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\end{frame}}
- %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Regular Languages\end{tabular}}
+\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
+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}
+\end{center}\bigskip\bigskip
+\small
+\noindent So we cannot find out with regular expressions
+whether parentheses are matched or unmatched.
-\end{frame}}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-\newcommand{\qq}{\mbox{\texttt{"}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Grammars\end{tabular}}
+\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}]
+
+\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
@@ -99,14 +107,14 @@
\end{center}
\end{itemize}
-
-\end{frame}}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Palindromes\end{tabular}}
+\frametitle{Palindromes}
+
+A grammar for palindromes over the alphabet~\bl{$\{a,b\}$}:
\begin{center}
\bl{\begin{tabular}{lcl}
@@ -122,18 +130,17 @@
\bl{\begin{tabular}{lcl}
$S$ & $\rightarrow$ & $\epsilon \;|\; a\cdot S\cdot a \;|\;b\cdot S\cdot b$ \\
\end{tabular}}
-\end{center}
+\end{center}\pause\bigskip
+\small
+Can you find the grammar rules for matched parentheses?
-\end{frame}}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Arithmetic Expressions\end{tabular}}
+\frametitle{Arithmetic Expressions}
\begin{center}
\bl{\begin{tabular}{lcl}
@@ -147,15 +154,12 @@
\bl{\texttt{1 + 2 * 3 + 4}}
-\end{frame}}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
-\frametitle{\begin{tabular}{c}A CFG Derivation\end{tabular}}
+\frametitle{A CFG Derivation}
\begin{enumerate}
\item Begin with a string containing only the start symbol, say \bl{$S$}\bigskip
@@ -168,14 +172,12 @@
\bl{$S \rightarrow \ldots \rightarrow \ldots \rightarrow \ldots \rightarrow \ldots $}
\end{center}
-\end{frame}}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Example Derivation\end{tabular}}
+\frametitle{Example Derivation}
\begin{center}
\bl{\begin{tabular}{lcl}
@@ -183,7 +185,6 @@
\end{tabular}}
\end{center}\bigskip
-
\begin{center}
\begin{tabular}{lcl}
\bl{$S$} & \bl{$\rightarrow$} & \bl{$aSa$}\\
@@ -195,13 +196,12 @@
\end{tabular}
\end{center}
-\end{frame}}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Example Derivation\end{tabular}}
+\frametitle{Example Derivation}
\begin{center}
\bl{\begin{tabular}{lcl}
@@ -231,14 +231,12 @@
\end{tabular}
\end{center}
-\end{frame}}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Language of a CFG\end{tabular}}
+\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:
@@ -254,13 +252,12 @@
(but can also be strings).
\end{itemize}
-\end{frame}}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Parse Trees\end{tabular}}
+\frametitle{Parse Trees}
\begin{center}
\bl{\begin{tabular}{lcl}
@@ -299,14 +296,12 @@
\bl{\texttt{(2*3)+(3+4)}}
\end{textblock}
-\end{frame}}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Arithmetic Expressions\end{tabular}}
+\frametitle{Arithmetic Expressions}
\begin{center}
\bl{\begin{tabular}{lcl}
@@ -321,16 +316,15 @@
A CFG is \alert{left-recursive} if it has a nonterminal \bl{$E$} such
that \bl{$E \rightarrow^+ E\cdot \ldots$}
-\end{frame}}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Ambiguous Grammars\end{tabular}}
+\frametitle{Ambiguous Grammars}
-A grammar is \alert{ambiguous} if there is a string that has at least two different parse trees.
+A grammar is \alert{ambiguous} if there is a string that has
+at least two different parse trees.
\begin{center}
@@ -345,13 +339,12 @@
\bl{\texttt{1 + 2 * 3 + 4}}
-\end{frame}}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Dangling Else\end{tabular}}
+\frametitle{Dangling Else}
Another ambiguous grammar:\bigskip
@@ -365,13 +358,12 @@
\bl{\texttt{if a then if x then y else c}}
-\end{frame}}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Parser Combinators\end{tabular}}
+\frametitle{Parser Combinators}
Parser combinators: \bigskip
@@ -383,30 +375,47 @@
\end{minipage}\bigskip
\begin{itemize}
+\item atomic parsers
\item sequencing
\item alternative
\item semantic action
\end{itemize}
-\end{frame}}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
+\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
+\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}}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -418,7 +427,10 @@
\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)
+\item then combine the results:\medskip
+\begin{center}
+((output$_1$, output$_2$), unparsed part)
+\end{center}
\end{itemize}
\begin{center}
@@ -517,78 +529,73 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Input Types of Parsers\end{tabular}}
+\frametitle{Input Types of Parsers}
\begin{itemize}
-\item input: \alert{string}
-\item output: set of (output\_type, \alert{string})
+\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)
+actually it can be any input type as long as it is a kind of
+sequence (for example a string)
-\end{frame}}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Scannerless Parsers\end{tabular}}
+\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
+but lexers are better when whitespaces or comments need to be
+filtered out; then input is a sequence of tokens
-\end{frame}}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Successful Parses\end{tabular}}
+\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)
+a parse is successful whenever the input has been fully
+``consumed'' (that is the second component is empty)
-
-\end{frame}}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
\frametitle{Abstract Parser Class}
-\mbox{\lstset{language=Scala}\fontsize{10}{12}\selectfont
-\texttt{\lstinputlisting{../progs/app7.scala}}}
-\end{frame}}
+\small
+\lstinputlisting[language=Scala,xleftmargin=1mm]{../progs/app7.scala}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
-{\lstset{language=Scala}\fontsize{10}{12}\selectfont
-\texttt{\lstinputlisting{../progs/app8.scala}}}
-\end{frame}}
+
+\small
+\fontsize{10}{12}\selectfont
+\lstinputlisting[language=Scala,xleftmargin=1mm]{../progs/app8.scala}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Two Grammars\end{tabular}}
+\frametitle{Two Grammars}
Which languages are recognised by the following two grammars?
@@ -606,83 +613,63 @@
\end{tabular}}
\end{center}
-\end{frame}}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[t]
-\frametitle{\begin{tabular}{c}Ambiguous Grammars\end{tabular}}
-
-\mbox{}\\[-25mm]\mbox{}
+\frametitle{Ambiguous Grammars}
\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}
+\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}}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}While-Language\end{tabular}}
-
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}
+\frametitle{While-Language}
+\mbox{}\\[-23mm]\mbox{}
-\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}
+\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}}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
-\frametitle{\begin{tabular}{c}An Interpreter\end{tabular}}
+\frametitle{An Interpreter}
\begin{center}
\bl{\begin{tabular}{l}
@@ -697,17 +684,13 @@
\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)}
+\item \bl{\texttt{eval(stmt, env)}}
\end{itemize}
-
-\end{frame}}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-
\end{document}
%%% Local Variables: