53 %\end{frame}

    53 % \end{frame}

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

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

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

    64   %\begin{center}

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

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

    64 

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

    65   \begin{itemize}

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

    66   \item did undergraduate in Germany

    68   %\end{center}

    67   \item Master in St Andrews

    69 

    68   \item PhD in Cambridge  

    70   \normalsize

    69   \end{itemize}\bigskip\bigskip

    71   \begin{center}

    70 

    72   \begin{tabular}{ll}

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

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

    72 

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

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

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

    74 \end{frame}

    76   Slides \& Progs: & KEATS\\

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

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

    78   \end{tabular}

    79   \end{center}

    80 

    81   \begin{center}

    82     \begin{tikzpicture}

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

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

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

    86           \cellcolor{blue!50}

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

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

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

    90           4 Lexing, Tokenising               & 9 Optimisations \\

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

    92         \end{tabular}%

    93       };

    94     \end{tikzpicture}

    95   \end{center}

    96 

    97 \end{frame}

    98 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    99 

   100 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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

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

   103 

   104 \begin{center}

   105   \begin{tikzpicture}[scale=1,

   106                       node/.style={

   107                       rectangle,rounded corners=3mm,

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

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

   110 

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

   112 

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

   114   \node [above=5mm of 0]

   115   {\makebox[0mm]{\footnotesize

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

   117      

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

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

   120 

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

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

   123 

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

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

   126 

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

   128   \node [above=5mm of 1]

   129   {\makebox[0mm]{\footnotesize

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

   131 

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

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

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

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

   136   \end{tikzpicture}

   137   \end{center}

   138 

   139 \only<2,3,4>{

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

   141 \begin{bubble}[9.8cm]

   142 \normalsize

   143 lexer input: a string\smallskip\\

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

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

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

   147 \end{bubble}

   148 \end{textblock}} 

   149 

   150 \only<3,4>{

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

   152 \begin{tabular}{c}

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

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

   155 \end{tabular}

   156 \end{textblock}}

   157 

   158 \only<4>{

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

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

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

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

   163 \end{tabular}  

   164 \end{textblock}}

   165 

   166 \only<6>{

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

   168 \begin{bubble}[8.5cm]

   169 \normalsize

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

   171 

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

   173 

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

   175 \footnotesize

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

   177   \node {\code{read}}

   178     child {node {\code{lpar}}}

   179     child {node {\code{n}}}

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

   181 \end{tikzpicture}

   182 \end{bubble}

   183 \end{textblock}}

   184 

   185 \only<8,9>{

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

   187 \begin{bubble}[4cm]

   188 \normalsize

   189 code generation:\smallskip\\

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

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

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

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

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

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

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

   197 \end{bubble}

   198 \end{textblock}}

   199 

   200 \only<9>{

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

   202 \begin{bubble}[5cm]

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

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

   205     xlabel=n,

   206     enlargelimits=0.05,

   207     ybar interval=0.7, legend style=small]

   208 \addplot file {interpreted2.data};

   209 \addplot file {compiled2.data};

   210 %\legend{interpreted, compiled}

   211 \end{axis}

   212 \end{tikzpicture}}

   213 \end{bubble}

   214 \end{textblock}}

   215 

   216 \only<10>{

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

   218   \begin{bubble}[11cm]

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

   220   \begin{tikzpicture}[]

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

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

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

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

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

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

   227 \end{tikzpicture}

   228 \end{bubble}

   229 

   230 \end{textblock}}

   231 \only<11>{

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

   233   \begin{bubble}[11cm]

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

   235   \begin{tikzpicture}[]

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

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

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

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

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

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

   242 \end{tikzpicture}

   243 \end{bubble}

   244 \end{textblock}}

   245 

   246 

   247 \end{frame}

   248 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     

   249 

   250 

   251 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   252 \begin{frame}[t]

   253 \frametitle{Why Study Compilers?}

   254 

   255 

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

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

   258 \smallskip\\

   259 

   260 \begin{bubble}[10.5cm]

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

   262   employment act for solid compiler hackers.''

   263 \end{bubble}

   264 

   265 \onslide<1->{

   266 \only<2>{

   267 \begin{itemize}

   268 \item {\bf Hardware is getting weirder

   269   rather than getting clocked faster.}

   270 

   271 \begin{itemize}

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

   273   like there is increasing asymmetry in resources across cores.

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

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

   276   surface.''

   277 \end{itemize}  

   278 \end{itemize}}

   279 \only<3>{

   280 \begin{itemize}

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

   282     their associated security disasters.}

   283   

   284 \begin{itemize}

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

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

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

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

   289   languages and increasingly wacky platforms.''

   290 \end{itemize}  

   291 \end{itemize}}}

   292 

   293 \end{frame}

   294 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   295 

   296 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   297 {

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

   299 \begin{frame}[c]

   300 

   301 \frametitle{}

   302 \begin{mybox3}{}\it

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

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

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

   306 Source Software group, on AArch64 specific optimisations for the

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

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

   309 \end{mybox3}\pause

   310 

   311 

   312 Student numbers in CFL\medskip\\

   313 \begin{tabular}{ll}

   314 2019: & 32\\  

   315 2020: & 59\\  

   316 2021: & 109\\

   317 2022: & 121\\  

   318 \end{tabular}  

   319 

   320 \end{frame}

   321 }

   322 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   323 

   324 

   325 

   326 

   327 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   328 \begin{frame}[c]

   329 \frametitle{Why Bother with Compilers?}

   330   

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

   332 triple redundancy for potential hardware faults.

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

   334   

   335 They compile 1 Ada program to\medskip

   336   

   337 \begin{itemize}

   338   \item Intel 80486

   339   \item Motorola 68040 (old Macintosh's)

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

   341 \end{itemize}\medskip\medskip

   342   

   343 using 3 independent compilers.\bigskip\pause

   344   

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

   346 

   347 \only<1->{%

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

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

   350 \end{textblock}}

   351 

   352 \end{frame}

   353 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   354 

   355 

   356 

   357 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   358 \begin{frame}[c]

   359 \frametitle{What Do Compilers Do?}

   360 

   361 Remember BF*** from PEP?

   362 

   363 \begin{center}

   364 \begin{tabular}{rcl}

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

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

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

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

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

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

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

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

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

   374 \end{tabular}  

   375 \end{center}  

   376 

   377 \end{frame}

   378 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   379 

   380 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   381 \begin{frame}[c]

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

   383   

   384   \begin{center}

   385   \begin{tabular}{rcl}

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

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

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

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

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

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

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

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

   394                   & $\Rightarrow$ & ignore everything else\\

   395   \end{tabular}  

   396   \end{center}\bigskip  

   397   

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

   399   

   400 \end{frame}

   401 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   402 

   403 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   404 \begin{frame}[c]

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

   406   

   407   \begin{center}

   408   \begin{tabular}{rcl}

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

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

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

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

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

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

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

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

   417                   & $\Rightarrow$ & ignore everything else\\

   418   \end{tabular}  

   419   \end{center}\bigskip  

   420   

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

   422   

   423 \end{frame}

   424 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   425     

   426 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   427 \begin{frame}[t]

   428 \frametitle{A Brief Compiler History}

   429 

   430 \bigskip

   431 \begin{itemize}

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

   433 \item Regular Expressions, 1956\\

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

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

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

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

   438 \end{itemize}

   439 

   440 

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

   442 \begin{flushright}

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

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

   445 

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

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

   448 \end{flushright}

   449 \end{textblock}

   450 

   451 \end{frame}

   452 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     

   453 

   454 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   455 \begin{frame}[c]

   456 \frametitle{Some Housekeeping}

   457 

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

   459 

   460 \begin{itemize}

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

   462 \item five CWs (65\%) 

   463 \end{itemize}\bigskip\bigskip\pause

   464 

   465 

   466 \textbf{Weekly Homework (optional):}

   467 \begin{itemize}

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

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

   470 \end{itemize}  

   471 

   472 \end{frame}

   473 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   474 

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

   476 {

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

   478 \begin{frame}[c]

   479 \frametitle{Homework}

   480 

   481 Last year(s): I did not give out solutions; students sent emails to me and I responded them individually\bigskip\\

   482 

   483 

   484 This year: We will do homework mainly during the Labs (TAs have the solutions)\bigskip\\\pause

   485 

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

   487 some larger amount of deviation.

   488 

   489 \end{frame}

   490 }

   491 

   492 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   493 \begin{frame}[c]

   494 \frametitle{Some Housekeeping}

   495 

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

   497 

   498 \begin{itemize}

   499 \item matcher (5\%)

   500 \item lexer (10\%)

   501 \item parser / interpreter (10\%)

   502 \item JVM compiler (15\%)

   503 \item LLVM compiler (25\%) 

   504 \end{itemize}\bigskip\pause

   505 

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

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

   508 

   509 \end{frame}

   510 

   511 

   512 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   513 \begin{frame}[c]

   514 \frametitle{Lectures 1 - 5}

   515 

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

   517 

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

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

   520 

   521 {\LARGE\bf Parsing}\medskip\\

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

   523 

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

   525 \begin{tabular}{c}

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

   527 \footnotesize Stone of Rosetta

   528 \end{tabular}

   529 \end{textblock}

   530 

   531 \end{frame}

   532 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   533 

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

   535 \begin{frame}[c]

   536 \frametitle{Lectures 1 - 5}

   537 

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

   539 

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

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

   542 

   543 {\LARGE\bf Parsing}\medskip\\

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

   545 

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

   547 \begin{tabular}{c}

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

   549 \footnotesize Stone of Rosetta

   550 \end{tabular}

   551 \end{textblock}

   552 

   553 \end{frame}

   554 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   555 

   556 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   557 \begin{frame}[c]

   558   \frametitle{Lectures 5 - 10}

   559   

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

   561   

   562   {\LARGE\bf Interpreters}\medskip\\

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

   564   

   565   {\LARGE\bf Compilers}\medskip\\

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

   567   

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

   569   \begin{tabular}{c@{}c}

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

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

   572   \end{tabular}

   573   \end{textblock}

   574   

   575   \end{frame}

   576 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   577   

   578 

   579 

   580 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   581 \begin{frame}[t]

   582 \frametitle{Familiar Regular Expresssions}

   583 \small

   584 \begin{center}

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

   586 \end{center}\smallskip

   587 

   588 \begin{center}

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

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

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

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

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

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

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

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

   597 brackets\\

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

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

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

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

   602 the matched text

   603 \end{tabular}

   604 \end{center}

   605 

   606 \end{frame}

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

   608 {

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

   610 \begin{frame}[t]

   611 \frametitle{Notation for REs}

   612 

   613 

   614 

   615   

   616 \end{frame}  

   617 }

   618 

   619 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   620 \begin{frame}[c]

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

   622 

   623 Let's try two examples

   624 

   625 \begin{center}

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

   627   \hspace{2cm}

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

   629 \end{center}\bigskip\pause  

   630 

   631 and match them with strings of the form

   632 

   633 \begin{center}

   634   \bl{\texttt{a}},

   635   \bl{\texttt{aa}},

   636   \bl{\texttt{aaa}},

   637   \bl{\texttt{aaaa}},

   638   \bl{\texttt{aaaaa}},

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

   640 \end{center}  

   641 

   642 \end{frame}

   643 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%