367 \end{frame} |
367 \end{frame} |
368 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
368 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
369 |
369 |
370 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
370 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
371 \begin{frame}[c] |
371 \begin{frame}[c] |
372 \frametitle{A ``Compiler'' for BF*** to C} |
372 \frametitle{Another~``Compiler''~for~BF~to~C} |
373 |
373 |
374 \begin{center} |
374 \begin{center} |
375 \begin{tabular}{rcl} |
375 \begin{tabular}{rcl} |
376 \bl{\texttt{>\ldots>}} & $\Rightarrow$ & \texttt{ptr += n}\\ |
376 \bl{\texttt{>\ldots>}} & $\Rightarrow$ & \texttt{ptr += n}\\ |
377 \bl{\texttt{<\ldots<}} & $\Rightarrow$ & \texttt{ptr -= n}\\ |
377 \bl{\texttt{<\ldots<}} & $\Rightarrow$ & \texttt{ptr -= n}\\ |
387 |
387 |
388 \texttt{char field[30000]\\ char *ptr = \&field[15000]} |
388 \texttt{char field[30000]\\ char *ptr = \&field[15000]} |
389 |
389 |
390 \end{frame} |
390 \end{frame} |
391 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
391 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
392 |
392 |
393 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
394 \begin{frame}[c] |
|
395 \frametitle{Recap} |
|
396 |
|
397 \begin{itemize} |
|
398 \item interpreter \bl{\texttt{bfi.sc}} \\$\Rightarrow$ 11 mins\pause |
|
399 \item simple compiler \bl{\texttt{bfi0.sc}}, no optimisations \\$\Rightarrow$ 20 secs\pause |
|
400 \item ``advanced'' compiler \bl{\texttt{bfi1.sc}}, no optimisations \\$\Rightarrow$ 5 secs\bigskip\pause |
|
401 |
|
402 \item simple compiler \bl{\texttt{bfi0.sc}}, |
|
403 \alert{\textbf{full optimisations}} \\$\Rightarrow$ 7 secs |
|
404 \end{itemize}\bigskip\pause |
|
405 |
|
406 \hspace{4cm}all programs on KEATS |
|
407 |
|
408 \end{frame} |
|
409 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
410 |
|
411 |
|
412 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
393 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
413 \begin{frame}[t] |
394 \begin{frame}[t] |
414 \frametitle{A Brief Compiler History} |
395 \frametitle{A Brief Compiler History} |
415 |
396 |
416 \bigskip |
397 \bigskip |
437 \end{frame} |
418 \end{frame} |
438 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
419 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
439 |
420 |
440 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
421 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
441 \begin{frame}[c] |
422 \begin{frame}[c] |
|
423 \frametitle{Some Housekeeping} |
|
424 |
|
425 \textbf{Exams will be online:}\bigskip |
|
426 |
|
427 \begin{itemize} |
|
428 \item final exam in January (30\%) |
|
429 \item mid-term shortly after Reading Week (10\%)\bigskip |
|
430 |
|
431 \item weekly engagement (10\%) |
|
432 \end{itemize}\bigskip\bigskip\pause |
|
433 |
|
434 |
|
435 \textbf{Weekly Homework (optional):} |
|
436 \begin{itemize} |
|
437 \item uploaded on KEATS, send answers via email, responded individually |
|
438 \item \alert{\bf all} questions in the exam and mid-term will be from the HW!! |
|
439 \end{itemize} |
|
440 |
|
441 \end{frame} |
|
442 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
443 |
|
444 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
445 \begin{frame}[c] |
|
446 \frametitle{Some Housekeeping} |
|
447 |
|
448 \textbf{Coursework (5 accounting for 45\%):}\bigskip |
|
449 |
|
450 \begin{itemize} |
|
451 \item matcher (5\%) |
|
452 \item lexer (8\%) |
|
453 \item parser / interpreter (10\%) |
|
454 \item JVM compiler (10\%) |
|
455 \item LLVM compiler (12\%) |
|
456 \end{itemize}\bigskip\pause |
|
457 |
|
458 you can use any programming language you like (Haskell, Rust)\\\pause |
|
459 you can use any code I showed you and uploaded to KEATS\ldots\textbf{BUT NOTHING ELSE!}\pause |
|
460 |
|
461 \end{frame} |
|
462 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
463 |
|
464 |
|
465 |
|
466 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
467 \begin{frame}[c] |
442 \frametitle{Lectures 1 - 5} |
468 \frametitle{Lectures 1 - 5} |
443 |
469 |
444 transforming strings into structured data\\[10mm] |
470 transforming strings into structured data\\[10mm] |
445 |
471 |
446 {\LARGE\bf Lexing} {\hfill{}based on regular expressions}\medskip\\ |
472 {\LARGE\bf Lexing} {\hfill{}based on regular expressions}\medskip\\ |
459 \end{frame} |
485 \end{frame} |
460 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
486 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
461 |
487 |
462 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
488 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
463 \begin{frame}[c] |
489 \begin{frame}[c] |
|
490 \frametitle{Lectures 1 - 5} |
|
491 |
|
492 transforming strings into structured data\\[10mm] |
|
493 |
|
494 {\LARGE\bf Lexing} {\hfill{}based on regular expressions}\medskip\\ |
|
495 \hspace{5mm}(recognising ``words'')\\[6mm] |
|
496 |
|
497 {\LARGE\bf Parsing}\medskip\\ |
|
498 \hspace{5mm}(recognising ``sentences'') |
|
499 |
|
500 \begin{textblock}{1}(10,9.1) |
|
501 \begin{tabular}{c} |
|
502 \includegraphics[scale=0.1]{../pics/rosetta.jpg}\\[-2mm] |
|
503 \footnotesize Stone of Rosetta |
|
504 \end{tabular} |
|
505 \end{textblock} |
|
506 |
|
507 \end{frame} |
|
508 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
509 |
|
510 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
511 \begin{frame}[c] |
464 \frametitle{Lectures 5 - 10} |
512 \frametitle{Lectures 5 - 10} |
465 |
513 |
466 code generation for a small imperative and a small functional language\\[10mm] |
514 code generation for a small imperative and a small functional language\\[10mm] |
467 |
515 |
468 {\LARGE\bf Interpreters}\medskip\\ |
516 {\LARGE\bf Interpreters}\medskip\\ |
477 \includegraphics[scale=0.23]{../pics/llvmlogo.png} |
525 \includegraphics[scale=0.23]{../pics/llvmlogo.png} |
478 \end{tabular} |
526 \end{tabular} |
479 \end{textblock} |
527 \end{textblock} |
480 |
528 |
481 \end{frame} |
529 \end{frame} |
482 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
530 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
483 |
531 |
484 |
532 |
485 |
533 |
486 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
534 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
487 \begin{frame}[t] |
535 \begin{frame}[t] |
488 \frametitle{Familiar Regular Expr.} |
536 \frametitle{Familiar Regular Expresssions} |
489 \small |
537 \small |
490 \begin{center} |
538 \begin{center} |
491 \texttt{[a-z0-9\_$\backslash{}$.-]+ @ [a-z0-9$\backslash{}$.-]+ . [a-z$\backslash{}$.]\{2,6\}} |
539 \texttt{[a-z0-9\_$\backslash{}$.-]+ @ [a-z0-9$\backslash{}$.-]+ . [a-z$\backslash{}$.]\{2,6\}} |
492 \end{center}\smallskip |
540 \end{center}\smallskip |
493 |
541 |
507 \pcode{(re)} & groups regular expressions and remembers |
555 \pcode{(re)} & groups regular expressions and remembers |
508 the matched text |
556 the matched text |
509 \end{tabular} |
557 \end{tabular} |
510 \end{center} |
558 \end{center} |
511 |
559 |
512 |
|
513 \end{frame} |
560 \end{frame} |
514 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
561 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
515 |
562 |
|
563 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
564 \begin{frame}[c] |
|
565 \frametitle{Some ``innocent'' examples} |
|
566 |
|
567 Let's try two examples |
|
568 |
|
569 \begin{center} |
|
570 \bl{\texttt{(a*)*b}} |
|
571 \hspace{2cm} |
|
572 \bl{\texttt{[a?]\{n\}[a]\{n\}}} |
|
573 \end{center}\bigskip\pause |
|
574 |
|
575 and match them with strings of the form |
|
576 |
|
577 \begin{center} |
|
578 \bl{\texttt{a}}, |
|
579 \bl{\texttt{aa}}, |
|
580 \bl{\texttt{aaa}}, |
|
581 \bl{\texttt{aaaa}}, |
|
582 \bl{\texttt{aaaaa}}, |
|
583 \bl{$\underbrace{\texttt{a}...\texttt{a}}_n$} |
|
584 \end{center} |
|
585 |
|
586 \end{frame} |
|
587 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
516 |
588 |
517 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
589 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
518 \begin{frame}[c] |
590 \begin{frame}[c] |
519 \frametitle{Why Bother with Regexes?} |
591 \frametitle{Why Bother with Regexes?} |
520 |
592 |
802 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
874 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
803 |
875 |
804 |
876 |
805 |
877 |
806 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
878 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
807 \begin{frame}[t] |
879 %\begin{frame}[t] |
808 \frametitle{A Regular Expression} |
880 %\frametitle{A Regular Expression} |
809 |
881 % |
810 \begin{itemize} |
882 %\begin{itemize} |
811 \item \ldots{} is a pattern or template for specifying strings |
883 %\item \ldots{} is a pattern or template for specifying strings |
812 \end{itemize}\bigskip |
884 %\end{itemize}\bigskip |
813 |
885 % |
814 \begin{center} |
886 %\begin{center} |
815 \only<1>{\scode{"https?://[^"]*"}}% |
887 %\only<1>{\scode{"https?://[^"]*"}}% |
816 \only<2>{\scode{""""https?://[^"]*"""".r}} |
888 %\only<2>{\scode{""""https?://[^"]*"""".r}} |
817 \end{center}\bigskip\bigskip |
889 %\end{center}\bigskip\bigskip |
818 |
890 % |
819 matches for example\smallskip\\ |
891 %matches for example\smallskip\\ |
820 \hspace{2mm}\code{"http://www.foobar.com"}\\ |
892 %\hspace{2mm}\code{"http://www.foobar.com"}\\ |
821 \hspace{2mm}\code{"https://www.tls.org"}\smallskip\\ |
893 %\hspace{2mm}\code{"https://www.tls.org"}\smallskip\\ |
822 |
894 % |
823 but not\smallskip\\ |
895 %but not\smallskip\\ |
824 \hspace{2mm}\code{"http://www."foo"bar.com"}\\ |
896 %\hspace{2mm}\code{"http://www."foo"bar.com"}\\ |
825 |
897 % |
826 \end{frame} |
898 %\end{frame} |
827 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
899 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
828 |
900 |
829 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
901 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
830 %\begin{frame}[c] |
902 %\begin{frame}[c] |
831 %\frametitle{Finding Operations in Scala} |
903 %\frametitle{Finding Operations in Scala} |
885 %\end{frame} |
957 %\end{frame} |
886 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
958 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
887 |
959 |
888 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
960 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
889 \begin{frame}[t] |
961 \begin{frame}[t] |
890 \frametitle{Regular Expressions} |
962 \frametitle{(Basic) Regular Expressions} |
891 |
963 |
892 Their inductive definition: |
964 Their inductive definition: |
893 |
965 |
894 |
966 |
895 \begin{textblock}{6}(2,7.5) |
967 \begin{textblock}{6}(2,7.5) |