363 \frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}} |
363 \frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}} |
364 |
364 |
365 \begin{textblock}{6}(2,4) |
365 \begin{textblock}{6}(2,4) |
366 \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l} |
366 \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l} |
367 \bl{r} & \bl{$::=$} & \bl{$\varnothing$} & null\\ |
367 \bl{r} & \bl{$::=$} & \bl{$\varnothing$} & null\\ |
368 & \bl{$\mid$} & \bl{$\epsilon$} & empty string / ""\\ |
368 & \bl{$\mid$} & \bl{$\epsilon$} & empty string / "" / []\\ |
369 & \bl{$\mid$} & \bl{c} & character\\ |
369 & \bl{$\mid$} & \bl{c} & character\\ |
370 & \bl{$\mid$} & \bl{r$_1$ $\cdot$ r$_2$} & sequence\\ |
370 & \bl{$\mid$} & \bl{r$_1$ $\cdot$ r$_2$} & sequence\\ |
371 & \bl{$\mid$} & \bl{r$_1$ + r$_2$} & alternative / choice\\ |
371 & \bl{$\mid$} & \bl{r$_1$ + r$_2$} & alternative / choice\\ |
372 & \bl{$\mid$} & \bl{r$^*$} & star (zero or more)\\ |
372 & \bl{$\mid$} & \bl{r$^*$} & star (zero or more)\\ |
373 \end{tabular} |
373 \end{tabular} |
400 \bl{$L$($\epsilon$)} & \bl{$\dn$} & \bl{$\{$""$\}$}\\ |
400 \bl{$L$($\epsilon$)} & \bl{$\dn$} & \bl{$\{$""$\}$}\\ |
401 \bl{$L$(c)} & \bl{$\dn$} & \bl{$\{$"c"$\}$}\\ |
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$)}\\ |
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$ |
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$) $\}$}\\ |
404 $L$(r$_2$) $\}$}\\ |
405 \bl{$L$(r$^*$)} & \bl{$\dn$} & \onslide<3>{\bl{$\bigcup_{n \ge 0}$ $L$(r)$^n$}}\\ |
405 \bl{$L$(r$^*$)} & \bl{$\dn$} & \onslide<4->{\bl{$\bigcup_{n \ge 0}$ $L$(r)$^n$}}\\ |
406 \end{tabular}\bigskip |
406 \end{tabular}\bigskip |
407 |
407 |
408 \onslide<2->{ |
408 \onslide<2->{ |
409 \hspace{5mm}\bl{$L$(r)$^0$ $\;\dn\;$ $\{$""$\}$}\\ |
409 \hspace{5mm}\bl{$L$(r)$^0$ $\;\dn\;$ $\{$""$\}$}\\ |
410 \bl{$L$(r)$^{n+1}$ $\;\dn\;$ $L$(r) @ $L$(r)$^n$}\hspace{9mm}\small\textcolor{gray}{(append on sets)}\\ |
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$_1$) $\wedge$ s$_2$ $\in$ |
411 \small\hspace{5cm}\textcolor{gray}{$\{$ s$_1$ @ s$_2$ $|$ s$_1$ $\in$ $L$(r) $\wedge$ s$_2$ $\in$ |
412 $L$(r$_2$) $\}$} |
412 $L$(r)$^n$ $\}$}} |
413 } |
413 } |
414 \end{textblock} |
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 Matcher\end{tabular}} |
|
506 |
|
507 |
|
508 {\lstset{language=Scala}\fontsize{8}{10}\selectfont |
|
509 \texttt{\lstinputlisting{app7.scala}}} |
|
510 |
|
511 |
415 |
512 |
416 \end{frame}} |
513 \end{frame}} |
417 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
514 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
418 |
515 |
419 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
516 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |