afl-material: comparison slides/slides02.tex

equal deleted inserted replaced

-:b5d57d7064bb
+:2be8c4c77418
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
+\begin{frame}[t]
-\frametitle{\begin{tabular}{@ {}c@ {}}
+\frametitle{\Large
-An Efficient Regular\\[-1mm]
+Lets Implement an Efficient\\[-2mm]
-Expression Matcher\end{tabular}}
+Regular Expression Matcher}
 \footnotesize
 \begin{center}
-{\normalsize Graphs: \bl{$a^{?\{n\}} \cdot a^{\{n\}}$} and strings \bl{$\underbrace{\,a\ldots a\,}_{n}$}}\smallskip\\
+{\normalsize Graphs: \bl{$a^{?\{n\}} \cdot a^{\{n\}}$} and strings \bl{$\underbrace{\,a\ldots a\,}_{n}$}}\medskip\\
 \begin{tabular}{@{}cc@{}}
 \begin{tikzpicture}
 \begin{axis}[
 xlabel={$n$},
 x label style={at={(1.05,0.0)}},
 scaled ticks=false,
 axis lines=left,
 width=5cm,
 height=4.5cm,
 legend entries={Scala V2,Scala V3},
-legend pos=north west,
+legend pos=north east,
 legend cell align=left]
 \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}
 \end{tabular}
 \end{center}
 \small
-In the handouts is a similar graph for \bl{$(a^*)^* \cdot b$} and Java.
+In the handouts is a similar graph for \bl{$(a^*)^* \cdot b$} and Java 8.
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{itemize}
 \item \alert{R}egular \alert{e}xpression \alert{D}enial \alert{o}f \alert{S}ervice (ReDoS)\bigskip
 \item Evil regular expressions\medskip
 \begin{itemize}
-\item \bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$}
+\item \bl{$a^{?\{n\}} \cdot a^{\{n\}}$}
 \item \bl{$(a^*)^*$}
 \item \bl{$([a$\,-\,$z]^+)^*$}
 \item \bl{$(a + a \cdot a)^*$}
-\item \bl{$(a + a?)^*$}
+\item \bl{$(a + a^?)^*$}
 \end{itemize}
 \item sometimes also called \alert{catastrophic backtracking}
 \end{itemize}
 \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{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}The Meaning of a\\[-2mm]
+\frametitle{
-Regular Expression\end{tabular}}
+The Meaning of a\\[-2mm]
+Regular Expression}
 \begin{textblock}{15}(1,4)
 \begin{tabular}{rcl}
 \bl{$L(\ZERO)$}  & \bl{$\dn$} & \bl{$\{\}$}\\
 \bl{$L(\ONE)$}     & \bl{$\dn$} & \bl{$\{[]\}$}\\
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
+\begin{frame}[t]
-\frametitle{Semantic Derivative}
+\frametitle{Semantic Derivative\\[5mm]}
 \begin{itemize}
 \item The \alert{\bf Semantic Derivative} of a
-\underline{language}\\ wrt to a character \bl{$c$}:
+\underline{language}\\ w.r.t.~to a character \bl{$c$}:
 \bigskip
 \begin{center}
 \bl{$\Der\,c\,A \dn \{ s \;|\;  c\!::\!s \in A\}$ }
-\end{center}\bigskip\bigskip\bigskip
+\end{center}\bigskip
 For \bl{$A = \{\textit{foo}, \textit{bar}, \textit{frak}\}$} then
 \begin{center}
 \bl{\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}l}
 $\Der\,f\,A$ & $=$ & $\{\textit{oo}, \textit{rak}\}$\\
 $\Der\,b\,A$ & $=$ &  $\{\textit{ar}\}$\\
-$\Der\,a\,A$ & $=$ & $\{\}$\\\pause
+$\Der\,a\,A$ & $=$ & $\{\}$\pause
 \end{tabular}}
 \end{center}
 \small
 We can extend this definition to strings
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}The Specification\\ of Matching\end{tabular}}
+\frametitle{The Specification\\ for Matching}
 \begin{bubble}[10cm]
 \large
 A regular expression \bl{$r$} matches a string~\bl{$s$}
 provided
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}
+\frametitle{
 When Are Two Regular\\[-1mm]
-Expressions Equivalent?\end{tabular}}
+Expressions Equivalent?}
 \large
 \begin{center}
 \bl{$r_1 \equiv r_2 \;\;\dn\;\; L(r_1) = L(r_2)$}
 \end{center}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[t]
 \frametitle{Simplification Rules}
 \begin{center}
 \bl{\begin{tabular}{rcl}
 $r + \ZERO$  & $\equiv$ & $r$\\
 $\ZERO + r$  & $\equiv$ & $r$\\
 $r \cdot \ONE$ & $\equiv$ & $r$\\
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[t]
-\frametitle{A Matching Algorithm}
+\frametitle{A Matching Algorithm (1)}
 \ldots{}whether a regular expression can match the empty string:
 \begin{center}
 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
-\frametitle{The Algorithm}
+\frametitle{\mbox{The Brzozowski Algorithm}}
 \begin{center}
 \begin{tabular}{l}
-\bl{$\textit{matches}\,r\,s \dn \textit{nullable}(\ders\,r\,s)$}
+\bl{$\textit{matches}\,r\,s \dn \textit{nullable}(\ders\;s\;r)$}
 \end{tabular}
 \end{center}
 \end{frame}
 %%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[t]
-\frametitle{An Example}
+\frametitle{Brzozowski: An Example}
 Does \bl{$r_1$} match \bl{$abc$}?
 \begin{center}
 \begin{tabular}{@{}rl@{}l@{}}
 Step 1: & build derivative of \bl{$a$} and \bl{$r_1$} & \bl{$(r_2 = \der\,a\,r_1)$}\smallskip\\
 Step 2: & build derivative of \bl{$b$} and \bl{$r_2$} & \bl{$(r_3 = \der\,b\,r_2)$}\smallskip\\
 Step 3: & build derivative of \bl{$c$} and \bl{$r_3$} & \bl{$(r_4 = \der\,c\,r_3)$}\smallskip\\
 Step 4: & the string is exhausted: & \bl{($nullable(r_4))$}\\
 & test whether \bl{$r_4$} can recognise\\
-& the empty string\smallskip\\
+& the empty string\medskip\\
 Output: & result of the test\\
 & $\Rightarrow \bl{\textit{true}} \,\text{or}\,
 \bl{\textit{false}}$\\
 \end{tabular}
 \end{center}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
-\frametitle{Oops\ldots\bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$}}
+\frametitle{Oops\ldots \;\bl{$a^{?\{n\}} \cdot a^{\{n\}}$}}
 \begin{center}
 \begin{tikzpicture}
 \begin{axis}[
 xlabel={$n$},
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
+\begin{frame}[t]
-\frametitle{A Problem}
+\frametitle{A Problem\medskip}
 We represented the ``n-times'' \bl{$a^{\{n\}}$} as a
 sequence regular expression:
 \begin{center}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[t]
-\frametitle{\bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$}}
+\frametitle{Brzozowski: \bl{$a^{?\{n\}} \cdot a^{\{n\}}$}}
 \begin{center}
 \begin{tikzpicture}
 \begin{axis}[
 xlabel={$n$},
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
-\frametitle{Simplifiaction}
+\frametitle{Simplification Rules}
 \begin{center}
 \bl{\begin{tabular}{rcl}
 $r + \ZERO$       & $\Rightarrow$ & $r$\\
 $\ZERO + r$       & $\Rightarrow$ & $r$\\
 $r + r$           & $\Rightarrow$ & $r$
 \end{tabular}}
 \end{center}
 \footnotesize
-\lstinputlisting{../progs/app60.scala}
+\lstinputlisting[firstline=22,lastline=26]{../progs/app6.scala}
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
 \footnotesize
-\lstinputlisting{../progs/app6.scala}
+\lstinputlisting[firstline=1,lastline=21]{../progs/app6.scala}
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[t]
-\frametitle{\bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$}}
+\frametitle{Brzozowski: \bl{$a^{?\{n\}} \cdot a^{\{n\}}$}}
 \begin{center}
 \begin{tikzpicture}
 \begin{axis}[
 xlabel={$n$},
 \end{center}
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%\begin{frame}[c]
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%\frametitle{\bl{$(a^*)^* \cdot b$}}
+\begin{frame}[c]
-%
+\frametitle{
-%\begin{center}
+Another Example\\[-1mm]
-%\begin{tikzpicture}
+in Java \liningnums{8} and Python}
-%  \begin{axis}[
-%    xlabel={$n$},
+\begin{center}
-%    x label style={at={(1.09,0.0)}},
+\begin{tikzpicture}
-%    ylabel={time in secs},
+\begin{axis}[
-%    enlargelimits=false,
+xlabel={$n$},
-%    xmax=27,
+x label style={at={(1.05,0.0)}},
-%    xtick={0,5,...,20},
+ylabel={time in secs},
-%    ytick={0,5,...,25},
+enlargelimits=false,
-%    ymax=13,
+xtick={0,5,...,30},
-%    scaled ticks=false,
+xmax=33,
-%    axis lines=left,
+ymax=35,
-%    width=9cm,
+ytick={0,10,...,30},
-%    height=5cm,
+scaled ticks=false,
-%    legend entries={Scala V2},
+axis lines=left,
-%    legend pos=north west,
+width=9cm,
-%    legend cell align=left]
+height=5cm,
-%\addplot[green,mark=square*,mark options={fill=white}] table {re2a.data};
+legend entries={Java 8, Python},
-%% still needs to be done
+legend pos=north west,
-%%\addplot[black,mark=square*,mark options={fill=white}] table {re3a.data};
+legend cell align=left]
-%\end{axis}
+\addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};
-%\end{tikzpicture}
+\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};
-%\end{center}
+\end{axis}
-%
+\end{tikzpicture}
-%\end{frame}
+\end{center}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+Regex: \bl{$(a^*)^* \cdot b$}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
+Strings of the form \bl{$\underbrace{\,a\ldots a\,}_{n}$}
-\frametitle{\bl{$(a^*)^* \cdot b$}}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Same Example in Java \liningnums{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}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{and with Brzozowski}
 \begin{center}
 \begin{tikzpicture}
 \begin{axis}[
 xlabel={$n$},
 x label style={at={(1.09,0.0)}},
 ylabel={time in secs},
+scaled x ticks=false,
+xtick distance=2000000,
 enlargelimits=false,
+xmax=6400000,
 ytick={0,10,...,30},
 ymax=35,
 axis lines=left,
 width=9cm,
 height=5cm,
 legend entries={Scala V3},
-legend pos=north east,
+legend pos=north west,
 legend cell align=left]
 %\addplot[green,mark=square*,mark options={fill=white}] table {re2a.data};
 \addplot[black,mark=square*,mark options={fill=white}] table {re3a.data};
 \end{axis}
 \end{tikzpicture}
 \end{center}
-\end{frame}
+Regex: \bl{$(a^*)^* \cdot b$}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+Strings of the form \bl{$\underbrace{\,a\ldots a\,}_{n}$}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[t]
 \frametitle{What is good about this Alg.}

changeset 565	2be8c4c77418
parent 564	b5d57d7064bb
child 566	b153c04834eb