% !TEX program = xelatex+
−
\documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer}+
−
\usepackage{../slides}+
−
\usepackage{../graphicss}+
−
\usepackage{../langs}+
−
\usepackage{../data}+
−
\usetikzlibrary{cd}+
−
\usepackage{listings-rust}+
−
+
−
+
−
\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 Lunch with a Lecturer (29 March)\\[5mm] +
−
%  \end{tabular}}+
−
%+
−
%  I teach CFL (compilers) and PEP (Scala)\bigskip+
−
%+
−
%  \begin{itemize}+
−
%  \item did undergraduate in Germany+
−
%  \item Master in St Andrews+
−
%  \item PhD in Cambridge  +
−
%  \end{itemize}\bigskip\bigskip+
−
%+
−
%  use mainly the Isabelle theorem prover in my work (see 6CCS3VER)+
−
%+
−
%  write code in functional programming languages (Scala, SML, Ocaml, Haskell)+
−
%\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{}In PEP \& CFL \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{}+
−
% %\begin{mybox3}{}\it+
−
%  ``This conversation is interesting to me, and I've researched it a little bit... I also disagree with Dr. Urban on the cost/benefit of non-GC languages...[..]\\+
−
%+
−
%  But regardless, Scala is a lot slower than, say, C or Rust. To say it's not is basically wrong (imo)....[..]+
−
%  ''\\+
−
%\mbox{}\hfill-- Oliver Iliffe,  discussion this year in PEP+
−
%\end{mybox3}\pause+
−
%+
−
%\end{frame}+
−
+
−
%\begin{frame}<1-10>+
−
%\end{frame}  +
−
+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+
−
\begin{frame}[t]+
−
\frametitle{%  +
−
  \begin{tabular}{@ {}c@ {}}+
−
  \\[-3mm]+
−
  \LARGE Compilers and \\[-1mm] +
−
  \LARGE Formal Languages\\[-5mm] +
−
  \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 Hour: & Thurdays 15 -- 16\\+
−
  Location: & N7.07 (North Wing, Bush House)\\+
−
  Slides \& Progs: & KEATS\\+
−
  Pollev: & \texttt{\alert{https://pollev.com/cfltutoratki576}}\\  +
−
  \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=3mm] (0) -- (A); +
−
  \draw [->,line width=3mm] (A) -- (B); +
−
  \draw [->,line width=3mm] (B) -- (C); +
−
  \draw [->,line width=3mm] (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}+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+
−
+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+
−
% {+
−
% \setbeamercolor{background canvas}{bg=cream}+
−
% \begin{frame}[c]+
−
+
−
% \frametitle{}+
−
% \begin{mybox3}{}\it+
−
%    ``I enjoyed the module - it was genuinely the stand out academic+
−
% experience of my undergraduate degree, and very much influenced my+
−
% career interests. In fact I am currently working at ARM, in their Open+
−
% Source Software group, on AArch64 specific optimisations for the+
−
% Java/Kotlin compiler that forms part of the Android Runtime.''\\+
−
% \mbox{}\hfill-- Hari Limaye in year 2021/22+
−
% \end{mybox3}\pause+
−
+
−
+
−
% Student numbers in CFL\medskip\\+
−
% \begin{tabular}{ll}+
−
% 2019: & 32\\  +
−
% 2020: & 59\\  +
−
% 2021: & 109\\+
−
% 2022: & 121\\  +
−
% \end{tabular}  +
−
+
−
% \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} /+
−
    \here{https://www.youtube.com/watch?v=oE2uls6iIEU})}}+
−
\end{flushright}+
−
\end{textblock}+
−
+
−
\end{frame}+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     +
−
+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+
−
\begin{frame}[c]+
−
\frametitle{Some Housekeeping}+
−
+
−
\textbf{Exam will be computer-based, invigilated in some big examination hall:}\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}+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +
−
+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +
−
{\definecolor{rred}{HTML}{C0504D}+
−
\setbeamercolor{background canvas}{bg=cream}+
−
\begin{frame}[c]+
−
\frametitle{Students in CFL}+
−
+
−
\begin{center}+
−
\begin{tikzpicture}+
−
  \begin{axis}[symbolic x coords={2016,2017,2018,2019,2020,2021,2022,2023},+
−
    width  = \textwidth,+
−
    height = 5cm,+
−
    bar width=8mm,+
−
    nodes near coords,+
−
    axis lines = left,+
−
    text=black,+
−
    ymin=0,+
−
    clip=false,+
−
    hide y axis,+
−
    axis line style={-},+
−
    name=mygraph+
−
    ]+
−
    +
−
\addplot[ybar,style={rred,fill=rred!75,mark=none},text=black] coordinates {+
−
(2023,183)+
−
(2022,112)+
−
(2021,98)+
−
(2020,59)+
−
(2019,38)+
−
(2018,20)+
−
(2017,22)+
−
(2016,8)};+
−
\end{axis}+
−
\node[anchor=north, yshift=-10mm] at (mygraph.south) {\small{}Student numbers since the start of the compiler module.};+
−
+
−
\end{tikzpicture}+
−
\end{center}+
−
+
−
+
−
\end{frame}+
−
}+
−
+
−
+
−
+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +
−
{+
−
\setbeamercolor{background canvas}{bg=cream}+
−
\begin{frame}[c]+
−
\frametitle{Homework}+
−
+
−
Until 2 years ago: I did not give out solutions; students+
−
sent emails to me and I responded to them individually.\bigskip\\+
−
+
−
+
−
Since last year: We will review the homework mainly during the SGTs.\bigskip\\\pause+
−
+
−
I will still choose the questions from the HW for the exam, but there might be+
−
some larger amount of deviation.+
−
+
−
\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, Swift)\\\pause+
−
you can use any code I show you and is uploaded to KEATS\ldots\textbf{BUT NOTHING ELSE!}+
−
+
−
\end{frame}+
−
+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +
−
{+
−
\setbeamercolor{background canvas}{bg=cream}+
−
\begin{frame}[c,fragile]+
−
\frametitle{Ammonite \& Scala 3}+
−
+
−
I will show you all my code in Amm / Scala 3+
−
+
−
\begin{minipage}{1.4\textwidth}+
−
\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]+
−
$ amm+
−
Loading...+
−
Welcome to the Ammonite Repl 2.5.9 (Scala 3.2.2 Java 17.0.7)+
−
scala> 1 + 2+
−
res0: Int = 3+
−
\end{lstlisting} %% $+
−
\end{minipage}\medskip+
−
\pause+
−
+
−
Do not use Amm + Scala 2!+
−
+
−
\begin{minipage}{1.4\textwidth}+
−
\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]+
−
$ amm2+
−
Loading...+
−
Welcome to the Ammonite Repl 2.5.9 (Scala 2.13.11 Java 17.0.7)+
−
scala> +
−
\end{lstlisting} %% $+
−
\end{minipage}+
−
\end{frame}+
−
}+
−
+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +
−
{+
−
\setbeamercolor{background canvas}{bg=cream}+
−
\begin{frame}[c]+
−
\frametitle{For Install Problems}+
−
+
−
\begin{itemize}+
−
\item Harry Dilnot (harry.dilnot@kcl.ac.uk) \\+
−
  \;\;Windows expert+
−
\item Meilai Ji (meilai.ji@kcl.ac.uk) +
−
\end{itemize}+
−
  +
−
\end{frame}+
−
}+
−
+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +
−
{+
−
\setbeamercolor{background canvas}{bg=cream}+
−
\begin{frame}[c]+
−
+
−
\begin{minipage}{1.3\textwidth}+
−
\begin{mybox3}{}\it\small+
−
Unequivocally the worst module I've taken on this course. The subject+
−
matter is fascinating, however the insistence on the use of this+
−
abomination of a language "Scala" completely ruins it. If you're going+
−
to teach something as complex as this, use a proper language, not some+
−
"object oriented functional" abomination. Use C, you know, the+
−
language that real compilers are written in. I will go to the end of+
−
the earth to dissuade others from taking this module so long as Scala+
−
is still being used.\\+
−
\mbox{}\hfill-- Lone voice in the end-of-year feedback in 2019+
−
\end{mybox3}+
−
\end{minipage}\bigskip+
−
+
−
\small (for alternative opinions check ``What the students say'' on KEATS)+
−
  +
−
\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}+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   +
−
{+
−
\setbeamercolor{background canvas}{bg=cream}+
−
\begin{frame}[t]+
−
\frametitle{Notation for REs}+
−
  +
−
\end{frame}  +
−
}+
−
+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   +
−
{+
−
\setbeamercolor{background canvas}{bg=cream}+
−
\begin{frame}[t]+
−
  +
−
\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}+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+
−
+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +
−
{+
−
\setbeamercolor{background canvas}{bg=cream}+
−
\begin{frame}[c]+
−
\frametitle{Rust vs.~Scala (from PEP)}+
−
+
−
\mbox{}+
−
+
−
\begin{minipage}{1.3\textwidth}+
−
\begin{mybox3}{}\it\small+
−
\textbf{Re: Another question of purely academic interest about regex implementation in cw3}+
−
+
−
This conversation is interesting to me, and I've researched it a+
−
little bit [...] I also disagree with Dr.~Urban on the cost/benefit of+
−
non-GC languages [...]\smallskip+
−
+
−
But regardless, Scala is a lot slower than, say, C or Rust. To say+
−
it's not is basically wrong (imo). Perhaps one could argue that some+
−
of the guarantees Scala has makes it easier to write multi-threaded+
−
programs that utilise more of the CPU... but, in my opinion, this is+
−
also a bit misleading. Most CPUs have something like 4 to 12 cores+
−
nowadays. It's very possible that a given Scala program runs 4-12x+
−
slower than its Rust equivalent. Would you rather have your program+
−
run quickly and use a single core, or have it run equally+
−
quickly... and... hog your entire CPU for its duration?\ldots{}+
−
+
−
\mbox{}\hfill-- Oliver Iliffe,  discussion from PEP+
−
\end{mybox3}+
−
\end{minipage}+
−
+
−
\end{frame}+
−
}+
−
+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +
−
{+
−
\setbeamercolor{background canvas}{bg=cream}+
−
\begin{frame}[c]+
−
\frametitle{Regex Lib in Rust}+
−
+
−
\begin{center}+
−
\includegraphics[scale=0.34]{../pics/rust-regex.png}+
−
\end{center}+
−
+
−
\end{frame}+
−
}+
−
+
−
+
−
+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+
−
{+
−
\setbeamercolor{background canvas}{bg=cream}+
−
\begin{frame}[c,fragile]+
−
+
−
\begin{columns}[t,onlytextwidth]+
−
\begin{column}{1\textwidth}+
−
\small re: \bl{$(abc)^{\{n\}}$}\quad str: \bl{$\underbrace{abc\ldots{}abc}_n$}\medskip\\  +
−
\begin{tikzpicture}\footnotesize+
−
\begin{axis}[+
−
    xlabel={$n$},+
−
    x label style={at={(1.07,0.0)}},+
−
    ylabel={time in secs},+
−
    enlargelimits=false,+
−
    xmax=65000,+
−
    ymax=100,+
−
    xtick={0,15000,...,60000},+
−
    ytick={0,10,...,90},+
−
    scaled ticks=false,+
−
    axis lines=left,+
−
    width=7cm,+
−
    height=5cm]+
−
    \addplot[black,mark=square*,mark options={fill=red}] table [x=x, y=y, col sep=comma, row sep=crcr]+
−
    {x, y\\+
−
      0, 0\\+
−
     5000, 0.487\\ +
−
     10000, 1.650\\+
−
     15000, 3.617\\+
−
     20000, 6.462\\+
−
     25000, 10.736\\+
−
     30000, 17.665\\+
−
     35000, 25.662\\+
−
     40000, 36.422\\+
−
     45000, 49.119\\+
−
     50000, 62.058\\+
−
     55000, 75.941\\+
−
     60000, 93.022\\+
−
    };+
−
\end{axis}+
−
\end{tikzpicture}+
−
\end{column}+
−
\end{columns}+
−
+
−
\begin{textblock}{10}(8.4,3.8)+
−
\tiny  +
−
\begin{lstlisting}[language=Rust]+
−
extern crate regex;+
−
+
−
use regex::Regex;+
−
use std::time::Instant;+
−
+
−
// bounded regular expression example+
−
+
−
fn main() {+
−
   for bound in (0..=60000).step_by(5000) {+
−
   +
−
      let re = Regex::new(&format!("(abc){{{}}}", bound)).unwrap();+
−
      let text = "abc".repeat(bound);+
−
+
−
      let start_time = Instant::now();+
−
      let is_match = re.is_match(&text);+
−
      let elapsed_time = start_time.elapsed().as_secs_f64();+
−
+
−
      println!("Bound: {}, Match: {}, Time: {} seconds", bound, is_match, elapsed_time);+
−
   }+
−
}+
−
\end{lstlisting}    +
−
\end{textblock}+
−
\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{Questions}+
−
+
−
  \begin{itemize}+
−
  \item Assume a set $A$ contains 4 strings and a set $B$+
−
  contains 7 strings. None of the strings is the empty+
−
  string.+
−
+
−
  \item How many strings are in $A \,@\, B$?+
−
  \end{itemize}+
−
+
−
  +
−
\end{frame}+
−
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  +
−
+
−
{+
−
\setbeamercolor{background canvas}{bg=cream}+
−
\begin{frame}[c]+
−
+
−
\begin{minipage}{1.3\textwidth}+
−
+
−
\end{minipage}+
−
\includegraphics[scale=0.4]{../pics/chatgpt.png}+
−
\end{frame}+
−
}+
−
+
−
{+
−
\setbeamercolor{background canvas}{bg=cream}+
−
\begin{frame}[c]+
−
\frametitle{\dots{}for amusement}+
−
+
−
\begin{minipage}{1.3\textwidth}+
−
\includegraphics[scale=0.4]{../pics/chatgpt1.png}+
−
\end{minipage}+
−
+
−
\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}\\[1cm]\alert{Questions?}\end{tabular}}+
−
+
−
+
−
\begin{tabular}{lll}+
−
  SGT TAs: & Flavio Melinte Citea & (was a KURF last summer)\\+
−
           & Krishi Wali \\+
−
           & Meilai Ji \medskip\\+
−
  Amm Helpers & Harry Dilnot & (harry.dilnot@kcl.ac.uk)\\+
−
              & Meilai Ji & (meilai.ji@kcl.ac.uk)\medskip\\+
−
\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}{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}+
−
\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]+
−
\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: +
−
+
−