# HG changeset patch # User Christian Urban # Date 1664481242 -3600 # Node ID 771396fa6cc49bb404651e2a7312e57e17142e04 # Parent 49d21814a633317aef4ffd8a08afc91e3a60eb7c updated diff -r 49d21814a633 -r 771396fa6cc4 cws/cw01.pdf Binary file cws/cw01.pdf has changed diff -r 49d21814a633 -r 771396fa6cc4 cws/cw02.pdf Binary file cws/cw02.pdf has changed diff -r 49d21814a633 -r 771396fa6cc4 cws/cw03.pdf Binary file cws/cw03.pdf has changed diff -r 49d21814a633 -r 771396fa6cc4 cws/cw04.pdf Binary file cws/cw04.pdf has changed diff -r 49d21814a633 -r 771396fa6cc4 cws/cw05.pdf Binary file cws/cw05.pdf has changed diff -r 49d21814a633 -r 771396fa6cc4 handouts/ho01.pdf Binary file handouts/ho01.pdf has changed diff -r 49d21814a633 -r 771396fa6cc4 handouts/ho01.tex --- a/handouts/ho01.tex Fri Sep 16 12:52:21 2022 +0100 +++ b/handouts/ho01.tex Thu Sep 29 20:54:02 2022 +0100 @@ -46,6 +46,7 @@ \section*{Handout 1} +$\neq$ The purpose of a compiler is to transform a program a human can read and write into code machines can run as fast as possible. Developing a diff -r 49d21814a633 -r 771396fa6cc4 hws/hw01.pdf Binary file hws/hw01.pdf has changed diff -r 49d21814a633 -r 771396fa6cc4 hws/hw01.tex --- a/hws/hw01.tex Fri Sep 16 12:52:21 2022 +0100 +++ b/hws/hw01.tex Thu Sep 29 20:54:02 2022 +0100 @@ -2,6 +2,11 @@ \documentclass{article} \usepackage{../style} +\newcommand{\solution}[1]{% + \begin{quote}\sf% + #1% + \end{quote}} + \begin{document} \section*{Homework 1} @@ -47,11 +52,21 @@ strings and languages. In the context of the CFL-course, what is meant by the term \emph{language}? + \solution{A language - in this context - is just a set of + strings. Some of these sets can actually not be described by + regular expressions. Only regular​ languages can. This is + something for lecture 3.} + \item Give the definition for regular expressions---this is an inductive datatype. What is the meaning of a regular expression? (Hint: The meaning is defined recursively.) + \solution{Here I would also expect the grammar for basic regular + expressions and the definition of the recursive L-function. Discuss + differences between $r_1 + r_2$ and $r^+$. Discuss differences between + ``real-life regexes'' and regexes in this module.} + \item Assume the concatenation operation of two strings is written as $s_1 @ s_2$. Define the operation of \emph{concatenating} two sets of strings. This operation @@ -59,24 +74,38 @@ this definition, what is $A \,@\, \{\}$ equal to? Is in general $A\,@\,B$ equal to $B\,@\,A$? + \solution{ What is $A @ {[]}$? Are there special cases + where $A @ B = B @ A$? } + \item Assume a set $A$ contains 4 strings and a set $B$ contains 7 strings. None of the strings is the empty string. How many strings are in $A \,@\, B$? + \solution{28, but there are corner cases where there are fewer + than 28 elements. Can students think of such corner cases? + For example $A = \{a, ab, \ldots\}$, $B = \{bc, c,\ldots\}$ } + \item How is the power of a language defined? (Hint: There are two rules, one for $\_^0$ and one for $\_^{n+1}$.) + \solution{Two rules: 0-case and n+1 case.} + \item Let $A = \{[a], [b], [c], [d]\}$. (1) How many strings are in $A^4$? (2) Consider also the case of $A^4$ where one of the strings in $A$ is the empty string, for example $A = \{[a], [b], [c], []\}$. + \solution{121 is correct. But make sure you understand why it is 121 + in cases you do not have a computer at your fingertips.} + \item (1) How many basic regular expressions are there to match \textbf{only} the string $abcd$? (2) How many if they cannot include $\ONE$ and $\ZERO$? (3) How many if they are also not allowed to contain stars? (4) How many if they are also not allowed to contain $\_ + \_$? + \solution{1-3 are infinite (tell the idea why - examples); 4 is five - remember regexes are trees.} + \item When are two regular expressions equivalent? Can you think of instances where two regular expressions match the same strings, but it is not so obvious that they do? @@ -84,9 +113,14 @@ obviously match the same strings, namely $[a]$ and $[b]$. + \solution{for example $r^* = 1 + r \cdot r^*$ for any regular expression $r$. + Can students think about why this is the case?} + \item What is meant by the notions \emph{evil regular expressions} and by \emph{catastrophic backtracking}? + \solution{catastrophic backtracking also applies to other regexes, not just $(a^*)^*b$} + \item Given the regular expression $(a + b)^* \cdot b \cdot (a + b)^*$, which of the following regular expressions are equivalent @@ -97,6 +131,8 @@ 3) & $(a + b)^* \cdot (a + b) \cdot (a + b)^*$ % no \end{tabular} \end{center} + + \solution{no, yes (why?), no.} \item \POSTSCRIPT diff -r 49d21814a633 -r 771396fa6cc4 hws/hw08.pdf Binary file hws/hw08.pdf has changed diff -r 49d21814a633 -r 771396fa6cc4 hws/hw08.tex --- a/hws/hw08.tex Fri Sep 16 12:52:21 2022 +0100 +++ b/hws/hw08.tex Thu Sep 29 20:54:02 2022 +0100 @@ -1,5 +1,6 @@ \documentclass{article} \usepackage{../style} +\usepackage{../langs} \usepackage{../graphics} \begin{document} @@ -18,6 +19,22 @@ \item What is the main difference between the Java assembler (as processed by Jasmin) and Java Byte Code? +\item Consider the following Scala snippet. Are the two functions +\texttt{is\_even} and \texttt{is\_odd} tail-recursive? + +\begin{lstlisting}[numbers=none] +def iseven(n: Int) : Boolean = { + if (n == 0) true else isodd(n - 1) +} + +def isodd(n: Int) : Boolean = { + if (n == 0) false + else if (n == 1) true else iseven(n - 1) +} +\end{lstlisting} + +Do they cause stack-overflows when compiled to the JVM (for example by Scala)? + \item Explain what is meant by the terms lazy evaluation and eager evaluation. diff -r 49d21814a633 -r 771396fa6cc4 slides/slides01.pdf Binary file slides/slides01.pdf has changed diff -r 49d21814a633 -r 771396fa6cc4 slides/slides01.tex --- a/slides/slides01.tex Fri Sep 16 12:52:21 2022 +0100 +++ b/slides/slides01.tex Thu Sep 29 20:54:02 2022 +0100 @@ -1,1752 +1,1755 @@ -% !TEX program = xelatex -\documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer} -\usepackage{../slides} -\usepackage{../graphicss} -\usepackage{../langs} -\usepackage{../data} - -\usepackage{tcolorbox} -\newtcolorbox{mybox}{colback=red!5!white,colframe=red!75!black} -\newtcolorbox{mybox2}[1]{colback=red!5!white,colframe=red!75!black,fonttitle=\bfseries,title=#1} -\newtcolorbox{mybox3}[1]{colback=Cyan!5!white,colframe=Cyan!75!black,fonttitle=\bfseries,title=#1} - - - -\hfuzz=220pt - -\lstset{language=Scala, - style=mystyle, - numbersep=0pt, - numbers=none, - xleftmargin=0mm} - -\newcommand{\bl}[1]{\textcolor{blue}{#1}} - -% beamer stuff -\renewcommand{\slidecaption}{CFL 01, King's College London} - -%% https://cs.rit.edu/~hh/teaching/_media/cc18/lectures/lect1/main.pdf -%% https://cs.rit.edu/~hh/teaching/_media/cc18/lectures/lect2/main.pdf -%% https://cs.rit.edu/~hh/teaching/_media/cc18/lectures/lect3/main.pdf - -\begin{document} - -%\begin{frame}[t] -% -%\begin{mybox} -%A physical explanation the \emph{dynamic matrix}\\ -%lots of text -%\end{mybox} - - -%\begin{mybox2}{Test} -%A physical explanation the \emph{dynamic matrix}\\ -%lots of text -%\end{mybox2} - -%\begin{mybox3}{Test} -%A physical explanation the \emph{dynamic matrix}\\ -%lots of text -%\end{mybox3} -%\end{frame} - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[t] -\frametitle{% - \begin{tabular}{@ {}c@ {}} - \\[-3mm] - \LARGE Compilers and \\[-1mm] - \LARGE Formal Languages\\[-3mm] - \end{tabular}} - - \begin{center} - %\includegraphics[scale=0.3]{pics/ante1.jpg}\hspace{5mm} - %\includegraphics[scale=0.31]{pics/ante2.jpg}\\ - %\footnotesize\textcolor{gray}{Antikythera automaton, 100 BC (Archimedes?)} - \end{center} - - \normalsize - \begin{center} - \begin{tabular}{ll} - Email: & christian.urban at kcl.ac.uk\\ - %Office Hours: & Thursdays 12 -- 14\\ - %Location: & N7.07 (North Wing, Bush House)\\ - Slides \& Progs: & KEATS\\ - \end{tabular} - \end{center} - - \begin{center} - \begin{tikzpicture} - \node[drop shadow,fill=white,inner sep=0pt] - {\footnotesize\rowcolors{1}{capri!10}{white} - \begin{tabular}{|p{4.8cm}|p{4.8cm}|}\hline - \cellcolor{blue!50} - 1 Introduction, Languages & 6 While-Language \\ - 2 Regular Expressions, Derivatives & 7 Compilation, JVM \\ - 3 Automata, Regular Languages & 8 Compiling Functional Languages \\ - 4 Lexing, Tokenising & 9 Optimisations \\ - 5 Grammars, Parsing & 10 LLVM \\ \hline - \end{tabular}% - }; - \end{tikzpicture} - \end{center} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}<1-12>[c] -\frametitle{The Goal of this Module\ldots} - -\begin{center} - \begin{tikzpicture}[scale=1, - node/.style={ - rectangle,rounded corners=3mm, - very thick,draw=black!50,minimum height=18mm, minimum width=20mm, - top color=white,bottom color=black!20,drop shadow}] - - \node at (3.05, 1.8) {\Large\bf \ldots{} you write a compiler}; - - \node (0) at (-2.3,0) {}; - \node [above=5mm of 0] - {\makebox[0mm]{\footnotesize - \begin{tabular}{@{}l@{}}input\\[-1mm]program\end{tabular}}}; - - \node (A) at (0,0) [node] {}; - \node [below right] at (A.north west) {lexer}; - - \node (B) at (3,0) [node] {}; - \node [below right=1mm] at (B.north west) {\mbox{}\hspace{-1mm}parser}; - - \node (C) at (6,0) [node] {}; - \node [below right] at (C.north west) {\mbox{}\hspace{-1mm}code gen}; - - \node (1) at (8.4,0) {}; - \node [above=5mm of 1] - {\makebox[0mm]{\footnotesize - \begin{tabular}{@{}r@{}}binary\\[-1mm]code\end{tabular}}}; - - \draw [->,line width=4mm] (0) -- (A); - \draw [->,line width=4mm] (A) -- (B); - \draw [->,line width=4mm] (B) -- (C); - \draw [->,line width=4mm] (C) -- (1); - \end{tikzpicture} - \end{center} - -\only<2,3,4>{ -\begin{textblock}{1}(1,2.1) -\begin{bubble}[9.8cm] -\normalsize -lexer input: a string\smallskip\\ -\hspace{5mm}\code{"read(n);"}\medskip\\ -lexer output: a sequence of tokens\smallskip\\ -\hspace{5mm}\code{key(read) lpar id(n) rpar semi} -\end{bubble} -\end{textblock}} - -\only<3,4>{ -\begin{textblock}{1}(6,7.8) -\begin{tabular}{c} -\includegraphics[scale=0.2]{../pics/rosetta.jpg}\\[-2mm] -\footnotesize lexing $\Rightarrow$ recognising words (Stone of Rosetta) -\end{tabular} -\end{textblock}} - -\only<4>{ -\begin{textblock}{1}(0.5,12)\small -\begin{tabular}{l@{}c@{}l} - \pcode{if} & $\;\Rightarrow\;$ & keyword\\ - \pcode{iffoo} & $\;\Rightarrow\;$ & identifier\\ -\end{tabular} -\end{textblock}} - -\only<6>{ -\begin{textblock}{1}(1,1.5) -\begin{bubble}[8.5cm] -\normalsize -parser input: a sequence of tokens\smallskip\\ - -{\small\hspace{5mm}\code{key(read) lpar id(n) rpar semi}}\smallskip\\ - -parser output: an abstract syntax tree\smallskip\\ -\footnotesize -\hspace{2cm}\begin{tikzpicture} - \node {\code{read}} - child {node {\code{lpar}}} - child {node {\code{n}}} - child {node {\code{rpar}}}; -\end{tikzpicture} -\end{bubble} -\end{textblock}} - -\only<8,9>{ -\begin{textblock}{1}(1,1.5) -\begin{bubble}[4cm] -\normalsize -code generation:\smallskip\\ -\hspace{5mm}\code{istore 2}\\ -\hspace{5mm}\code{iload 2}\\ -\hspace{5mm}\code{ldc 10}\\ -\hspace{5mm}\code{isub}\\ -\hspace{5mm}\code{ifeq Label2}\\ -\hspace{5mm}\code{iload 2}\\ -\hspace{5mm}\code{...}\\ -\end{bubble} -\end{textblock}} - -\only<9>{ -\begin{textblock}{6}(8.4,7) -\begin{bubble}[5cm] -\mbox{\begin{tikzpicture}[scale=0.58,rounded corners=0mm] -\begin{axis}[axis x line=bottom, axis y line=left, ylabel=secs, - xlabel=n, - enlargelimits=0.05, - ybar interval=0.7, legend style=small] -\addplot file {interpreted2.data}; -\addplot file {compiled2.data}; -%\legend{interpreted, compiled} -\end{axis} -\end{tikzpicture}} -\end{bubble} -\end{textblock}} - -\only<10>{ -\begin{textblock}{6}(1,3) - \begin{bubble}[11cm] - Compiler explorers, e.g.: \url{https://gcc.godbolt.org} \;\video{https://youtu.be/ysaBmhMEyUg} - \begin{tikzpicture}[] - \node (0) at (-2.3,0) {\includegraphics[scale=0.3]{pics/csource.png}}; - \node (1) [right=35mm] at (0) {\includegraphics[scale=0.3]{pics/cassmbl.png}}; - \draw [->,line width=4mm, red] (0) -- (1); - \node (2) [below=20mm] at (0) {\LARGE\bf source}; - \node (3) [right=40mm] at (2) {\LARGE\bf binary}; - \draw [->,line width=1mm] (2) -- (3); -\end{tikzpicture} -\end{bubble} - -\end{textblock}} -\only<11>{ -\begin{textblock}{6}(1,3) - \begin{bubble}[11cm] - Compiler explorer for Java: \url{https://javap.yawk.at} - \begin{tikzpicture}[] - \node (0) at (-2.3,0) {\includegraphics[scale=0.4]{pics/jsource.png}}; - \node (1) [right=35mm] at (0) {\includegraphics[scale=0.4]{pics/jassmbl.png}}; - \draw [->,line width=4mm, red] (0) -- (1); - \node (2) [below=20mm] at (0) {\LARGE\bf source}; - \node (3) [right=40mm] at (2) {\LARGE\bf byte code}; - \draw [->,line width=1mm] (2) -- (3); -\end{tikzpicture} -\end{bubble} -\end{textblock}} - - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[t] -\frametitle{Why Study Compilers?} - - -John Regehr {\small(Univ.~Utah, LLVM compiler hacker)} -\here{https://blog.regehr.org/archives/1419} -\smallskip\\ - -\begin{bubble}[10.5cm] - \bf ``\ldots{}It’s effectively a perpetual - employment act for solid compiler hackers.'' -\end{bubble} - -\onslide<1->{ -\only<2>{ -\begin{itemize} -\item {\bf Hardware is getting weirder - rather than getting clocked faster.} - -\begin{itemize} -\item[] ``Almost all processors are multicores nowadays and it looks - like there is increasing asymmetry in resources across cores. - Processors come with vector units, crypto accelerators etc. We have - DSPs, GPUs, ARM big.little, and Xeon Phi. This is only scratching the - surface.'' -\end{itemize} -\end{itemize}} -\only<3>{ -\begin{itemize} -\item {\bf We’re getting tired of low-level languages and - their associated security disasters.} - -\begin{itemize} -\item [] ``We want to write new code, to whatever extent possible, in - safer, higher-level languages. Compilers are caught right in the - middle of these opposing trends: one of their main jobs is to help - bridge the large and growing gap between increasingly high-level - languages and increasingly wacky platforms.'' -\end{itemize} -\end{itemize}}} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{Why Bother with Compilers?} - -\textbf{Boeing 777's}: First flight in 1994. They want to achieve -triple redundancy for potential hardware faults. -\here{http://www.citemaster.net/get/db3a81c6-548e-11e5-9d2e-00163e009cc7/R8.pdf}\bigskip - -They compile 1 Ada program to\medskip - -\begin{itemize} - \item Intel 80486 - \item Motorola 68040 (old Macintosh's) - \item AMD 29050 (RISC chips used often in laser printers) -\end{itemize}\medskip\medskip - -using 3 independent compilers.\bigskip\pause - -\small Airbus uses C and static analysers. Recently started using CompCert. - -\only<1->{% -\begin{textblock}{6}(8,4.5) -\includegraphics[scale=0.28]{../pics/777.png} -\end{textblock}} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{What Do Compilers Do?} - -Remember BF*** from PEP? - -\begin{center} -\begin{tabular}{rcl} -\bl{\texttt{>}} & $\Rightarrow$ & move one cell right\\ -\bl{\texttt{<}} & $\Rightarrow$ & move one cell left\\ -\bl{\texttt{+}} & $\Rightarrow$ & increase cell by one\\ -\bl{\texttt{-}} & $\Rightarrow$ & decrease cell by one\\ -\bl{\texttt{.}} & $\Rightarrow$ & print current cell\\ -\bl{\texttt{,}} & $\Rightarrow$ & input current cell\\ -\bl{\texttt{[}} & $\Rightarrow$ & loop begin\\ -\bl{\texttt{]}} & $\Rightarrow$ & loop end\medskip\\ - & $\Rightarrow$ & everything else is a comment\\ -\end{tabular} -\end{center} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] - \frametitle{A ``Compiler'' for BF*** to C} - - \begin{center} - \begin{tabular}{rcl} - \bl{\texttt{>}} & $\Rightarrow$ & \texttt{ptr++}\\ - \bl{\texttt{<}} & $\Rightarrow$ & \texttt{ptr--}\\ - \bl{\texttt{+}} & $\Rightarrow$ & \texttt{(*ptr)++}\\ - \bl{\texttt{-}} & $\Rightarrow$ & \texttt{(*ptr)--}\\ - \bl{\texttt{.}} & $\Rightarrow$ & \texttt{putchar(*ptr)}\\ - \bl{\texttt{,}} & $\Rightarrow$ & \texttt{*ptr = getchar()}\\ - \bl{\texttt{[}} & $\Rightarrow$ & \texttt{while(*ptr)\{}\\ - \bl{\texttt{]}} & $\Rightarrow$ & \texttt{\}}\medskip\\ - & $\Rightarrow$ & ignore everything else\\ - \end{tabular} - \end{center}\bigskip - - \texttt{char field[30000]\\ char *ptr = \&field[15000]} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] - \frametitle{Another~``Compiler''~for~BF~to~C} - - \begin{center} - \begin{tabular}{rcl} - \bl{\texttt{>\ldots>}} & $\Rightarrow$ & \texttt{ptr += n}\\ - \bl{\texttt{<\ldots<}} & $\Rightarrow$ & \texttt{ptr -= n}\\ - \bl{\texttt{+\ldots+}} & $\Rightarrow$ & \texttt{(*ptr) += n}\\ - \bl{\texttt{-\ldots-}} & $\Rightarrow$ & \texttt{(*ptr) -= n}\\ - \bl{\texttt{.}} & $\Rightarrow$ & \texttt{putchar(*ptr)}\\ - \bl{\texttt{,}} & $\Rightarrow$ & \texttt{*ptr = getchar()}\\ - \bl{\texttt{[}} & $\Rightarrow$ & \texttt{while(*ptr)\{}\\ - \bl{\texttt{]}} & $\Rightarrow$ & \texttt{\}}\medskip\\ - & $\Rightarrow$ & ignore everything else\\ - \end{tabular} - \end{center}\bigskip - - \texttt{char field[30000]\\ char *ptr = \&field[15000]} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[t] -\frametitle{A Brief Compiler History} - -\bigskip -\begin{itemize} -\item Turing Machines, 1936 (a tape as memory) -\item Regular Expressions, 1956\\ -\item The first compiler for COBOL, 1957\\ (Grace Hopper)\medskip -\item But surprisingly research papers are still published nowadays\\ -\item ``Parsing: The Solved Problem That Isn't'' - \here{https://tratt.net/laurie/blog/entries/parsing_the_solved_problem_that_isnt.html} -\end{itemize} - - -\begin{textblock}{8.5}(5,7.6) -\begin{flushright} -\includegraphics[scale=0.3]{pics/hopper.jpg}\\ -\footnotesize\textcolor{gray}{Grace Hopper}\smallskip\\ - -{\small\textcolor{gray}{(she made it to David Letterman's Tonight Show - \here{https://youtu.be/3N_ywhx6_K0?t=31})}} -\end{flushright} -\end{textblock} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{Some Housekeeping} - -\textbf{Exam will be online:}\bigskip - -\begin{itemize} -\item final exam in January (35\%) -\item five CWs (65\%) -\end{itemize}\bigskip\bigskip\pause - - -\textbf{Weekly Homework (optional):} -\begin{itemize} -\item uploaded on KEATS, send answers via email, (try to!) respond individually -\item \alert{\bf all} questions in the exam will be from the HWs!! -\end{itemize} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{Some Housekeeping} - -\textbf{Coursework (5 accounting for 65\%):}\bigskip - -\begin{itemize} -\item matcher (5\%) -\item lexer (10\%) -\item parser / interpreter (10\%) -\item JVM compiler (15\%) -\item LLVM compiler (25\%) -\end{itemize}\bigskip\pause - -you can use \alert{any} programming language you like (Haskell, Rust)\\\pause -you can use any code I show you and is uploaded to KEATS\ldots\textbf{BUT NOTHING ELSE!} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{Lectures 1 - 5} - -transforming strings into structured data\\[10mm] - -{\LARGE\bf Lexing} {\hfill{}based on regular expressions}\medskip\\ -\hspace{5mm}(recognising ``words'')\\[6mm] - -{\LARGE\bf Parsing}\medskip\\ -\hspace{5mm}(recognising ``sentences'') - -\begin{textblock}{1}(10,9.1) -\begin{tabular}{c} -\includegraphics[scale=0.1]{../pics/rosetta.jpg}\\[-2mm] -\footnotesize Stone of Rosetta -\end{tabular} -\end{textblock} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{Lectures 1 - 5} - -transforming strings into structured data\\[10mm] - -{\LARGE\bf Lexing} {\hfill{}based on regular expressions}\medskip\\ -\hspace{5mm}(recognising ``words'')\\[6mm] - -{\LARGE\bf Parsing}\medskip\\ -\hspace{5mm}(recognising ``sentences'') - -\begin{textblock}{1}(10,9.1) -\begin{tabular}{c} -\includegraphics[scale=0.1]{../pics/rosetta.jpg}\\[-2mm] -\footnotesize Stone of Rosetta -\end{tabular} -\end{textblock} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] - \frametitle{Lectures 5 - 10} - - code generation for a small imperative and a small functional language\\[10mm] - - {\LARGE\bf Interpreters}\medskip\\ - \hspace{5mm}(directly runs a program)\\[6mm] - - {\LARGE\bf Compilers}\medskip\\ - \hspace{5mm}(generate JVM code and LLVM-IR code) - - \begin{textblock}{1}(8.8,8.1) - \begin{tabular}{c@{}c} - \includegraphics[scale=0.4]{../pics/javaduke.png} & - \includegraphics[scale=0.23]{../pics/llvmlogo.png} - \end{tabular} - \end{textblock} - - \end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[t] -\frametitle{Familiar Regular Expresssions} -\small -\begin{center} -\texttt{[a-z0-9\_$\backslash{}$.-]+ @ [a-z0-9$\backslash{}$.-]+ . [a-z$\backslash{}$.]\{2,6\}} -\end{center}\smallskip - -\begin{center} -\begin{tabular}{@{}lp{8.5cm}@{}} -\pcode{re*} & matches 0 or more times\\ -\pcode{re+} & matches 1 or more times\\ -\pcode{re?} & matches 0 or 1 times\\ -\pcode{re\{n\}} & matches exactly \pcode{n} number of times\\ -\pcode{re\{n,m\}} & matches at least \pcode{n} and at most {\tt m} times\\ -\pcode{[...]} & matches any single character inside the brackets\\ -\pcode{[^...]} & matches any single character not inside the -brackets\\ -\pcode{a-z A-Z} & character ranges\\ -\pcode{\\d} & matches digits; equivalent to \pcode{[0-9]}\\ -\pcode{.} & matches every character except newline\\ -\pcode{(re)} & groups regular expressions and remembers -the matched text -\end{tabular} -\end{center} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{Some ``innocent'' examples} - -Let's try two examples - -\begin{center} - \bl{\texttt{(a*)*b}} - \hspace{2cm} - \bl{\texttt{[a?]\{n\}[a]\{n\}}} -\end{center}\bigskip\pause - -and match them with strings of the form - -\begin{center} - \bl{\texttt{a}}, - \bl{\texttt{aa}}, - \bl{\texttt{aaa}}, - \bl{\texttt{aaaa}}, - \bl{\texttt{aaaaa}}, - \bl{$\underbrace{\texttt{a}...\texttt{a}}_n$} -\end{center} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{Why Bother with Regexes?} - -\begin{columns}[t,onlytextwidth] -\begin{column}{1.8cm} -\mbox{} -\end{column} -\begin{column}{.5\textwidth} -\small{}Ruby, Python, Java 8\medskip\\ -\begin{tikzpicture}\footnotesize -\begin{axis}[ - xlabel={$n$}, - x label style={at={(1.05,0.0)}}, - ylabel={time in secs}, - enlargelimits=false, - xtick={0,5,...,30}, - xmax=33, - ymax=35, - ytick={0,5,...,30}, - scaled ticks=false, - axis lines=left, - width=\textwidth, - height=4cm, - legend entries={Python,Ruby}, - legend pos=north west, - legend cell align=left] -\addplot[blue,mark=*, mark options={fill=white}] table {re-python.data}; -\addplot[brown,mark=triangle*, mark options={fill=white}] table {re-ruby.data}; -\end{axis} -\end{tikzpicture} -\begin{tikzpicture}\footnotesize -\begin{axis}[ - xlabel={$n$}, - x label style={at={(1.05,0.0)}}, - ylabel={time in secs}, - enlargelimits=false, - xtick={0,5,...,30}, - xmax=33, - ymax=35, - ytick={0,5,...,30}, - scaled ticks=false, - axis lines=left, - width=\textwidth, - height=4cm, - legend entries={Python, Java 8, JavaScript, Swift}, - legend pos=north west, - legend cell align=left] -\addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data}; -\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data}; -\addplot[red,mark=*, mark options={fill=white}] table {re-js.data}; -\addplot[magenta,mark=*, mark options={fill=white}] table {re-swift.data}; -\end{axis} -\end{tikzpicture} -% -\end{column} -\begin{column}{.5\textwidth} -\small{}Us (after next lecture)\medskip\\ -\begin{tikzpicture}\footnotesize -\begin{axis}[ - xlabel={$n$}, - x label style={at={(1.07,0.0)}}, - ylabel={time in secs}, - enlargelimits=false, - xtick={0,5000,...,10000}, - xmax=11000, - ymax=35, - ytick={0,5,...,30}, - scaled ticks=false, - axis lines=left, - width=\textwidth, - height=4cm] -\addplot[green,mark=square*,mark options={fill=white}] table {re2.data}; -\addplot[black,mark=square*,mark options={fill=white}] table {re3.data}; -\end{axis} -\end{tikzpicture} -\begin{tikzpicture}\footnotesize -\begin{axis}[ - xlabel={$n$}, - x label style={at={(1.07,0.0)}}, - ylabel={time in secs}, - enlargelimits=false, - ymax=35, - ytick={0,5,...,30}, - scaled ticks=false, - axis lines=left, - width=\textwidth, - height=4cm] -\addplot[black,mark=square*,mark options={fill=white}] table {re3a.data}; -\end{axis} -\end{tikzpicture} -\end{column} -\end{columns} -\medskip - -\begin{textblock}{3}(-0.1,3.3) -\small\hfill\bl{\texttt{[a?]\{n\}[a]\{n\}}}: -\end{textblock} - -\begin{textblock}{3}(-0.1,8.7) -\small\hfill\bl{\texttt{(a*)*b}}: -\end{textblock} - -\begin{textblock}{3}(0.3,13) -\small{}matching with strings -\bl{$\underbrace{\texttt{a}...\texttt{a}}_n$} -\end{textblock} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c,fragile] - \frametitle{Incidents} - - \begin{itemize} - \item a global outage on 2 July 2019 at \textbf{Cloudflare} - (first one for six years)\medskip - - \begin{center}\small\color{blue} - \begin{verbatim} - (?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false| - null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s - |-|~|!|{}|\|\||\+)*.*(?:.*=.*))) - \end{verbatim} - \end{center}\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip - - \item on 20 July 2016 the \textbf{Stack Exchange} webpage went down - because of an evil regular expression - \here{https://stackstatus.net/post/147710624694/outage-postmortem-july-20-2016} - \end{itemize} - - \begin{textblock}{6}(6,7.6) - \includegraphics[scale=0.14]{../pics/cloudflare.png}\\ - \footnotesize - It serves more web traffic than Twitter, Amazon, Apple, - Instagram, Bing \& Wikipedia combined. - \here{https://blog.cloudflare.com/details-of-the-cloudflare-outage-on-july-2-2019/} - \end{textblock} - - \end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{Evil Regular Expressions} - -\begin{itemize} -\item \alert{R}egular \alert{e}xpression \alert{D}enial \alert{o}f \alert{S}ervice (ReDoS)\medskip -\item Some evil regular expressions:\medskip -\begin{itemize} -\item \bl{\texttt{[a?]\{n\}\;[a]\{n\}}} -\item \bl{\texttt{(a*)*\;b}} -\item \bl{\texttt{([a-z]+)*}} -\item \bl{\texttt{(a + aa)*}} -\item \bl{\texttt{(a + a?)*}} -\end{itemize} - -\item sometimes also called \alert{catastrophic backtracking} -\item this is a problem for \alert{N}etwork \alert{I}ntrusion - \alert{D}etection systems, Cloudflare, StackExchange, Atom editor -\item \url{https://vimeo.com/112065252} -\end{itemize} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%\begin{frame}[c] -%\frametitle{Today} -% -%\begin{itemize} -%\item While the ultimate goal is to implement a small compiler for the JVM -% \ldots\bigskip -%\end{itemize} -% -%Let's start with: -% -%\begin{itemize} -%\item a web-crawler -%\item an email harvester -%\item \textcolor{gray}{(a web-scraper)} -%\end{itemize} -% -%\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%\begin{frame}[t] -%\frametitle{A Web-Crawler} -% -%\mbox{}\\[10mm] -% -%\begin{enumerate} -%\item given an URL, read the corresponding webpage -%\item extract all links from it -%\item call the web-crawler again for all these links -%\end{enumerate} -% -%\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%\begin{frame}[t] -%\frametitle{A Web-Crawler} -% -%\mbox{}\\[10mm] -% -% -%\begin{enumerate} -%\item given an URL, read the corresponding webpage -%\item if not possible print, out a problem -%\item if possible, extract all links from it -%\item call the web-crawler again for all these links -%\end{enumerate}\bigskip\pause -% -%\small (we need a bound for the number of recursive calls) -% -%\small (the purpose is to check all links on my own webpage) -%\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%\begin{frame}[c] -% -%\begin{textblock}{1}(2,5) -%\begin{tabular}{c} -%\includegraphics[scale=0.15]{pics/servers.png}\\[-2mm] -%\small Server -%\end{tabular} -%\end{textblock} -% -%\begin{textblock}{1}(5.6,4) -% \begin{tikzpicture}[scale=1.1] -% \draw[white] (0,1) node (X) {}; -% \draw[white] (2,1) node (Y) {}; -% \draw[white] (0,0) node (X1) {}; -% \draw[white] (2,0) node (Y1) {}; -% \draw[white] (0,-1) node (X2) {}; -% \draw[white] (2,-1) node (Y2) {}; -% \draw[red, <-, line width = 2mm] (X) -- (Y); -% \node [inner sep=5pt,label=above:\textcolor{black}{GET request}] at ($ (X)!.5!(Y) $) {}; -% \draw[red, ->, line width = 2mm] (X1) -- (Y1); -% \node [inner sep=5pt,label=above:\textcolor{black}{webpage}] at ($ (X1)!.5!(Y1) $) {}; -% \draw[red, <-, line width = 2mm] (X2) -- (Y2); -% \node [inner sep=7pt,label=above:\textcolor{black}{POST data}] at ($ (X2)!.5!(Y2) $) {}; -% \end{tikzpicture} -%\end{textblock} -% -% -%\begin{textblock}{1}(9,5.5) -%\begin{tabular}{c} -%\includegraphics[scale=0.15]{pics/laptop.png}\\[-2mm] -%\small Browser -%\end{tabular} -%\end{textblock} -%\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%\begin{frame}[c] -%\frametitle{Scala} -% -%\small A simple Scala function for reading webpages: -%\bigskip -% -%\footnotesize -%\lstinputlisting{../progs/app0.scala} -%\medskip\pause -% -%\lstinline{get_page("""https://nms.kcl.ac.uk/christian.urban/""")} -%\bigskip\medskip\pause -% -% -%\small A slightly more complicated version for handling errors: -%\smallskip -% -%\footnotesize -%\lstinputlisting[xleftmargin=-4mm]{../progs/app1.scala} -% -% -%\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%\begin{frame}[t] -%\frametitle{A Regular Expression} -% -%\begin{itemize} -%\item \ldots{} is a pattern or template for specifying strings -%\end{itemize}\bigskip -% -%\begin{center} -%\only<1>{\scode{"https?://[^"]*"}}% -%\only<2>{\scode{""""https?://[^"]*"""".r}} -%\end{center}\bigskip\bigskip -% -%matches for example\smallskip\\ -%\hspace{2mm}\code{"http://www.foobar.com"}\\ -%\hspace{2mm}\code{"https://www.tls.org"}\smallskip\\ -% -%but not\smallskip\\ -%\hspace{2mm}\code{"http://www."foo"bar.com"}\\ -% -%\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%\begin{frame}[c] -%\frametitle{Finding Operations in Scala} -% -%{\bf\code{rexp.findAllIn(string)}}\medskip -% -%returns a list of all (sub)strings that match the -%regular expression -%\bigskip\bigskip -% -% -%{\bf\code{rexp.findFirstIn(string)}}\medskip -% -%returns either -% -%\begin{itemize} -%\item \code{None} if no (sub)string matches or -%\item \code{Some(s)} with the first (sub)string -%\end{itemize} -% -%\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%\begin{frame}[c] -% -%\footnotesize -%\lstinputlisting{../progs/app2.scala} -% -%\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%\begin{frame}[c] -% -%\small -%A version that only crawls links in ``my'' domain:\bigskip -% -%\footnotesize -%\lstinputlisting{../progs/app3.scala} -% -%\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%\begin{frame}[c] -%\lstset{xleftmargin=-4mm} -%\small -%A little email harvester: -% -%\footnotesize -%\lstinputlisting{../progs/app4.scala}\bigskip -% -%\tiny -%\url{http://net.tutsplus.com/tutorials/other/8-regular-expressions-you-should-know/} -% -%\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[t] -\frametitle{(Basic) Regular Expressions} - -Their inductive definition: - - -\begin{textblock}{6}(2,7.5) - \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l} - \bl{$r$} & \bl{$::=$} & \bl{$\ZERO$} & nothing\\ - & \bl{$\mid$} & \bl{$\ONE$} & empty string / \pcode{""} / $[]$\\ - & \bl{$\mid$} & \bl{$c$} & character\\ - & \bl{$\mid$} & \bl{$r_1 + r_2$} & alternative / choice\\ - & \bl{$\mid$} & \bl{$r_1 \cdot r_2$} & sequence\\ - & \bl{$\mid$} & \bl{$r^*$} & star (zero or more)\\ - \end{tabular} - \end{textblock} - - -\only<2->{\footnotesize -\begin{textblock}{9}(2,0.5) -\begin{bubble}[9.8cm] -\lstinputlisting{../progs/app01.scala} -\end{bubble} -\end{textblock}} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%\begin{frame}[t] -%\frametitle{Regular Expressions} -% -%\small -%In Scala:\bigskip -% -%\footnotesize -%\lstinputlisting{../progs/app51.scala} -% -% -%\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[t] -\frametitle{Strings} - -\ldots are lists of characters. For example \code{"hello"} - -\begin{center} -\bl{$[h, e, l, l, o]$} or just \bl{$hello$} -\end{center} - -the empty string: \bl{$[]$} or \bl{\pcode{""}}\bigskip\\ - -the concatenation of two strings: - -\begin{center} -\bl{$s_1 \,@\, s_2$} -\end{center} - -\bl{\textit{foo $@$ bar = foobar}}\\ -\bl{\textit{baz $@\, []$ = baz}} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{Languages, Strings} - -\begin{itemize} -\item \alert{\bf Strings} are lists of characters, for example -\begin{center} -\bl{$[]$},\;\bl{$abc$} \hspace{2cm}(Pattern match: \bl{$c\!::\!s$}) -\end{center}\bigskip - - -\item A \alert{\bf language} is a set of strings, for example\medskip -\begin{center} -\bl{$\{[], hello, \textit{foobar}, a, abc\}$} -\end{center}\bigskip - -\item \alert{\bf Concatenation} of strings and languages - -\begin{center} -\begin{tabular}{rcl} -\bl{$\textit{foo}\;@\;bar$} & \bl{$=$} & \bl{$\textit{foobar}$}\medskip\\ -\bl{$A\;@\;B$} & \bl{$\dn$} & \bl{$\{ s_1\,@\,s_2 \;\mid\; s_1 \in A \wedge s_2 \in B\}$} -\end{tabular} -\end{center} - -%\item The \alert{\bf meaning} of a regular expression is a set of -% strings, or language. -\end{itemize} - -\only<2>{ -\begin{textblock}{4}(10.5,8) -\small -Let - -\bl{$A = \{foo, bar\}$} \bl{$B = \{a, b\}$} -\[ -\bl{A \,@\, B = \{fooa, foob, bara, barb\}} -\] -\end{textblock}} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] - \frametitle{Two Corner Cases} - - \Large - \begin{center} - \bl{$A \,@\, \{[]\} = \;?$}\bigskip\bigskip\pause\\ - \bl{$A \,@\, \{\} = \;?$} - \end{center} - - \end{frame} - %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{The Meaning of a Regex} - - ...all the strings a regular expression can match. - -\begin{center} - \begin{tabular}{rcl} - \bl{$L(\ZERO)$} & \bl{$\dn$} & \bl{$\{\}$}\\ - \bl{$L(\ONE)$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ - \bl{$L(c)$} & \bl{$\dn$} & \bl{$\{[c]\}$}\\ - \bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\ - \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \,@\, L(r_2)$}\\ - \bl{$L(r^*)$} & \bl{$\dn$} & \\ - \end{tabular} -\end{center} - -\begin{textblock}{14}(1.5,13.5)\small -\bl{$L$} is a function from regular expressions to -sets of strings (languages):\smallskip\\ -\bl{\quad$L$ : Rexp $\Rightarrow$ Set$[$String$]$} -\end{textblock} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] - \frametitle{The Power Operation} - - \begin{itemize} - \item The \alert{\textbf{\boldmath$n$th Power}} of a language: - - \begin{center} - \begin{tabular}{lcl} - \bl{$A^0$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ - \bl{$A^{n+1}$} & \bl{$\dn$} & \bl{$A \,@\, A^n$} - \end{tabular} - \end{center}\bigskip - - \item[] For example - - \begin{center} - \begin{tabular}{lcl@{\hspace{10mm}}l} - \bl{$A^4$} & \bl{$=$} & \bl{$A \,@\, A \,@\, A \,@\, A$} & \bl{$(@\,\{[]\})$}\\ - \bl{$A^1$} & \bl{$=$} & \bl{$A$} & \bl{$(@\,\{[]\})$}\\ - \bl{$A^0$} & \bl{$=$} & \bl{$\{[]\}$}\\ - \end{tabular} - \end{center} - - \end{itemize} - - \end{frame} - %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{The Meaning of a Regex} - -\begin{textblock}{15}(1,4) - \begin{tabular}{rcl} - \bl{$L(\ZERO)$} & \bl{$\dn$} & \bl{$\{\}$}\\ - \bl{$L(\ONE)$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ - \bl{$L(c)$} & \bl{$\dn$} & \bl{$\{[c]\}$}\\ - \bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\ - \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$\{ s_1 \,@\, s_2 \;|\; s_1 \in L(r_1) \wedge s_2 \in L(r_2) \}$}\\ - \bl{$L(r^*)$} & \bl{$\dn$} & \onslide<2->{\bl{$\bigcup_{0 \le n} L(r)^n$}}\\ - \end{tabular}\bigskip - -%\onslide<2->{ -%\hspace{5mm}\bl{$L(r)^0 \;\dn\; \{[]\}$}\\ -%\bl{$L(r)^{n+1} \;\dn\; L(r) \,@\, L(r)^n$}\hspace{9mm}\onslide<3->{\small\textcolor{gray}{(append on sets)}\\ -%\small\hspace{5cm}\textcolor{gray}{$\{ s_1 @ s_2 \;|\; s_1\in L(r) \wedge s_2 \in L(r)^n \}$}} -%} -\end{textblock} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] - \frametitle{The Star Operation} - - \begin{itemize} - \item The \alert{\bf Kleene Star} of a \underline{language}: - \bigskip - - \begin{center} - \begin{tabular}{c} - \bl{$A\star \dn \bigcup_{0\le n} A^n$} - \end{tabular} - \end{center}\bigskip - - \item[] This expands to - - \[ - \bl{A^0 \cup A^1 \cup A^2 \cup A^3 \cup A^4 \cup \ldots} - \] - - or - - \small - \[ - \bl{\{[]\} \;\cup\; A \;\cup\; A\,@\,A \;\cup\; - A\,@\,A\,@\,A \;\cup\; A\,@\,A\,@\,A\,@\,A \cup \ldots} - \] - - \end{itemize} - - \end{frame} - %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{The Meaning of a Regex} - -\begin{textblock}{15}(1,4) - \begin{tabular}{rcl} - \bl{$L(\ZERO)$} & \bl{$\dn$} & \bl{$\{\}$}\\ - \bl{$L(\ONE)$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ - \bl{$L(c)$} & \bl{$\dn$} & \bl{$\{[c]\}$}\\ - \bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\ - \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$\{ s_1 \,@\, s_2 \;|\; s_1 \in L(r_1) \wedge s_2 \in L(r_2) \}$}\\ - \bl{$L(r^*)$} & \bl{$\dn$} & \bl{$(L(r))\star$}\\ - \end{tabular} - -\end{textblock} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{The Meaning of Matching} - -\begin{bubble}[10cm] -\large\bf -A regular expression \bl{$r$} matches a string~\bl{$s$} -provided - -\begin{center} -\bl{$s \in L(r)$}\\ -\end{center} -\end{bubble}\bigskip\bigskip - -\ldots and the point of the next lecture is -to decide this problem as fast as possible (unlike Python, -Ruby, Java) - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] - \frametitle{Questions} - - \begin{itemize} - \item Say \bl{$A = \{[a],[b],[c],[d]\}$}.\bigskip - - \item[] - How many strings are in \bl{$A^4$}\,? - \bigskip\medskip\pause - - - \item[] - What if \bl{$A = \{[a],[b],[c],[]\}$};\\ - how many strings are then in \bl{$A^4$}\,? - \end{itemize} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% \begin{frame}[c] -% \frametitle{Languages (Sets of Strings)} - -% \begin{itemize} - -% \item A \alert{\bf Language} is a set of strings, for example\medskip -% \begin{center} -% \bl{$\{[], hello, foobar, a, abc\}$} -% \end{center}\bigskip - -% \item \alert{\bf Concatenation} for strings and languages - -% \begin{center} -% \begin{tabular}{rcl} -% \bl{$foo\;@\;bar$} & \bl{$=$} & \bl{$foobar$}\medskip\\ -% \bl{$A\;@\;B$} & \bl{$\dn$} & \bl{$\{ s_1\,@\,s_2 \;\mid\; s_1 \in A \wedge s_2 \in B\}$} -% \end{tabular} -% \end{center} -% \bigskip - -% \small -% \item [] For example \bl{$A = \{foo, bar\}$}, \bl{$B = \{a, b\}$} - -% \[ -% \bl{A \,@\, B = \{fooa, foob, bara, barb\}} -% \] - - - - -% \end{itemize} -% \end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% \begin{frame}[c] -% \frametitle{Two Corner Cases} - -% \Large -% \begin{center} -% \bl{$A \,@\, \{[]\} = \;?$}\bigskip\bigskip\pause\\ -% \bl{$A \,@\, \{\} = \;?$} -% \end{center} - -% \end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% \begin{frame}[c] -% \frametitle{The Meaning of a Regex} - -% ...all the strings a regular expression can match. - -% \begin{center} -% \begin{tabular}{rcl} -% \bl{$L(\ZERO)$} & \bl{$\dn$} & \bl{$\{\}$}\\ -% \bl{$L(\ONE)$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ -% \bl{$L(c)$} & \bl{$\dn$} & \bl{$\{[c]\}$}\\ -% \bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\ -% \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \,@\, L(r_2)$}\\ -% \bl{$L(r^*)$} & \bl{$\dn$} & \\ -% \end{tabular} -% \end{center} - -% \begin{textblock}{14}(1.5,13.5)\small -% \bl{$L$} is a function from regular expressions to -% sets of strings (languages):\smallskip\\ -% \bl{\quad$L$ : Rexp $\Rightarrow$ Set$[$String$]$} -% \end{textblock} - -% \end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% \begin{frame}[c] -% \frametitle{The Power Operation} - -% \begin{itemize} -% \item The \alert{\textbf{\boldmath$n$th Power}} of a language: - -% \begin{center} -% \begin{tabular}{lcl} -% \bl{$A^0$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ -% \bl{$A^{n+1}$} & \bl{$\dn$} & \bl{$A \,@\, A^n$} -% \end{tabular} -% \end{center}\bigskip - -% \item[] For example - -% \begin{center} -% \begin{tabular}{lcl@{\hspace{10mm}}l} -% \bl{$A^4$} & \bl{$=$} & \bl{$A \,@\, A \,@\, A \,@\, A$} & \bl{$(@\,\{[]\})$}\\ -% \bl{$A^1$} & \bl{$=$} & \bl{$A$} & \bl{$(@\,\{[]\})$}\\ -% \bl{$A^0$} & \bl{$=$} & \bl{$\{[]\}$}\\ -% \end{tabular} -% \end{center} - -% \end{itemize} - -% \end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% \begin{frame}[c] -% \frametitle{Written Exam} - -% \begin{itemize} -% \item Accounts for 80\%.\bigskip - -% \item The question ``\textit{Is this relevant for -% the exam?}'' is very demotivating for the lecturer!\bigskip\\ - -% \item Deal: Whatever is in the homework (and is not marked -% ``\textit{optional}'') is relevant for the exam.\bigskip - -% \item Each lecture has also a handout. There are also handouts about -% notation and Scala. -% \end{itemize} - -% \end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% \begin{frame}[t] -% \frametitle{Coursework} - -% \begin{itemize} -% \item Accounts for 20\%. Two strands. Choose \alert{\bf one}!\bigskip -% \end{itemize} - -% \begin{columns}[t] -% \begin{column}{.5\textwidth} -% \underline{\bf Strand 1}\medskip -% \begin{itemize} -% \item 4 programming tasks: -% \begin{itemize} -% \item matcher (4\%, 11.10.) -% \item lexer (5\%, 04.11.) -% \item parser (5\%, 22.11.) -% \item compiler (6\%, 13.12.) -% \end{itemize} -% \item in any lang.~you like,\\ but I want to see the\\ code -% \end{itemize} -% \end{column} - -% \hspace{-45pt}\vrule{}\hspace{10pt} -% \begin{column}{.5\textwidth} -% \underline{\bf Strand 2}\smallskip\begin{itemize} -% \item one task: prove the correctness of a regular expression matcher in -% the \underline{Isabelle} theorem prover -% \item 20\%, submission on~13.12.\hspace{-5mm}\mbox{} -% \end{itemize} -% \end{column} -% \end{columns}\medskip - -% \small -% \begin{itemize} -% \item Solving more than one strand will {\bf not} give you more -% marks. - -% \end{itemize} - -% \end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%\begin{frame}[c] -%\frametitle{Lecture Capture} -% -%\begin{itemize} -%\item Hope it works\ldots\pause actually no, it does not!\medskip\pause -%\item It is important to use lecture capture wisely\\ (it is only the ``baseline''): -%\begin{itemize} -%\item Lecture recordings are a study and revision aid. -%\item Statistically, there is a clear and direct link between attendance and -% attainment: students who do not attend lectures, do less well in exams. -%\end{itemize} -% -%\item Attending a lecture is more than watching it online -- if you do not -%attend, you miss out! -% -%\end{itemize} -% -%\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{\begin{tabular}{c}\\[3cm]\alert{Questions?}\end{tabular}} - - -\begin{tabular}{lll} - TAs: & Finley Warman & (took the module last year)\\ - & Chengsong Tan & (PhD student working on derivatives) -\end{tabular} -\mbox{} -\end{frame} - -\begin{frame}[c] -\end{frame} - -\begin{frame}[c] -\end{frame} - -\begin{frame}[c] -\end{frame} - -\begin{frame}[c] -\end{frame} - -\begin{frame}[c] -\end{frame} - -\begin{frame}[c] -\end{frame} - -\begin{frame}[c] -\end{frame} - -\begin{frame}[c] -\end{frame} - -\begin{frame}[c] -\end{frame} - -\begin{frame}[c] -\end{frame} - -\begin{frame}[c] -\end{frame} - -\begin{frame}[c] -\end{frame} - -\begin{frame}[c] -\end{frame} - -\begin{frame}[c] -\end{frame} - - -\begin{frame}[c] -\begin{mybox3}{Coursework} - Do we need to provide instructions on running the coursework files - if we're using languages other than Scala? Thanks -\end{mybox3}\pause - -\begin{mybox2}{Zip-File for Coursework} - Please, please submit a zipfile that generates a subdirectory - \begin{center} - \texttt{NameFamilyName} - \end{center} -\end{mybox2} -\end{frame} - - -\begin{frame}[c] -\begin{mybox3}{Coursework} - What is the purpose of the workshop session on the timetable? - - Slightly confused about how to undertake cw1 and what exactly we - should be implementing. This is more for clarification of the cw1 - structure, including the implementation and questions present in - cw1. -\end{mybox3} -\end{frame} - -\begin{frame}[c] -\begin{mybox3}{What is the trick?}\small - What was the trick to improve the evil regular expressions matcher - to have such good results compared to other programming languages? - Is it working better on casual regular expressions (the ones that - Python and Java handle pretty well), too? Or was it just optimised - for these evil ones? -\end{mybox3} - -\begin{mybox3}{}\small - It was shown in the lectures that the pattern matching algorithms - currently implemented in popular programming languages (Python, JS, - Java, etc) are far slower than the algorithm we are going to be - implementing in this module. My question is why do these programming - languages not implement the algorithm that we are going to implement - in this module? -\end{mybox3} -\end{frame} - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] - \frametitle{Thanks to Martin Mikusovic} - -\bigskip -\begin{center} -\begin{tikzpicture} - \begin{axis}[ - xlabel={$n$}, - x label style={at={(1.05,0.0)}}, - ylabel={time in secs}, - enlargelimits=false, - xtick={0,5,...,30}, - xmax=33, - ymax=35, - ytick={0,10,...,30}, - scaled ticks=false, - axis lines=left, - width=9cm, - height=5.5cm, - legend entries={Java 8, Python, JavaScript, Swift}, - legend pos=north west, - legend cell align=left] -\addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data}; -\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data}; -\addplot[red,mark=*, mark options={fill=white}] table {re-js.data}; -\addplot[magenta,mark=*, mark options={fill=white}] table {re-swift.data}; -\end{axis} -\end{tikzpicture} -\end{center} - -Regex: \bl{$(a^*)^* \cdot b$} - -Strings of the form \bl{$\underbrace{\,a\ldots a\,}_{n}$} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{Same Example in Java 9+} - -\begin{center} -\begin{tikzpicture} - \begin{axis}[ - xlabel={$n$}, - x label style={at={(1.09,-0.15)}}, - ylabel={time in secs}, - scaled x ticks=false, - enlargelimits=false, - xtick distance=10000, - xmax=44000, - ytick={0,10,...,30}, - ymax=35, - axis lines=left, - width=9cm, - height=5cm, - legend entries={Java \liningnums{9}+}, - legend pos=north west, - legend cell align=left] -\addplot[blue,mark=square*,mark options={fill=white}] table {re-java9.data}; -\end{axis} -\end{tikzpicture} -\end{center} - -Regex: \bl{$(a^*)^* \cdot b$} - -Strings of the form \bl{$\underbrace{\,a\ldots a\,}_{n}$} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% Questions - -\begin{frame}[c] -\begin{mybox3}{} - Are there any (common) languages that have a built-in regex - implementation matching the set of functions of a formal 'simple' - regular expression, as opposed to an 'extended' regular expression - implemented in most regex-supporting languages? -\end{mybox3} -\end{frame} - -\begin{frame}[c] -\begin{mybox3}{Regexes} - Can we determine all the possible regular expressions matching a - certain string? If we take into account all the possible ways to - combine the operations: \bl{$\ZERO$}, \bl{$\ONE$}, - \bl{$r_1 + r_2$}, \bl{$r_1 \cdot r_2$}, \bl{$r^*$}? -\end{mybox3} -\end{frame} - -\begin{frame}[c] -\begin{mybox3}{\bl{$L$} + Equivalence} - When we explain why two regular expressions are not equivalent, what - method is better for us, using mathematics formulas or making an - example? -\end{mybox3} -\begin{mybox3}{} - Meaning of Regex and Operations -\end{mybox3} -\end{frame} - -\begin{frame}[c] -\begin{mybox3}{\bl{$L$}} - Can the function L be applied to anything other than regular - expressions? For example would L(L(c)) return anything? -\end{mybox3} - -\hfill $\Rightarrow$ No -\end{frame} - -\begin{frame}[c] -\begin{mybox3}{\bl{$(a?)\{n\} \cdot a\{n\}$}} - In the evil regexes section, is there any reason why in the regex - \texttt{[a?]\{n\}[a]\{n\}} the square brackets are used? It is defined as a - single character from the square brackets, however there is just one - character, so it seems like it is not necessary. Maybe it is just - necessary for the first part, because ? is a token instead of a - character and we need to refer to a? as a ``unit''? Could regular - brackets be used instead? Is there any difference apart from the - fact that it would create a group? Also, are the regexes - \texttt{[a?]\{n\}} and - \texttt{a\{0,3\}} equivalent? -\end{mybox3} -\end{frame} - -\begin{frame}[c] -\begin{mybox3}{Python + Parser Combinators (CW3)}\small - Hi Christian, - - I don’t see a problem: you certainly have higher order functions and - it is easy to implement algebraic data types using classes. As far - as I can see that’s all you need. You don’t get the static types but - that should be obvious. Basically if you can do it in LISP you can - do it in Python. The only problem could be stack overflows due to a - lack of tail recursion optimisation. On the other hand you can - simulate laziness using generators. - - Cheers, - Thorsten -\end{mybox3} - -Trees \url{https://youtu.be/7tCNu4CnjVc} - -Laziness \url{https://youtu.be/5jwV3zxXc8E} - -\end{frame} - -\begin{frame}[c] -\begin{mybox3}{} - What suggestions do you have for us to get the most out of this - module, especially in the online format? I.e. form discussion - groups, will you have office hours? -\end{mybox3} - -\small -\hfill $\Rightarrow$\mbox{} Discussion Forum on KEATS - -\hfill online tutorial sessions - -\end{frame} - -\begin{frame}[c] - \small -\begin{mybox3}{} -Where do most students struggle with this module? What will the format -of the exam be? What is the most efficient way of studying for the -exam? There are plenty of resources available on KEATS, but is there -anything else you'd recommend us to study? Although (just by skimming -the headings) the module seems to be a combination of practical and -theoretical matters, exactly in what field would the syllabus be -applied? Besides these questions and the ones other students asked, is -there anything else we should know? Thank you! -\end{mybox3} -\end{frame} - - -\begin{frame}[c] -\end{frame} - -\begin{frame}[c] -\end{frame} - -\begin{frame}[c] -\end{frame} - -\begin{frame}[c] -\end{frame} - -\begin{frame}[c] -\end{frame} - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\end{document} - -%%% Local Variables: -%%% mode: latex -%%% TeX-master: t -%%% End: - +% !TEX program = xelatex +\documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer} +\usepackage{../slides} +\usepackage{../graphicss} +\usepackage{../langs} +\usepackage{../data} +\usetikzlibrary{cd} + + +\usepackage{tcolorbox} +\newtcolorbox{mybox}{colback=red!5!white,colframe=red!75!black} +\newtcolorbox{mybox2}[1]{colback=red!5!white,colframe=red!75!black,fonttitle=\bfseries,title=#1} +\newtcolorbox{mybox3}[1]{colback=Cyan!5!white,colframe=Cyan!75!black,fonttitle=\bfseries,title=#1} + + + +\hfuzz=220pt + +\lstset{language=Scala, + style=mystyle, + numbersep=0pt, + numbers=none, + xleftmargin=0mm} + +\newcommand{\bl}[1]{\textcolor{blue}{#1}} + +% beamer stuff +\renewcommand{\slidecaption}{CFL 01, King's College London} + +%% https://cs.rit.edu/~hh/teaching/_media/cc18/lectures/lect1/main.pdf +%% https://cs.rit.edu/~hh/teaching/_media/cc18/lectures/lect2/main.pdf +%% https://cs.rit.edu/~hh/teaching/_media/cc18/lectures/lect3/main.pdf + +\begin{document} + +%\begin{frame}[t] +% +%\begin{mybox} +%A physical explanation the \emph{dynamic matrix}\\ +%lots of text +%\end{mybox} + + +%\begin{mybox2}{Test} +%A physical explanation the \emph{dynamic matrix}\\ +%lots of text +%\end{mybox2} + +%\begin{mybox3}{Test} +%A physical explanation the \emph{dynamic matrix}\\ +%lots of text +%\end{mybox3} +%\end{frame} + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[t] +\frametitle{% + \begin{tabular}{@ {}c@ {}} + \\[-3mm] + \LARGE Compilers and \\[-1mm] + \LARGE Formal Languages\\[-3mm] + \end{tabular}} + + \begin{center} + %\includegraphics[scale=0.3]{pics/ante1.jpg}\hspace{5mm} + %\includegraphics[scale=0.31]{pics/ante2.jpg}\\ + %\footnotesize\textcolor{gray}{Antikythera automaton, 100 BC (Archimedes?)} + \end{center} + + \normalsize + \begin{center} + \begin{tabular}{ll} + Email: & christian.urban at kcl.ac.uk\\ + %Office Hours: & Thursdays 12 -- 14\\ + %Location: & N7.07 (North Wing, Bush House)\\ + Slides \& Progs: & KEATS\\ + \end{tabular} + \end{center} + + \begin{center} + \begin{tikzpicture} + \node[drop shadow,fill=white,inner sep=0pt] + {\footnotesize\rowcolors{1}{capri!10}{white} + \begin{tabular}{|p{4.8cm}|p{4.8cm}|}\hline + \cellcolor{blue!50} + 1 Introduction, Languages & 6 While-Language \\ + 2 Regular Expressions, Derivatives & 7 Compilation, JVM \\ + 3 Automata, Regular Languages & 8 Compiling Functional Languages \\ + 4 Lexing, Tokenising & 9 Optimisations \\ + 5 Grammars, Parsing & 10 LLVM \\ \hline + \end{tabular}% + }; + \end{tikzpicture} + \end{center} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}<1-12>[c] +\frametitle{The Goal of this Module\ldots} + +\begin{center} + \begin{tikzpicture}[scale=1, + node/.style={ + rectangle,rounded corners=3mm, + very thick,draw=black!50,minimum height=18mm, minimum width=20mm, + top color=white,bottom color=black!20,drop shadow}] + + \node at (3.05, 1.8) {\Large\bf \ldots{} you write a compiler}; + + \node (0) at (-2.3,0) {}; + \node [above=5mm of 0] + {\makebox[0mm]{\footnotesize + \begin{tabular}{@{}l@{}}input\\[-1mm]program\end{tabular}}}; + + \node (A) at (0,0) [node] {}; + \node [below right] at (A.north west) {lexer}; + + \node (B) at (3,0) [node] {}; + \node [below right=1mm] at (B.north west) {\mbox{}\hspace{-1mm}parser}; + + \node (C) at (6,0) [node] {}; + \node [below right] at (C.north west) {\mbox{}\hspace{-1mm}code gen}; + + \node (1) at (8.4,0) {}; + \node [above=5mm of 1] + {\makebox[0mm]{\footnotesize + \begin{tabular}{@{}r@{}}binary\\[-1mm]code\end{tabular}}}; + + \draw [->,line width=4mm] (0) -- (A); + \draw [->,line width=4mm] (A) -- (B); + \draw [->,line width=4mm] (B) -- (C); + \draw [->,line width=4mm] (C) -- (1); + \end{tikzpicture} + \end{center} + +\only<2,3,4>{ +\begin{textblock}{1}(1,2.1) +\begin{bubble}[9.8cm] +\normalsize +lexer input: a string\smallskip\\ +\hspace{5mm}\code{"read(n);"}\medskip\\ +lexer output: a sequence of tokens\smallskip\\ +\hspace{5mm}\code{key(read) lpar id(n) rpar semi} +\end{bubble} +\end{textblock}} + +\only<3,4>{ +\begin{textblock}{1}(6,7.8) +\begin{tabular}{c} +\includegraphics[scale=0.2]{../pics/rosetta.jpg}\\[-2mm] +\footnotesize lexing $\Rightarrow$ recognising words (Stone of Rosetta) +\end{tabular} +\end{textblock}} + +\only<4>{ +\begin{textblock}{1}(0.5,12)\small +\begin{tabular}{l@{}c@{}l} + \pcode{if} & $\;\Rightarrow\;$ & keyword\\ + \pcode{iffoo} & $\;\Rightarrow\;$ & identifier\\ +\end{tabular} +\end{textblock}} + +\only<6>{ +\begin{textblock}{1}(1,1.5) +\begin{bubble}[8.5cm] +\normalsize +parser input: a sequence of tokens\smallskip\\ + +{\small\hspace{5mm}\code{key(read) lpar id(n) rpar semi}}\smallskip\\ + +parser output: an abstract syntax tree\smallskip\\ +\footnotesize +\hspace{2cm}\begin{tikzpicture} + \node {\code{read}} + child {node {\code{lpar}}} + child {node {\code{n}}} + child {node {\code{rpar}}}; +\end{tikzpicture} +\end{bubble} +\end{textblock}} + +\only<8,9>{ +\begin{textblock}{1}(1,1.5) +\begin{bubble}[4cm] +\normalsize +code generation:\smallskip\\ +\hspace{5mm}\code{istore 2}\\ +\hspace{5mm}\code{iload 2}\\ +\hspace{5mm}\code{ldc 10}\\ +\hspace{5mm}\code{isub}\\ +\hspace{5mm}\code{ifeq Label2}\\ +\hspace{5mm}\code{iload 2}\\ +\hspace{5mm}\code{...}\\ +\end{bubble} +\end{textblock}} + +\only<9>{ +\begin{textblock}{6}(8.4,7) +\begin{bubble}[5cm] +\mbox{\begin{tikzpicture}[scale=0.58,rounded corners=0mm] +\begin{axis}[axis x line=bottom, axis y line=left, ylabel=secs, + xlabel=n, + enlargelimits=0.05, + ybar interval=0.7, legend style=small] +\addplot file {interpreted2.data}; +\addplot file {compiled2.data}; +%\legend{interpreted, compiled} +\end{axis} +\end{tikzpicture}} +\end{bubble} +\end{textblock}} + +\only<10>{ +\begin{textblock}{6}(1,3) + \begin{bubble}[11cm] + Compiler explorers, e.g.: \url{https://gcc.godbolt.org} \;\video{https://youtu.be/ysaBmhMEyUg} + \begin{tikzpicture}[] + \node (0) at (-2.3,0) {\includegraphics[scale=0.3]{pics/csource.png}}; + \node (1) [right=35mm] at (0) {\includegraphics[scale=0.3]{pics/cassmbl.png}}; + \draw [->,line width=4mm, red] (0) -- (1); + \node (2) [below=20mm] at (0) {\LARGE\bf source}; + \node (3) [right=40mm] at (2) {\LARGE\bf binary}; + \draw [->,line width=1mm] (2) -- (3); +\end{tikzpicture} +\end{bubble} + +\end{textblock}} +\only<11>{ +\begin{textblock}{6}(1,3) + \begin{bubble}[11cm] + Compiler explorer for Java: \url{https://javap.yawk.at} + \begin{tikzpicture}[] + \node (0) at (-2.3,0) {\includegraphics[scale=0.4]{pics/jsource.png}}; + \node (1) [right=35mm] at (0) {\includegraphics[scale=0.4]{pics/jassmbl.png}}; + \draw [->,line width=4mm, red] (0) -- (1); + \node (2) [below=20mm] at (0) {\LARGE\bf source}; + \node (3) [right=40mm] at (2) {\LARGE\bf byte code}; + \draw [->,line width=1mm] (2) -- (3); +\end{tikzpicture} +\end{bubble} +\end{textblock}} + + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[t] +\frametitle{Why Study Compilers?} + + +John Regehr {\small(Univ.~Utah, LLVM compiler hacker)} +\here{https://blog.regehr.org/archives/1419} +\smallskip\\ + +\begin{bubble}[10.5cm] + \bf ``\ldots{}It’s effectively a perpetual + employment act for solid compiler hackers.'' +\end{bubble} + +\onslide<1->{ +\only<2>{ +\begin{itemize} +\item {\bf Hardware is getting weirder + rather than getting clocked faster.} + +\begin{itemize} +\item[] ``Almost all processors are multicores nowadays and it looks + like there is increasing asymmetry in resources across cores. + Processors come with vector units, crypto accelerators etc. We have + DSPs, GPUs, ARM big.little, and Xeon Phi. This is only scratching the + surface.'' +\end{itemize} +\end{itemize}} +\only<3>{ +\begin{itemize} +\item {\bf We’re getting tired of low-level languages and + their associated security disasters.} + +\begin{itemize} +\item [] ``We want to write new code, to whatever extent possible, in + safer, higher-level languages. Compilers are caught right in the + middle of these opposing trends: one of their main jobs is to help + bridge the large and growing gap between increasingly high-level + languages and increasingly wacky platforms.'' +\end{itemize} +\end{itemize}}} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Why Bother with Compilers?} + +\textbf{Boeing 777's}: First flight in 1994. They want to achieve +triple redundancy for potential hardware faults. +\here{http://www.citemaster.net/get/db3a81c6-548e-11e5-9d2e-00163e009cc7/R8.pdf}\bigskip + +They compile 1 Ada program to\medskip + +\begin{itemize} + \item Intel 80486 + \item Motorola 68040 (old Macintosh's) + \item AMD 29050 (RISC chips used often in laser printers) +\end{itemize}\medskip\medskip + +using 3 independent compilers.\bigskip\pause + +\small Airbus uses C and static analysers. Recently started using CompCert. + +\only<1->{% +\begin{textblock}{6}(8,4.5) +\includegraphics[scale=0.28]{../pics/777.png} +\end{textblock}} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{What Do Compilers Do?} + +Remember BF*** from PEP? + +\begin{center} +\begin{tabular}{rcl} +\bl{\texttt{>}} & $\Rightarrow$ & move one cell right\\ +\bl{\texttt{<}} & $\Rightarrow$ & move one cell left\\ +\bl{\texttt{+}} & $\Rightarrow$ & increase cell by one\\ +\bl{\texttt{-}} & $\Rightarrow$ & decrease cell by one\\ +\bl{\texttt{.}} & $\Rightarrow$ & print current cell\\ +\bl{\texttt{,}} & $\Rightarrow$ & input current cell\\ +\bl{\texttt{[}} & $\Rightarrow$ & loop begin\\ +\bl{\texttt{]}} & $\Rightarrow$ & loop end\medskip\\ + & $\Rightarrow$ & everything else is a comment\\ +\end{tabular} +\end{center} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] + \frametitle{A ``Compiler'' for BF*** to C} + + \begin{center} + \begin{tabular}{rcl} + \bl{\texttt{>}} & $\Rightarrow$ & \texttt{ptr++}\\ + \bl{\texttt{<}} & $\Rightarrow$ & \texttt{ptr--}\\ + \bl{\texttt{+}} & $\Rightarrow$ & \texttt{(*ptr)++}\\ + \bl{\texttt{-}} & $\Rightarrow$ & \texttt{(*ptr)--}\\ + \bl{\texttt{.}} & $\Rightarrow$ & \texttt{putchar(*ptr)}\\ + \bl{\texttt{,}} & $\Rightarrow$ & \texttt{*ptr = getchar()}\\ + \bl{\texttt{[}} & $\Rightarrow$ & \texttt{while(*ptr)\{}\\ + \bl{\texttt{]}} & $\Rightarrow$ & \texttt{\}}\medskip\\ + & $\Rightarrow$ & ignore everything else\\ + \end{tabular} + \end{center}\bigskip + + \texttt{char field[30000]\\ char *ptr = \&field[15000]} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] + \frametitle{Another~``Compiler''~for~BF~to~C} + + \begin{center} + \begin{tabular}{rcl} + \bl{\texttt{>\ldots>}} & $\Rightarrow$ & \texttt{ptr += n}\\ + \bl{\texttt{<\ldots<}} & $\Rightarrow$ & \texttt{ptr -= n}\\ + \bl{\texttt{+\ldots+}} & $\Rightarrow$ & \texttt{(*ptr) += n}\\ + \bl{\texttt{-\ldots-}} & $\Rightarrow$ & \texttt{(*ptr) -= n}\\ + \bl{\texttt{.}} & $\Rightarrow$ & \texttt{putchar(*ptr)}\\ + \bl{\texttt{,}} & $\Rightarrow$ & \texttt{*ptr = getchar()}\\ + \bl{\texttt{[}} & $\Rightarrow$ & \texttt{while(*ptr)\{}\\ + \bl{\texttt{]}} & $\Rightarrow$ & \texttt{\}}\medskip\\ + & $\Rightarrow$ & ignore everything else\\ + \end{tabular} + \end{center}\bigskip + + \texttt{char field[30000]\\ char *ptr = \&field[15000]} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[t] +\frametitle{A Brief Compiler History} + +\bigskip +\begin{itemize} +\item Turing Machines, 1936 (a tape as memory) +\item Regular Expressions, 1956\\ +\item The first compiler for COBOL, 1957\\ (Grace Hopper)\medskip +\item But surprisingly research papers are still published nowadays\\ +\item ``Parsing: The Solved Problem That Isn't'' + \here{https://tratt.net/laurie/blog/entries/parsing_the_solved_problem_that_isnt.html} +\end{itemize} + + +\begin{textblock}{8.5}(5,7.6) +\begin{flushright} +\includegraphics[scale=0.3]{pics/hopper.jpg}\\ +\footnotesize\textcolor{gray}{Grace Hopper}\smallskip\\ + +{\small\textcolor{gray}{(she made it to David Letterman's Tonight Show + \here{https://youtu.be/3N_ywhx6_K0?t=31})}} +\end{flushright} +\end{textblock} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Some Housekeeping} + +\textbf{Exam will be online:}\bigskip + +\begin{itemize} +\item final exam in January (35\%) +\item five CWs (65\%) +\end{itemize}\bigskip\bigskip\pause + + +\textbf{Weekly Homework (optional):} +\begin{itemize} +\item uploaded on KEATS, send answers via email, (try to!) respond individually +\item \alert{\bf all} questions in the exam will be from the HWs!! +\end{itemize} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Some Housekeeping} + +\textbf{Coursework (5 accounting for 65\%):}\bigskip + +\begin{itemize} +\item matcher (5\%) +\item lexer (10\%) +\item parser / interpreter (10\%) +\item JVM compiler (15\%) +\item LLVM compiler (25\%) +\end{itemize}\bigskip\pause + +you can use \alert{any} programming language you like (Haskell, Rust)\\\pause +you can use any code I show you and is uploaded to KEATS\ldots\textbf{BUT NOTHING ELSE!} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Lectures 1 - 5} + +transforming strings into structured data\\[10mm] + +{\LARGE\bf Lexing} {\hfill{}based on regular expressions}\medskip\\ +\hspace{5mm}(recognising ``words'')\\[6mm] + +{\LARGE\bf Parsing}\medskip\\ +\hspace{5mm}(recognising ``sentences'') + +\begin{textblock}{1}(10,9.1) +\begin{tabular}{c} +\includegraphics[scale=0.1]{../pics/rosetta.jpg}\\[-2mm] +\footnotesize Stone of Rosetta +\end{tabular} +\end{textblock} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Lectures 1 - 5} + +transforming strings into structured data\\[10mm] + +{\LARGE\bf Lexing} {\hfill{}based on regular expressions}\medskip\\ +\hspace{5mm}(recognising ``words'')\\[6mm] + +{\LARGE\bf Parsing}\medskip\\ +\hspace{5mm}(recognising ``sentences'') + +\begin{textblock}{1}(10,9.1) +\begin{tabular}{c} +\includegraphics[scale=0.1]{../pics/rosetta.jpg}\\[-2mm] +\footnotesize Stone of Rosetta +\end{tabular} +\end{textblock} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] + \frametitle{Lectures 5 - 10} + + code generation for a small imperative and a small functional language\\[10mm] + + {\LARGE\bf Interpreters}\medskip\\ + \hspace{5mm}(directly runs a program)\\[6mm] + + {\LARGE\bf Compilers}\medskip\\ + \hspace{5mm}(generate JVM code and LLVM-IR code) + + \begin{textblock}{1}(8.8,8.1) + \begin{tabular}{c@{}c} + \includegraphics[scale=0.4]{../pics/javaduke.png} & + \includegraphics[scale=0.23]{../pics/llvmlogo.png} + \end{tabular} + \end{textblock} + + \end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[t] +\frametitle{Familiar Regular Expresssions} +\small +\begin{center} +\texttt{[a-z0-9\_$\backslash{}$.-]+ @ [a-z0-9$\backslash{}$.-]+ . [a-z$\backslash{}$.]\{2,6\}} +\end{center}\smallskip + +\begin{center} +\begin{tabular}{@{}lp{8.5cm}@{}} +\pcode{re*} & matches 0 or more times\\ +\pcode{re+} & matches 1 or more times\\ +\pcode{re?} & matches 0 or 1 times\\ +\pcode{re\{n\}} & matches exactly \pcode{n} number of times\\ +\pcode{re\{n,m\}} & matches at least \pcode{n} and at most {\tt m} times\\ +\pcode{[...]} & matches any single character inside the brackets\\ +\pcode{[^...]} & matches any single character not inside the +brackets\\ +\pcode{a-z A-Z} & character ranges\\ +\pcode{\\d} & matches digits; equivalent to \pcode{[0-9]}\\ +\pcode{.} & matches every character except newline\\ +\pcode{(re)} & groups regular expressions and remembers +the matched text +\end{tabular} +\end{center} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Some ``innocent'' examples} + +Let's try two examples + +\begin{center} + \bl{\texttt{(a*)*b}} + \hspace{2cm} + \bl{\texttt{[a?]\{n\}[a]\{n\}}} +\end{center}\bigskip\pause + +and match them with strings of the form + +\begin{center} + \bl{\texttt{a}}, + \bl{\texttt{aa}}, + \bl{\texttt{aaa}}, + \bl{\texttt{aaaa}}, + \bl{\texttt{aaaaa}}, + \bl{$\underbrace{\texttt{a}...\texttt{a}}_n$} +\end{center} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Why Bother with Regexes?} + +\begin{columns}[t,onlytextwidth] +\begin{column}{1.8cm} +\mbox{} +\end{column} +\begin{column}{.5\textwidth} +\small{}Ruby, Python, Java 8\medskip\\ +\begin{tikzpicture}\footnotesize +\begin{axis}[ + xlabel={$n$}, + x label style={at={(1.05,0.0)}}, + ylabel={time in secs}, + enlargelimits=false, + xtick={0,5,...,30}, + xmax=33, + ymax=35, + ytick={0,5,...,30}, + scaled ticks=false, + axis lines=left, + width=\textwidth, + height=4cm, + legend entries={Python,Ruby}, + legend pos=north west, + legend cell align=left] +\addplot[blue,mark=*, mark options={fill=white}] table {re-python.data}; +\addplot[brown,mark=triangle*, mark options={fill=white}] table {re-ruby.data}; +\end{axis} +\end{tikzpicture} +\begin{tikzpicture}\footnotesize +\begin{axis}[ + xlabel={$n$}, + x label style={at={(1.05,0.0)}}, + ylabel={time in secs}, + enlargelimits=false, + xtick={0,5,...,30}, + xmax=33, + ymax=35, + ytick={0,5,...,30}, + scaled ticks=false, + axis lines=left, + width=\textwidth, + height=4cm, + legend entries={Python, Java 8, JavaScript, Swift}, + legend pos=north west, + legend cell align=left] +\addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data}; +\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data}; +\addplot[red,mark=*, mark options={fill=white}] table {re-js.data}; +\addplot[magenta,mark=*, mark options={fill=white}] table {re-swift.data}; +\end{axis} +\end{tikzpicture} +% +\end{column} +\begin{column}{.5\textwidth} +\small{}Us (after next lecture)\medskip\\ +\begin{tikzpicture}\footnotesize +\begin{axis}[ + xlabel={$n$}, + x label style={at={(1.07,0.0)}}, + ylabel={time in secs}, + enlargelimits=false, + xtick={0,5000,...,10000}, + xmax=11000, + ymax=35, + ytick={0,5,...,30}, + scaled ticks=false, + axis lines=left, + width=\textwidth, + height=4cm] +\addplot[green,mark=square*,mark options={fill=white}] table {re2.data}; +\addplot[black,mark=square*,mark options={fill=white}] table {re3.data}; +\end{axis} +\end{tikzpicture} +\begin{tikzpicture}\footnotesize +\begin{axis}[ + xlabel={$n$}, + x label style={at={(1.07,0.0)}}, + ylabel={time in secs}, + enlargelimits=false, + ymax=35, + ytick={0,5,...,30}, + scaled ticks=false, + axis lines=left, + width=\textwidth, + height=4cm] +\addplot[black,mark=square*,mark options={fill=white}] table {re3a.data}; +\end{axis} +\end{tikzpicture} +\end{column} +\end{columns} +\medskip + +\begin{textblock}{3}(-0.1,3.3) +\small\hfill\bl{\texttt{[a?]\{n\}[a]\{n\}}}: +\end{textblock} + +\begin{textblock}{3}(-0.1,8.7) +\small\hfill\bl{\texttt{(a*)*b}}: +\end{textblock} + +\begin{textblock}{3}(0.3,13) +\small{}matching with strings +\bl{$\underbrace{\texttt{a}...\texttt{a}}_n$} +\end{textblock} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c,fragile] + \frametitle{Incidents} + + \begin{itemize} + \item a global outage on 2 July 2019 at \textbf{Cloudflare} + (first one for six years)\medskip + + \begin{center}\small\color{blue} + \begin{verbatim} + (?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false| + null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s + |-|~|!|{}|\|\||\+)*.*(?:.*=.*))) + \end{verbatim} + \end{center}\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip + + \item on 20 July 2016 the \textbf{Stack Exchange} webpage went down + because of an evil regular expression + \here{https://stackstatus.net/post/147710624694/outage-postmortem-july-20-2016} + \end{itemize} + + \begin{textblock}{6}(6,7.6) + \includegraphics[scale=0.14]{../pics/cloudflare.png}\\ + \footnotesize + It serves more web traffic than Twitter, Amazon, Apple, + Instagram, Bing \& Wikipedia combined. + \here{https://blog.cloudflare.com/details-of-the-cloudflare-outage-on-july-2-2019/} + \end{textblock} + + \end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Evil Regular Expressions} + +\begin{itemize} +\item \alert{R}egular \alert{e}xpression \alert{D}enial \alert{o}f \alert{S}ervice (ReDoS)\medskip +\item Some evil regular expressions:\medskip +\begin{itemize} +\item \bl{\texttt{[a?]\{n\}\;[a]\{n\}}} +\item \bl{\texttt{(a*)*\;b}} +\item \bl{\texttt{([a-z]+)*}} +\item \bl{\texttt{(a + aa)*}} +\item \bl{\texttt{(a + a?)*}} +\end{itemize} + +\item sometimes also called \alert{catastrophic backtracking} +\item this is a problem for \alert{N}etwork \alert{I}ntrusion + \alert{D}etection systems, Cloudflare, StackExchange, Atom editor +\item \url{https://vimeo.com/112065252} +\end{itemize} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%\begin{frame}[c] +%\frametitle{Today} +% +%\begin{itemize} +%\item While the ultimate goal is to implement a small compiler for the JVM +% \ldots\bigskip +%\end{itemize} +% +%Let's start with: +% +%\begin{itemize} +%\item a web-crawler +%\item an email harvester +%\item \textcolor{gray}{(a web-scraper)} +%\end{itemize} +% +%\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%\begin{frame}[t] +%\frametitle{A Web-Crawler} +% +%\mbox{}\\[10mm] +% +%\begin{enumerate} +%\item given an URL, read the corresponding webpage +%\item extract all links from it +%\item call the web-crawler again for all these links +%\end{enumerate} +% +%\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%\begin{frame}[t] +%\frametitle{A Web-Crawler} +% +%\mbox{}\\[10mm] +% +% +%\begin{enumerate} +%\item given an URL, read the corresponding webpage +%\item if not possible print, out a problem +%\item if possible, extract all links from it +%\item call the web-crawler again for all these links +%\end{enumerate}\bigskip\pause +% +%\small (we need a bound for the number of recursive calls) +% +%\small (the purpose is to check all links on my own webpage) +%\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%\begin{frame}[c] +% +%\begin{textblock}{1}(2,5) +%\begin{tabular}{c} +%\includegraphics[scale=0.15]{pics/servers.png}\\[-2mm] +%\small Server +%\end{tabular} +%\end{textblock} +% +%\begin{textblock}{1}(5.6,4) +% \begin{tikzpicture}[scale=1.1] +% \draw[white] (0,1) node (X) {}; +% \draw[white] (2,1) node (Y) {}; +% \draw[white] (0,0) node (X1) {}; +% \draw[white] (2,0) node (Y1) {}; +% \draw[white] (0,-1) node (X2) {}; +% \draw[white] (2,-1) node (Y2) {}; +% \draw[red, <-, line width = 2mm] (X) -- (Y); +% \node [inner sep=5pt,label=above:\textcolor{black}{GET request}] at ($ (X)!.5!(Y) $) {}; +% \draw[red, ->, line width = 2mm] (X1) -- (Y1); +% \node [inner sep=5pt,label=above:\textcolor{black}{webpage}] at ($ (X1)!.5!(Y1) $) {}; +% \draw[red, <-, line width = 2mm] (X2) -- (Y2); +% \node [inner sep=7pt,label=above:\textcolor{black}{POST data}] at ($ (X2)!.5!(Y2) $) {}; +% \end{tikzpicture} +%\end{textblock} +% +% +%\begin{textblock}{1}(9,5.5) +%\begin{tabular}{c} +%\includegraphics[scale=0.15]{pics/laptop.png}\\[-2mm] +%\small Browser +%\end{tabular} +%\end{textblock} +%\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%\begin{frame}[c] +%\frametitle{Scala} +% +%\small A simple Scala function for reading webpages: +%\bigskip +% +%\footnotesize +%\lstinputlisting{../progs/app0.scala} +%\medskip\pause +% +%\lstinline{get_page("""https://nms.kcl.ac.uk/christian.urban/""")} +%\bigskip\medskip\pause +% +% +%\small A slightly more complicated version for handling errors: +%\smallskip +% +%\footnotesize +%\lstinputlisting[xleftmargin=-4mm]{../progs/app1.scala} +% +% +%\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%\begin{frame}[t] +%\frametitle{A Regular Expression} +% +%\begin{itemize} +%\item \ldots{} is a pattern or template for specifying strings +%\end{itemize}\bigskip +% +%\begin{center} +%\only<1>{\scode{"https?://[^"]*"}}% +%\only<2>{\scode{""""https?://[^"]*"""".r}} +%\end{center}\bigskip\bigskip +% +%matches for example\smallskip\\ +%\hspace{2mm}\code{"http://www.foobar.com"}\\ +%\hspace{2mm}\code{"https://www.tls.org"}\smallskip\\ +% +%but not\smallskip\\ +%\hspace{2mm}\code{"http://www."foo"bar.com"}\\ +% +%\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%\begin{frame}[c] +%\frametitle{Finding Operations in Scala} +% +%{\bf\code{rexp.findAllIn(string)}}\medskip +% +%returns a list of all (sub)strings that match the +%regular expression +%\bigskip\bigskip +% +% +%{\bf\code{rexp.findFirstIn(string)}}\medskip +% +%returns either +% +%\begin{itemize} +%\item \code{None} if no (sub)string matches or +%\item \code{Some(s)} with the first (sub)string +%\end{itemize} +% +%\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%\begin{frame}[c] +% +%\footnotesize +%\lstinputlisting{../progs/app2.scala} +% +%\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%\begin{frame}[c] +% +%\small +%A version that only crawls links in ``my'' domain:\bigskip +% +%\footnotesize +%\lstinputlisting{../progs/app3.scala} +% +%\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%\begin{frame}[c] +%\lstset{xleftmargin=-4mm} +%\small +%A little email harvester: +% +%\footnotesize +%\lstinputlisting{../progs/app4.scala}\bigskip +% +%\tiny +%\url{http://net.tutsplus.com/tutorials/other/8-regular-expressions-you-should-know/} +% +%\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[t] +\frametitle{(Basic) Regular Expressions} + +Their inductive definition: + + +\begin{textblock}{6}(2,7.5) + \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l} + \bl{$r$} & \bl{$::=$} & \bl{$\ZERO$} & nothing\\ + & \bl{$\mid$} & \bl{$\ONE$} & empty string / \pcode{""} / $[]$\\ + & \bl{$\mid$} & \bl{$c$} & character\\ + & \bl{$\mid$} & \bl{$r_1 + r_2$} & alternative / choice\\ + & \bl{$\mid$} & \bl{$r_1 \cdot r_2$} & sequence\\ + & \bl{$\mid$} & \bl{$r^*$} & star (zero or more)\\ + \end{tabular} + \end{textblock} + + +\only<2->{\footnotesize +\begin{textblock}{9}(2,0.5) +\begin{bubble}[9.8cm] +\lstinputlisting{../progs/app01.scala} +\end{bubble} +\end{textblock}} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%\begin{frame}[t] +%\frametitle{Regular Expressions} +% +%\small +%In Scala:\bigskip +% +%\footnotesize +%\lstinputlisting{../progs/app51.scala} +% +% +%\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[t] +\frametitle{Strings} + +\ldots are lists of characters. For example \code{"hello"} + +\begin{center} +\bl{$[h, e, l, l, o]$} or just \bl{$hello$} +\end{center} + +the empty string: \bl{$[]$} or \bl{\pcode{""}}\bigskip\\ + +the concatenation of two strings: + +\begin{center} +\bl{$s_1 \,@\, s_2$} +\end{center} + +\bl{\textit{foo $@$ bar = foobar}}\\ +\bl{\textit{baz $@\, []$ = baz}} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Languages, Strings} + +\begin{itemize} +\item \alert{\bf Strings} are lists of characters, for example +\begin{center} +\bl{$[]$},\;\bl{$abc$} \hspace{2cm}(Pattern match: \bl{$c\!::\!s$}) +\end{center}\bigskip + + +\item A \alert{\bf language} is a set of strings, for example\medskip +\begin{center} +\bl{$\{[], hello, \textit{foobar}, a, abc\}$} +\end{center}\bigskip + +\item \alert{\bf Concatenation} of strings and languages + +\begin{center} +\begin{tabular}{rcl} +\bl{$\textit{foo}\;@\;bar$} & \bl{$=$} & \bl{$\textit{foobar}$}\medskip\\ +\bl{$A\;@\;B$} & \bl{$\dn$} & \bl{$\{ s_1\,@\,s_2 \;\mid\; s_1 \in A \wedge s_2 \in B\}$} +\end{tabular} +\end{center} + +%\item The \alert{\bf meaning} of a regular expression is a set of +% strings, or language. +\end{itemize} + +\only<2>{ +\begin{textblock}{4}(10.5,8) +\small +Let + +\bl{$A = \{foo, bar\}$} \bl{$B = \{a, b\}$} +\[ +\bl{A \,@\, B = \{fooa, foob, bara, barb\}} +\] +\end{textblock}} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] + \frametitle{Two Corner Cases} + + \Large + \begin{center} + \bl{$A \,@\, \{[]\} = \;?$}\bigskip\bigskip\pause\\ + \bl{$A \,@\, \{\} = \;?$} + \end{center} + + \end{frame} + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{The Meaning of a Regex} + + ...all the strings a regular expression can match. + +\begin{center} + \begin{tabular}{rcl} + \bl{$L(\ZERO)$} & \bl{$\dn$} & \bl{$\{\}$}\\ + \bl{$L(\ONE)$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ + \bl{$L(c)$} & \bl{$\dn$} & \bl{$\{[c]\}$}\\ + \bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\ + \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \,@\, L(r_2)$}\\ + \bl{$L(r^*)$} & \bl{$\dn$} & \\ + \end{tabular} +\end{center} + +\begin{textblock}{14}(1.5,13.5)\small +\bl{$L$} is a function from regular expressions to +sets of strings (languages):\smallskip\\ +\bl{\quad$L$ : Rexp $\Rightarrow$ Set$[$String$]$} +\end{textblock} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] + \frametitle{The Power Operation} + + \begin{itemize} + \item The \alert{\textbf{\boldmath$n$th Power}} of a language: + + \begin{center} + \begin{tabular}{lcl} + \bl{$A^0$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ + \bl{$A^{n+1}$} & \bl{$\dn$} & \bl{$A \,@\, A^n$} + \end{tabular} + \end{center}\bigskip + + \item[] For example + + \begin{center} + \begin{tabular}{lcl@{\hspace{10mm}}l} + \bl{$A^4$} & \bl{$=$} & \bl{$A \,@\, A \,@\, A \,@\, A$} & \bl{$(@\,\{[]\})$}\\ + \bl{$A^1$} & \bl{$=$} & \bl{$A$} & \bl{$(@\,\{[]\})$}\\ + \bl{$A^0$} & \bl{$=$} & \bl{$\{[]\}$}\\ + \end{tabular} + \end{center} + + \end{itemize} + + \end{frame} + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{The Meaning of a Regex} + +\begin{textblock}{15}(1,4) + \begin{tabular}{rcl} + \bl{$L(\ZERO)$} & \bl{$\dn$} & \bl{$\{\}$}\\ + \bl{$L(\ONE)$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ + \bl{$L(c)$} & \bl{$\dn$} & \bl{$\{[c]\}$}\\ + \bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\ + \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$\{ s_1 \,@\, s_2 \;|\; s_1 \in L(r_1) \wedge s_2 \in L(r_2) \}$}\\ + \bl{$L(r^*)$} & \bl{$\dn$} & \onslide<2->{\bl{$\bigcup_{0 \le n} L(r)^n$}}\\ + \end{tabular}\bigskip + +%\onslide<2->{ +%\hspace{5mm}\bl{$L(r)^0 \;\dn\; \{[]\}$}\\ +%\bl{$L(r)^{n+1} \;\dn\; L(r) \,@\, L(r)^n$}\hspace{9mm}\onslide<3->{\small\textcolor{gray}{(append on sets)}\\ +%\small\hspace{5cm}\textcolor{gray}{$\{ s_1 @ s_2 \;|\; s_1\in L(r) \wedge s_2 \in L(r)^n \}$}} +%} +\end{textblock} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] + \frametitle{The Star Operation} + + \begin{itemize} + \item The \alert{\bf Kleene Star} of a \underline{language}: + \bigskip + + \begin{center} + \begin{tabular}{c} + \bl{$A\star \dn \bigcup_{0\le n} A^n$} + \end{tabular} + \end{center}\bigskip + + \item[] This expands to + + \[ + \bl{A^0 \cup A^1 \cup A^2 \cup A^3 \cup A^4 \cup \ldots} + \] + + or + + \small + \[ + \bl{\{[]\} \;\cup\; A \;\cup\; A\,@\,A \;\cup\; + A\,@\,A\,@\,A \;\cup\; A\,@\,A\,@\,A\,@\,A \cup \ldots} + \] + + \end{itemize} + + \end{frame} + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{The Meaning of a Regex} + +\begin{textblock}{15}(1,4) + \begin{tabular}{rcl} + \bl{$L(\ZERO)$} & \bl{$\dn$} & \bl{$\{\}$}\\ + \bl{$L(\ONE)$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ + \bl{$L(c)$} & \bl{$\dn$} & \bl{$\{[c]\}$}\\ + \bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\ + \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$\{ s_1 \,@\, s_2 \;|\; s_1 \in L(r_1) \wedge s_2 \in L(r_2) \}$}\\ + \bl{$L(r^*)$} & \bl{$\dn$} & \bl{$(L(r))\star$}\\ + \end{tabular} + +\end{textblock} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{The Meaning of Matching} + +\begin{bubble}[10cm] +\large\bf +A regular expression \bl{$r$} matches a string~\bl{$s$} +provided + +\begin{center} +\bl{$s \in L(r)$}\\ +\end{center} +\end{bubble}\bigskip\bigskip + +\ldots and the point of the next lecture is +to decide this problem as fast as possible (unlike Python, +Ruby, Java) + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] + \frametitle{Questions} + + \begin{itemize} + \item Say \bl{$A = \{[a],[b],[c],[d]\}$}.\bigskip + + \item[] + How many strings are in \bl{$A^4$}\,? + \bigskip\medskip\pause + + + \item[] + What if \bl{$A = \{[a],[b],[c],[]\}$};\\ + how many strings are then in \bl{$A^4$}\,? + \end{itemize} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% \begin{frame}[c] +% \frametitle{Languages (Sets of Strings)} + +% \begin{itemize} + +% \item A \alert{\bf Language} is a set of strings, for example\medskip +% \begin{center} +% \bl{$\{[], hello, foobar, a, abc\}$} +% \end{center}\bigskip + +% \item \alert{\bf Concatenation} for strings and languages + +% \begin{center} +% \begin{tabular}{rcl} +% \bl{$foo\;@\;bar$} & \bl{$=$} & \bl{$foobar$}\medskip\\ +% \bl{$A\;@\;B$} & \bl{$\dn$} & \bl{$\{ s_1\,@\,s_2 \;\mid\; s_1 \in A \wedge s_2 \in B\}$} +% \end{tabular} +% \end{center} +% \bigskip + +% \small +% \item [] For example \bl{$A = \{foo, bar\}$}, \bl{$B = \{a, b\}$} + +% \[ +% \bl{A \,@\, B = \{fooa, foob, bara, barb\}} +% \] + + + + +% \end{itemize} +% \end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% \begin{frame}[c] +% \frametitle{Two Corner Cases} + +% \Large +% \begin{center} +% \bl{$A \,@\, \{[]\} = \;?$}\bigskip\bigskip\pause\\ +% \bl{$A \,@\, \{\} = \;?$} +% \end{center} + +% \end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% \begin{frame}[c] +% \frametitle{The Meaning of a Regex} + +% ...all the strings a regular expression can match. + +% \begin{center} +% \begin{tabular}{rcl} +% \bl{$L(\ZERO)$} & \bl{$\dn$} & \bl{$\{\}$}\\ +% \bl{$L(\ONE)$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ +% \bl{$L(c)$} & \bl{$\dn$} & \bl{$\{[c]\}$}\\ +% \bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\ +% \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \,@\, L(r_2)$}\\ +% \bl{$L(r^*)$} & \bl{$\dn$} & \\ +% \end{tabular} +% \end{center} + +% \begin{textblock}{14}(1.5,13.5)\small +% \bl{$L$} is a function from regular expressions to +% sets of strings (languages):\smallskip\\ +% \bl{\quad$L$ : Rexp $\Rightarrow$ Set$[$String$]$} +% \end{textblock} + +% \end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% \begin{frame}[c] +% \frametitle{The Power Operation} + +% \begin{itemize} +% \item The \alert{\textbf{\boldmath$n$th Power}} of a language: + +% \begin{center} +% \begin{tabular}{lcl} +% \bl{$A^0$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ +% \bl{$A^{n+1}$} & \bl{$\dn$} & \bl{$A \,@\, A^n$} +% \end{tabular} +% \end{center}\bigskip + +% \item[] For example + +% \begin{center} +% \begin{tabular}{lcl@{\hspace{10mm}}l} +% \bl{$A^4$} & \bl{$=$} & \bl{$A \,@\, A \,@\, A \,@\, A$} & \bl{$(@\,\{[]\})$}\\ +% \bl{$A^1$} & \bl{$=$} & \bl{$A$} & \bl{$(@\,\{[]\})$}\\ +% \bl{$A^0$} & \bl{$=$} & \bl{$\{[]\}$}\\ +% \end{tabular} +% \end{center} + +% \end{itemize} + +% \end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% \begin{frame}[c] +% \frametitle{Written Exam} + +% \begin{itemize} +% \item Accounts for 80\%.\bigskip + +% \item The question ``\textit{Is this relevant for +% the exam?}'' is very demotivating for the lecturer!\bigskip\\ + +% \item Deal: Whatever is in the homework (and is not marked +% ``\textit{optional}'') is relevant for the exam.\bigskip + +% \item Each lecture has also a handout. There are also handouts about +% notation and Scala. +% \end{itemize} + +% \end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% \begin{frame}[t] +% \frametitle{Coursework} + +% \begin{itemize} +% \item Accounts for 20\%. Two strands. Choose \alert{\bf one}!\bigskip +% \end{itemize} + +% \begin{columns}[t] +% \begin{column}{.5\textwidth} +% \underline{\bf Strand 1}\medskip +% \begin{itemize} +% \item 4 programming tasks: +% \begin{itemize} +% \item matcher (4\%, 11.10.) +% \item lexer (5\%, 04.11.) +% \item parser (5\%, 22.11.) +% \item compiler (6\%, 13.12.) +% \end{itemize} +% \item in any lang.~you like,\\ but I want to see the\\ code +% \end{itemize} +% \end{column} + +% \hspace{-45pt}\vrule{}\hspace{10pt} +% \begin{column}{.5\textwidth} +% \underline{\bf Strand 2}\smallskip\begin{itemize} +% \item one task: prove the correctness of a regular expression matcher in +% the \underline{Isabelle} theorem prover +% \item 20\%, submission on~13.12.\hspace{-5mm}\mbox{} +% \end{itemize} +% \end{column} +% \end{columns}\medskip + +% \small +% \begin{itemize} +% \item Solving more than one strand will {\bf not} give you more +% marks. + +% \end{itemize} + +% \end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%\begin{frame}[c] +%\frametitle{Lecture Capture} +% +%\begin{itemize} +%\item Hope it works\ldots\pause actually no, it does not!\medskip\pause +%\item It is important to use lecture capture wisely\\ (it is only the ``baseline''): +%\begin{itemize} +%\item Lecture recordings are a study and revision aid. +%\item Statistically, there is a clear and direct link between attendance and +% attainment: students who do not attend lectures, do less well in exams. +%\end{itemize} +% +%\item Attending a lecture is more than watching it online -- if you do not +%attend, you miss out! +% +%\end{itemize} +% +%\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{\begin{tabular}{c}\\[3cm]\alert{Questions?}\end{tabular}} + + +\begin{tabular}{lll} + TAs: & Finley Warman & (took the module last year)\\ + & Chengsong Tan & (PhD student working on derivatives) +\end{tabular} +\mbox{} +\end{frame} + +\begin{frame}[c] +\end{frame} + +\begin{frame}[c] +\end{frame} + +\begin{frame}[c] +\end{frame} + +\begin{frame}[c] +\end{frame} + +\begin{frame}[c] +\end{frame} + +\begin{frame}[c] +\end{frame} + +\begin{frame}[c] +\end{frame} + +\begin{frame}[c] +\end{frame} + +\begin{frame}[c] +\end{frame} + +\begin{frame}[c] +\end{frame} + +\begin{frame}[c] +\end{frame} + +\begin{frame}[c] +\end{frame} + +\begin{frame}[c] +\end{frame} + +\begin{frame}[c] +\end{frame} + + +\begin{frame}[c] +\begin{mybox3}{Coursework} + Do we need to provide instructions on running the coursework files + if we're using languages other than Scala? Thanks +\end{mybox3}\pause + +\begin{mybox2}{Zip-File for Coursework} + Please, please submit a zipfile that generates a subdirectory + \begin{center} + \texttt{NameFamilyName} + \end{center} +\end{mybox2} +\end{frame} + + +\begin{frame}[c] +\begin{mybox3}{Coursework} + What is the purpose of the workshop session on the timetable? + + Slightly confused about how to undertake cw1 and what exactly we + should be implementing. This is more for clarification of the cw1 + structure, including the implementation and questions present in + cw1. +\end{mybox3} +\end{frame} + +\begin{frame}[c] +\begin{mybox3}{What is the trick?}\small + What was the trick to improve the evil regular expressions matcher + to have such good results compared to other programming languages? + Is it working better on casual regular expressions (the ones that + Python and Java handle pretty well), too? Or was it just optimised + for these evil ones? +\end{mybox3} + +\begin{mybox3}{}\small + It was shown in the lectures that the pattern matching algorithms + currently implemented in popular programming languages (Python, JS, + Java, etc) are far slower than the algorithm we are going to be + implementing in this module. My question is why do these programming + languages not implement the algorithm that we are going to implement + in this module? +\end{mybox3} +\end{frame} + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] + \frametitle{Thanks to Martin Mikusovic} + +\bigskip +\begin{center} +\begin{tikzpicture} + \begin{axis}[ + xlabel={$n$}, + x label style={at={(1.05,0.0)}}, + ylabel={time in secs}, + enlargelimits=false, + xtick={0,5,...,30}, + xmax=33, + ymax=35, + ytick={0,10,...,30}, + scaled ticks=false, + axis lines=left, + width=9cm, + height=5.5cm, + legend entries={Java 8, Python, JavaScript, Swift}, + legend pos=north west, + legend cell align=left] +\addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data}; +\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data}; +\addplot[red,mark=*, mark options={fill=white}] table {re-js.data}; +\addplot[magenta,mark=*, mark options={fill=white}] table {re-swift.data}; +\end{axis} +\end{tikzpicture} +\end{center} + +Regex: \bl{$(a^*)^* \cdot b$} + +Strings of the form \bl{$\underbrace{\,a\ldots a\,}_{n}$} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Same Example in Java 9+} + +\begin{center} +\begin{tikzpicture} + \begin{axis}[ + xlabel={$n$}, + x label style={at={(1.09,-0.15)}}, + ylabel={time in secs}, + scaled x ticks=false, + enlargelimits=false, + xtick distance=10000, + xmax=44000, + ytick={0,10,...,30}, + ymax=35, + axis lines=left, + width=9cm, + height=5cm, + legend entries={Java \liningnums{9}+}, + legend pos=north west, + legend cell align=left] +\addplot[blue,mark=square*,mark options={fill=white}] table {re-java9.data}; +\end{axis} +\end{tikzpicture} +\end{center} + +Regex: \bl{$(a^*)^* \cdot b$} + +Strings of the form \bl{$\underbrace{\,a\ldots a\,}_{n}$} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% Questions + +\begin{frame}[c] +\begin{mybox3}{} + Are there any (common) languages that have a built-in regex + implementation matching the set of functions of a formal 'simple' + regular expression, as opposed to an 'extended' regular expression + implemented in most regex-supporting languages? +\end{mybox3} +\end{frame} + +\begin{frame}[c] +\begin{mybox3}{Regexes} + Can we determine all the possible regular expressions matching a + certain string? If we take into account all the possible ways to + combine the operations: \bl{$\ZERO$}, \bl{$\ONE$}, + \bl{$r_1 + r_2$}, \bl{$r_1 \cdot r_2$}, \bl{$r^*$}? +\end{mybox3} +\end{frame} + +\begin{frame}[c] +\begin{mybox3}{\bl{$L$} + Equivalence} + When we explain why two regular expressions are not equivalent, what + method is better for us, using mathematics formulas or making an + example? +\end{mybox3} +\begin{mybox3}{} + Meaning of Regex and Operations +\end{mybox3} +\end{frame} + +\begin{frame}[c] +\begin{mybox3}{\bl{$L$}} + Can the function L be applied to anything other than regular + expressions? For example would L(L(c)) return anything? +\end{mybox3} + +\hfill $\Rightarrow$ No +\end{frame} + +\begin{frame}[c] +\begin{mybox3}{\bl{$(a?)\{n\} \cdot a\{n\}$}} + In the evil regexes section, is there any reason why in the regex + \texttt{[a?]\{n\}[a]\{n\}} the square brackets are used? It is defined as a + single character from the square brackets, however there is just one + character, so it seems like it is not necessary. Maybe it is just + necessary for the first part, because ? is a token instead of a + character and we need to refer to a? as a ``unit''? Could regular + brackets be used instead? Is there any difference apart from the + fact that it would create a group? Also, are the regexes + \texttt{[a?]\{n\}} and + \texttt{a\{0,3\}} equivalent? +\end{mybox3} +\end{frame} + +\begin{frame}[c] +\begin{mybox3}{Python + Parser Combinators (CW3)}\small + Hi Christian, + + I don’t see a problem: you certainly have higher order functions and + it is easy to implement algebraic data types using classes. As far + as I can see that’s all you need. You don’t get the static types but + that should be obvious. Basically if you can do it in LISP you can + do it in Python. The only problem could be stack overflows due to a + lack of tail recursion optimisation. On the other hand you can + simulate laziness using generators. + + Cheers, + Thorsten +\end{mybox3} + +Trees \url{https://youtu.be/7tCNu4CnjVc} + +Laziness \url{https://youtu.be/5jwV3zxXc8E} + +\end{frame} + +\begin{frame}[c] +\begin{mybox3}{} + What suggestions do you have for us to get the most out of this + module, especially in the online format? I.e. form discussion + groups, will you have office hours? +\end{mybox3} + +\small +\hfill $\Rightarrow$\mbox{} Discussion Forum on KEATS + +\hfill online tutorial sessions + +\end{frame} + +\begin{frame}[c] + \small +\begin{mybox3}{} +Where do most students struggle with this module? What will the format +of the exam be? What is the most efficient way of studying for the +exam? There are plenty of resources available on KEATS, but is there +anything else you'd recommend us to study? Although (just by skimming +the headings) the module seems to be a combination of practical and +theoretical matters, exactly in what field would the syllabus be +applied? Besides these questions and the ones other students asked, is +there anything else we should know? Thank you! +\end{mybox3} +\end{frame} + + +\begin{frame}[c] +\end{frame} + +\begin{frame}[c] +\end{frame} + +\begin{frame}[c] +\end{frame} + +\begin{frame}[c] +\end{frame} + +\begin{frame}[c,fragile] + +\end{frame} + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\end{document} + +%%% Local Variables: +%%% mode: latex +%%% TeX-master: t +%%% End: + diff -r 49d21814a633 -r 771396fa6cc4 style.sty --- a/style.sty Fri Sep 16 12:52:21 2022 +0100 +++ b/style.sty Thu Sep 29 20:54:02 2022 +0100 @@ -75,10 +75,10 @@ % CW deadlines -\def\cwONE{18 October} -\def\cwTWO{\textcolor{red}{11 November}} % 8 November -\def\cwTHREE{\textcolor{red}{3 December}} %29 November -\def\cwFOUR{\textcolor{red}{17 December}} -\def\cwFIVE{25 January} +\def\cwONE{17 October} +\def\cwTWO{11 November} +\def\cwTHREE{2 December} +\def\cwFOUR{15 December} +\def\cwFIVE{19 January} -\def\cwISABELLE{11 December} +%%\def\cwISABELLE{11 December}