60   \LARGE Lunch with a Lecturer (29 March)\\[5mm] 

   241   \LARGE Compilers and \\[-1mm] 

   242   \LARGE Formal Languages\\[-5mm] 

    63   I teach CFL (compilers) and PEP (Scala)\bigskip

   245   %\begin{center}

    64 

   246   %\includegraphics[scale=0.3]{pics/ante1.jpg}\hspace{5mm}

    65   \begin{itemize}

   247   %\includegraphics[scale=0.31]{pics/ante2.jpg}\\

    66   \item did undergraduate in Germany

   248   %\footnotesize\textcolor{gray}{Antikythera automaton, 100 BC (Archimedes?)}

    67   \item Master in St Andrews

   249   %\end{center}

    68   \item PhD in Cambridge  

   250 

    69   \end{itemize}\bigskip\bigskip

   251   \normalsize

    70 

   252   \begin{center}

    71   use mainly the Isabelle theorem prover in my work (see 6CCS3VER)

   253   \begin{tabular}{ll}

    72 

   254   Email:  & christian.urban at kcl.ac.uk\\

    73   write code in functional programming languages (Scala, SML, Ocaml, Haskell)

   255   Office Hour: & Fridays 11 -- 12\\

    74 \end{frame}

   256   Location: & N7.07 (North Wing, Bush House)\\

    75 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   257   Slides \& Progs: & KEATS\\

   258   Pollev: & \texttt{\alert{https://pollev.com/cfltutoratki576}}\\  

   259   \end{tabular}

   260   \end{center}

   261 

   262   \begin{center}

   263     \begin{tikzpicture}

   264       \node[drop shadow,fill=white,inner sep=0pt] 

   265       {\footnotesize\rowcolors{1}{capri!10}{white}

   266         \begin{tabular}{|p{4.8cm}|p{4.8cm}|}\hline

   267           \cellcolor{blue!50}

   268           1 Introduction, Languages          & 6 While-Language \\

   269           2 Regular Expressions, Derivatives & 7 Compilation, JVM \\

   270           3 Automata, Regular Languages      & 8 Compiling Functional Languages \\

   271           4 Lexing, Tokenising               & 9 Optimisations \\

   272           5 Grammars, Parsing                & 10 LLVM \\ \hline

   273         \end{tabular}%

   274       };

   275     \end{tikzpicture}

   276   \end{center}

   277 

   278 \end{frame}

   279 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   280 

   281 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   282 \begin{frame}<1-12>[c]

   283 \frametitle{The Goal of this Module\ldots}

   284 

   285 \begin{center}

   286   \begin{tikzpicture}[scale=1,

   287                       node/.style={

   288                       rectangle,rounded corners=3mm,

   289                       very thick,draw=black!50,minimum height=18mm, minimum width=20mm,

   290                       top color=white,bottom color=black!20,drop shadow}]

   291 

   292   \node at (3.05, 1.8) {\Large\bf \ldots{} you write a compiler};

   293 

   294   \node (0) at (-2.3,0) {};  

   295   \node [above=5mm of 0]

   296   {\makebox[0mm]{\footnotesize

   297       \begin{tabular}{@{}l@{}}input\\[-1mm]program\end{tabular}}}; 

   298      

   299   \node (A) at (0,0)  [node] {};

   300   \node [below right] at (A.north west) {lexer};

   301 

   302   \node (B) at (3,0)  [node] {};

   303   \node [below right=1mm] at (B.north west) {\mbox{}\hspace{-1mm}parser};

   304 

   305   \node (C) at (6,0)  [node] {};

   306   \node [below right] at (C.north west) {\mbox{}\hspace{-1mm}code gen};

   307 

   308   \node (1) at (8.4,0) {};

   309   \node [above=5mm of 1]

   310   {\makebox[0mm]{\footnotesize

   311       \begin{tabular}{@{}r@{}}binary\\[-1mm]code\end{tabular}}};

   312 

   313   \draw [->,line width=4mm] (0) -- (A); 

   314   \draw [->,line width=4mm] (A) -- (B); 

   315   \draw [->,line width=4mm] (B) -- (C); 

   316   \draw [->,line width=4mm] (C) -- (1); 

   317   \end{tikzpicture}

   318   \end{center}

   319 

   320 \only<2,3,4>{

   321 \begin{textblock}{1}(1,2.1)

   322 \begin{bubble}[9.8cm]

   323 \normalsize

   324 lexer input: a string\smallskip\\

   325 \hspace{5mm}\code{"read(n);"}\medskip\\

   326 lexer output: a sequence of tokens\smallskip\\

   327 \hspace{5mm}\code{key(read) lpar id(n) rpar semi}

   328 \end{bubble}

   329 \end{textblock}} 

   330 

   331 \only<3,4>{

   332 \begin{textblock}{1}(6,7.8)

   333 \begin{tabular}{c}

   334 \includegraphics[scale=0.2]{../pics/rosetta.jpg}\\[-2mm]

   335 \footnotesize lexing $\Rightarrow$ recognising words (Stone of Rosetta)

   336 \end{tabular}

   337 \end{textblock}}

   338 

   339 \only<4>{

   340 \begin{textblock}{1}(0.5,12)\small

   341 \begin{tabular}{l@{}c@{}l}

   342   \pcode{if}    & $\;\Rightarrow\;$ & keyword\\

   343   \pcode{iffoo} & $\;\Rightarrow\;$ & identifier\\

   344 \end{tabular}  

   345 \end{textblock}}

   346 

   347 \only<6>{

   348 \begin{textblock}{1}(1,1.5)

   349 \begin{bubble}[8.5cm]

   350 \normalsize

   351 parser input: a sequence of tokens\smallskip\\

   352 

   353 {\small\hspace{5mm}\code{key(read) lpar id(n) rpar semi}}\smallskip\\

   354 

   355 parser output: an abstract syntax tree\smallskip\\

   356 \footnotesize

   357 \hspace{2cm}\begin{tikzpicture}

   358   \node {\code{read}}

   359     child {node {\code{lpar}}}

   360     child {node {\code{n}}}

   361     child {node {\code{rpar}}};

   362 \end{tikzpicture}

   363 \end{bubble}

   364 \end{textblock}}

   365 

   366 \only<8,9>{

   367 \begin{textblock}{1}(1,1.5)

   368 \begin{bubble}[4cm]

   369 \normalsize

   370 code generation:\smallskip\\

   371 \hspace{5mm}\code{istore 2}\\ 

   372 \hspace{5mm}\code{iload 2}\\ 

   373 \hspace{5mm}\code{ldc 10}\\

   374 \hspace{5mm}\code{isub}\\

   375 \hspace{5mm}\code{ifeq Label2}\\ 

   376 \hspace{5mm}\code{iload 2}\\

   377 \hspace{5mm}\code{...}\\

   378 \end{bubble}

   379 \end{textblock}}

   380 

   381 \only<9>{

   382 \begin{textblock}{6}(8.4,7)

   383 \begin{bubble}[5cm]

   384 \mbox{\begin{tikzpicture}[scale=0.58,rounded corners=0mm]

   385 \begin{axis}[axis x line=bottom, axis y line=left, ylabel=secs,

   386     xlabel=n,

   387     enlargelimits=0.05,

   388     ybar interval=0.7, legend style=small]

   389 \addplot file {interpreted2.data};

   390 \addplot file {compiled2.data};

   391 %\legend{interpreted, compiled}

   392 \end{axis}

   393 \end{tikzpicture}}

   394 \end{bubble}

   395 \end{textblock}}

   396 

   397 \only<10>{

   398 \begin{textblock}{6}(1,3)

   399   \begin{bubble}[11cm]

   400     Compiler explorers, e.g.: \url{https://gcc.godbolt.org} \;\video{https://youtu.be/ysaBmhMEyUg}

   401   \begin{tikzpicture}[]

   402   \node (0) at (-2.3,0) {\includegraphics[scale=0.3]{pics/csource.png}};

   403   \node (1) [right=35mm] at (0) {\includegraphics[scale=0.3]{pics/cassmbl.png}}; 

   404   \draw [->,line width=4mm, red] (0) -- (1);   

   405   \node (2) [below=20mm] at (0) {\LARGE\bf source};

   406   \node (3) [right=40mm] at (2) {\LARGE\bf binary};

   407   \draw [->,line width=1mm] (2) -- (3);   

   408 \end{tikzpicture}

   409 \end{bubble}

   410 

   411 \end{textblock}}

   412 \only<11>{

   413 \begin{textblock}{6}(1,3)

   414   \begin{bubble}[11cm]

   415     Compiler explorer for Java: \url{https://javap.yawk.at} 

   416   \begin{tikzpicture}[]

   417   \node (0) at (-2.3,0) {\includegraphics[scale=0.4]{pics/jsource.png}};

   418   \node (1) [right=35mm] at (0) {\includegraphics[scale=0.4]{pics/jassmbl.png}}; 

   419   \draw [->,line width=4mm, red] (0) -- (1);   

   420   \node (2) [below=20mm] at (0) {\LARGE\bf source};

   421   \node (3) [right=40mm] at (2) {\LARGE\bf byte code};

   422   \draw [->,line width=1mm] (2) -- (3);   

   423 \end{tikzpicture}

   424 \end{bubble}

   425 \end{textblock}}

   426 

   427 

   428 \end{frame}

   429 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     

   430 

   431 

   432 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   433 \begin{frame}[t]

   434 \frametitle{Why Study Compilers?}

   435 

   436 

   437 John Regehr {\small(Univ.~Utah, LLVM compiler hacker)}

   438 \here{https://blog.regehr.org/archives/1419}

   439 \smallskip\\

   440 

   441 \begin{bubble}[10.5cm]

   442   \bf ``\ldots{}It’s effectively a perpetual

   443   employment act for solid compiler hackers.''

   444 \end{bubble}

   445 

   446 \onslide<1->{

   447 \only<2>{

   448 \begin{itemize}

   449 \item {\bf Hardware is getting weirder

   450   rather than getting clocked faster.}

   451 

   452 \begin{itemize}

   453 \item[]  ``Almost all processors are multicores nowadays and it looks

   454   like there is increasing asymmetry in resources across cores.

   455   Processors come with vector units, crypto accelerators etc. We have

   456   DSPs, GPUs, ARM big.little, and Xeon Phi. This is only scratching the

   457   surface.''

   458 \end{itemize}  

   459 \end{itemize}}

   460 \only<3>{

   461 \begin{itemize}

   462 \item {\bf We’re getting tired of low-level languages and

   463     their associated security disasters.}

   464   

   465 \begin{itemize}

   466 \item [] ``We want to write new code, to whatever extent possible, in

   467   safer, higher-level languages. Compilers are caught right in the

   468   middle of these opposing trends: one of their main jobs is to help

   469   bridge the large and growing gap between increasingly high-level

   470   languages and increasingly wacky platforms.''

   471 \end{itemize}  

   472 \end{itemize}}}

   473 

   474 \end{frame}

   475 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   476 

   477 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   478 {

   479 \setbeamercolor{background canvas}{bg=cream}

   480 \begin{frame}[c]

   481 

   482 \frametitle{}

   483 \begin{mybox3}{}\it

   484    ``I enjoyed the module - it was genuinely the stand out academic

   485 experience of my undergraduate degree, and very much influenced my

   486 career interests. In fact I am currently working at ARM, in their Open

   487 Source Software group, on AArch64 specific optimisations for the

   488 Java/Kotlin compiler that forms part of the Android Runtime.''\\

   489 \mbox{}\hfill-- Hari Limaye in year 2021/22

   490 \end{mybox3}\pause

   491 

   492 

   493 Student numbers in CFL\medskip\\

   494 \begin{tabular}{ll}

   495 2019: & 32\\  

   496 2020: & 59\\  

   497 2021: & 109\\

   498 2022: & 121\\  

   499 \end{tabular}  

   500 

   501 \end{frame}

   502 }

   503 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   504 

   505 

   506 

   507 

   508 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   509 \begin{frame}[c]

   510 \frametitle{Why Bother with Compilers?}

   511   

   512 \textbf{Boeing 777's}: First flight in 1994. They want to achieve

   513 triple redundancy for potential hardware faults.

   514 \here{http://www.citemaster.net/get/db3a81c6-548e-11e5-9d2e-00163e009cc7/R8.pdf}\bigskip

   515   

   516 They compile 1 Ada program to\medskip

   517   

   518 \begin{itemize}

   519   \item Intel 80486

   520   \item Motorola 68040 (old Macintosh's)

   521   \item AMD 29050 (RISC chips used often in laser printers)

   522 \end{itemize}\medskip\medskip

   523   

   524 using 3 independent compilers.\bigskip\pause

   525   

   526 \small Airbus uses C and static analysers. Recently started using CompCert.

   527 

   528 \only<1->{%

   529 \begin{textblock}{6}(8,4.5)

   530 \includegraphics[scale=0.28]{../pics/777.png}

   531 \end{textblock}}

   532 

   533 \end{frame}

   534 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   535 

   536 

   537 

   538 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   539 \begin{frame}[c]

   540 \frametitle{What Do Compilers Do?}

   541 

   542 Remember BF*** from PEP?

   543 

   544 \begin{center}

   545 \begin{tabular}{rcl}

   546 \bl{\texttt{>}} & $\Rightarrow$ & move one cell right\\

   547 \bl{\texttt{<}} & $\Rightarrow$ & move one cell left\\

   548 \bl{\texttt{+}} & $\Rightarrow$ & increase cell by one\\

   549 \bl{\texttt{-}} & $\Rightarrow$ & decrease cell by one\\

   550 \bl{\texttt{.}} & $\Rightarrow$ & print current cell\\

   551 \bl{\texttt{,}} & $\Rightarrow$ & input current cell\\

   552 \bl{\texttt{[}} & $\Rightarrow$ & loop begin\\

   553 \bl{\texttt{]}} & $\Rightarrow$ & loop end\medskip\\

   554                 & $\Rightarrow$ & everything else is a comment\\

   555 \end{tabular}  

   556 \end{center}  

   557 

   558 \end{frame}

   559 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   560 

   561 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   562 \begin{frame}[c]

   563   \frametitle{A ``Compiler'' for BF*** to C}

   564   

   565   \begin{center}

   566   \begin{tabular}{rcl}

   567   \bl{\texttt{>}} & $\Rightarrow$ & \texttt{ptr++}\\

   568   \bl{\texttt{<}} & $\Rightarrow$ & \texttt{ptr--}\\

   569   \bl{\texttt{+}} & $\Rightarrow$ & \texttt{(*ptr)++}\\

   570   \bl{\texttt{-}} & $\Rightarrow$ & \texttt{(*ptr)--}\\

   571   \bl{\texttt{.}} & $\Rightarrow$ & \texttt{putchar(*ptr)}\\

   572   \bl{\texttt{,}} & $\Rightarrow$ & \texttt{*ptr = getchar()}\\

   573   \bl{\texttt{[}} & $\Rightarrow$ & \texttt{while(*ptr)\{}\\

   574   \bl{\texttt{]}} & $\Rightarrow$ & \texttt{\}}\medskip\\

   575                   & $\Rightarrow$ & ignore everything else\\

   576   \end{tabular}  

   577   \end{center}\bigskip  

   578   

   579   \texttt{char field[30000]\\ char *ptr = \&field[15000]}

   580   

   581 \end{frame}

   582 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   583 

   584 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   585 \begin{frame}[c]

   586   \frametitle{Another~``Compiler''~for~BF~to~C}

   587   

   588   \begin{center}

   589   \begin{tabular}{rcl}

   590   \bl{\texttt{>\ldots>}} & $\Rightarrow$ & \texttt{ptr += n}\\

   591   \bl{\texttt{<\ldots<}} & $\Rightarrow$ & \texttt{ptr -= n}\\

   592   \bl{\texttt{+\ldots+}} & $\Rightarrow$ & \texttt{(*ptr) += n}\\

   593   \bl{\texttt{-\ldots-}} & $\Rightarrow$ & \texttt{(*ptr) -= n}\\

   594   \bl{\texttt{.}} & $\Rightarrow$ & \texttt{putchar(*ptr)}\\

   595   \bl{\texttt{,}} & $\Rightarrow$ & \texttt{*ptr = getchar()}\\

   596   \bl{\texttt{[}} & $\Rightarrow$ & \texttt{while(*ptr)\{}\\

   597   \bl{\texttt{]}} & $\Rightarrow$ & \texttt{\}}\medskip\\

   598                   & $\Rightarrow$ & ignore everything else\\

   599   \end{tabular}  

   600   \end{center}\bigskip  

   601   

   602   \texttt{char field[30000]\\ char *ptr = \&field[15000]}

   603   

   604 \end{frame}

   605 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   606     

   607 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   608 \begin{frame}[t]

   609 \frametitle{A Brief Compiler History}

   610 

   611 \bigskip

   612 \begin{itemize}

   613 \item Turing Machines, 1936 (a tape as memory)

   614 \item Regular Expressions, 1956\\

   615 \item The first compiler for COBOL, 1957\\ (Grace Hopper)\medskip

   616 \item But surprisingly research papers are still published nowadays\\

   617 \item ``Parsing: The Solved Problem That Isn't''

   618   \here{https://tratt.net/laurie/blog/entries/parsing_the_solved_problem_that_isnt.html}

   619 \end{itemize}

   620 

   621 

   622 \begin{textblock}{8.5}(5,7.6)

   623 \begin{flushright}

   624 \includegraphics[scale=0.3]{pics/hopper.jpg}\\

   625 \footnotesize\textcolor{gray}{Grace Hopper}\smallskip\\

   626 

   627 {\small\textcolor{gray}{(she made it to David Letterman's Tonight Show

   628  \here{https://youtu.be/3N_ywhx6_K0?t=31})}}

   629 \end{flushright}

   630 \end{textblock}

   631 

   632 \end{frame}

   633 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     

   634 

   635 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   636 \begin{frame}[c]

   637 \frametitle{Some Housekeeping}

   638 

   639 \textbf{Exam will be online:}\bigskip

   640 

   641 \begin{itemize}

   642 \item final exam in January (35\%)

   643 \item five CWs (65\%) 

   644 \end{itemize}\bigskip\bigskip\pause

   645 

   646 

   647 \textbf{Weekly Homework (optional):}

   648 \begin{itemize}

   649 \item uploaded on KEATS, send answers via email, (try to!) respond individually

   650 \item \alert{\bf all} questions in the exam will be from the HWs!!

   651 \end{itemize}  

   652 

   653 \end{frame}

   654 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   655 

   656 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   657 {

   658 \setbeamercolor{background canvas}{bg=cream}

   659 \begin{frame}[c]

   660 \frametitle{Homework}

   661 

   662 Until 2 years ago: I did not give out solutions; students sent emails to me and I responded to them individually.\bigskip\\

   663 

   664 

   665 Since last year: We will review the homework mainly during the SGTs.\bigskip\\\pause

   666 

   667 I will still choose the questions from the HW for the exam, but there might be

   668 some larger amount of deviation.

   669 

   670 \end{frame}

   671 }

   672 

   673 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   674 \begin{frame}[c]

   675 \frametitle{Some Housekeeping}

   676 

   677 \textbf{Coursework (5 accounting for 65\%):}\bigskip

   678 

   679 \begin{itemize}

   680 \item matcher (5\%)

   681 \item lexer (10\%)

   682 \item parser / interpreter (10\%)

   683 \item JVM compiler (15\%)

   684 \item LLVM compiler (25\%) 

   685 \end{itemize}\bigskip\pause

   686 

   687 you can use \alert{any} programming language you like (Haskell, Rust)\\\pause

   688 you can use any code I show you and is uploaded to KEATS\ldots\textbf{BUT NOTHING ELSE!}

   689 

   690 \end{frame}

   691 

   692 

   693 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   694 \begin{frame}[c]

   695 \frametitle{Lectures 1 - 5}

   696 

   697 transforming strings into structured data\\[10mm]

   698 

   699 {\LARGE\bf Lexing} {\hfill{}based on regular expressions}\medskip\\

   700 \hspace{5mm}(recognising ``words'')\\[6mm]

   701 

   702 {\LARGE\bf Parsing}\medskip\\

   703 \hspace{5mm}(recognising ``sentences'')

   704 

   705 \begin{textblock}{1}(10,9.1)

   706 \begin{tabular}{c}

   707 \includegraphics[scale=0.1]{../pics/rosetta.jpg}\\[-2mm]

   708 \footnotesize Stone of Rosetta

   709 \end{tabular}

   710 \end{textblock}

   711 

   712 \end{frame}

   713 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   714 

   715 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   716 \begin{frame}[c]

   717 \frametitle{Lectures 1 - 5}

   718 

   719 transforming strings into structured data\\[10mm]

   720 

   721 {\LARGE\bf Lexing} {\hfill{}based on regular expressions}\medskip\\

   722 \hspace{5mm}(recognising ``words'')\\[6mm]

   723 

   724 {\LARGE\bf Parsing}\medskip\\

   725 \hspace{5mm}(recognising ``sentences'')

   726 

   727 \begin{textblock}{1}(10,9.1)

   728 \begin{tabular}{c}

   729 \includegraphics[scale=0.1]{../pics/rosetta.jpg}\\[-2mm]

   730 \footnotesize Stone of Rosetta

   731 \end{tabular}

   732 \end{textblock}

   733 

   734 \end{frame}

   735 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   736 

   737 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   738 \begin{frame}[c]

   739   \frametitle{Lectures 5 - 10}

   740   

   741   code generation for a small imperative and a small functional language\\[10mm]

   742   

   743   {\LARGE\bf Interpreters}\medskip\\

   744   \hspace{5mm}(directly runs a program)\\[6mm]

   745   

   746   {\LARGE\bf Compilers}\medskip\\

   747   \hspace{5mm}(generate JVM code and LLVM-IR code)

   748   

   749   \begin{textblock}{1}(8.8,8.1)

   750   \begin{tabular}{c@{}c}

   751     \includegraphics[scale=0.4]{../pics/javaduke.png} &

   752     \includegraphics[scale=0.23]{../pics/llvmlogo.png}

   753   \end{tabular}

   754   \end{textblock}

   755   

   756   \end{frame}

   757 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   758   

   759 

   760 

   761 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   762 \begin{frame}[t]

   763 \frametitle{Familiar Regular Expresssions}

   764 \small

   765 \begin{center}

   766 \texttt{[a-z0-9\_$\backslash{}$.-]+ @ [a-z0-9$\backslash{}$.-]+ . [a-z$\backslash{}$.]\{2,6\}}

   767 \end{center}\smallskip

   768 

   769 \begin{center}

   770 \begin{tabular}{@{}lp{8.5cm}@{}}

   771 \pcode{re*} & matches 0 or more times\\

   772 \pcode{re+} & matches 1 or more times\\

   773 \pcode{re?} & matches 0 or 1 times\\

   774 \pcode{re\{n\}}	& matches exactly \pcode{n} number of times\\

   775 \pcode{re\{n,m\}} & matches at least \pcode{n} and at most {\tt m} times\\

   776 \pcode{[...]} & matches any single character inside the brackets\\

   777 \pcode{[^...]} & matches any single character not inside the 

   778 brackets\\

   779 \pcode{a-z A-Z} & character ranges\\

   780 \pcode{\\d} & matches digits; equivalent to \pcode{[0-9]}\\

   781 \pcode{.} & matches every character except newline\\

   782 \pcode{(re)}	& groups regular expressions and remembers 

   783 the matched text

   784 \end{tabular}

   785 \end{center}

   786 

   787 \end{frame}

   788 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   789 {

   790 \setbeamercolor{background canvas}{bg=cream}

   791 \begin{frame}[t]

   792 \frametitle{Notation for REs}

   793 

   794 

   795 

   796   

   797 \end{frame}  

   798 }

   799 

   800 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   801 \begin{frame}[c]

   802 \frametitle{Some ``innocent'' examples}

   803 

   804 Let's try two examples

   805 

   806 \begin{center}

   807   \bl{\texttt{(a*)*b}}

   808   \hspace{2cm}

   809   \bl{\texttt{[a?]\{n\}[a]\{n\}}}

   810 \end{center}\bigskip\pause  

   811 

   812 and match them with strings of the form

   813 

   814 \begin{center}

   815   \bl{\texttt{a}},

   816   \bl{\texttt{aa}},

   817   \bl{\texttt{aaa}},

   818   \bl{\texttt{aaaa}},

   819   \bl{\texttt{aaaaa}},

   820   \bl{$\underbrace{\texttt{a}...\texttt{a}}_n$}  

   821 \end{center}  

   822 

   823 \end{frame}

   824 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%