diff -r 603e171a7b48 -r b3129cff41e9 slides/slides05.tex --- 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{ \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{ \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{ -\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{ +\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: