47 \path[->,red, line width=2mm] (rexp) edge node [above=4mm, black] |
47 \path[->,red, line width=2mm] (rexp) edge node [above=4mm, black] |
48 {\begin{tabular}{c@{\hspace{9mm}}}Thompson's\\[-1mm] construction\end{tabular}} (nfa); |
48 {\begin{tabular}{c@{\hspace{9mm}}}Thompson's\\[-1mm] construction\end{tabular}} (nfa); |
49 \path[->,red, line width=2mm] (nfa) edge node [above=4mm, black] |
49 \path[->,red, line width=2mm] (nfa) edge node [above=4mm, black] |
50 {\begin{tabular}{c}subset\\[-1mm] construction\end{tabular}}(dfa); |
50 {\begin{tabular}{c}subset\\[-1mm] construction\end{tabular}}(dfa); |
51 \path[->, red, line width=2mm] (dfa) edge node [below=5mm, black] {minimisation} (mdfa); |
51 \path[->, red, line width=2mm] (dfa) edge node [below=5mm, black] {minimisation} (mdfa); |
52 \path[->, red, line width=2mm] (dfa) edge [bend left=45] (rexp); |
52 %%\path[->, red, line width=2mm] (dfa) edge [bend left=45] (rexp); |
|
53 \path[->, red, line width=2mm] (dfa) edge [bend left=45] node [below, black] {\begin{tabular}{l}Brzozowski's\\ method\end{tabular}} (rexp); |
|
54 |
53 \end{tikzpicture}\\ |
55 \end{tikzpicture}\\ |
54 \end{center} |
56 \end{center} |
55 |
57 |
56 \end{frame} |
58 \end{frame} |
57 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
59 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
58 |
60 |
59 |
61 |
60 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
62 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
61 \mode<presentation>{ |
|
62 \begin{frame}[t] |
63 \begin{frame}[t] |
63 \frametitle{\bl{$(a?\{n\}) \cdot a\{n\}$}} |
64 \frametitle{\bl{$a^?^{\{n\}} \cdot a^{\{n\}}$}} |
64 |
65 |
65 \begin{tikzpicture} |
66 \begin{tikzpicture} |
66 \begin{axis}[xlabel={\pcode{a}s},ylabel={time in secs}, |
67 \begin{axis}[xlabel={\pcode{a}s},ylabel={time in secs}, |
67 enlargelimits=false, |
68 enlargelimits=false, |
68 xtick={0,5,...,30}, |
69 xtick={0,5,...,30}, |
142 \end{center} |
140 \end{center} |
143 are marked. If yes, then also mark \bl{$(q, p)$}. |
141 are marked. If yes, then also mark \bl{$(q, p)$}. |
144 \item Repeat last step until no change. |
142 \item Repeat last step until no change. |
145 \item All unmarked pairs can be merged. |
143 \item All unmarked pairs can be merged. |
146 \end{enumerate} |
144 \end{enumerate} |
147 |
|
148 \end{frame}} |
|
149 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
150 |
|
151 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
152 \begin{frame}[c] |
|
153 |
|
154 \begin{center} |
|
155 \begin{tikzpicture}[>=stealth',very thick,auto, |
|
156 every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] |
|
157 \node[state,initial] (q_0) {$q_0$}; |
|
158 \node[state] (q_1) [right=of q_0] {$q_1$}; |
|
159 \node[state] (q_2) [below right=of q_0] {$q_2$}; |
|
160 \node[state] (q_3) [right=of q_2] {$q_3$}; |
|
161 \node[state, accepting] (q_4) [right=of q_1] {$q_4$}; |
|
162 \path[->] (q_0) edge node [above] {\alert{$a$}} (q_1); |
|
163 \path[->] (q_1) edge node [above] {\alert{$a$}} (q_4); |
|
164 \path[->] (q_4) edge [loop right] node {\alert{$a, b$}} (); |
|
165 \path[->] (q_3) edge node [right] {\alert{$a$}} (q_4); |
|
166 \path[->] (q_2) edge node [above] {\alert{$a$}} (q_3); |
|
167 \path[->] (q_1) edge node [right] {\alert{$b$}} (q_2); |
|
168 \path[->] (q_0) edge node [above] {\alert{$b$}} (q_2); |
|
169 \path[->] (q_2) edge [loop left] node {\alert{$b$}} (); |
|
170 \path[->] (q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (q_0); |
|
171 \end{tikzpicture} |
|
172 \end{center} |
|
173 |
|
174 \mbox{}\\[-20mm]\mbox{} |
|
175 |
|
176 \begin{center} |
|
177 \begin{tikzpicture}[scale=0.8,line width=0.8mm] |
|
178 \draw (0,0) -- (4,0); |
|
179 \draw (0,1) -- (4,1); |
|
180 \draw (0,2) -- (3,2); |
|
181 \draw (0,3) -- (2,3); |
|
182 \draw (0,4) -- (1,4); |
|
183 |
|
184 \draw (0,0) -- (0, 4); |
|
185 \draw (1,0) -- (1, 4); |
|
186 \draw (2,0) -- (2, 3); |
|
187 \draw (3,0) -- (3, 2); |
|
188 \draw (4,0) -- (4, 1); |
|
189 |
|
190 \draw (0.5,-0.5) node {$q_0$}; |
|
191 \draw (1.5,-0.5) node {$q_1$}; |
|
192 \draw (2.5,-0.5) node {$q_2$}; |
|
193 \draw (3.5,-0.5) node {$q_3$}; |
|
194 |
|
195 \draw (-0.5, 3.5) node {$q_1$}; |
|
196 \draw (-0.5, 2.5) node {$q_2$}; |
|
197 \draw (-0.5, 1.5) node {$q_3$}; |
|
198 \draw (-0.5, 0.5) node {$q_4$}; |
|
199 |
|
200 \draw (0.5,0.5) node {\large$\star$}; |
|
201 \draw (1.5,0.5) node {\large$\star$}; |
|
202 \draw (2.5,0.5) node {\large$\star$}; |
|
203 \draw (3.5,0.5) node {\large$\star$}; |
|
204 \end{tikzpicture} |
|
205 \end{center} |
|
206 |
145 |
207 \end{frame} |
146 \end{frame} |
208 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
147 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
209 |
148 |
210 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
149 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
286 \end{frame} |
225 \end{frame} |
287 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
226 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
288 |
227 |
289 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
228 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
290 \begin{frame}[c] |
229 \begin{frame}[c] |
291 \frametitle{Alternatives} |
|
292 \mbox{}\\[-17mm]\mbox{} |
|
293 |
|
294 \begin{center} |
|
295 \begin{tikzpicture}[>=stealth',very thick,auto, |
|
296 every state/.style={minimum size=0pt, |
|
297 inner sep=2pt,draw=blue!50,very thick,fill=blue!20}] |
|
298 \only<1>{\node[state,initial] (q_0) {$q_0$};} |
|
299 \only<2->{\node[state,accepting] (q_0) {$q_0$};} |
|
300 \node[state] (q_1) [right=of q_0] {$q_1$}; |
|
301 \node[state] (q_2) [below right=of q_0] {$q_2$}; |
|
302 \node[state] (q_3) [right=of q_2] {$q_3$}; |
|
303 \only<1>{\node[state, accepting] (q_4) [right=of q_1] {$q_4$};} |
|
304 \only<2->{\node[state, initial right] (q_4) [right=of q_1] {$q_4$};} |
|
305 \only<1-2>{ |
|
306 \path[->] (q_0) edge node [above] {\alert{$a$}} (q_1); |
|
307 \path[->] (q_1) edge node [above] {\alert{$a$}} (q_4); |
|
308 \path[->] (q_4) edge [loop above] node {\alert{$a, b$}} (); |
|
309 \path[->] (q_3) edge node [right] {\alert{$a$}} (q_4); |
|
310 \path[->] (q_2) edge node [above] {\alert{$a$}} (q_3); |
|
311 \path[->] (q_1) edge node [right] {\alert{$b$}} (q_2); |
|
312 \path[->] (q_0) edge node [above] {\alert{$b$}} (q_2); |
|
313 \path[->] (q_2) edge [loop left] node {\alert{$b$}} (); |
|
314 \path[->] (q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (q_0);} |
|
315 \only<3->{ |
|
316 \path[<-] (q_0) edge node [above] {\alert{$a$}} (q_1); |
|
317 \path[<-] (q_1) edge node [above] {\alert{$a$}} (q_4); |
|
318 \path[<-] (q_4) edge [loop above] node {\alert{$a, b$}} (); |
|
319 \path[<-] (q_3) edge node [right] {\alert{$a$}} (q_4); |
|
320 \path[<-] (q_2) edge node [above] {\alert{$a$}} (q_3); |
|
321 \path[<-] (q_1) edge node [right] {\alert{$b$}} (q_2); |
|
322 \path[<-] (q_0) edge node [above] {\alert{$b$}} (q_2); |
|
323 \path[<-] (q_2) edge [loop left] node {\alert{$b$}} (); |
|
324 \path[<-] (q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (q_0);} |
|
325 \end{tikzpicture} |
|
326 \end{center} |
|
327 \mbox{}\\[-18mm] |
|
328 |
|
329 \begin{itemize} |
|
330 \item<2-> exchange initial / accepting states |
|
331 \item<3-> reverse all edges |
|
332 \item<4-> subset construction $\Rightarrow$ DFA |
|
333 \item<5-> repeat once more \onslide<6->{$\Rightarrow$ minimal DFA} |
|
334 \end{itemize} |
|
335 |
|
336 \end{frame} |
|
337 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
338 |
|
339 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
340 \begin{frame}[c] |
|
341 \frametitle{Regular Languages} |
230 \frametitle{Regular Languages} |
342 |
231 |
343 Two equivalent definitions:\bigskip |
232 Two equivalent definitions:\bigskip |
344 |
233 |
345 \begin{quote}\rm A language is \alert{regular} iff there exists a |
234 \begin{quote}\rm A language is \alert{regular} iff there exists a |
380 (q2) edge [loop right] node {\alert{$a$}} () |
269 (q2) edge [loop right] node {\alert{$a$}} () |
381 (q0) edge [loop below] node {\alert{$b$}} (); |
270 (q0) edge [loop below] node {\alert{$b$}} (); |
382 \end{tikzpicture} |
271 \end{tikzpicture} |
383 \end{center}\bigskip\bigskip |
272 \end{center}\bigskip\bigskip |
384 |
273 |
385 \onslide<2>{But requires that the automaton is \alert{completed}!} |
274 But requires that the automaton is \alert{completed}! |
386 |
275 |
387 \end{frame} |
276 \end{frame} |
388 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
277 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
389 |
278 |
390 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
279 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
391 \begin{frame}[c] |
280 \begin{frame}[c] |
|
281 \frametitle{The Goal of this Course} |
|
282 \mbox{}\\[-26mm]\mbox{} |
|
283 |
|
284 \begin{center} |
|
285 \begin{tikzpicture}[scale=1, |
|
286 node/.style={ |
|
287 rectangle,rounded corners=3mm, |
|
288 very thick,draw=black!50, |
|
289 minimum height=18mm, minimum width=20mm, |
|
290 top color=white,bottom color=black!20}] |
|
291 |
|
292 \node at (3.05, 1.8) {\Large\bf Write A Compiler}; |
|
293 |
|
294 \node (0) at (-2.3,0) {}; |
|
295 |
|
296 \node (A) at (0,0) [node] {}; |
|
297 \node [below right] at (A.north west) {lexer}; |
|
298 |
|
299 \node (B) at (3,0) [node] {}; |
|
300 \node [below right=1mm] at (B.north west) |
|
301 {\mbox{}\hspace{-1mm}parser}; |
|
302 |
|
303 \node (C) at (6,0) [node] {}; |
|
304 \node [below right] at (C.north west) |
|
305 {\mbox{}\hspace{-1mm}code gen}; |
|
306 |
|
307 \node (1) at (8.4,0) {}; |
|
308 |
|
309 \draw [->,line width=4mm] (0) -- (A); |
|
310 \draw [->,line width=4mm] (A) -- (B); |
|
311 \draw [->,line width=4mm] (B) -- (C); |
|
312 \draw [->,line width=4mm] (C) -- (1); |
|
313 \end{tikzpicture} |
|
314 \end{center} |
|
315 |
|
316 Today a lexer. |
|
317 |
|
318 \end{frame} |
|
319 |
|
320 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
321 \begin{frame}[c] |
|
322 \frametitle{Survey: Thanks!} |
|
323 \small |
|
324 |
|
325 \begin{itemize} |
|
326 \item {\bf My Voice} ``lecturer speaks in a low voice and |
|
327 is hard to hear him'' ``please use mic'' ``please use mic |
|
328 \& lecture recording'' |
|
329 \item {\bf Pace} ``faster pace'' ``a bit quick for me |
|
330 personally'' |
|
331 \item {\bf Recording} ``please use recording class'' |
|
332 \item {\bf Module Name} ``misleading'' |
|
333 \item {\bf Examples} ``more examples'' |
|
334 \item {\bf Assessment} ``really appreciate extension of |
|
335 first coursework'' |
|
336 \end{itemize} |
|
337 |
|
338 \end{frame} |
|
339 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
340 |
|
341 |
|
342 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
343 \begin{frame}[c] |
|
344 \frametitle{Lexing} |
392 |
345 |
393 \mbox{\lstinputlisting[language=While]{../progs/fib.while}} |
346 \mbox{\lstinputlisting[language=While]{../progs/fib.while}} |
394 |
347 |
395 \end{frame} |
348 \end{frame} |
396 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
349 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
401 |
354 |
402 \mbox{\lstinputlisting[language=While]{../progs/collatz.while}} |
355 \mbox{\lstinputlisting[language=While]{../progs/collatz.while}} |
403 |
356 |
404 \end{frame} |
357 \end{frame} |
405 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
358 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
406 |
|
407 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
408 \begin{frame}[c] |
|
409 \frametitle{A Compiler} |
|
410 |
|
411 \begin{tikzpicture}[scale=1] |
|
412 \draw[line width=1mm] (-0.3, 0) rectangle (1.5,2); |
|
413 \draw[line width=1mm] (-1.8, 0) rectangle (-3.6,2); |
|
414 \draw (4.4,1) node {Code Gen}; |
|
415 \draw (0.6,1.7) node {\small Parser}; |
|
416 \draw (-2.7,1.7) node {\small Lexer}; |
|
417 |
|
418 \draw[red,->,line width = 2mm] (1.7,1) -- (3.2,1); |
|
419 \draw[red,<-,line width = 2mm] (-0.6,1) -- (-1.6,1); |
|
420 \draw[red,<-,line width = 2mm] (-3.8,1) -- (-4.8,1); |
|
421 |
|
422 \draw (-4.6,1.7) node {\small string}; |
|
423 \draw (-1.1,1.7) node {\small tokens}; |
|
424 \draw ( 2.3,1.7) node {\small AST}; |
|
425 \end{tikzpicture} |
|
426 |
|
427 \end{frame} |
|
428 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
429 |
359 |
430 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
360 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
431 \begin{frame}[t] |
361 \begin{frame}[t] |
432 |
362 |
433 \tt |
363 \tt |
656 |
610 |
657 \footnotesize |
611 \footnotesize |
658 \bl{$inj$}: 1st arg $\mapsto$ a rexp; 2nd arg $\mapsto$ a character; 3rd arg $\mapsto$ a value |
612 \bl{$inj$}: 1st arg $\mapsto$ a rexp; 2nd arg $\mapsto$ a character; 3rd arg $\mapsto$ a value |
659 \end{frame} |
613 \end{frame} |
660 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
614 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
615 |
|
616 |
|
617 |
|
618 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
619 \begin{frame}[c] |
|
620 |
|
621 \begin{textblock}{10}(3,5) |
|
622 \begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}] |
|
623 \node (r1) {\bl{$r_1$}}; |
|
624 \node (r2) [right=of r1] {\bl{$r_2$}}; |
|
625 \draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}}; |
|
626 \node (r3) [right=of r2] {\bl{$r_3$}}; |
|
627 \draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}}; |
|
628 \node (r4) [right=of r3] {\bl{$r_4$}}; |
|
629 \draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}}; |
|
630 \draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}}; |
|
631 \node (v4) [below=of r4] {\bl{$v_4$}}; |
|
632 \draw[->,line width=1mm] (r4) -- (v4); |
|
633 \node (v3) [left=of v4] {\bl{$v_3$}}; |
|
634 \draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}}; |
|
635 \node (v2) [left=of v3] {\bl{$v_2$}}; |
|
636 \draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}}; |
|
637 \node (v1) [left=of v2] {\bl{$v_1$}}; |
|
638 \draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}}; |
|
639 \draw[->,line width=0.5mm] (r3) -- (v3); |
|
640 \draw[->,line width=0.5mm] (r2) -- (v2); |
|
641 \draw[->,line width=0.5mm] (r1) -- (v1); |
|
642 \draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}}; |
|
643 \end{tikzpicture} |
|
644 \end{textblock} |
|
645 |
|
646 \only<2->{ |
|
647 \begin{textblock}{6}(1,0.8) |
|
648 \begin{bubble}[6cm] |
|
649 \small |
|
650 \begin{tabular}{ll} |
|
651 \bl{$r_1$}: & \bl{$a \cdot (b \cdot c)$}\\ |
|
652 \bl{$r_2$}: & \bl{$\epsilon \cdot (b \cdot c)$}\\ |
|
653 \bl{$r_3$}: & \bl{$(\varnothing \cdot (b \cdot c)) + (\epsilon \cdot c)$}\\ |
|
654 \bl{$r_4$}: & \bl{$(\varnothing \cdot (b \cdot c)) + ((\varnothing \cdot c) + \epsilon)$}\\ |
|
655 \end{tabular} |
|
656 \end{bubble} |
|
657 \end{textblock}} |
|
658 |
|
659 \only<2->{ |
|
660 \begin{textblock}{6}(5,11.4) |
|
661 \begin{bubble}[7.6cm] |
|
662 \small |
|
663 \begin{tabular}{ll} |
|
664 \bl{$v_1$}: & \bl{$Seq(Char(a), Seq(Char(b), Char(c)))$}\\ |
|
665 \bl{$v_2$}: & \bl{$Seq(Empty, Seq(Char(b), Char(c)))$}\\ |
|
666 \bl{$v_3$}: & \bl{$Right(Seq(Empty, Char(c)))$}\\ |
|
667 \bl{$v_4$}: & \bl{$Right(Right(Empty))$}\\ |
|
668 \end{tabular} |
|
669 \end{bubble} |
|
670 \end{textblock}} |
|
671 \end{frame} |
|
672 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
673 |
|
674 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
675 \begin{frame}[c] |
|
676 \frametitle{Flatten} |
|
677 |
|
678 Obtaining the string underlying a value: |
|
679 |
|
680 \begin{center} |
|
681 \begin{tabular}{lcl} |
|
682 \bl{$|Empty|$} & \bl{$\dn$} & \bl{$[]$}\\ |
|
683 \bl{$|Char(c)|$} & \bl{$\dn$} & \bl{$[c]$}\\ |
|
684 \bl{$|Left(v)|$} & \bl{$\dn$} & \bl{$|v|$}\\ |
|
685 \bl{$|Right(v)|$} & \bl{$\dn$} & \bl{$|v|$}\\ |
|
686 \bl{$|Seq(v_1,v_2)|$}& \bl{$\dn$} & \bl{$|v_1| \,@\, |v_2|$}\\ |
|
687 \bl{$|[v_1,\ldots ,v_n]|$} & \bl{$\dn$} & \bl{$|v_1| \,@\ldots @\, |v_n|$}\\ |
|
688 \end{tabular} |
|
689 \end{center} |
|
690 |
|
691 \end{frame} |
|
692 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
693 |
|
694 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
695 \begin{frame}[c] |
|
696 |
|
697 \begin{textblock}{10}(3,5) |
|
698 \begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}] |
|
699 \node (r1) {\bl{$r_1$}}; |
|
700 \node (r2) [right=of r1] {\bl{$r_2$}}; |
|
701 \draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}}; |
|
702 \node (r3) [right=of r2] {\bl{$r_3$}}; |
|
703 \draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}}; |
|
704 \node (r4) [right=of r3] {\bl{$r_4$}}; |
|
705 \draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}}; |
|
706 \draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}}; |
|
707 \node (v4) [below=of r4] {\bl{$v_4$}}; |
|
708 \draw[->,line width=1mm] (r4) -- (v4); |
|
709 \node (v3) [left=of v4] {\bl{$v_3$}}; |
|
710 \draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}}; |
|
711 \node (v2) [left=of v3] {\bl{$v_2$}}; |
|
712 \draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}}; |
|
713 \node (v1) [left=of v2] {\bl{$v_1$}}; |
|
714 \draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}}; |
|
715 \draw[->,line width=0.5mm] (r3) -- (v3); |
|
716 \draw[->,line width=0.5mm] (r2) -- (v2); |
|
717 \draw[->,line width=0.5mm] (r1) -- (v1); |
|
718 \draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}}; |
|
719 \end{tikzpicture} |
|
720 \end{textblock} |
|
721 |
|
722 \begin{textblock}{6}(1,0.8) |
|
723 \begin{bubble}[6cm] |
|
724 \small |
|
725 \begin{tabular}{ll} |
|
726 \bl{$r_1$}: & \bl{$a \cdot (b \cdot c)$}\\ |
|
727 \bl{$r_2$}: & \bl{$\epsilon \cdot (b \cdot c)$}\\ |
|
728 \bl{$r_3$}: & \bl{$(\varnothing \cdot (b \cdot c)) + (\epsilon \cdot c)$}\\ |
|
729 \bl{$r_4$}: & \bl{$(\varnothing \cdot (b \cdot c)) + ((\varnothing \cdot c) + \epsilon)$}\\ |
|
730 \end{tabular} |
|
731 \end{bubble} |
|
732 \end{textblock} |
|
733 |
|
734 \begin{textblock}{6}(1,11.4) |
|
735 \begin{bubble}[7.6cm] |
|
736 \small |
|
737 \begin{tabular}{ll} |
|
738 \bl{$v_1$}: & \bl{$Seq(Char(a), Seq(Char(b), Char(c)))$}\\ |
|
739 \bl{$v_2$}: & \bl{$Seq(Empty, Seq(Char(b), Char(c)))$}\\ |
|
740 \bl{$v_3$}: & \bl{$Right(Seq(Empty, Char(c)))$}\\ |
|
741 \bl{$v_4$}: & \bl{$Right(Right(Empty))$}\\ |
|
742 \end{tabular} |
|
743 \end{bubble} |
|
744 \end{textblock} |
|
745 |
|
746 \begin{textblock}{6}(12,11.4) |
|
747 \begin{bubble}[2cm] |
|
748 \small |
|
749 \begin{tabular}{ll} |
|
750 \bl{$|v_1|$}: & \bl{$abc$}\\ |
|
751 \bl{$|v_2|$}: & \bl{$bc$}\\ |
|
752 \bl{$|v_3|$}: & \bl{$c$}\\ |
|
753 \bl{$|v_4|$}: & \bl{$[]$} |
|
754 \end{tabular} |
|
755 \end{bubble} |
|
756 \end{textblock} |
|
757 |
|
758 |
|
759 \end{frame} |
|
760 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
761 |
661 |
762 |
662 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
763 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
663 \begin{frame}[c] |
764 \begin{frame}[c] |
664 \frametitle{Lexing} |
765 \frametitle{Lexing} |
665 |
766 |
717 \small |
818 \small |
718 for extracting subpatterns \bl{$(z: ((x:ab) + (y:ba))$} |
819 for extracting subpatterns \bl{$(z: ((x:ab) + (y:ba))$} |
719 |
820 |
720 \end{frame} |
821 \end{frame} |
721 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
822 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
823 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
824 \begin{frame}[c] |
|
825 \frametitle{Records} |
|
826 |
|
827 \begin{itemize} |
|
828 \item new regex: \bl{$(x:r)$}\hspace{7mm}new value: \bl{$Rec(x,v)$}\medskip\pause |
|
829 |
|
830 \item \bl{$nullable(x:r) \dn nullable(r)$} |
|
831 \item \bl{$der\,c\,(x:r) \dn (x:der\,c\,r)$} |
|
832 \item \bl{$mkeps(x:r) \dn Rec(x, mkeps(r))$} |
|
833 \item \bl{$inj\,(x:r)\,c\,v \dn Rec(x, inj\,r\,c\,v)$} |
|
834 \end{itemize}\bigskip\bigskip\pause |
|
835 |
|
836 \small |
|
837 for extracting subpatterns \bl{$(z: ((x:ab) + (y:ba))$} |
|
838 |
|
839 \end{frame} |
|
840 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
841 |
|
842 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
843 \begin{frame}[c] |
|
844 |
|
845 \begin{itemize} |
|
846 \item Regular expression for email addresses |
|
847 |
|
848 \begin{center} |
|
849 \begin{tabular}{l} |
|
850 (name: \bl{$[a\mbox{-}z0\mbox{-}9\_\!\_\,.-]^+$})\bl{$\cdot @\cdot$}\\ |
|
851 \qquad(domain: \bl{$[a\mbox{-}z0\mbox{-}9\,.-]^+$}) \bl{$\cdot .\cdot$}\\ |
|
852 \qquad\qquad(top\_level: \bl{$[a\mbox{-}z\,.]^{\{2,6\}}$}) |
|
853 \end{tabular} |
|
854 \end{center} |
|
855 |
|
856 \bl{\[ |
|
857 \texttt{christian.urban@kcl.ac.uk} |
|
858 \]} |
|
859 |
|
860 \item result environment: |
|
861 |
|
862 \begin{center} |
|
863 \begin{tabular}{l} |
|
864 \bl{$[(name:\texttt{christian.urban}),$}\\ |
|
865 \bl{$\phantom{[}(domain:\texttt{kcl}),$}\\ |
|
866 \bl{$\phantom{[}(top\_level:\texttt{ac.uk})]$} |
|
867 \end{tabular} |
|
868 \end{center} |
|
869 \end{itemize} |
|
870 |
|
871 \end{frame} |
|
872 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
873 |
722 |
874 |
723 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
875 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
724 \begin{frame}[c] |
876 \begin{frame}[c] |
725 \frametitle{While Tokens} |
877 \frametitle{While Tokens} |
726 |
878 |
800 \small |
959 \small |
801 old \bl{$simp$} returns a rexp;\\ |
960 old \bl{$simp$} returns a rexp;\\ |
802 new \bl{$simp$} returns a rexp and a rectification~fun. |
961 new \bl{$simp$} returns a rexp and a rectification~fun. |
803 \end{frame} |
962 \end{frame} |
804 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
963 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
964 |
|
965 |
|
966 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
967 \begin{frame}[c] |
|
968 \frametitle{Rectification} |
|
969 |
|
970 \begin{center} |
|
971 \begin{tabular}{l} |
|
972 \bl{$simp(r)$}:\\ |
|
973 \quad case \bl{$r = r_1 + r_2$}\\ |
|
974 \qquad let \bl{$(r_{1s}, f_{1s}) = simp(r_1)$}\\ |
|
975 \qquad \phantom{let} \bl{$(r_{2s}, f_{2s}) = simp(r_2)$}\smallskip\\ |
|
976 \qquad case \bl{$r_{1s} = \varnothing$}: |
|
977 return \bl{$(r_{2s}, \lambda v. \,Right(f_{2s}(v)))$}\\ |
|
978 \qquad case \bl{$r_{2s} = \varnothing$}: |
|
979 return \bl{$(r_{1s}, \lambda v. \,Left(f_{1s}(v)))$}\\ |
|
980 \qquad case \bl{$r_{1s} = r_{2s}$}: |
|
981 return \bl{$(r_{1s}, \lambda v. \,Left(f_{1s}(v)))$}\\ |
|
982 \qquad otherwise: |
|
983 return \bl{$(r_{1s} + r_{2s}, f_{alt}(f_{1s}, f_{2s}))$}\\ |
|
984 \end{tabular} |
|
985 \end{center} |
|
986 |
|
987 \small |
|
988 \begin{center} |
|
989 \begin{tabular}{l@{\hspace{1mm}}l} |
|
990 \bl{$f_{alt}(f_1, f_2) \dn$}\\ |
|
991 \qquad \bl{$\lambda v.\,$} case \bl{$v = Left(v')$}: |
|
992 & return \bl{$Left(f_1(v'))$}\\ |
|
993 \qquad \phantom{$\lambda v.\,$} case \bl{$v = Right(v')$}: |
|
994 & return \bl{$Right(f_2(v'))$}\\ |
|
995 \end{tabular} |
|
996 \end{center} |
|
997 |
|
998 |
|
999 \end{frame} |
|
1000 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1001 |
|
1002 \begin{frame}[c] |
|
1003 |
|
1004 {\footnotesize\lstinputlisting[language=Scala,numbers=none, |
|
1005 xleftmargin=-5mm] {../progs/app05.scala}} |
|
1006 |
|
1007 \end{frame} |
|
1008 |
|
1009 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1010 \begin{frame}[c] |
|
1011 \frametitle{Rectification} |
|
1012 |
|
1013 \begin{center} |
|
1014 \begin{tabular}{@{\hspace{-3mm}}l} |
|
1015 \bl{$simp(r)$}:\ldots\\ |
|
1016 \quad case \bl{$r = r_1 \cdot r_2$}\\ |
|
1017 \qquad let \bl{$(r_{1s}, f_{1s}) = simp(r_1)$}\\ |
|
1018 \qquad \phantom{let} \bl{$(r_{2s}, f_{2s}) = simp(r_2)$}\smallskip\\ |
|
1019 \qquad case \bl{$r_{1s} = \varnothing$}: |
|
1020 return \bl{$(\varnothing, f_{error})$}\\ |
|
1021 \qquad case \bl{$r_{2s} = \varnothing$}: |
|
1022 return \bl{$(\varnothing, f_{error})$}\\ |
|
1023 \qquad case \bl{$r_{1s} = \epsilon$}: |
|
1024 return \bl{$(r_{2s}, \lambda v. \,Seq(f_{1s}(Empty), f_{2s}(v)))$}\\ |
|
1025 \qquad case \bl{$r_{2s} = \epsilon$}: |
|
1026 return \bl{$(r_{1s}, \lambda v. \,Seq(f_{1s}(v), f_{2s}(Empty)))$}\\ |
|
1027 \qquad otherwise: |
|
1028 return \bl{$(r_{1s} \cdot r_{2s}, f_{seq}(f_{1s}, f_{2s}))$}\\ |
|
1029 \end{tabular} |
|
1030 \end{center} |
|
1031 |
|
1032 \small |
|
1033 \begin{center} |
|
1034 \begin{tabular}{l@{\hspace{1mm}}l} |
|
1035 \bl{$f_{seq}(f_1, f_2) \dn$}\\ |
|
1036 \qquad \bl{$\lambda v.\,$ case $v = Seq(v_1, v_2)$}: |
|
1037 & return \bl{$Seq(f_1(v_1), f_2(v_2))$}\\ |
|
1038 \end{tabular} |
|
1039 \end{center} |
|
1040 \end{frame} |
|
1041 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1042 |
|
1043 |
|
1044 |
|
1045 \begin{frame}[c] |
|
1046 |
|
1047 {\footnotesize\lstinputlisting[language=Scala,numbers=none, |
|
1048 xleftmargin=-5mm] {../progs/app06.scala}} |
|
1049 |
|
1050 \end{frame} |
|
1051 |
805 |
1052 |
806 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1053 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
807 \begin{frame}[c] |
1054 \begin{frame}[c] |
808 \frametitle{Lexing with Simplification} |
1055 \frametitle{Lexing with Simplification} |
809 |
1056 |