afl-material: comparison slides/slides06.tex

equal deleted inserted replaced

-:c29853b672fb
+:19f23c4c2167
 \documentclass[dvipsnames,14pt,t]{beamer}
-\usepackage{beamerthemeplaincu}
+\usepackage{../slides}
-\usepackage[absolute,overlay]{textpos}
+\usepackage{../graphics}
-\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{../langs}
 \usepackage{../data}
+\usepackage{../grammar}
-\makeatletter
+\hfuzz=220pt
-\lst@CCPutMacro\lst@ProcessOther {"2D}{\lst@ttfamily{-{}}{-{}}}
-\@empty\z@\@empty
+\pgfplotsset{compat=1.11}
-\makeatother
+\newcommand{\bl}[1]{\textcolor{blue}{#1}}
 % beamer stuff
-\renewcommand{\slidecaption}{AFL 06, King's College London, 30.~October 2013}
+\renewcommand{\slidecaption}{AFL 06, King's College London}
-\newcommand{\bl}[1]{\textcolor{blue}{#1}}
-\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions
 \begin{document}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
+\begin{frame}[t]
-\begin{frame}<1>[t]
 \frametitle{%
 \begin{tabular}{@ {}c@ {}}
 \\[-3mm]
 \LARGE Automata and \\[-2mm]
 \LARGE Formal Languages (6)\\[3mm]
 Office: & S1.27 (1st floor Strand Building)\\
 Slides: & KEATS (also home work is there)\\
 \end{tabular}
 \end{center}
+\end{frame}
-\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
+\begin{frame}[c]
-\begin{frame}[c]
+\frametitle{Regular Languages}
-\frametitle{\begin{tabular}{c}Regular Languages\end{tabular}}
+While regular expressions are very useful for lexing, there is
-While regular expressions are very useful for lexing,
+no regular expression that can recognise the language
-there is no regular expression that can recognise the language \bl{$a^nb^n$}.\bigskip
+\bl{$a^nb^n$}.\bigskip
 \begin{center}
 \bl{$(((()()))())$} \;\;vs.\;\; \bl{$(((()()))()))$}
-\end{center}
+\end{center}\bigskip\bigskip
+\small
-\end{frame}}
+\noindent So we cannot find out with regular expressions
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+whether parentheses are matched or unmatched.
+\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
 \begin{itemize}
 \item a finite set of nonterminal symbols (upper case)
 \begin{center}
 \bl{$A \rightarrow \text{rhs}_1 | \text{rhs}_2 | \ldots$}
 \end{center}
 \end{itemize}
+\end{frame}
-\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
-\mode<presentation>{
+\frametitle{Palindromes}
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Palindromes\end{tabular}}
+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$ \\
 \begin{center}
 \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
-\end{frame}}
+Can you find the grammar rules for matched parentheses?
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
+\begin{frame}[c]
-\begin{frame}[c]
+\frametitle{Arithmetic Expressions}
-\frametitle{\begin{tabular}{c}Arithmetic Expressions\end{tabular}}
 \begin{center}
 \bl{\begin{tabular}{lcl}
 $E$ & $\rightarrow$ &  $num\_token$ \\
 $E$ & $\rightarrow$ &  $E \cdot + \cdot E$ \\
 \end{tabular}}
 \end{center}\pause
 \bl{\texttt{1 + 2 * 3 + 4}}
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\frametitle{A CFG Derivation}
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}A CFG Derivation\end{tabular}}
 \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 \text{rhs}$}\bigskip
 \begin{center}
 \bl{$S \rightarrow \ldots \rightarrow \ldots  \rightarrow \ldots  \rightarrow \ldots $}
 \end{center}
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
-\mode<presentation>{
+\frametitle{Example Derivation}
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Example Derivation\end{tabular}}
 \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$}\\
 \end{tabular}
 \end{center}
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
+\begin{frame}[c]
-\begin{frame}[c]
+\frametitle{Example Derivation}
-\frametitle{\begin{tabular}{c}Example Derivation\end{tabular}}
 \begin{center}
 \bl{\begin{tabular}{lcl}
 $E$ & $\rightarrow$ &  $num\_token$ \\
 $E$ & $\rightarrow$ &  $E \cdot + \cdot E$ \\
 & \bl{$\rightarrow^+$} & \bl{$1+2*3+4$}\\
 \end{tabular}
 \end{tabular}
 \end{center}
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
-\mode<presentation>{
+\frametitle{Language of a CFG}
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Language of a CFG\end{tabular}}
 Let \bl{$G$} be a context-free grammar with start symbol \bl{$S$}.
 Then the language \bl{$L(G)$} is:
 \begin{center}
 \item Once generated, terminals are ``permanent''.
 \item Terminals ought to be tokens of the language\\
 (but can also be strings).
 \end{itemize}
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
+\begin{frame}[c]
-\begin{frame}[c]
+\frametitle{Parse Trees}
-\frametitle{\begin{tabular}{c}Parse Trees\end{tabular}}
 \begin{center}
 \bl{\begin{tabular}{lcl}
 $E$ & $\rightarrow$ &  $F \;|\; F \cdot * \cdot F$\\
 $F$ & $\rightarrow$ & $T \;|\; T \cdot + \cdot T \;|\; T \cdot - \cdot T$\\
 \begin{textblock}{5}(1, 6.5)
 \bl{\texttt{(2*3)+(3+4)}}
 \end{textblock}
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
-\mode<presentation>{
+\frametitle{Arithmetic Expressions}
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Arithmetic Expressions\end{tabular}}
 \begin{center}
 \bl{\begin{tabular}{lcl}
 $E$ & $\rightarrow$ &  $num\_token$ \\
 $E$ & $\rightarrow$ &  $E \cdot + \cdot E$ \\
 \end{center}\pause\bigskip
 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}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
-\mode<presentation>{
+\frametitle{Ambiguous Grammars}
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Ambiguous Grammars\end{tabular}}
+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}
 \bl{\begin{tabular}{lcl}
 $E$ & $\rightarrow$ &  $num\_token$ \\
 \end{tabular}}
 \end{center}
 \bl{\texttt{1 + 2 * 3 + 4}}
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
+\begin{frame}[c]
-\begin{frame}[c]
+\frametitle{Dangling Else}
-\frametitle{\begin{tabular}{c}Dangling Else\end{tabular}}
 Another ambiguous grammar:\bigskip
 \begin{center}
 \bl{\begin{tabular}{lcl}
 \end{tabular}}
 \end{center}\bigskip
 \bl{\texttt{if a then if x then y else c}}
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
+\begin{frame}[c]
-\begin{frame}[c]
+\frametitle{Parser Combinators}
-\frametitle{\begin{tabular}{c}Parser Combinators\end{tabular}}
 Parser combinators: \bigskip
 \begin{minipage}{1.1\textwidth}
 \begin{center}
 $\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}}
+\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}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \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)
+\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]
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
+\begin{frame}[c]
-\begin{frame}[c]
+\frametitle{Input Types of Parsers}
-\frametitle{\begin{tabular}{c}Input Types of Parsers\end{tabular}}
+\begin{itemize}
-\begin{itemize}
+\item input: \alert{token list}
-\item input: \alert{string}
+\item output: set of (output\_type, \alert{token list})
-\item output: set of (output\_type, \alert{string})
 \end{itemize}\bigskip\pause
-actually it can be any input type as long as it is a kind of sequence
+actually it can be any input type as long as it is a kind of
-(for example a string)
+sequence (for example a string)
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
+\begin{frame}[c]
-\begin{frame}[c]
+\frametitle{Scannerless Parsers}
-\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;
+but lexers are better when whitespaces or comments need to be
-then input is a sequence of tokens
+filtered out; then input is a sequence of tokens
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
+\begin{frame}[c]
-\begin{frame}[c]
+\frametitle{Successful Parses}
-\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
+a parse is successful whenever the input has been fully
-fully ``consumed'' (that is the second component is empty)
+``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
+\small
-\texttt{\lstinputlisting{../progs/app7.scala}}}
+\lstinputlisting[language=Scala,xleftmargin=1mm]{../progs/app7.scala}
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
+\begin{frame}[c]
-\begin{frame}[c]
-{\lstset{language=Scala}\fontsize{10}{12}\selectfont
+\small
-\texttt{\lstinputlisting{../progs/app8.scala}}}
+\fontsize{10}{12}\selectfont
-\end{frame}}
+\lstinputlisting[language=Scala,xleftmargin=1mm]{../progs/app8.scala}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
+\begin{frame}[c]
-\begin{frame}[c]
+\frametitle{Two Grammars}
-\frametitle{\begin{tabular}{c}Two Grammars\end{tabular}}
 Which languages are recognised by the following two grammars?
 \begin{center}
 \bl{\begin{tabular}{lcl}
 $U$ & $\rightarrow$ &  $1 \cdot U$\\
 & $|$ & $\epsilon$
 \end{tabular}}
 \end{center}
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[t]
-\frametitle{\begin{tabular}{c}Ambiguous Grammars\end{tabular}}
+\frametitle{Ambiguous Grammars}
-\mbox{}\\[-25mm]\mbox{}
+\begin{center}
+\begin{tikzpicture}
-\begin{center}
+\begin{axis}[xlabel={\pcode{1}s},ylabel={time in secs},
-\begin{tikzpicture}[y=.2cm, x=.009cm]
+enlargelimits=false,
-	%axis
+xtick={0,100,...,1000},
-	\draw (0,0) -- coordinate (x axis mid) (1000,0);
+xmax=1050,
-	\draw (0,0) -- coordinate (y axis mid) (0,30);
+ymax=33,
-	%ticks
+ytick={0,5,...,30},
-	\foreach \x in {0, 20, 100, 200,...,1000}
+scaled ticks=false,
-		\draw (\x,1pt) -- (\x,-3pt)
+axis lines=left,
-			node[anchor=north] {\small \x};
+width=11cm,
-	\foreach \y in {0,5,...,30}
+height=7cm,
-		\draw (1pt,\y) -- (-3pt,\y)
+legend entries={unambiguous,ambiguous},
-			node[anchor=east] {\small\y};
+legend pos=north east,
-	%labels
+legend cell align=left,
-	\node[below=0.6cm] at (x axis mid) {\bl{1}s};
+x tick label style={font=\small,/pgf/number format/1000 sep={}}]
-	\node[rotate=90, left=1.2cm] at (y axis mid) {secs};
+\addplot[blue,mark=*, mark options={fill=white}]
+table {s-grammar1.data};
-	%plots
+\only<2>{
-	\draw[color=blue] plot[mark=*, mark options={fill=white}]
+\addplot[red,mark=triangle*, mark options={fill=white}]
-		file {s-grammar1.data};
+table {s-grammar2.data};}
-\only<2->{\draw[color=red] plot[mark=triangle*, mark options={fill=white} ]
+\end{axis}
-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}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}
-\mode<presentation>{
+\frametitle{While-Language}
-\begin{frame}[c]
+\mbox{}\\[-23mm]\mbox{}
-\frametitle{\begin{tabular}{c}While-Language\end{tabular}}
+\bl{\begin{plstx}[rhs style=,one per line]
+: \meta{Stmt} ::= skip
-\begin{center}
+| \meta{Id} := \meta{AExp}
-\bl{\begin{tabular}{@{}lcl@{}}
+| if \meta{BExp} then \meta{Block} else \meta{Block}
-$Stmt$ & $\rightarrow$ &  $\text{skip}$\\
+| while \meta{BExp} do \meta{Block}\\
-& $|$ & $Id := AExp$\\
+: \meta{Stmts} ::= \meta{Stmt} ; \meta{Stmts}
-& $|$ & $\text{if}\; B\!Exp \;\text{then}\; Block \;\text{else}\; Block$\\
+| \meta{Stmt}\\
-& $|$ & $\text{while}\; B\!Exp \;\text{do}\; Block$\medskip\\
+: \meta{Block} ::= \{ \meta{Stmts} \}
-$Stmts$ & $\rightarrow$ &  $Stmt \;\text{;}\; Stmts$\\
+| \meta{Stmt}\\
-& $|$ & $Stmt$\medskip\\
+: \meta{AExp} ::= \ldots\\
-$Block$ & $\rightarrow$ &  $\{ Stmts \}$\\
+: \meta{BExp} ::= \ldots\\
-& $|$ & $Stmt$\medskip\\
+\end{plstx}}
-$AExp$ & $\rightarrow$ & \ldots\\
-$BExp$ & $\rightarrow$ & \ldots\\
+\end{frame}
-\end{tabular}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\end{center}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
-\end{frame}}
+\frametitle{An Interpreter}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}An Interpreter\end{tabular}}
 \begin{center}
 \bl{\begin{tabular}{l}
 $\{$\\
 \;\;$x := 5 \text{;}$\\
 \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)}
+\item \bl{\texttt{eval(stmt, env)}}
 \end{itemize}
+\end{frame}
-\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \end{document}
 %%% Local Variables:

changeset 295	19f23c4c2167
parent 215	828303e8e4af
child 365	9b71dead1219