|
1 \documentclass[dvipsnames,14pt,t]{beamer} |
|
2 \usepackage{beamerthemeplainculight} |
|
3 \usepackage[T1]{fontenc} |
|
4 \usepackage[latin1]{inputenc} |
|
5 \usepackage{mathpartir} |
|
6 \usepackage[absolute,overlay]{textpos} |
|
7 \usepackage{ifthen} |
|
8 \usepackage{tikz} |
|
9 \usepackage{pgf} |
|
10 \usepackage{calc} |
|
11 \usepackage{ulem} |
|
12 \usepackage{courier} |
|
13 \usepackage{listings} |
|
14 \renewcommand{\uline}[1]{#1} |
|
15 \usetikzlibrary{arrows} |
|
16 \usetikzlibrary{automata} |
|
17 \usetikzlibrary{shapes} |
|
18 \usetikzlibrary{shadows} |
|
19 \usetikzlibrary{positioning} |
|
20 \usetikzlibrary{calc} |
|
21 \usepackage{graphicx} |
|
22 |
|
23 \definecolor{javared}{rgb}{0.6,0,0} % for strings |
|
24 \definecolor{javagreen}{rgb}{0.25,0.5,0.35} % comments |
|
25 \definecolor{javapurple}{rgb}{0.5,0,0.35} % keywords |
|
26 \definecolor{javadocblue}{rgb}{0.25,0.35,0.75} % javadoc |
|
27 |
|
28 \lstset{language=Java, |
|
29 basicstyle=\ttfamily, |
|
30 keywordstyle=\color{javapurple}\bfseries, |
|
31 stringstyle=\color{javagreen}, |
|
32 commentstyle=\color{javagreen}, |
|
33 morecomment=[s][\color{javadocblue}]{/**}{*/}, |
|
34 numbers=left, |
|
35 numberstyle=\tiny\color{black}, |
|
36 stepnumber=1, |
|
37 numbersep=10pt, |
|
38 tabsize=2, |
|
39 showspaces=false, |
|
40 showstringspaces=false} |
|
41 |
|
42 \lstdefinelanguage{scala}{ |
|
43 morekeywords={abstract,case,catch,class,def,% |
|
44 do,else,extends,false,final,finally,% |
|
45 for,if,implicit,import,match,mixin,% |
|
46 new,null,object,override,package,% |
|
47 private,protected,requires,return,sealed,% |
|
48 super,this,throw,trait,true,try,% |
|
49 type,val,var,while,with,yield}, |
|
50 otherkeywords={=>,<-,<\%,<:,>:,\#,@}, |
|
51 sensitive=true, |
|
52 morecomment=[l]{//}, |
|
53 morecomment=[n]{/*}{*/}, |
|
54 morestring=[b]", |
|
55 morestring=[b]', |
|
56 morestring=[b]""" |
|
57 } |
|
58 |
|
59 \lstset{language=Scala, |
|
60 basicstyle=\ttfamily, |
|
61 keywordstyle=\color{javapurple}\bfseries, |
|
62 stringstyle=\color{javagreen}, |
|
63 commentstyle=\color{javagreen}, |
|
64 morecomment=[s][\color{javadocblue}]{/**}{*/}, |
|
65 numbers=left, |
|
66 numberstyle=\tiny\color{black}, |
|
67 stepnumber=1, |
|
68 numbersep=10pt, |
|
69 tabsize=2, |
|
70 showspaces=false, |
|
71 showstringspaces=false} |
|
72 |
|
73 % beamer stuff |
|
74 \renewcommand{\slidecaption}{AFL 01, King's College London, 26.~September 2012} |
|
75 |
|
76 |
|
77 \begin{document} |
|
78 |
|
79 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
80 \mode<presentation>{ |
|
81 \begin{frame}<1>[t] |
|
82 \frametitle{% |
|
83 \begin{tabular}{@ {}c@ {}} |
|
84 \\[-3mm] |
|
85 \LARGE Automata and \\[-2mm] |
|
86 \LARGE Formal Languages (1)\\[-3mm] |
|
87 \end{tabular}} |
|
88 |
|
89 \begin{center} |
|
90 \includegraphics[scale=0.3]{pics/ante1.jpg}\hspace{5mm} |
|
91 \includegraphics[scale=0.31]{pics/ante2.jpg}\\ |
|
92 \footnotesize\textcolor{gray}{Antikythera automaton, 100 BC (Archimedes?)} |
|
93 \end{center} |
|
94 |
|
95 \normalsize |
|
96 \begin{center} |
|
97 \begin{tabular}{ll} |
|
98 Email: & christian.urban at kcl.ac.uk\\ |
|
99 Of$\!$fice: & S1.27 (1st floor Strand Building)\\ |
|
100 Slides: & KEATS |
|
101 \end{tabular} |
|
102 \end{center} |
|
103 |
|
104 |
|
105 \end{frame}} |
|
106 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
107 |
|
108 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
109 \mode<presentation>{ |
|
110 \begin{frame}[c] |
|
111 |
|
112 \begin{textblock}{1}(2,5) |
|
113 \begin{tabular}{c} |
|
114 \includegraphics[scale=0.15]{pics/servers.png}\\[-2mm] |
|
115 \small Server |
|
116 \end{tabular} |
|
117 \end{textblock} |
|
118 |
|
119 \begin{textblock}{1}(5.6,4) |
|
120 \begin{tikzpicture}[scale=1.1] |
|
121 \draw[white] (0,1) node (X) {}; |
|
122 \draw[white] (2,1) node (Y) {}; |
|
123 \draw[white] (0,0) node (X1) {}; |
|
124 \draw[white] (2,0) node (Y1) {}; |
|
125 \draw[white] (0,-1) node (X2) {}; |
|
126 \draw[white] (2,-1) node (Y2) {}; |
|
127 \draw[red, <-, line width = 2mm] (X) -- (Y); |
|
128 \node [inner sep=5pt,label=above:\textcolor{black}{GET request}] at ($ (X)!.5!(Y) $) {}; |
|
129 \draw[red, ->, line width = 2mm] (X1) -- (Y1); |
|
130 \node [inner sep=5pt,label=above:\textcolor{black}{webpage}] at ($ (X1)!.5!(Y1) $) {}; |
|
131 \draw[red, <-, line width = 2mm] (X2) -- (Y2); |
|
132 \node [inner sep=7pt,label=above:\textcolor{black}{POST data}] at ($ (X2)!.5!(Y2) $) {}; |
|
133 \end{tikzpicture} |
|
134 \end{textblock} |
|
135 |
|
136 |
|
137 \begin{textblock}{1}(9,5.5) |
|
138 \begin{tabular}{c} |
|
139 \includegraphics[scale=0.15]{pics/laptop.png}\\[-2mm] |
|
140 \small Browser |
|
141 \end{tabular} |
|
142 \end{textblock} |
|
143 |
|
144 \only<2>{ |
|
145 \begin{textblock}{10}(2,13.5) |
|
146 \begin{itemize} |
|
147 \item programming languages, compilers |
|
148 \end{itemize} |
|
149 \end{textblock}} |
|
150 |
|
151 |
|
152 \end{frame}} |
|
153 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
154 |
|
155 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
156 \mode<presentation>{ |
|
157 \begin{frame}[c] |
|
158 |
|
159 transforming strings into structured data\\[10mm] |
|
160 |
|
161 {\LARGE\bf Lexing}\medskip\\ |
|
162 \hspace{5mm}(recognising ``words'')\\[6mm] |
|
163 |
|
164 {\LARGE\bf Parsing}\medskip\\ |
|
165 \hspace{5mm}(recognising ``sentences'') |
|
166 |
|
167 \end{frame}} |
|
168 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
169 |
|
170 |
|
171 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
172 \mode<presentation>{ |
|
173 \begin{frame}[c] |
|
174 |
|
175 The subject is quite old: |
|
176 |
|
177 \begin{itemize} |
|
178 \item Turing Machines, 1936 |
|
179 \item first compiler for COBOL, 1957 (Grace Hopper) |
|
180 \item but surprisingly research papers are still published now |
|
181 \end{itemize} |
|
182 |
|
183 \begin{flushright} |
|
184 \includegraphics[scale=0.3]{pics/hopper.jpg}\\ |
|
185 \footnotesize\textcolor{gray}{Grace Hopper} |
|
186 \end{flushright} |
|
187 |
|
188 {\footnotesize\textcolor{gray}{(she made it to David Letterman's Tonight Show, \url{http://www.youtube.com/watch?v=aZOxtURhfEU})}} |
|
189 |
|
190 \end{frame}} |
|
191 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
192 |
|
193 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
194 \mode<presentation>{ |
|
195 \begin{frame}[c] |
|
196 \frametitle{\begin{tabular}{c}This Course\end{tabular}} |
|
197 |
|
198 \begin{itemize} |
|
199 \item the ultimate goal is to implement a small web-browser (really small one)\bigskip |
|
200 \end{itemize} |
|
201 |
|
202 Let's start with: |
|
203 |
|
204 \begin{itemize} |
|
205 \item a web-crawler |
|
206 \item an email harvester |
|
207 \item a web-scraper |
|
208 \end{itemize} |
|
209 |
|
210 \end{frame}} |
|
211 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
212 |
|
213 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
214 \mode<presentation>{ |
|
215 \begin{frame}[t] |
|
216 \frametitle{\begin{tabular}{c}A Web Crawler\end{tabular}} |
|
217 |
|
218 \mbox{}\\[10mm] |
|
219 |
|
220 \begin{enumerate} |
|
221 \item given an URL, read the corresponding webpage |
|
222 \item extract all links from it |
|
223 \item call the web-crawler again for all these links |
|
224 \end{enumerate} |
|
225 |
|
226 \end{frame}} |
|
227 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
228 |
|
229 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
230 \mode<presentation>{ |
|
231 \begin{frame}[t] |
|
232 \frametitle{\begin{tabular}{c}A Web Crawler\end{tabular}} |
|
233 |
|
234 \mbox{}\\[10mm] |
|
235 |
|
236 |
|
237 \begin{enumerate} |
|
238 \item given an URL, read the corresponding webpage |
|
239 \item if not possible print, out a problem |
|
240 \item if possible, extract all links from it |
|
241 \item call the web-crawler again for all these links |
|
242 \end{enumerate}\bigskip\pause |
|
243 |
|
244 \small (we need a bound for the number of recursive calls) |
|
245 |
|
246 \small (the purpose is to check all links on my own webpage) |
|
247 \end{frame}} |
|
248 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
249 |
|
250 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
251 \mode<presentation>{ |
|
252 \begin{frame}[c] |
|
253 \frametitle{\begin{tabular}{c}Scala\end{tabular}} |
|
254 |
|
255 \footnotesize a simple Scala function for reading webpages\\[-3mm] |
|
256 |
|
257 {\lstset{language=Scala}\fontsize{8}{10}\selectfont |
|
258 \texttt{\lstinputlisting{app0.scala}}}\pause |
|
259 {\lstset{language=Scala}\fontsize{8}{10}\selectfont |
|
260 \texttt{\lstinline{get_page("""http://www.inf.kcl.ac.uk/staff/urbanc/""")}}}\pause\bigskip |
|
261 |
|
262 |
|
263 \footnotesize slightly more complicated for handling errors properly:\\[-3mm] |
|
264 |
|
265 \footnotesize |
|
266 {\lstset{language=Scala}\fontsize{8}{10}\selectfont |
|
267 \texttt{\lstinputlisting{app1.scala}}} |
|
268 |
|
269 |
|
270 \end{frame}} |
|
271 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
272 |
|
273 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
274 \mode<presentation>{ |
|
275 \begin{frame}[t] |
|
276 \frametitle{\begin{tabular}{c}A Regular Expression\end{tabular}} |
|
277 |
|
278 \begin{itemize} |
|
279 \item \ldots{} is a pattern or template for specifying strings |
|
280 \end{itemize}\bigskip |
|
281 |
|
282 \begin{center} |
|
283 \only<1>{{\lstset{language=Scala}\fontsize{18}{19}\selectfont\bf |
|
284 \texttt{"https?://[$\hat{\hspace{2mm}}$"]*"}}}% |
|
285 \only<2>{{\lstset{language=Scala}\fontsize{18}{19}\selectfont\bf |
|
286 \texttt{"""\textbackslash{}"https?://[$\hat{\hspace{2mm}}$\textbackslash{}"]*\textbackslash{}"""".r}}} |
|
287 \end{center}\bigskip\bigskip |
|
288 |
|
289 matches for example\\ |
|
290 \;{\lstset{language=Scala}\fontsize{12}{14}\selectfont\bf |
|
291 \texttt{"http://www.foobar.com"}}\\ |
|
292 \;{\lstset{language=Scala}\fontsize{12}{14}\selectfont\bf |
|
293 \texttt{"https://www.tls.org"}}\\ |
|
294 |
|
295 \end{frame}} |
|
296 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
297 |
|
298 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
299 \mode<presentation>{ |
|
300 \begin{frame}[c] |
|
301 |
|
302 {\lstset{language=Scala}\fontsize{18}{19}\selectfont\bf |
|
303 \texttt{rexp.findAllIn(string)}}\medskip |
|
304 |
|
305 returns a list of all (sub)strings that match the regular expression\bigskip\bigskip |
|
306 |
|
307 {\lstset{language=Scala}\fontsize{18}{19}\selectfont\bf |
|
308 \texttt{rexp.findFirstIn(string)}}\medskip |
|
309 |
|
310 returns either {\bf\texttt{None}} if no (sub)string matches |
|
311 or {\bf\texttt{Some(s)}} with the first (sub)string |
|
312 |
|
313 \end{frame}} |
|
314 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
315 |
|
316 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
317 \mode<presentation>{ |
|
318 \begin{frame}[c] |
|
319 |
|
320 {\lstset{language=Scala}\fontsize{8}{10}\selectfont |
|
321 \texttt{\lstinputlisting{app2.scala}}}\medskip |
|
322 |
|
323 {\lstset{language=Scala}\fontsize{8}{10}\selectfont |
|
324 \texttt{crawl(some\_start\_URL, 2)}}\ |
|
325 |
|
326 \end{frame}} |
|
327 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
328 |
|
329 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
330 \mode<presentation>{ |
|
331 \begin{frame}[c] |
|
332 |
|
333 \footnotesize |
|
334 a version that only ``crawls'' links in my domain: |
|
335 |
|
336 {\lstset{language=Scala}\fontsize{8}{10}\selectfont |
|
337 \texttt{\lstinputlisting{app3.scala}}} |
|
338 |
|
339 |
|
340 \end{frame}} |
|
341 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
342 |
|
343 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
344 \mode<presentation>{ |
|
345 \begin{frame}[c] |
|
346 |
|
347 \footnotesize |
|
348 a little email ``harvester'': |
|
349 |
|
350 {\lstset{language=Scala}\fontsize{8}{10}\selectfont |
|
351 \texttt{\lstinputlisting{app4.scala}}}\bigskip |
|
352 |
|
353 \tiny |
|
354 \textcolor{gray}{\url{http://net.tutsplus.com/tutorials/other/8-regular-expressions-you-should-know/}} |
|
355 |
|
356 \end{frame}} |
|
357 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
358 |
|
359 \newcommand{\bl}[1]{\textcolor{blue}{#1}} |
|
360 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
361 \mode<presentation>{ |
|
362 \begin{frame}[c] |
|
363 \frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}} |
|
364 |
|
365 \begin{textblock}{6}(2,4) |
|
366 \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l} |
|
367 \bl{r} & \bl{$::=$} & \bl{$\varnothing$} & null\\ |
|
368 & \bl{$\mid$} & \bl{$\epsilon$} & empty string / "" / []\\ |
|
369 & \bl{$\mid$} & \bl{c} & character\\ |
|
370 & \bl{$\mid$} & \bl{r$_1$ $\cdot$ r$_2$} & sequence\\ |
|
371 & \bl{$\mid$} & \bl{r$_1$ + r$_2$} & alternative / choice\\ |
|
372 & \bl{$\mid$} & \bl{r$^*$} & star (zero or more)\\ |
|
373 \end{tabular} |
|
374 \end{textblock} |
|
375 |
|
376 \end{frame}} |
|
377 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
378 |
|
379 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
380 \mode<presentation>{ |
|
381 \begin{frame}[t] |
|
382 \frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}} |
|
383 |
|
384 {\lstset{language=Scala}\fontsize{8}{10}\selectfont |
|
385 \texttt{\lstinputlisting{app51.scala}}} |
|
386 |
|
387 |
|
388 \end{frame}} |
|
389 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
390 |
|
391 \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions |
|
392 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
393 \mode<presentation>{ |
|
394 \begin{frame}[c] |
|
395 \frametitle{\begin{tabular}{c}The Meaning of a\\[-2mm] Regular Expression\end{tabular}} |
|
396 |
|
397 \begin{textblock}{15}(1,4) |
|
398 \begin{tabular}{@ {}rcl} |
|
399 \bl{$L$($\varnothing$)} & \bl{$\dn$} & \bl{$\varnothing$}\\ |
|
400 \bl{$L$($\epsilon$)} & \bl{$\dn$} & \bl{$\{$""$\}$}\\ |
|
401 \bl{$L$(c)} & \bl{$\dn$} & \bl{$\{$"c"$\}$}\\ |
|
402 \bl{$L$(r$_1$ + r$_2$)} & \bl{$\dn$} & \bl{$L$(r$_1$) $\cup$ $L$(r$_2$)}\\ |
|
403 \bl{$L$(r$_1$ $\cdot$ r$_2$)} & \bl{$\dn$} & \bl{$\{$ s$_1$ @ s$_2$ $|$ s$_1$ $\in$ $L$(r$_1$) $\wedge$ s$_2$ $\in$ |
|
404 $L$(r$_2$) $\}$}\\ |
|
405 \bl{$L$(r$^*$)} & \bl{$\dn$} & \onslide<4->{\bl{$\bigcup_{n \ge 0}$ $L$(r)$^n$}}\\ |
|
406 \end{tabular}\bigskip |
|
407 |
|
408 \onslide<2->{ |
|
409 \hspace{5mm}\bl{$L$(r)$^0$ $\;\dn\;$ $\{$""$\}$}\\ |
|
410 \bl{$L$(r)$^{n+1}$ $\;\dn\;$ $L$(r) @ $L$(r)$^n$}\hspace{9mm}\onslide<3->{\small\textcolor{gray}{(append on sets)}\\ |
|
411 \small\hspace{5cm}\textcolor{gray}{$\{$ s$_1$ @ s$_2$ $|$ s$_1$ $\in$ $L$(r) $\wedge$ s$_2$ $\in$ |
|
412 $L$(r)$^n$ $\}$}} |
|
413 } |
|
414 \end{textblock} |
|
415 |
|
416 \end{frame}} |
|
417 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
418 |
|
419 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
420 \mode<presentation>{ |
|
421 \begin{frame}[c] |
|
422 \frametitle{\begin{tabular}{c}The Meaning of a Matching\end{tabular}} |
|
423 |
|
424 \large |
|
425 a regular expression \bl{r} matches a string \bl{s} is defined as |
|
426 |
|
427 \begin{center} |
|
428 \bl{s $\in$ $L$(r)}\\ |
|
429 \end{center} |
|
430 |
|
431 \end{frame}} |
|
432 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
433 |
|
434 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
435 \mode<presentation>{ |
|
436 \begin{frame}[c] |
|
437 \frametitle{\begin{tabular}{c}Nullability\end{tabular}} |
|
438 |
|
439 \small |
|
440 whether a regular expression matches the empty string:\medskip |
|
441 |
|
442 |
|
443 {\lstset{language=Scala}\fontsize{8}{10}\selectfont |
|
444 \texttt{\lstinputlisting{app5.scala}}} |
|
445 |
|
446 |
|
447 |
|
448 \end{frame}} |
|
449 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
450 |
|
451 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
452 \mode<presentation>{ |
|
453 \begin{frame}[c] |
|
454 \frametitle{\begin{tabular}{c}Derivative of a Rexp\end{tabular}} |
|
455 |
|
456 \large |
|
457 If \bl{r} matches the string \bl{c::s}, what is a regular expression that matches \bl{s}?\bigskip\bigskip\bigskip\bigskip |
|
458 |
|
459 \small |
|
460 \bl{der c r} gives the answer |
|
461 \end{frame}} |
|
462 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
463 |
|
464 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
465 \mode<presentation>{ |
|
466 \begin{frame}[c] |
|
467 \frametitle{\begin{tabular}{c}The Derivative\end{tabular}} |
|
468 |
|
469 \begin{center} |
|
470 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}} |
|
471 \bl{der c ($\varnothing$)} & \bl{$\dn$} & \bl{$\varnothing$} & \\ |
|
472 \bl{der c ($\epsilon$)} & \bl{$\dn$} & \bl{$\varnothing$} & \\ |
|
473 \bl{der c (d)} & \bl{$\dn$} & \bl{if c $=$ d then [] else $\varnothing$} & \\ |
|
474 \bl{der c (r$_1$ + r$_2$)} & \bl{$\dn$} & \bl{(der c r$_1$) + (der c r$_2$)} & \\ |
|
475 \bl{der c (r$_1$ $\cdot$ r$_2$)} & \bl{$\dn$} & \bl{((der c r$_1$) $\cdot$ r$_2$) + } & \\ |
|
476 & & \bl{\hspace{3mm}(if nullable r$_1$ then der c r$_2$ else $\varnothing$)}\\ |
|
477 \bl{der c (r$^*$)} & \bl{$\dn$} & \bl{(der c r) $\cdot$ (r$^*$)} &\smallskip\\\pause |
|
478 |
|
479 \bl{ders [] r} & \bl{$\dn$} & \bl{r} & \\ |
|
480 \bl{ders (c::s) r} & \bl{$\dn$} & \bl{ders s (der c r)} & \\ |
|
481 \end{tabular} |
|
482 \end{center} |
|
483 |
|
484 \end{frame}} |
|
485 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
486 |
|
487 |
|
488 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
489 \mode<presentation>{ |
|
490 \begin{frame}[c] |
|
491 \frametitle{\begin{tabular}{c}The Derivative\end{tabular}} |
|
492 |
|
493 |
|
494 {\lstset{language=Scala}\fontsize{8}{10}\selectfont |
|
495 \texttt{\lstinputlisting{app6.scala}}} |
|
496 |
|
497 |
|
498 |
|
499 \end{frame}} |
|
500 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
501 |
|
502 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
503 \mode<presentation>{ |
|
504 \begin{frame}[c] |
|
505 \frametitle{\begin{tabular}{c}The Rexp Matcher\end{tabular}} |
|
506 |
|
507 |
|
508 {\lstset{language=Scala}\fontsize{8}{10}\selectfont |
|
509 \texttt{\lstinputlisting{app7.scala}}} |
|
510 |
|
511 |
|
512 |
|
513 \end{frame}} |
|
514 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
515 |
|
516 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
517 \mode<presentation>{ |
|
518 \begin{frame}[c] |
|
519 \frametitle{\begin{tabular}{c}This Course\end{tabular}} |
|
520 |
|
521 We will have a look at: |
|
522 |
|
523 \begin{itemize} |
|
524 \item regular expressions / regular expression matching |
|
525 \item automata |
|
526 \item the Myhill-Nerode theorem |
|
527 \item parsing |
|
528 \item grammars |
|
529 \item a small interpreter / web browser |
|
530 \end{itemize} |
|
531 |
|
532 \end{frame}} |
|
533 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
534 |
|
535 |
|
536 |
|
537 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
538 \mode<presentation>{ |
|
539 \begin{frame}[c] |
|
540 \frametitle{\begin{tabular}{c}Exam\end{tabular}} |
|
541 |
|
542 \begin{itemize} |
|
543 \item The question ``Is this relevant for the exam?'' is not appreciated!\bigskip\\ |
|
544 |
|
545 Whatever is in the homework sheets (and is not marked optional) is relevant for the |
|
546 exam.\\ No code needs to be written. |
|
547 \end{itemize} |
|
548 |
|
549 \end{frame}} |
|
550 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
551 |
|
552 |
|
553 |
|
554 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
555 \mode<presentation>{ |
|
556 \begin{frame}[t] |
|
557 \frametitle{\begin{tabular}{c}Maps in Scala\end{tabular}} |
|
558 |
|
559 \begin{itemize} |
|
560 \item {\bf\texttt{map}} takes a function, say f, and applies it to every element of the list: |
|
561 \end{itemize} |
|
562 |
|
563 \begin{textblock}{15}(2,7) |
|
564 \fontsize{13}{14}\selectfont |
|
565 \bf\texttt{List(1, 2, 3, 4, 5, 6, 7, 8, 9)} |
|
566 \end{textblock} |
|
567 |
|
568 \begin{textblock}{15}(2,10) |
|
569 \fontsize{13}{14}\selectfont |
|
570 \bf\texttt{List(1, 4, 9, 16, 25, 36, 49, 64, 81)} |
|
571 \end{textblock} |
|
572 |
|
573 \end{frame}} |
|
574 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
575 |
|
576 |
|
577 \end{document} |
|
578 |
|
579 %%% Local Variables: |
|
580 %%% mode: latex |
|
581 %%% TeX-master: t |
|
582 %%% End: |
|
583 |