336 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
336 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
337 |
337 |
338 |
338 |
339 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
339 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
340 \begin{frame}[c] |
340 \begin{frame}[c] |
341 \frametitle{Lexing} |
341 \frametitle{Lexing: Test Case} |
342 |
342 |
343 \mbox{\lstinputlisting[language=While]{../progs/fib.while}} |
343 \mbox{\lstinputlisting[language=While]{../progs/fib.while}} |
344 |
344 |
345 \end{frame} |
345 \end{frame} |
346 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
346 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
347 |
347 |
348 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
348 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
349 \begin{frame}[c] |
349 \begin{frame}[c] |
350 \frametitle{??} |
350 \frametitle{?? Test Case} |
351 |
351 |
352 \mbox{\lstinputlisting[language=While]{../progs/collatz.while}} |
352 \mbox{\lstinputlisting[language=While]{../progs/collatz.while}} |
353 |
353 |
354 \end{frame} |
354 \end{frame} |
355 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
355 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
366 \begin{tabular}{@{}l} |
366 \begin{tabular}{@{}l} |
367 KEYWORD: \\ |
367 KEYWORD: \\ |
368 \hspace{5mm}{if}, {then}, {else},\\ |
368 \hspace{5mm}{if}, {then}, {else},\\ |
369 WHITESPACE:\\ |
369 WHITESPACE:\\ |
370 \hspace{5mm}{" "}, {$\backslash$n},\\ |
370 \hspace{5mm}{" "}, {$\backslash$n},\\ |
371 IDENT:\\ |
371 IDENTIFIER:\\ |
372 \hspace{5mm}LETTER $\cdot$ (LETTER + DIGIT + {\_})$^*$\\ |
372 \hspace{5mm}LETTER $\cdot$ (LETTER + DIGIT + {\_})$^*$\\ |
373 NUM:\\ |
373 NUM:\\ |
374 \hspace{5mm}(NONZERODIGIT $\cdot$ DIGIT$^*$) + {0}\\ |
374 \hspace{5mm}(NONZERODIGIT $\cdot$ DIGIT$^*$) + {0}\\ |
375 OP:\\ |
375 OP:\\ |
376 \hspace{5mm}{+}\\ |
376 \hspace{5mm}+, -, *, \%, <, <=\\ |
377 COMMENT:\\ |
377 COMMENT:\\ |
378 \hspace{5mm}{$\slash$*} $\cdot$ $\sim$(ALL$^*$ $\cdot$ (*$\slash$) $\cdot$ ALL$^*$) $\cdot$ {*$\slash$} |
378 \hspace{5mm}{$\slash$*} $\cdot$ $\sim$(ALL$^*$ $\cdot$ (*$\slash$) $\cdot$ ALL$^*$) $\cdot$ {*$\slash$} |
379 \end{tabular} |
379 \end{tabular} |
380 |
380 |
381 \end{frame} |
381 \end{frame} |
508 \draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};\pause |
508 \draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};\pause |
509 \node (r3) [right=of r2] {\bl{$r_3$}}; |
509 \node (r3) [right=of r2] {\bl{$r_3$}}; |
510 \draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};\pause |
510 \draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};\pause |
511 \node (r4) [right=of r3] {\bl{$r_4$}}; |
511 \node (r4) [right=of r3] {\bl{$r_4$}}; |
512 \draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};\pause |
512 \draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};\pause |
513 \draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};\pause |
513 \draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable?$}}};\pause |
514 \node (v4) [below=of r4] {\bl{$v_4$}}; |
514 \node (v4) [below=of r4] {\bl{$v_4$}}; |
515 \draw[->,line width=1mm] (r4) -- (v4);\pause |
515 \draw[->,line width=1mm] (r4) -- (v4);\pause |
516 \node (v3) [left=of v4] {\bl{$v_3$}}; |
516 \node (v3) [left=of v4] {\bl{$v_3$}}; |
517 \draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};\pause |
517 \draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};\pause |
518 \node (v2) [left=of v3] {\bl{$v_2$}}; |
518 \node (v2) [left=of v3] {\bl{$v_2$}}; |
584 |
584 |
585 Finding a (posix) value for recognising the empty string: |
585 Finding a (posix) value for recognising the empty string: |
586 |
586 |
587 \begin{center} |
587 \begin{center} |
588 \begin{tabular}{lcl} |
588 \begin{tabular}{lcl} |
589 \bl{$mkeps\,\ONE$} & \bl{$\dn$} & \bl{$Empty$}\\ |
589 \bl{$mkeps\,(\ONE)$} & \bl{$\dn$} & \bl{$Empty$}\\ |
590 \bl{$mkeps\,r_1 + r_2$} & \bl{$\dn$} & \bl{if $nullable(r_1)$} \\ |
590 \bl{$mkeps\,(r_1 + r_2)$} & \bl{$\dn$} & \bl{if $nullable(r_1)$} \\ |
591 & & \bl{then $Left(mkeps(r_1))$}\\ |
591 & & \bl{then $Left(mkeps(r_1))$}\\ |
592 & & \bl{else $Right(mkeps(r_2))$}\\ |
592 & & \bl{else $Right(mkeps(r_2))$}\\ |
593 \bl{$mkeps\,r_1 \cdot r_2$} & \bl{$\dn$} & \bl{$Seq(mkeps(r_1),mkeps(r_2))$}\\ |
593 \bl{$mkeps\,(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$Seq(mkeps(r_1),mkeps(r_2))$}\\ |
594 \bl{$mkeps\,r^*$} & \bl{$\dn$} & \bl{$[]$} \\ |
594 \bl{$mkeps\,(r^*)$} & \bl{$\dn$} & \bl{$[]$} \\ |
595 \end{tabular} |
595 \end{tabular} |
596 \end{center} |
596 \end{center} |
597 |
597 |
598 \end{frame} |
598 \end{frame} |
599 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
599 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
600 |
600 |
601 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
601 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
602 \begin{frame}[c] |
602 \begin{frame}[c] |
603 \frametitle{Inject} |
603 \frametitle{Inject} |
604 |
604 |
605 Injecting (``Adding'') a character to a value\\ |
605 Injecting (``Adding'') a character to a value\\[-12mm]\mbox{} |
606 |
606 |
607 \begin{center} |
607 \begin{center} |
608 \begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l} |
608 \begin{tabular}{@{}l@{\hspace{1mm}}c@{\hspace{1mm}}l@{}} |
609 \bl{$inj\,(c)\,c\,Empty$} & \bl{$\dn$} & \bl{$Char\,c$}\\ |
609 \bl{$inj\,(c)\,c\,Empty$} & \bl{$\dn$} & \bl{$Char\,c$}\\ |
610 \bl{$inj\,(r_1 + r_2)\,c\,Left(v)$} & \bl{$\dn$} & \bl{$Left(inj\,r_1\,c\,v)$}\\ |
610 \bl{$inj\,(r_1 + r_2)\,c\,Left(v)$} & \bl{$\dn$} & \bl{$Left(inj\,r_1\,c\,v)$}\\ |
611 \bl{$inj\,(r_1 + r_2)\,c\,Right(v)$} & \bl{$\dn$} & \bl{$Right(inj\,r_2\,c\,v)$}\\ |
611 \bl{$inj\,(r_1 + r_2)\,c\,Right(v)$} & \bl{$\dn$} & \bl{$Right(inj\,r_2\,c\,v)$}\\ |
612 \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)$}\\ |
612 \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)$}\\ |
613 \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)$}\\ |
613 \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)$}\\ |