661
+ − 1 % !TEX program = xelatex
743
+ − 2 \documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer}
270
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 3 \usepackage{../slides}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 4 \usepackage{../graphics}
215
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 5 \usepackage{../langs}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 6 \usepackage{../data}
33
+ − 7
270
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 8 \hfuzz=220pt
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 9
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 10 \pgfplotsset{compat=1.11}
145
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 11
722
+ − 12
788
+ − 13 \usepackage{tcolorbox}
+ − 14 \newtcolorbox{mybox}{colback=red!5!white,colframe=red!75!black}
+ − 15 \newtcolorbox{mybox2}[1]{colback=red!5!white,colframe=red!75!black,fonttitle=\bfseries,title=#1}
+ − 16 \newtcolorbox{mybox3}[1]{colback=Cyan!5!white,colframe=Cyan!75!black,fonttitle=\bfseries,title=#1}
+ − 17
722
+ − 18 % a hand written lexer for SML
+ − 19 % https://ponyo.org/
+ − 20 % https://github.com/eatonphil/ponyo/blob/master/src/Sml/Lexer.sml
788
+ − 21 \beamertemplateballitem
722
+ − 22
270
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 23 \newcommand{\bl}[1]{\textcolor{blue}{#1}}
33
+ − 24
445
+ − 25 \renewcommand{\slidecaption}{CFL 04, King's College London}
33
+ − 26
+ − 27 \begin{document}
+ − 28
+ − 29 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
270
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 30 \begin{frame}[t]
33
+ − 31 \frametitle{%
+ − 32 \begin{tabular}{@ {}c@ {}}
+ − 33 \\[-3mm]
445
+ − 34 \LARGE Compilers and \\[-2mm]
743
+ − 35 \LARGE Formal Languages\\[3mm]
33
+ − 36 \end{tabular}}
+ − 37
+ − 38 \normalsize
+ − 39 \begin{center}
+ − 40 \begin{tabular}{ll}
660
+ − 41 Email: & christian.urban at kcl.ac.uk\\
743
+ − 42 %Office Hours: & Thursdays 12 -- 14\\
+ − 43 %Location: & N7.07 (North Wing, Bush House)\\
660
+ − 44 Slides \& Progs: & KEATS (also homework is there)\\
33
+ − 45 \end{tabular}
+ − 46 \end{center}
660
+ − 47
743
+ − 48
+ − 49 \begin{center}
+ − 50 \begin{tikzpicture}
+ − 51 \node[drop shadow,fill=white,inner sep=0pt]
+ − 52 {\footnotesize\rowcolors{1}{capri!10}{white}
+ − 53 \begin{tabular}{|p{4.8cm}|p{4.8cm}|}\hline
+ − 54 1 Introduction, Languages & 6 While-Language \\
+ − 55 2 Regular Expressions, Derivatives & 7 Compilation, JVM \\
+ − 56 3 Automata, Regular Languages & 8 Compiling Functional Languages \\
+ − 57 \cellcolor{blue!50}
+ − 58 4 Lexing, Tokenising & 9 Optimisations \\
+ − 59 5 Grammars, Parsing & 10 LLVM \\ \hline
+ − 60 \end{tabular}%
+ − 61 };
+ − 62 \end{tikzpicture}
+ − 63 \end{center}
270
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 64 \end{frame}
574
+ − 65 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 66
139
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 67
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 68 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
785
+ − 69 %\begin{frame}[c]
+ − 70 %\frametitle{Coursework}
+ − 71 %
+ − 72 %\begin{itemize}
+ − 73 %\item \bl{$\der\,c\,(r^+) \dn \der\,c (r\cdot r^*)$}\quad given
+ − 74 %that \bl{$r^+ \dn r\cdot r^*$}
+ − 75 %\end{itemize}\bigskip\pause
661
+ − 76
785
+ − 77 %\begin{center}
+ − 78 %\begin{tabular}{lcl}
+ − 79 %\bl{$\der\,c\,(r\cdot r^*)$} & \bl{$\dn$} &
+ − 80 %\only<2-4>{if \bl{$nullable\,r$}}%
+ − 81 %\only<5>{\bl{$(\der\,c\,r)\cdot r^*$}}\\
+ − 82 % & &
+ − 83 % \only<2>{then \bl{$(\der\,c\,r)\cdot r^* \,+\, \der\,c\,(r^*)$}}%
+ − 84 % \only<3>{then \bl{$(\der\,c\,r)\cdot r^* \,+\, (\der\,c\,r)\cdot r^*$}}%
+ − 85 % \only<4>{then \bl{$(\der\,c\,r)\cdot r^*$}}\\
+ − 86 % & & \only<2-4>{else \bl{$(\der\,c\,r)\cdot r^*$}}
+ − 87 %\end{tabular}
+ − 88 %\end{center}
+ − 89 %\end{frame}
661
+ − 90 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 91
+ − 92 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
785
+ − 93 %\begin{frame}[c]
+ − 94 % \frametitle{Coursework (2)}
+ − 95 %
+ − 96 % \begin{itemize}
+ − 97 % \item \bl{\texttt{CFUN(f: Char => Boolean)}}
+ − 98 % \end{itemize}\medskip
+ − 99 %
+ − 100 % \begin{center}
+ − 101 % \begin{tabular}{l}
+ − 102 % \bl{\texttt{CHAR(c: Char)}} \bl{$\dn$}\\
+ − 103 % \quad\bl{\texttt{CFUN(\_ == c)}}\medskip\\
+ − 104 % \bl{\texttt{RANGE(cs: Set[Char])}} \bl{$\dn$}\\
+ − 105 % \quad\bl{\texttt{CFUN(cs.contains(\_))}}\medskip\\
+ − 106 % \bl{\texttt{ALL}} \bl{$\dn$}\\
+ − 107 % \quad\bl{\texttt{CFUN((c: Char) => true)}}\\
+ − 108 % \end{tabular}
+ − 109 % \end{center}
+ − 110 %\end{frame}
661
+ − 111 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
743
+ − 112
272
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 113
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 114 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 115 \begin{frame}[c]
352
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 116 \frametitle{The Goal of this Course}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 117 \mbox{}\\[-26mm]\mbox{}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 118
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 119 \begin{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 120 \begin{tikzpicture}[scale=1,
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 121 node/.style={
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 122 rectangle,rounded corners=3mm,
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 123 very thick,draw=black!50,
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 124 minimum height=18mm, minimum width=20mm,
743
+ − 125 top color=white,bottom color=black!20,drop shadow}]
352
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 126
578
+ − 127 \node at (3.05, 1.8) {\Large\bf Write a compiler};
352
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 128
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 129 \node (0) at (-2.3,0) {};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 130
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 131 \node (A) at (0,0) [node] {};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 132 \node [below right] at (A.north west) {lexer};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 133
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 134 \node (B) at (3,0) [node] {};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 135 \node [below right=1mm] at (B.north west)
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 136 {\mbox{}\hspace{-1mm}parser};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 137
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 138 \node (C) at (6,0) [node] {};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 139 \node [below right] at (C.north west)
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 140 {\mbox{}\hspace{-1mm}code gen};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 141
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 142 \node (1) at (8.4,0) {};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 143
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 144 \draw [->,line width=4mm] (0) -- (A);
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 145 \draw [->,line width=4mm] (A) -- (B);
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 146 \draw [->,line width=4mm] (B) -- (C);
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 147 \draw [->,line width=4mm] (C) -- (1);
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 148 \end{tikzpicture}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 149 \end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 150
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 151 Today a lexer.
579
+ − 152
+ − 153 \only<2>{
+ − 154 \begin{textblock}{1}(6,9.8)
+ − 155 \begin{tabular}{c}
+ − 156 \includegraphics[scale=0.13]{../pics/rosetta.jpg}\\[-2mm]
+ − 157 \footnotesize lexing $\Rightarrow$ recognising words (Stone of Rosetta)
+ − 158 \end{tabular}
+ − 159 \end{textblock}}
352
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 160 \end{frame}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 161
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 162 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 163 \begin{frame}[c]
578
+ − 164 \frametitle{Regular Expressions}
+ − 165
+ − 166 In programming languages they are often used to recognise:\medskip
352
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 167
578
+ − 168 \begin{itemize}
662
+ − 169 \item operands, digits
578
+ − 170 \item identifiers
+ − 171 \item numbers (non-leading zeros)
+ − 172 \item keywords
+ − 173 \item comments
+ − 174 \end{itemize}\bigskip
+ − 175
+ − 176 \mbox{}\hfill\bl{\url{http://www.regexper.com}}
352
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 177 \end{frame}
578
+ − 178 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
352
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 179
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 180
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 181 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 182 \begin{frame}[c]
521
+ − 183 \frametitle{Lexing: Test Case}
272
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 184
785
+ − 185 \mbox{\lstinputlisting[language=While]{../progs/while-tests/fib.while}}
272
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 186
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 187 \end{frame}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 188 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 189
578
+ − 190 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 191 %\begin{frame}[c]
+ − 192 %\frametitle{?? Test Case}
+ − 193 %
+ − 194 %\mbox{\lstinputlisting[language=While]{../progs/collatz.while}}
+ − 195 %
+ − 196 %\end{frame}
139
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 197 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 198
35
+ − 199 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
272
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 200 \begin{frame}[t]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 201
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 202 \tt
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 203 \begin{center}\large
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 204 \code{"if true then then 42 else +"}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 205 \end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 206
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 207
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 208 \begin{tabular}{@{}l}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 209 KEYWORD: \\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 210 \hspace{5mm}{if}, {then}, {else},\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 211 WHITESPACE:\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 212 \hspace{5mm}{" "}, {$\backslash$n},\\
521
+ − 213 IDENTIFIER:\\
272
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 214 \hspace{5mm}LETTER $\cdot$ (LETTER + DIGIT + {\_})$^*$\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 215 NUM:\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 216 \hspace{5mm}(NONZERODIGIT $\cdot$ DIGIT$^*$) + {0}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 217 OP:\\
521
+ − 218 \hspace{5mm}+, -, *, \%, <, <=\\
272
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 219 COMMENT:\\
277
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 220 \hspace{5mm}{$\slash$*} $\cdot$ $\sim$(ALL$^*$ $\cdot$ (*$\slash$) $\cdot$ ALL$^*$) $\cdot$ {*$\slash$}
272
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 221 \end{tabular}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 222
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 223 \end{frame}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 224 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 225
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 226 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 227 \begin{frame}[t]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 228
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 229 \tt
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 230 \begin{center}\large
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 231 \code{"if true then then 42 else +"}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 232 \end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 233
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 234 \only<1>{
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 235 \small\begin{tabular}{l}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 236 KEYWORD(if),\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 237 WHITESPACE,\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 238 IDENT(true),\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 239 WHITESPACE,\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 240 KEYWORD(then),\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 241 WHITESPACE,\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 242 KEYWORD(then),\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 243 WHITESPACE,\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 244 NUM(42),\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 245 WHITESPACE,\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 246 KEYWORD(else),\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 247 WHITESPACE,\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 248 OP(+)
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 249 \end{tabular}}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 250
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 251 \only<2>{
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 252 \small\begin{tabular}{l}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 253 KEYWORD(if),\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 254 IDENT(true),\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 255 KEYWORD(then),\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 256 KEYWORD(then),\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 257 NUM(42),\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 258 KEYWORD(else),\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 259 OP(+)
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 260 \end{tabular}}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 262 \end{frame}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 263 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 264
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 265 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 266 \begin{frame}[c]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 268
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 269 There is one small problem with the tokenizer. How should we
578
+ − 270 tokenize\ldots?
272
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 271
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 272 \begin{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 273 \large\code{"x-3"}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 274 \end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 275
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 276 \tt
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 277 \begin{tabular}{@{}l}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 278 ID: \ldots\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 279 OP:\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 280 \hspace{5mm}\texttt{"+"}, \texttt{"-"}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 281 NUM:\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 282 \hspace{5mm}(NONZERODIGIT $\cdot$ DIGIT$^*$) + {''0''}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 283 NUMBER:\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 284 \hspace{5mm}NUM + (\texttt{"-"} $\cdot$ NUM)\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 285 \end{tabular}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 286
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 287 \end{frame}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 288 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 289
352
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 290 \begin{frame}[c]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 291
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 292 The same problem with\medskip
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 293
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 294 \[
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 295 \bl{(ab + a) \cdot (c + bc)}
353
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 296 \]\medskip
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 297
662
+ − 298 and the string $\bl{abc}$.\pause\bigskip
352
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 299
662
+ − 300 Or, keywords are \code{if} etc and identifiers are
353
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 301 letters followed by ``letters + numbers + \_''$^*$
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 302
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 303 \[
785
+ − 304 \bl{\texttt{if}}\qquad\bl{\texttt{iffoo}}
353
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 305 \]
352
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 306
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 307 \end{frame}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 308
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 309
272
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 310 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 311 \begin{frame}[c]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 312 \frametitle{POSIX: Two Rules}
33
+ − 313
38
+ − 314 \begin{itemize}
272
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 315 \item Longest match rule (``maximal munch rule''): The
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 316 longest initial substring matched by any regular expression is taken
278
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 317 as the next token.\bigskip
272
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 318
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 319 \item Rule priority:
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 320 For a particular longest initial substring, the first regular
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 321 expression that can match determines the token.
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 322 \end{itemize}\bigskip\bigskip\pause
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 323
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 324 \small
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 325 \hfill most posix matchers are buggy\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 326 \footnotesize
353
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 327 \hfill
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 328 \url{http://www.haskell.org/haskellwiki/Regex_Posix}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 329 \smallskip\pause
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 330
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 331 \hfill \small traditional lexers are fast, but hairy
272
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 332
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 333 %\url{http://www.technologyreview.com/tr10/?year=2011}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 334 %finite deterministic automata/ nondeterministic automaton
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 335 %\item problem with infix operations, for example i-12
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 336
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 337 \end{frame}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 338 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 339
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 340 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 341 \begin{frame}[c]
581
+ − 342 \frametitle{Sulzmann \& Lu Matcher}
272
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 343
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 344 We want to match the string \bl{$abc$} using \bl{$r_1$}:
38
+ − 345
272
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 346 \begin{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 347 \begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 348 \node (r1) {\bl{$r_1$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 349 \node (r2) [right=of r1] {\bl{$r_2$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 350 \draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};\pause
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 351 \node (r3) [right=of r2] {\bl{$r_3$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 352 \draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};\pause
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 353 \node (r4) [right=of r3] {\bl{$r_4$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 354 \draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};\pause
521
+ − 355 \draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable?$}}};\pause
272
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 356 \node (v4) [below=of r4] {\bl{$v_4$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 357 \draw[->,line width=1mm] (r4) -- (v4);\pause
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 358 \node (v3) [left=of v4] {\bl{$v_3$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 359 \draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};\pause
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 360 \node (v2) [left=of v3] {\bl{$v_2$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 361 \draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};\pause
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 362 \node (v1) [left=of v2] {\bl{$v_1$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 363 \draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};\pause
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 364 \draw[->,line width=0.5mm] (r3) -- (v3);
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 365 \draw[->,line width=0.5mm] (r2) -- (v2);
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 366 \draw[->,line width=0.5mm] (r1) -- (v1);
273
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 367 \draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};
272
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 368 \end{tikzpicture}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 369 \end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 370
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 371 \end{frame}
33
+ − 372 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 373
273
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 374 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 375 \begin{frame}[c]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 376 \frametitle{Regexes and Values}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 377
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 378 Regular expressions and their corresponding values:
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 379
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 380 \begin{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 381 \begin{columns}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 382 \begin{column}{3cm}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 383 \begin{tabular}{@{}rrl@{}}
445
+ − 384 \bl{$r$} & \bl{$::=$} & \bl{$\ZERO$}\\
+ − 385 & \bl{$\mid$} & \bl{$\ONE$} \\
273
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 386 & \bl{$\mid$} & \bl{$c$} \\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 387 & \bl{$\mid$} & \bl{$r_1 \cdot r_2$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 388 & \bl{$\mid$} & \bl{$r_1 + r_2$} \\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 389 \\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 390 & \bl{$\mid$} & \bl{$r^*$} \\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 391 \\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 392 \end{tabular}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 393 \end{column}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 394 \begin{column}{3cm}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 395 \begin{tabular}{@{\hspace{-7mm}}rrl@{}}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 396 \bl{$v$} & \bl{$::=$} & \\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 397 & & \bl{$Empty$} \\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 398 & \bl{$\mid$} & \bl{$Char(c)$} \\
279
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 399 & \bl{$\mid$} & \bl{$Seq(v_1,v_2)$}\\
273
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 400 & \bl{$\mid$} & \bl{$Left(v)$} \\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 401 & \bl{$\mid$} & \bl{$Right(v)$} \\
578
+ − 402 & \bl{$\mid$} & \bl{$Stars\,[]$} \\
+ − 403 & \bl{$\mid$} & \bl{$Stars\,[v_1,\ldots\,v_n]$} \\
273
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 404 \end{tabular}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 405 \end{column}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 406 \end{columns}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 407 \end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 408
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 409 \end{frame}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 410 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 411
352
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 412 \begin{frame}[c]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 413 \small
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 414
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 415 {\small\lstinputlisting[language=Scala,numbers=none,
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 416 xleftmargin=-5mm] {../progs/app01.scala}}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 417
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 418 {\small\lstinputlisting[language=Scala,numbers=none,
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 419 xleftmargin=-5mm] {../progs/app02.scala}}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 420
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 421 \end{frame}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 422
273
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 423
352
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 424
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 425
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 426 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 427 \begin{frame}[c]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 428
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 429 \begin{textblock}{10}(3,5)
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 430 \begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 431 \node (r1) {\bl{$r_1$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 432 \node (r2) [right=of r1] {\bl{$r_2$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 433 \draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 434 \node (r3) [right=of r2] {\bl{$r_3$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 435 \draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 436 \node (r4) [right=of r3] {\bl{$r_4$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 437 \draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 438 \draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 439 \node (v4) [below=of r4] {\bl{$v_4$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 440 \draw[->,line width=1mm] (r4) -- (v4);
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 441 \node (v3) [left=of v4] {\bl{$v_3$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 442 \draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 443 \node (v2) [left=of v3] {\bl{$v_2$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 444 \draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 445 \node (v1) [left=of v2] {\bl{$v_1$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 446 \draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 447 \draw[->,line width=0.5mm] (r3) -- (v3);
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 448 \draw[->,line width=0.5mm] (r2) -- (v2);
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 449 \draw[->,line width=0.5mm] (r1) -- (v1);
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 450 \draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 451 \end{tikzpicture}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 452 \end{textblock}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 453
662
+ − 454 \only<1->{
352
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 455 \begin{textblock}{6}(1,0.8)
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 456 \begin{bubble}[6cm]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 457 \small
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 458 \begin{tabular}{ll}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 459 \bl{$r_1$}: & \bl{$a \cdot (b \cdot c)$}\\
445
+ − 460 \bl{$r_2$}: & \bl{$\ONE \cdot (b \cdot c)$}\\
+ − 461 \bl{$r_3$}: & \bl{$(\ZERO \cdot (b \cdot c)) + (\ONE \cdot c)$}\\
+ − 462 \bl{$r_4$}: & \bl{$(\ZERO \cdot (b \cdot c)) + ((\ZERO \cdot c) + \ONE)$}\\
352
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 463 \end{tabular}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 464 \end{bubble}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 465 \end{textblock}}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 466
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 467 \only<2->{
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 468 \begin{textblock}{6}(5,11.4)
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 469 \begin{bubble}[7.6cm]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 470 \small
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 471 \begin{tabular}{ll}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 472 \bl{$v_1$}: & \bl{$Seq(Char(a), Seq(Char(b), Char(c)))$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 473 \bl{$v_2$}: & \bl{$Seq(Empty, Seq(Char(b), Char(c)))$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 474 \bl{$v_3$}: & \bl{$Right(Seq(Empty, Char(c)))$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 475 \bl{$v_4$}: & \bl{$Right(Right(Empty))$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 476 \end{tabular}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 477 \end{bubble}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 478 \end{textblock}}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 479 \end{frame}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 480 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 481
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 482 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 483 \begin{frame}[c]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 484 \frametitle{Flatten}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 485
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 486 Obtaining the string underlying a value:
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 487
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 488 \begin{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 489 \begin{tabular}{lcl}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 490 \bl{$|Empty|$} & \bl{$\dn$} & \bl{$[]$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 491 \bl{$|Char(c)|$} & \bl{$\dn$} & \bl{$[c]$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 492 \bl{$|Left(v)|$} & \bl{$\dn$} & \bl{$|v|$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 493 \bl{$|Right(v)|$} & \bl{$\dn$} & \bl{$|v|$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 494 \bl{$|Seq(v_1,v_2)|$}& \bl{$\dn$} & \bl{$|v_1| \,@\, |v_2|$}\\
786
+ − 495 \bl{$|Stars\,[v_1,\ldots ,v_n]|$} & \bl{$\dn$} & \bl{$|v_1| \,@\ldots @\, |v_n|$}\\
352
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 496 \end{tabular}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 497 \end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 498
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 499 \end{frame}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 500 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 501
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 502 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 503 \begin{frame}[c]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 504
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 505 \begin{textblock}{10}(3,5)
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 506 \begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 507 \node (r1) {\bl{$r_1$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 508 \node (r2) [right=of r1] {\bl{$r_2$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 509 \draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 510 \node (r3) [right=of r2] {\bl{$r_3$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 511 \draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 512 \node (r4) [right=of r3] {\bl{$r_4$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 513 \draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 514 \draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 515 \node (v4) [below=of r4] {\bl{$v_4$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 516 \draw[->,line width=1mm] (r4) -- (v4);
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 517 \node (v3) [left=of v4] {\bl{$v_3$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 518 \draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 519 \node (v2) [left=of v3] {\bl{$v_2$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 520 \draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 521 \node (v1) [left=of v2] {\bl{$v_1$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 522 \draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 523 \draw[->,line width=0.5mm] (r3) -- (v3);
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 524 \draw[->,line width=0.5mm] (r2) -- (v2);
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 525 \draw[->,line width=0.5mm] (r1) -- (v1);
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 526 \draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 527 \end{tikzpicture}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 528 \end{textblock}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 529
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 530 \begin{textblock}{6}(1,0.8)
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 531 \begin{bubble}[6cm]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 532 \small
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 533 \begin{tabular}{ll}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 534 \bl{$r_1$}: & \bl{$a \cdot (b \cdot c)$}\\
445
+ − 535 \bl{$r_2$}: & \bl{$\ONE \cdot (b \cdot c)$}\\
+ − 536 \bl{$r_3$}: & \bl{$(\ZERO \cdot (b \cdot c)) + (\ONE \cdot c)$}\\
+ − 537 \bl{$r_4$}: & \bl{$(\ZERO \cdot (b \cdot c)) + ((\ZERO \cdot c) + \ONE)$}\\
352
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 538 \end{tabular}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 539 \end{bubble}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 540 \end{textblock}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 541
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 542 \begin{textblock}{6}(1,11.4)
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 543 \begin{bubble}[7.6cm]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 544 \small
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 545 \begin{tabular}{ll}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 546 \bl{$v_1$}: & \bl{$Seq(Char(a), Seq(Char(b), Char(c)))$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 547 \bl{$v_2$}: & \bl{$Seq(Empty, Seq(Char(b), Char(c)))$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 548 \bl{$v_3$}: & \bl{$Right(Seq(Empty, Char(c)))$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 549 \bl{$v_4$}: & \bl{$Right(Right(Empty))$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 550 \end{tabular}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 551 \end{bubble}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 552 \end{textblock}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 553
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 554 \begin{textblock}{6}(12,11.4)
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 555 \begin{bubble}[2cm]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 556 \small
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 557 \begin{tabular}{ll}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 558 \bl{$|v_1|$}: & \bl{$abc$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 559 \bl{$|v_2|$}: & \bl{$bc$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 560 \bl{$|v_3|$}: & \bl{$c$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 561 \bl{$|v_4|$}: & \bl{$[]$}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 562 \end{tabular}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 563 \end{bubble}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 564 \end{textblock}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 565
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 566
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 567 \end{frame}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 568 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 569
662
+ − 570 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 571 \begin{frame}[c]
+ − 572 \frametitle{Mkeps}
+ − 573
+ − 574 Finding a (posix) value for recognising the empty string:
+ − 575
+ − 576 \begin{center}
+ − 577 \begin{tabular}{lcl}
+ − 578 \bl{$mkeps\,(\ONE)$} & \bl{$\dn$} & \bl{$Empty$}\\
+ − 579 \bl{$mkeps\,(r_1 + r_2)$} & \bl{$\dn$} & \bl{if $nullable(r_1)$} \\
+ − 580 & & \bl{then $Left(mkeps(r_1))$}\\
+ − 581 & & \bl{else $Right(mkeps(r_2))$}\\
+ − 582 \bl{$mkeps\,(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$Seq(mkeps(r_1),mkeps(r_2))$}\\
+ − 583 \bl{$mkeps\,(r^*)$} & \bl{$\dn$} & \bl{$Stars\,[]$} \\
+ − 584 \end{tabular}
+ − 585 \end{center}
+ − 586
+ − 587 \end{frame}
+ − 588 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
785
+ − 589
+ − 590 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 591 \begin{frame}[c]
+ − 592 \frametitle{Inject}
+ − 593 \large
+ − 594
+ − 595 \begin{center}
+ − 596 \begin{tikzpicture}[scale=3,node distance=1.2cm,
+ − 597 every node/.style={minimum size=7mm}]
+ − 598 \node (r) {$r$};
+ − 599 \node (rd) [right=of r]{$r_{der}$};
+ − 600 \draw[->,line width=1mm](r)--(rd) node[above,midway] {$\der\,c$};
+ − 601 \node (vd) [below=of r2]{$v_{der}$};
+ − 602 \draw[->,line width=1mm](rd) -- (vd);
+ − 603 \node (v) [left=of vd] {$v$};
+ − 604 \draw[->,line width=1mm](vd)--(v) node[below,midway] {$inj\,c$};
+ − 605 \draw[->,line width=0.5mm,dotted](r) -- (v) node[left,midway,red] {\bf ?};
+ − 606 \end{tikzpicture}
+ − 607 \end{center}
+ − 608 \end{frame}
+ − 609 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 610
662
+ − 611
786
+ − 612 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
662
+ − 613 \begin{frame}[c]
+ − 614 \frametitle{Inject}
+ − 615
+ − 616 Injecting (``Adding'') a character to a value\\[-12mm]\mbox{}
+ − 617
+ − 618 \begin{center}
+ − 619 \begin{tabular}{@{\hspace{-3mm}}l@{\hspace{1mm}}c@{\hspace{1mm}}l@{}}
+ − 620 \bl{$inj\,(c)\,c\,(Empty)$} & \bl{$\dn$} & \bl{$Char\,c$}\\
+ − 621 \bl{$inj\,(r_1 + r_2)\,c\,(Left(v))$} & \bl{$\dn$} & \bl{$Left(inj\,r_1\,c\,v)$}\\
+ − 622 \bl{$inj\,(r_1 + r_2)\,c\,(Right(v))$} & \bl{$\dn$} & \bl{$Right(inj\,r_2\,c\,v)$}\\
+ − 623 \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)$}\\
+ − 624 \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)$}\\
+ − 625 \bl{$inj\,(r_1 \cdot r_2)\,c\,(Right(v))$} & \bl{$\dn$} & \bl{$Seq(mkeps(r_1),inj\,r_2\,c\,v)$}\\
+ − 626 \bl{$inj\,(r^*)\,c\,(Seq(v,Stars\,vs))$} & \bl{$\dn$} & \bl{$Stars\,(inj\,r\,c\,v\,::\,vs)$}\\
+ − 627 \end{tabular}
+ − 628 \end{center}\bigskip
+ − 629
+ − 630 \footnotesize
+ − 631 \begin{tabular}{l@{\hspace{2mm}}l}
+ − 632 \bl{$inj$}: & 1st arg $\mapsto$ a rexp; 2nd arg $\mapsto$ a character;
+ − 633 3rd arg $\mapsto$ a value\\
+ − 634 & result $\mapsto$ a value
+ − 635 \end{tabular}
+ − 636 \end{frame}
786
+ − 637 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 638
+ − 639 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 640 \begin{frame}[t]
+ − 641
+ − 642 \begin{center}
+ − 643 \begin{tabular}{@{\hspace{-3mm}}l@{\hspace{1mm}}c@{\hspace{1mm}}l@{}}
+ − 644 \bl{$inj\,(c)\,c\,(Empty)$} & \bl{$\dn$} & \bl{$Char\,c$}\\
+ − 645 \end{tabular}
+ − 646 \end{center}
+ − 647
+ − 648 \end{frame}
+ − 649 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 650
+ − 651 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 652 \begin{frame}[t]
+ − 653
+ − 654 \begin{center}
+ − 655 \begin{tabular}{@{\hspace{-3mm}}l@{\hspace{1mm}}c@{\hspace{1mm}}l@{}}
+ − 656 \bl{$inj\,(r_1 + r_2)\,c\,(Left(v))$} & \bl{$\dn$} & \bl{$Left(inj\,r_1\,c\,v)$}\\
+ − 657 \bl{$inj\,(r_1 + r_2)\,c\,(Right(v))$} & \bl{$\dn$} & \bl{$Right(inj\,r_2\,c\,v)$}\\
+ − 658
+ − 659 \end{tabular}
+ − 660 \end{center}
+ − 661
+ − 662 \end{frame}
+ − 663 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 664
+ − 665 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 666 \begin{frame}[t]
+ − 667
+ − 668 \begin{center}
+ − 669 \begin{tabular}{@{\hspace{-8mm}}l@{\hspace{1mm}}c@{\hspace{1mm}}l@{}}
+ − 670 \\[-15mm]
+ − 671 \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)$}\\
+ − 672 \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)$}\\
+ − 673 \bl{$inj\,(r_1 \cdot r_2)\,c\,(Right(v))$} & \bl{$\dn$} & \bl{$Seq(mkeps(r_1),inj\,r_2\,c\,v)$}\\
+ − 674 \end{tabular}
+ − 675 \end{center}
+ − 676
+ − 677
+ − 678 \begin{textblock}{13}(1,13.4)
+ − 679 \begin{bubble}[13cm]
+ − 680 \small
+ − 681 \bl{$\der\, c\, (r_1 \cdot r_2)$} \bl{$\dn$} \bl{\textbf{if} $nullable (r_1)$}
+ − 682 \bl{\textbf{then} $(\der\,c\,r_1) \cdot r_2 + \der\, c\, r_2$}
+ − 683 \bl{\textbf{else} $(\der\, c\, r_1) \cdot r_2$}
+ − 684 \end{bubble}
+ − 685 \end{textblock}
+ − 686
+ − 687 \end{frame}
+ − 688 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 689
+ − 690 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 691 \begin{frame}[t]
+ − 692
+ − 693 \begin{center}
+ − 694 \begin{tabular}{@{\hspace{-3mm}}l@{\hspace{1mm}}c@{\hspace{1mm}}l@{}}
+ − 695 \bl{$inj\,(r^*)\,c\,(Seq(v,Stars\,vs))$} & \bl{$\dn$} & \bl{$Stars\,(inj\,r\,c\,v\,::\,vs)$}
+ − 696 \end{tabular}
+ − 697 \end{center}
+ − 698
+ − 699 \end{frame}
+ − 700 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 701
662
+ − 702
273
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 703 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 704 \begin{frame}[c]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 705 \frametitle{Lexing}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 706
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 707 \begin{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 708 \begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 709 \bl{$lex\,r\,[]$} & \bl{$\dn$} & \bl{if $nullable(r)$ then $mkeps(r)$ else $error$}\\
786
+ − 710 \bl{$lex\,r\,a::s$} & \bl{$\dn$} & \bl{$inj\,r\,a\,lex(der(a,r), s)$}\\
273
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 711 \end{tabular}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 712 \end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 713
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 714 \footnotesize
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 715 \bl{$lex$}: returns a value
280
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 716
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 717 \begin{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 718 \begin{tikzpicture}[scale=2,node distance=1.0cm,every node/.style={minimum size=6mm}]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 719 \node (r1) {\bl{$r_1$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 720 \node (r2) [right=of r1] {\bl{$r_2$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 721 \draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 722 \node (r3) [right=of r2] {\bl{$r_3$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 723 \draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 724 \node (r4) [right=of r3] {\bl{$r_4$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 725 \draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 726 \draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 727 \node (v4) [below=of r4] {\bl{$v_4$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 728 \draw[->,line width=1mm] (r4) -- (v4);
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 729 \node (v3) [left=of v4] {\bl{$v_3$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 730 \draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 731 \node (v2) [left=of v3] {\bl{$v_2$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 732 \draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 733 \node (v1) [left=of v2] {\bl{$v_1$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 734 \draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 735 \draw[->,line width=0.5mm] (r3) -- (v3);
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 736 \draw[->,line width=0.5mm] (r2) -- (v2);
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 737 \draw[->,line width=0.5mm] (r1) -- (v1);
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 738 \draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 739 \end{tikzpicture}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 740 \end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 741
273
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 742 \end{frame}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 743 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 744
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 745 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 746 \begin{frame}[c]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 747 \frametitle{Records}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 748
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 749 \begin{itemize}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 750 \item new regex: \bl{$(x:r)$}\hspace{7mm}new value: \bl{$Rec(x,v)$}\medskip\pause
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 751
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 752 \item \bl{$nullable(x:r) \dn nullable(r)$}
671
+ − 753 \item \bl{$der\,c\,(x:r) \dn der\,c\,r$}
273
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 754 \item \bl{$mkeps(x:r) \dn Rec(x, mkeps(r))$}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 755 \item \bl{$inj\,(x:r)\,c\,v \dn Rec(x, inj\,r\,c\,v)$}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 756 \end{itemize}\bigskip\bigskip\pause
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 757
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 758 \small
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 759 for extracting subpatterns \bl{$(z: ((x:ab) + (y:ba))$}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 760
786
+ − 761 \begin{textblock}{6}(10,10)
+ − 762 \begin{bubble}[2cm]
+ − 763 \small
+ − 764 \begin{tabular}{l}
+ − 765 \bl{$(id : r_{id})$}\\
+ − 766 \bl{$(key : r_{key})$}\\
+ − 767 \end{tabular}
+ − 768 \end{bubble}
+ − 769 \end{textblock}
+ − 770
+ − 771
273
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 772 \end{frame}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 773 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
352
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 774
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 775 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 776 \begin{frame}[c]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 777
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 778 \begin{itemize}
445
+ − 779 \item A regular expression for email addresses
352
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 780
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 781 \begin{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 782 \begin{tabular}{l}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 783 (name: \bl{$[a\mbox{-}z0\mbox{-}9\_\!\_\,.-]^+$})\bl{$\cdot @\cdot$}\\
794
+ − 784 \qquad(domain: \bl{$[a\mbox{-}z0\mbox{-}9\,-]^+$}) \bl{$\cdot .\cdot$}\\
352
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 785 \qquad\qquad(top\_level: \bl{$[a\mbox{-}z\,.]^{\{2,6\}}$})
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 786 \end{tabular}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 787 \end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 788
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 789 \bl{\[
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 790 \texttt{christian.urban@kcl.ac.uk}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 791 \]}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 792
445
+ − 793 \item the result environment:
352
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 794
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 795 \begin{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 796 \begin{tabular}{l}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 797 \bl{$[(name:\texttt{christian.urban}),$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 798 \bl{$\phantom{[}(domain:\texttt{kcl}),$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 799 \bl{$\phantom{[}(top\_level:\texttt{ac.uk})]$}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 800 \end{tabular}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 801 \end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 802 \end{itemize}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 803
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 804 \end{frame}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 805 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 806
273
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 807
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 808 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 809 \begin{frame}[c]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 810 \frametitle{While Tokens}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 811
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 812 \begin{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 813 \begin{tabular}{rcl}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 814 \pcode{WHILE\_REGS} & $\dn$ & \raisebox{-1mm}{\large(}\pcode{("k" : KEYWORD)} +\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 815 & & \phantom{(}\pcode{("i" : ID)} +\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 816 & & \phantom{(}\pcode{("o" : OP)} + \\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 817 & & \phantom{(}\pcode{("n" : NUM)} + \\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 818 & & \phantom{(}\pcode{("s" : SEMI)} +\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 819 & & \phantom{(}\pcode{("p" : (LPAREN + RPAREN))} +\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 820 & & \phantom{(}\pcode{("b" : (BEGIN + END))} +\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 821 & & \phantom{(}\pcode{("w" : WHITESPACE)}\raisebox{-1mm}{\large)$^*$}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 822 \end{tabular}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 823 \end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 824
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 825 \end{frame}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 826 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 827
352
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 828
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 829
274
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 830 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 831 \begin{frame}[c]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 832 \frametitle{Simplification}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 833
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 834 \begin{itemize}
522
+ − 835 \item If we simplify after the derivative, then we are building the
578
+ − 836 value for the simplified regular expression, but \alert{\textbf{not}} for the original
274
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 837 regular expression.
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 838 \end{itemize}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 839
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 840 \begin{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 841 \begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 842 \node (r1) {\bl{$r_1$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 843 \node (r2) [right=of r1] {\bl{$r_2$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 844 \draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 845 \node (r3) [right=of r2] {\bl{$r_3$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 846 \draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 847 \node (r4) [right=of r3] {\bl{$r_4$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 848 \draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 849 \draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 850 \node (v4) [below=of r4] {\bl{$v_4$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 851 \draw[->,line width=1mm] (r4) -- (v4);
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 852 \node (v3) [left=of v4] {\bl{$v_3$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 853 \draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 854 \node (v2) [left=of v3] {\bl{$v_2$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 855 \draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 856 \node (v1) [left=of v2] {\bl{$v_1$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 857 \draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 858 \draw[->,line width=0.5mm] (r3) -- (v3);
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 859 \draw[->,line width=0.5mm] (r2) -- (v2);
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 860 \draw[->,line width=0.5mm] (r1) -- (v1);
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 861 \draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 862 \end{tikzpicture}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 863 \end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 864
792
+ − 865 \small\pause
445
+ − 866 \hspace{4.5cm}\bl{$(\ZERO \cdot (b \cdot c)) + ((\ZERO \cdot c) + \ONE)$}
352
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 867 $\mapsto$
445
+ − 868 \bl{$\ONE$}
352
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 869
274
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 870 \end{frame}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 871 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 872
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 873 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 874 \begin{frame}[c]
447
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 875
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 876 Normally we would have
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 877
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 878 \begin{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 879 \bl{$(\ZERO \cdot (b \cdot c)) + ((\ZERO \cdot c) + \ONE)$}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 880 \end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 881
452
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 882 and answer how this regular expression matches the empty string
578
+ − 883 with the value
447
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 884
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 885 \begin{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 886 \bl{$Right(Right(Empty))$}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 887 \end{center}\bigskip
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 888
578
+ − 889 But now we simplify this to \bl{$\ONE$} and would produce \bl{$Empty$} (see \textit{mkeps}).
447
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 890
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 891 \end{frame}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 892 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 893
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 894 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 895 \begin{frame}[c]
274
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 896 \frametitle{Rectification}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 897
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 898 \def\arraystretch{1.05}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 899 \begin{center}
445
+ − 900 \begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}l@{\hspace{8mm}}l}
274
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 901 & & & \hspace{5mm}rectification \\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 902 & & & \hspace{5mm}functions:\\
445
+ − 903 \bl{$r \cdot \ZERO$} & $\mapsto$ & \bl{$\ZERO$} & \\
+ − 904 \bl{$\ZERO \cdot r$} & $\mapsto$ & \bl{$\ZERO$} & \\
+ − 905 \bl{$r \cdot \ONE$} & $\mapsto$ & \bl{$r$} & \bl{$\lambda f_1\,f_2\,v.\, Seq(f_1\,v, f_2\,Empty)$}\\
+ − 906 \bl{$\ONE \cdot r$} & $\mapsto$ & \bl{$r$} & \bl{$\lambda f_1\,f_2\,v.\, Seq(f_1\,Empty, f_2\,v)$}\\
+ − 907 \bl{$r + \ZERO$} & $\mapsto$ & \bl{$r$} & \bl{$\lambda f_1\,f_2\,v.\, Left(f_1\,v)$}\\
+ − 908 \bl{$\ZERO + r$} & $\mapsto$ & \bl{$r$} & \bl{$\lambda f_1\,f_2\,v.\, Right(f_2\,v)$}\\
274
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 909 \bl{$r + r$} & $\mapsto$ & \bl{$r$} & \bl{$\lambda f_1\,f_2\,v.\, Left(f_1\,v)$}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 910 \end{tabular}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 911 \end{center}\medskip\pause
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 912
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 913 \small
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 914 old \bl{$simp$} returns a rexp;\\
445
+ − 915 new \bl{$simp$} returns a rexp and a rectification~function.
274
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 916 \end{frame}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 917 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 918
352
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 919
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 920 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 921 \begin{frame}[c]
788
+ − 922 \frametitle{Rectification $\_ + \_$}
352
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 923
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 924 \begin{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 925 \begin{tabular}{l}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 926 \bl{$simp(r)$}:\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 927 \quad case \bl{$r = r_1 + r_2$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 928 \qquad let \bl{$(r_{1s}, f_{1s}) = simp(r_1)$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 929 \qquad \phantom{let} \bl{$(r_{2s}, f_{2s}) = simp(r_2)$}\smallskip\\
445
+ − 930 \qquad case \bl{$r_{1s} = \ZERO$}:
352
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 931 return \bl{$(r_{2s}, \lambda v. \,Right(f_{2s}(v)))$}\\
445
+ − 932 \qquad case \bl{$r_{2s} = \ZERO$}:
352
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 933 return \bl{$(r_{1s}, \lambda v. \,Left(f_{1s}(v)))$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 934 \qquad case \bl{$r_{1s} = r_{2s}$}:
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 935 return \bl{$(r_{1s}, \lambda v. \,Left(f_{1s}(v)))$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 936 \qquad otherwise:
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 937 return \bl{$(r_{1s} + r_{2s}, f_{alt}(f_{1s}, f_{2s}))$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 938 \end{tabular}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 939 \end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 940
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 941 \small
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 942 \begin{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 943 \begin{tabular}{l@{\hspace{1mm}}l}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 944 \bl{$f_{alt}(f_1, f_2) \dn$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 945 \qquad \bl{$\lambda v.\,$} case \bl{$v = Left(v')$}:
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 946 & return \bl{$Left(f_1(v'))$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 947 \qquad \phantom{$\lambda v.\,$} case \bl{$v = Right(v')$}:
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 948 & return \bl{$Right(f_2(v'))$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 949 \end{tabular}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 950 \end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 951
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 952
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 953 \end{frame}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 954 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 955
445
+ − 956 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
352
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 957 \begin{frame}[c]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 958
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 959 {\footnotesize\lstinputlisting[language=Scala,numbers=none,
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 960 xleftmargin=-5mm] {../progs/app05.scala}}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 961
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 962 \end{frame}
445
+ − 963 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
352
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 964
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 965 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 966 \begin{frame}[c]
788
+ − 967 \frametitle{Rectification $\_ \cdot \_$}
352
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 968
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 969 \begin{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 970 \begin{tabular}{@{\hspace{-3mm}}l}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 971 \bl{$simp(r)$}:\ldots\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 972 \quad case \bl{$r = r_1 \cdot r_2$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 973 \qquad let \bl{$(r_{1s}, f_{1s}) = simp(r_1)$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 974 \qquad \phantom{let} \bl{$(r_{2s}, f_{2s}) = simp(r_2)$}\smallskip\\
445
+ − 975 \qquad case \bl{$r_{1s} = \ZERO$}:
+ − 976 return \bl{$(\ZERO, f_{error})$}\\
+ − 977 \qquad case \bl{$r_{2s} = \ZERO$}:
+ − 978 return \bl{$(\ZERO, f_{error})$}\\
+ − 979 \qquad case \bl{$r_{1s} = \ONE$}:
352
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 980 return \bl{$(r_{2s}, \lambda v. \,Seq(f_{1s}(Empty), f_{2s}(v)))$}\\
445
+ − 981 \qquad case \bl{$r_{2s} = \ONE$}:
352
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 982 return \bl{$(r_{1s}, \lambda v. \,Seq(f_{1s}(v), f_{2s}(Empty)))$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 983 \qquad otherwise:
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 984 return \bl{$(r_{1s} \cdot r_{2s}, f_{seq}(f_{1s}, f_{2s}))$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 985 \end{tabular}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 986 \end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 987
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 988 \small
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 989 \begin{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 990 \begin{tabular}{l@{\hspace{1mm}}l}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 991 \bl{$f_{seq}(f_1, f_2) \dn$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 992 \qquad \bl{$\lambda v.\,$ case $v = Seq(v_1, v_2)$}:
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 993 & return \bl{$Seq(f_1(v_1), f_2(v_2))$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 994 \end{tabular}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 995 \end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 996 \end{frame}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 997 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 998
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 999
451
+ − 1000 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
352
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1001 \begin{frame}[c]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1002
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1003 {\footnotesize\lstinputlisting[language=Scala,numbers=none,
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1004 xleftmargin=-5mm] {../progs/app06.scala}}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1005
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1006 \end{frame}
451
+ − 1007 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1008
+ − 1009 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1010 \begin{frame}[t]
+ − 1011 \frametitle{Rectification Example}
+ − 1012
+ − 1013 \begin{center}
+ − 1014 \bl{$\only<1>{(b \cdot c)}%
+ − 1015 \only<2-3>{(\underline{b \cdot c})}%
+ − 1016 \only<1-3>{+}%
+ − 1017 \only<1>{(\ZERO + \ONE)}%
+ − 1018 \only<2-3>{(\underline{\ZERO + \ONE})}$}%
+ − 1019 \only<4->{%
+ − 1020 \bl{$\underline{(b \cdot c) + (\ZERO + \ONE)}$}%
+ − 1021 }
+ − 1022 $\mapsto$
+ − 1023 \bl{$(b \cdot c) + \ONE$}
+ − 1024 \end{center}\bigskip
+ − 1025
+ − 1026 \onslide<3->{%
+ − 1027 \begin{center}
+ − 1028 \begin{tabular}{lcl}
+ − 1029 \bl{$f_{s1}$} & \bl{$=$} & \bl{$\lambda v.v$}\\
+ − 1030 \bl{$f_{s2}$} & \bl{$=$} & \bl{$\lambda v. \textit{Right}(v)$}
+ − 1031 \end{tabular}
+ − 1032 \end{center}}
+ − 1033
+ − 1034 \only<4>{%
+ − 1035 \begin{center}
+ − 1036 \begin{tabular}{@{}l@{\hspace{1mm}}l@{}}
+ − 1037 \bl{$f_{alt}(f_{s1}, f_{s2}) \dn$}\\
+ − 1038 \quad \bl{$\lambda v.\,$}
+ − 1039 case \bl{$v = Left(v')$}:
+ − 1040 & return \bl{$Left(f_{s1}(v'))$}\\
+ − 1041 \quad \phantom{$\lambda v.\,$}
+ − 1042 case \bl{$v = Right(v')$}:
+ − 1043 & return \bl{$Right(f_{s2}(v'))$}\\
+ − 1044 \end{tabular}
+ − 1045 \end{center}}%
+ − 1046 \only<5->{%
+ − 1047 \begin{center}
+ − 1048 \begin{tabular}{@{}l@{\hspace{1mm}}l@{}}
+ − 1049 \only<5->{\phantom{\bl{$f_{alt}(f_{s1}, f_{s2}) \dn$}}}\\
+ − 1050 \quad \bl{$\lambda v.\,$}
+ − 1051 case \bl{$v = Left(v')$}:
+ − 1052 & return \bl{$Left(v')$}\\
+ − 1053 \quad \phantom{$\lambda v.\,$}
+ − 1054 case \bl{$v = Right(v')$}:
+ − 1055 & return \bl{$Right(Right(v'))$}\\
+ − 1056 \end{tabular}
+ − 1057 \end{center}}%
+ − 1058
+ − 1059 \only<6->{%
+ − 1060 \begin{center}
+ − 1061 \begin{tabular}{@{}l@{\hspace{4mm}}l@{}}
+ − 1062 \bl{$\textit{mkeps}$} simplified case: &
+ − 1063 \bl{$\textit{Right}(\textit{Empty})$}\\
+ − 1064 rectified case: &
+ − 1065 \bl{$\textit{Right}(\textit{Right}(\textit{Empty}))$}
+ − 1066 \end{tabular}
+ − 1067 \end{center}}%
+ − 1068
+ − 1069 \end{frame}
+ − 1070 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
352
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1071
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1072
274
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1073 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1074 \begin{frame}[c]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1075 \frametitle{Lexing with Simplification}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1076
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1077 \begin{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1078 \begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1079 \bl{$lex\,r\,[]$} & \bl{$\dn$} & \bl{if $nullable(r)$ then $mkeps(r)$ else $error$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1080 \bl{$lex\,r\,c::s$} & \bl{$\dn$} & \bl{let $(r', frect) = simp(der(c, r))$}\smallskip\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1081 & & \bl{$inj\,r\,c\,(frect(lex(r', s)))$}\\
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1082 \end{tabular}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1083 \end{center}\bigskip
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1084
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1085 \begin{center}\small
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1086 \begin{tikzpicture}[node distance=1.1cm,every node/.style={minimum size=7mm}]
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1087 \node (r1) {\bl{$r_1$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1088 \node (r2) [right=of r1] {\bl{$r_2$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1089 \draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1090 \node (r3) [right=of r2] {\bl{$r_3$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1091 \draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1092 \node (r4) [right=of r3] {\bl{$r_4$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1093 \draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1094 \draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1095 \node (v4) [below=of r4] {\bl{$v_4$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1096 \draw[->,line width=1mm] (r4) -- (v4);
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1097 \node (v3) [left=of v4] {\bl{$v_3$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1098 \draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1099 \node (v2) [left=of v3] {\bl{$v_2$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1100 \draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1101 \node (v1) [left=of v2] {\bl{$v_1$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1102 \draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1103 \draw[->,line width=0.5mm] (r3) -- (v3);
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1104 \draw[->,line width=0.5mm] (r2) -- (v2);
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1105 \draw[->,line width=0.5mm] (r1) -- (v1);
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1106 \draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1107 \end{tikzpicture}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1108 \end{center}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1109
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1110
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1111 \end{frame}
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1112 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1113
451
+ − 1114 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1115 \begin{frame}[c]
+ − 1116 \frametitle{Environments}
+ − 1117
+ − 1118 Obtaining the ``recorded'' parts of a value:
+ − 1119
+ − 1120 \begin{center}
+ − 1121 \begin{tabular}{lcl}
+ − 1122 \bl{$env(Empty)$} & \bl{$\dn$} & \bl{$[]$}\\
+ − 1123 \bl{$env(Char(c))$} & \bl{$\dn$} & \bl{$[]$}\\
+ − 1124 \bl{$env(Left(v))$} & \bl{$\dn$} & \bl{$env(v)$}\\
+ − 1125 \bl{$env(Right(v))$} & \bl{$\dn$} & \bl{$env(v)$}\\
+ − 1126 \bl{$env(Seq(v_1,v_2))$}& \bl{$\dn$} & \bl{$env(v_1) \,@\, env(v_2)$}\\
578
+ − 1127 \bl{$env(Stars\,[v_1,\ldots ,v_n])$} & \bl{$\dn$} &
451
+ − 1128 \bl{$env(v_1) \,@\ldots @\, env(v_n)$}\\
+ − 1129 \bl{$env(Rec(x:v))$} & \bl{$\dn$} & \bl{$(x:|v|) :: env(v)$}\\
+ − 1130 \end{tabular}
+ − 1131 \end{center}
+ − 1132
+ − 1133 \end{frame}
+ − 1134 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1135
+ − 1136
+ − 1137 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1138 \begin{frame}[c]
+ − 1139 \frametitle{While Tokens}
+ − 1140
+ − 1141 \begin{center}
+ − 1142 \begin{tabular}{@{}r@{\hspace{2mm}}c@{\hspace{2mm}}l@{}}
+ − 1143 \pcode{WHILE\_REGS} & $\dn$ & \raisebox{-1mm}{\large(}\pcode{("k" : KEYWORD)} +\\
+ − 1144 & & \phantom{(}\pcode{("i" : ID)} +\\
+ − 1145 & & \phantom{(}\pcode{("o" : OP)} + \\
+ − 1146 & & \phantom{(}\pcode{("n" : NUM)} + \\
+ − 1147 & & \phantom{(}\pcode{("s" : SEMI)} +\\
+ − 1148 & & \phantom{(}\pcode{("p" : (LPAREN + RPAREN))} +\\
+ − 1149 & & \phantom{(}\pcode{("b" : (BEGIN + END))} +\\
+ − 1150 & & \phantom{(}\pcode{("w" : WHITESPACE)}\raisebox{-1mm}{\large)$^*$}
+ − 1151 \end{tabular}
+ − 1152 \end{center}
+ − 1153
+ − 1154 \end{frame}
+ − 1155 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1156
+ − 1157
+ − 1158
+ − 1159 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1160 \begin{frame}[t]
+ − 1161
+ − 1162 \consolas
+ − 1163 \begin{center}
+ − 1164 \code{"if true then then 42 else +"}
+ − 1165 \end{center}
+ − 1166
+ − 1167 \only<1>{
+ − 1168 \small\begin{tabular}{l}
+ − 1169 KEYWORD(if),\\
+ − 1170 WHITESPACE,\\
+ − 1171 IDENT(true),\\
+ − 1172 WHITESPACE,\\
+ − 1173 KEYWORD(then),\\
+ − 1174 WHITESPACE,\\
+ − 1175 KEYWORD(then),\\
+ − 1176 WHITESPACE,\\
+ − 1177 NUM(42),\\
+ − 1178 WHITESPACE,\\
+ − 1179 KEYWORD(else),\\
+ − 1180 WHITESPACE,\\
+ − 1181 OP(+)
+ − 1182 \end{tabular}}
+ − 1183
+ − 1184 \only<2>{
+ − 1185 \small\begin{tabular}{l}
+ − 1186 KEYWORD(if),\\
+ − 1187 IDENT(true),\\
+ − 1188 KEYWORD(then),\\
+ − 1189 KEYWORD(then),\\
+ − 1190 NUM(42),\\
+ − 1191 KEYWORD(else),\\
+ − 1192 OP(+)
+ − 1193 \end{tabular}}
+ − 1194
+ − 1195 \end{frame}
+ − 1196 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1197
+ − 1198 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1199 \begin{frame}[c]
521
+ − 1200 \frametitle{Lexer: Two Rules}
451
+ − 1201
+ − 1202 \begin{itemize}
+ − 1203 \item Longest match rule (``maximal munch rule''): The
+ − 1204 longest initial substring matched by any regular expression is taken
+ − 1205 as next token.\bigskip
+ − 1206
+ − 1207 \item Rule priority:
+ − 1208 For a particular longest initial substring, the first regular
+ − 1209 expression that can match determines the token.
+ − 1210
+ − 1211 \end{itemize}
+ − 1212
+ − 1213 %\url{http://www.technologyreview.com/tr10/?year=2011}
+ − 1214
+ − 1215 %finite deterministic automata/ nondeterministic automaton
+ − 1216
+ − 1217 %\item problem with infix operations, for example i-12
+ − 1218
+ − 1219
+ − 1220 \end{frame}
+ − 1221 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1222
+ − 1223
352
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1224
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1225 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
788
+ − 1226 %\begin{frame}[c]
+ − 1227 %\begin{center}
+ − 1228 %\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
+ − 1229 %\bl{$zeroable(\ZERO)$} & \bl{$\dn$} & \bl{$true$}\\
+ − 1230 %\bl{$zeroable(\ONE)$} & \bl{$\dn$} & \bl{$\textit{false}$}\\
+ − 1231 %\bl{$zeroable(c)$} & \bl{$\dn$} & \bl{$\textit{false}$}\\
+ − 1232 %\bl{$zeroable(r_1 + r_2)$} & \bl{$\dn$} & \bl{$zeroable(r_1) \wedge zeroable(r_2)$}\\
+ − 1233 %\bl{$zeroable(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$zeroable(r_1) \vee zeroable(r_2)$}\\
+ − 1234 %\bl{$zeroable(r^*)$} & \bl{$\dn$} & \bl{$\textit{false}$}\\
+ − 1235 %\end{tabular}
+ − 1236 %\end{center}
+ − 1237 %
+ − 1238 %\begin{center}
+ − 1239 %\bl{$zeroable(r)$} if and only if \bl{$L(r) = \{\}$}
+ − 1240 %\end{center}
+ − 1241 %
+ − 1242 %
+ − 1243 %\end{frame}
352
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1244 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1245
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
+ − 1246
743
+ − 1247
+ − 1248 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
788
+ − 1249 %\begin{frame}[c]
+ − 1250 %\frametitle{\begin{tabular}{c}Last Week\\[-2mm]
+ − 1251 % Regexes and Values\end{tabular}}
+ − 1252 %
+ − 1253 %Regular expressions and their corresponding values:
+ − 1254 %
+ − 1255 %\begin{center}
+ − 1256 %\begin{columns}
+ − 1257 %\begin{column}{3cm}
+ − 1258 %\begin{tabular}{@{}rrl@{}}
+ − 1259 % \bl{$r$} & \bl{$::=$} & \bl{$\ZERO$}\\
+ − 1260 % & \bl{$\mid$} & \bl{$\ONE$} \\
+ − 1261 % & \bl{$\mid$} & \bl{$c$} \\
+ − 1262 % & \bl{$\mid$} & \bl{$r_1 \cdot r_2$}\\
+ − 1263 % & \bl{$\mid$} & \bl{$r_1 + r_2$} \\
+ − 1264 % \\
+ − 1265 % & \bl{$\mid$} & \bl{$r^*$} \\
+ − 1266 % \end{tabular}
+ − 1267 %\end{column}
+ − 1268 %\begin{column}{3cm}
+ − 1269 %\begin{tabular}{@{\hspace{-7mm}}rrl@{}}
+ − 1270 % \bl{$v$} & \bl{$::=$} & \\
+ − 1271 % & & \bl{$Empty$} \\
+ − 1272 % & \bl{$\mid$} & \bl{$Char(c)$} \\
+ − 1273 % & \bl{$\mid$} & \bl{$Seq(v_1,v_2)$}\\
+ − 1274 % & \bl{$\mid$} & \bl{$Left(v)$} \\
+ − 1275 % & \bl{$\mid$} & \bl{$Right(v)$} \\
+ − 1276 % & \bl{$\mid$} & \bl{$Stars [v_1,\ldots\,v_n]$} \\
+ − 1277 % \end{tabular}
+ − 1278 %\end{column}
+ − 1279 %\end{columns}
+ − 1280 %\end{center}
+ − 1281 %
+ − 1282 %\end{frame}
743
+ − 1283 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1284
+ − 1285 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
788
+ − 1286 %\begin{frame}[c]
+ − 1287 %
+ − 1288 %\begin{textblock}{10}(3,5)
+ − 1289 %\begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}]
+ − 1290 %\node (r1) {\bl{$r_1$}};
+ − 1291 %\node (r2) [right=of r1] {\bl{$r_2$}};
+ − 1292 %\draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};
+ − 1293 %\node (r3) [right=of r2] {\bl{$r_3$}};
+ − 1294 %\draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};
+ − 1295 %\node (r4) [right=of r3] {\bl{$r_4$}};
+ − 1296 %\draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};
+ − 1297 %\draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};
+ − 1298 %\node (v4) [below=of r4] {\bl{$v_4$}};
+ − 1299 %\draw[->,line width=1mm] (r4) -- (v4);
+ − 1300 %\node (v3) [left=of v4] {\bl{$v_3$}};
+ − 1301 %\draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};
+ − 1302 %\node (v2) [left=of v3] {\bl{$v_2$}};
+ − 1303 %\draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};
+ − 1304 %\node (v1) [left=of v2] {\bl{$v_1$}};
+ − 1305 %\draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};
+ − 1306 %\draw[->,line width=0.5mm] (r3) -- (v3);
+ − 1307 %\draw[->,line width=0.5mm] (r2) -- (v2);
+ − 1308 %\draw[->,line width=0.5mm] (r1) -- (v1);
+ − 1309 %\draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};
+ − 1310 %\end{tikzpicture}
+ − 1311 %\end{textblock}
+ − 1312 %
+ − 1313 %\begin{textblock}{6}(1,0.8)
+ − 1314 %\begin{bubble}[6cm]
+ − 1315 %\small
+ − 1316 %\begin{tabular}{ll}
+ − 1317 %\bl{$r_1$}: & \bl{$a \cdot (b \cdot c)$}\\
+ − 1318 %\bl{$r_2$}: & \bl{$\ONE \cdot (b \cdot c)$}\\
+ − 1319 %\bl{$r_3$}: & \bl{$(\ZERO \cdot (b \cdot c)) + (\ONE \cdot c)$}\\
+ − 1320 %\bl{$r_4$}: & \bl{$(\ZERO \cdot (b \cdot c)) + ((\ZERO \cdot c) + \ONE)$}\\
+ − 1321 %\end{tabular}
+ − 1322 %\end{bubble}
+ − 1323 %\end{textblock}
+ − 1324 %
+ − 1325 %\begin{textblock}{6}(1,11.4)
+ − 1326 %\begin{bubble}[7.6cm]
+ − 1327 %\small
+ − 1328 %\begin{tabular}{ll}
+ − 1329 %\bl{$v_1$}: & \bl{$Seq(Char(a), Seq(Char(b), Char(c)))$}\\
+ − 1330 %\bl{$v_2$}: & \bl{$Seq(Empty, Seq(Char(b), Char(c)))$}\\
+ − 1331 %\bl{$v_3$}: & \bl{$Right(Seq(Empty, Char(c)))$}\\
+ − 1332 %\bl{$v_4$}: & \bl{$Right(Right(Empty))$}\\
+ − 1333 %\end{tabular}
+ − 1334 %\end{bubble}
+ − 1335 %\end{textblock}
+ − 1336 %
+ − 1337 %\begin{textblock}{6}(12,11.4)
+ − 1338 %\begin{bubble}[2cm]
+ − 1339 %\small
+ − 1340 %\begin{tabular}{ll}
+ − 1341 %\bl{$|v_1|$}: & \bl{$abc$}\\
+ − 1342 %\bl{$|v_2|$}: & \bl{$bc$}\\
+ − 1343 %\bl{$|v_3|$}: & \bl{$c$}\\
+ − 1344 %\bl{$|v_4|$}: & \bl{$[]$}
+ − 1345 %\end{tabular}
+ − 1346 %\end{bubble}
+ − 1347 %\end{textblock}
+ − 1348 %
+ − 1349 %
+ − 1350 %%\end{frame}
+ − 1351 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1352 %
+ − 1353 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1354 %\begin{frame}[c]
+ − 1355 %\frametitle{Simplification}
+ − 1356 %
+ − 1357 %\begin{itemize}
+ − 1358 %\item If we simplify after the derivative, then we are builing the
+ − 1359 %value for the simplified regular expression, but \emph{not} for the original
+ − 1360 %regular expression.
+ − 1361 %\end{itemize}
+ − 1362 %
+ − 1363 %\begin{center}
+ − 1364 %\begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}]
+ − 1365 %\node (r1) {\bl{$r_1$}};
+ − 1366 %\node (r2) [right=of r1] {\bl{$r_2$}};
+ − 1367 %\draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};
+ − 1368 %\node (r3) [right=of r2] {\bl{$r_3$}};
+ − 1369 %\draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};
+ − 1370 %\node (r4) [right=of r3] {\bl{$r_4$}};
+ − 1371 %\draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};
+ − 1372 %\draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};
+ − 1373 %\node (v4) [below=of r4] {\bl{$v_4$}};
+ − 1374 %\draw[->,line width=1mm] (r4) -- (v4);
+ − 1375 %\node (v3) [left=of v4] {\bl{$v_3$}};
+ − 1376 %\draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};
+ − 1377 %\node (v2) [left=of v3] {\bl{$v_2$}};
+ − 1378 %\draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};
+ − 1379 %\node (v1) [left=of v2] {\bl{$v_1$}};
+ − 1380 %\draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};
+ − 1381 %\draw[->,line width=0.5mm] (r3) -- (v3);
+ − 1382 %\draw[->,line width=0.5mm] (r2) -- (v2);
+ − 1383 %\draw[->,line width=0.5mm] (r1) -- (v1);
+ − 1384 %\draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};
+ − 1385 %\end{tikzpicture}
+ − 1386 %\end{center}
+ − 1387 %
+ − 1388 %\small
+ − 1389 %\hspace{4.5cm}\bl{$(b \cdot c) + (\ZERO + \ONE)$}
+ − 1390 %$\mapsto$
+ − 1391 %\bl{$(b \cdot c) + \ONE$}
+ − 1392 %
+ − 1393 %\end{frame}
+ − 1394 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1395 %
+ − 1396 %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
743
+ − 1397 % \begin{frame}[t]
+ − 1398
+ − 1399 % \begin{center}
+ − 1400 % \bl{$\only<1>{(b \cdot c)}%
+ − 1401 % \only<2-3>{(\underline{b \cdot c})}%
+ − 1402 % \only<1-3>{+}%
+ − 1403 % \only<1>{(\ZERO + \ONE)}%
+ − 1404 % \only<2-3>{(\underline{\ZERO + \ONE})}$}%
+ − 1405 % \only<4->{%
+ − 1406 % \bl{$\underline{(b \cdot c) + (\ZERO + \ONE)}$}%
+ − 1407 % }
+ − 1408 % $\mapsto$
+ − 1409 % \bl{$(b \cdot c) + \ONE$}
+ − 1410 % \end{center}\bigskip
+ − 1411
+ − 1412 % \onslide<3->{%
+ − 1413 % \begin{center}
+ − 1414 % \begin{tabular}{lcl}
+ − 1415 % \bl{$f_{s1}$} & \bl{$=$} & \bl{$\lambda v.v$}\\
+ − 1416 % \bl{$f_{s2}$} & \bl{$=$} & \bl{$\lambda v. \textit{Right}(v)$}
+ − 1417 % \end{tabular}
+ − 1418 % \end{center}}
+ − 1419
+ − 1420 % \only<4>{%
+ − 1421 % \begin{center}
+ − 1422 % \begin{tabular}{@{}l@{\hspace{1mm}}l@{}}
+ − 1423 % \bl{$f_{alt}(f_{s1}, f_{s2}) \dn$}\\
+ − 1424 % \quad \bl{$\lambda v.\,$}
+ − 1425 % case \bl{$v = Left(v')$}:
+ − 1426 % & return \bl{$Left(f_{s1}(v'))$}\\
+ − 1427 % \quad \phantom{$\lambda v.\,$}
+ − 1428 % case \bl{$v = Right(v')$}:
+ − 1429 % & return \bl{$Right(f_{s2}(v'))$}\\
+ − 1430 % \end{tabular}
+ − 1431 % \end{center}}%
+ − 1432 % \only<5->{%
+ − 1433 % \begin{center}
+ − 1434 % \begin{tabular}{@{}l@{\hspace{1mm}}l@{}}
+ − 1435 % \only<5->{\phantom{\bl{$f_{alt}(f_{s1}, f_{s2}) \dn$}}}\\
+ − 1436 % \quad \bl{$\lambda v.\,$}
+ − 1437 % case \bl{$v = Left(v')$}:
+ − 1438 % & return \bl{$Left(v')$}\\
+ − 1439 % \quad \phantom{$\lambda v.\,$}
+ − 1440 % case \bl{$v = Right(v')$}:
+ − 1441 % & return \bl{$Right(Right(v'))$}\\
+ − 1442 % \end{tabular}
+ − 1443 % \end{center}}%
+ − 1444
+ − 1445 % \only<6->{%
+ − 1446 % \begin{center}
+ − 1447 % \begin{tabular}{@{}l@{\hspace{4mm}}l@{}}
+ − 1448 % \bl{$\textit{mkeps}$} simplified case: &
+ − 1449 % \bl{$\textit{Right}(\textit{Empty})$}\\
+ − 1450 % rectified case: &
+ − 1451 % \bl{$\textit{Right}(\textit{Right}(\textit{Empty}))$}
+ − 1452 % \end{tabular}
+ − 1453 % \end{center}}%
+ − 1454
+ − 1455 % \end{frame}
+ − 1456 % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1457
788
+ − 1458 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1459 %\begin{frame}[c]
+ − 1460 %\frametitle{Records}
+ − 1461 %
+ − 1462 %\begin{itemize}
+ − 1463 %\item new regex: \bl{$(x:r)$}\hspace{7mm}new value: \bl{$Rec(x,v)$}\medskip\pause
+ − 1464 %
+ − 1465 %\item \bl{$nullable(x:r) \dn nullable(r)$}
+ − 1466 %\item \bl{$der\,c\,(x:r) \dn der\,c\,r$}
+ − 1467 %\item \bl{$mkeps(x:r) \dn Rec(x, mkeps(r))$}
+ − 1468 %\item \bl{$inj\,(x:r)\,c\,v \dn Rec(x, inj\,r\,c\,v)$}
+ − 1469 %\end{itemize}\bigskip\bigskip\pause
+ − 1470 %
+ − 1471 %\small
+ − 1472 %for extracting subpatterns \bl{$(z: ((x:ab) + (y:ba))$}
+ − 1473 %
+ − 1474 %\end{frame}
+ − 1475 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
743
+ − 1476
+ − 1477
+ − 1478 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1479 \begin{frame}[c]
+ − 1480 \frametitle{Environments}
+ − 1481
+ − 1482 Obtaining the ``recorded'' parts of a value:
+ − 1483
+ − 1484 \begin{center}
+ − 1485 \begin{tabular}{lcl}
+ − 1486 \bl{$env(Empty)$} & \bl{$\dn$} & \bl{$[]$}\\
+ − 1487 \bl{$env(Char(c))$} & \bl{$\dn$} & \bl{$[]$}\\
+ − 1488 \bl{$env(Left(v))$} & \bl{$\dn$} & \bl{$env(v)$}\\
+ − 1489 \bl{$env(Right(v))$} & \bl{$\dn$} & \bl{$env(v)$}\\
+ − 1490 \bl{$env(Seq(v_1,v_2))$}& \bl{$\dn$} & \bl{$env(v_1) \,@\, env(v_2)$}\\
+ − 1491 \bl{$env(Stars [v_1,\ldots ,v_n])$} & \bl{$\dn$} &
+ − 1492 \bl{$env(v_1) \,@\ldots @\, env(v_n)$}\\
+ − 1493 \bl{$env(Rec(x:v))$} & \bl{$\dn$} & \bl{$(x:|v|) :: env(v)$}\\
+ − 1494 \end{tabular}
+ − 1495 \end{center}
+ − 1496
+ − 1497 \end{frame}
+ − 1498 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1499
+ − 1500
+ − 1501 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1502 \begin{frame}[c]
+ − 1503 \frametitle{While Tokens}
+ − 1504
+ − 1505 \begin{center}
+ − 1506 \begin{tabular}{@{}r@{\hspace{2mm}}c@{\hspace{2mm}}l@{}}
+ − 1507 \pcode{WHILE\_REGS} & $\dn$ & \raisebox{-1mm}{\large(}\pcode{("k" : KEYWORD)} +\\
+ − 1508 & & \phantom{(}\pcode{("i" : ID)} +\\
+ − 1509 & & \phantom{(}\pcode{("o" : OP)} + \\
+ − 1510 & & \phantom{(}\pcode{("n" : NUM)} + \\
+ − 1511 & & \phantom{(}\pcode{("s" : SEMI)} +\\
+ − 1512 & & \phantom{(}\pcode{("p" : (LPAREN + RPAREN))} +\\
+ − 1513 & & \phantom{(}\pcode{("b" : (BEGIN + END))} +\\
+ − 1514 & & \phantom{(}\pcode{("w" : WHITESPACE)}\raisebox{-1mm}{\large)$^*$}
+ − 1515 \end{tabular}
+ − 1516 \end{center}
+ − 1517
+ − 1518 \end{frame}
+ − 1519 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1520
+ − 1521
+ − 1522
+ − 1523 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1524 \begin{frame}[t]
+ − 1525
+ − 1526 \consolas
+ − 1527 \begin{center}
+ − 1528 \code{"if true then then 42 else +"}
+ − 1529 \end{center}
+ − 1530
+ − 1531 \only<1>{
+ − 1532 \small\begin{tabular}{l}
+ − 1533 KEYWORD(if),\\
+ − 1534 WHITESPACE,\\
+ − 1535 IDENT(true),\\
+ − 1536 WHITESPACE,\\
+ − 1537 KEYWORD(then),\\
+ − 1538 WHITESPACE,\\
+ − 1539 KEYWORD(then),\\
+ − 1540 WHITESPACE,\\
+ − 1541 NUM(42),\\
+ − 1542 WHITESPACE,\\
+ − 1543 KEYWORD(else),\\
+ − 1544 WHITESPACE,\\
+ − 1545 OP(+)
+ − 1546 \end{tabular}}
+ − 1547
+ − 1548 \only<2>{
+ − 1549 \small\begin{tabular}{l}
+ − 1550 KEYWORD(if),\\
+ − 1551 IDENT(true),\\
+ − 1552 KEYWORD(then),\\
+ − 1553 KEYWORD(then),\\
+ − 1554 NUM(42),\\
+ − 1555 KEYWORD(else),\\
+ − 1556 OP(+)
+ − 1557 \end{tabular}}
+ − 1558
+ − 1559 \end{frame}
+ − 1560 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1561
+ − 1562
+ − 1563
+ − 1564 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1565 %\begin{frame}[c]
+ − 1566 %\frametitle{Coursework: PLs (16)}
+ − 1567 %
+ − 1568 %\begin{itemize}
+ − 1569 %\item Java (16)
+ − 1570 %\item C++, C, C\# (14)
+ − 1571 %\item JavaScript (10)
+ − 1572 %\item Scala (9)
+ − 1573 %\item Python (9)
+ − 1574 %\item PHP (6)
+ − 1575 %\item Haskell (3)
+ − 1576 %\item Ruby (4)
+ − 1577 %\item Bash, Perl, Powershell (2)
+ − 1578 %\item TypeScript (1)
+ − 1579 %\item R (1)
+ − 1580 %\item Coconut (1)
+ − 1581 %\item Pascal (1)
+ − 1582 %\end{itemize}
+ − 1583 %
+ − 1584 %\end{frame}
+ − 1585 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1586
+ − 1587 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1588 %\begin{frame}[c]
+ − 1589 %\frametitle{Coursework: Nullable}
+ − 1590 %
+ − 1591 %\begin{center}
+ − 1592 %\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
+ − 1593 % \bl{$nullable([c_1 c_2 \ldots c_n])$} & \bl{$\dn$} & $?$\\
+ − 1594 % \bl{$nullable(r^+)$} & \bl{$\dn$} & $?$\\
+ − 1595 % \bl{$nullable(r^?)$} & \bl{$\dn$} & $?$\\
+ − 1596 % \bl{$nullable(r^{\{n\}})$} & \bl{$\dn$} & $?$\\
+ − 1597 % \bl{$nullable(r^{\{n..\}})$} & \bl{$\dn$} & $?$\\
+ − 1598 % \bl{$nullable(r^{\{..n\}})$} & \bl{$\dn$} & $?$\\
+ − 1599 % \bl{$nullable(r^{\{n..m\}})$} & \bl{$\dn$} & $?$\\
+ − 1600 % \bl{$nullable(\sim{}r)$} & \bl{$\dn$} & $?$\\
+ − 1601 %
+ − 1602 %\end{tabular}
+ − 1603 %\end{center}
+ − 1604 %
+ − 1605 %\end{frame}
+ − 1606 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1607
+ − 1608 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1609 %\begin{frame}[c]
+ − 1610 %%%\frametitle{Coursework: der}
+ − 1611 %
+ − 1612 %\begin{center}
+ − 1613 %\begin{tabular}{@ {}l@ {\hspace{1mm}}c@ {\hspace{1mm}}l@ {}}
+ − 1614 % \bl{$der\, c\, ([c_1 c_2 \ldots c_n])$} & \bl{$\dn$} & $?$\\
+ − 1615 % \bl{$der\, c\, (r^+)$} & \bl{$\dn$} & $?$\\
+ − 1616 % \bl{$der\, c\, (r^?)$} & \bl{$\dn$} & $?$\\
+ − 1617 % \bl{$der\, c\, (r^{\{n\}})$} & \bl{$\dn$} &
+ − 1618 % \bl{$if\;n=0\;then\;\ZERO\;else\;(der\,c\,r)\cdot r^{\{n-\liningnums{1}\}}$}\\
+ − 1619 % \bl{$der\, c\, (r^{\{n..\}})$} & \bl{$\dn$} &
+ − 1620 % \bl{$if\;n=0\;then (der\,c\,r)\cdot r^*$}\\
+ − 1621 % & & \bl{$\phantom{if\;n=0\;}else \;(der\,c\,r)\cdot r^{\{n-\liningnums{1}..\}}$}\\
+ − 1622 % \bl{$der\, c\, (r^{\{..n\}})$} & \bl{$\dn$} &
+ − 1623 % \bl{$if\;n=0\;then\;\ZERO\;else\;(der\,c\,r)\cdot r^{\{..n-\liningnums{1}\}}$}\\
+ − 1624 %
+ − 1625 % \bl{$der\, c\, (r^{\{n..m\}})$} & \bl{$\dn$} &
+ − 1626 % \bl{$if\;n = 0 \wedge m = 0\;then\;\ZERO\; else$}\\
+ − 1627 % \multicolumn{3}{l}{\bl{$if\;n = 0 \wedge m > 0\;then\;(der\,c\,r)\cdot r^{\{..m-\liningnums{1}\}}$}}\\
+ − 1628 % \multicolumn{3}{l}{\bl{$\phantom{if\;n = 0 \wedge m > 0\;}else
+ − 1629 % \;(der\,c\,r)\cdot r^{\{n-\liningnums{1}..m-\liningnums{1}\}}$}}\\
+ − 1630 % \bl{$der\, c\, (\sim{}r)$} & \bl{$\dn$} & $?$\\
+ − 1631 %\end{tabular}
+ − 1632 %\end{center}
+ − 1633 %
+ − 1634 %\end{frame}
+ − 1635 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1636
+ − 1637 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ − 1638 %\begin{frame}[c]
+ − 1639 %\frametitle{Coursework: CFUN}
+ − 1640 %
+ − 1641 %\begin{center}
+ − 1642 %\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
+ − 1643 % \bl{$nullable(CFUN(\_))$} & \bl{$\dn$} & \bl{$false$}\\
+ − 1644 % \bl{$der\,c\,(CFUN(f))$} & \bl{$\dn$} &
+ − 1645 % \bl{$if\;f(c)\;then\;\ONE\;else\;\ZERO$}\bigskip\\
+ − 1646 % \bl{$CHAR(c)$} & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;c=d)$}\\
+ − 1647 % \bl{$CSET([c_1,\ldots,c_n])$} & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;d\in [c_1,\ldots,c_n])$}\\
+ − 1648 % \bl{$ALL$} & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;true)$}\\
+ − 1649 %\end{tabular}
+ − 1650 %\end{center}
+ − 1651 %
+ − 1652 %\end{frame}
+ − 1653 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
788
+ − 1654
+ − 1655 \begin{frame}[t]
+ − 1656 \begin{mybox3}{}
+ − 1657 Are dfas completed by definition as in do they have a to have transitions
+ − 1658 for every char at every state?
+ − 1659 \end{mybox3}
+ − 1660 \end{frame}
+ − 1661
+ − 1662 \begin{frame}[t]
+ − 1663 \begin{mybox3}{}
+ − 1664 How can you tell if a language will be regular or irregular?
+ − 1665 \end{mybox3}
+ − 1666 \end{frame}
+ − 1667
+ − 1668 \begin{frame}<1-12>[c]
+ − 1669 \end{frame}
+ − 1670
+ − 1671 \begin{frame}[c]
+ − 1672 \small
+ − 1673 \begin{itemize}
+ − 1674 \item[$\bullet$] contentwise probably the most enjoyable module I have had so far at KCL
+ − 1675
+ − 1676 \item[$\bullet$] I personally found the coursework sheets a bit unclear. For example I couldnt see what was required from the CFUN section but once explained it actually was very easy and didnt take long to get working
+ − 1677
+ − 1678 \item[$\bullet$] Please can tutorial sessions be recorded \& linked on Keats.
+ − 1679
+ − 1680 \item[$\bullet$] One of the best taught modules I've had, with a genuinely interested and engaging lecturer. Thanks Dr.~Urban!
+ − 1681 \end{itemize}
+ − 1682 \end{frame}
+ − 1683
+ − 1684 \begin{frame}[c]
+ − 1685 \small
+ − 1686 \begin{itemize}
+ − 1687 \item[$\bullet$] Dr.~Urban is honestly a great lecturer, he's incredibly helpful and responsive. He also teaches at a very good pace and explains things clearly so students who sometimes struggle with the content like myself can keep up. It's a pleasure to learn from him.
+ − 1688
+ − 1689 \item[$\bullet$] I just wish the Coursework content was explained better, in such a way that allows students to get on with the coursework as soon as possible.
+ − 1690
+ − 1691 \item[$\bullet$] I'm thoroughly enjoying the module so far. I find that the handouts and homework really solidify my knowledge and the feedback is extremely useful. I enjoy doing the homework and then using the feedback alongside the workshop to correct where I have gone wrong.
+ − 1692
+ − 1693 \item[$\bullet$] I enjoy this module and think it is taught well. The homework is very useful.
+ − 1694 \end{itemize}
+ − 1695 \end{frame}
+ − 1696
+ − 1697 \begin{frame}[c]
+ − 1698 \begin{center}
+ − 1699 \begin{tabular}{cc}
+ − 1700 \includegraphics[scale=0.3]{s1.png} &
+ − 1701 \includegraphics[scale=0.3]{s2.png} \\
+ − 1702 \includegraphics[scale=0.3]{s3.png} &
+ − 1703 \includegraphics[scale=0.3]{s4.png} \\
+ − 1704 \end{tabular}
+ − 1705 \end{center}
+ − 1706 \end{frame}
+ − 1707
+ − 1708 \begin{frame}[c]
+ − 1709 \begin{center}
+ − 1710 \begin{tabular}{cc}
+ − 1711 \includegraphics[scale=0.3]{s5.png} &
+ − 1712 \includegraphics[scale=0.3]{s6.png} \\
+ − 1713 \includegraphics[scale=0.3]{s7.png} &
+ − 1714 \includegraphics[scale=0.3]{s8.png} \\
+ − 1715 \end{tabular}
+ − 1716 \end{center}
+ − 1717 \end{frame}
+ − 1718
+ − 1719 \begin{frame}[c]
+ − 1720 \begin{center}
+ − 1721 \begin{tabular}{cc}
+ − 1722 \includegraphics[scale=0.3]{s9.png}
+ − 1723 \end{tabular}
+ − 1724 \end{center}
+ − 1725 \end{frame}
743
+ − 1726
33
+ − 1727 \end{document}
+ − 1728
+ − 1729 %%% Local Variables:
+ − 1730 %%% mode: latex
+ − 1731 %%% TeX-master: t
+ − 1732 %%% End:
+ − 1733