afl-material: comparison handouts/ho01.tex

equal deleted inserted replaced

-:f2d7b885b3e3
+:5dc452d7c08e
 \documentclass{article}
 \usepackage{../style}
 \usepackage{../langs}
 \usepackage{../graphics}
 \usepackage{../data}
+\usepackage{lstlinebgrd}
+\definecolor{capri}{rgb}{0.0, 0.75, 1.0}
 %%http://regexcrossword.com/challenges/cities/puzzles/1
 %%https://jex.im/regulex/
 %%https://www.reddit.com/r/ProgrammingLanguages/comments/42dlem/mona_compiler_development_part_2_parsing/
 %%https://www.reddit.com/r/ProgrammingLanguages/comments/43wlkq/formal_grammar_for_csh_tsch_sh_or_bash/
 %% https://www.debuggex.com
 %% https://jex.im/regulex/#!embed=false&flags=&re=%5E(a%7Cb)*%3F%24
 %% email validator
 %% http://www.ex-parrot.com/%7Epdw/Mail-RFC822-Address.html
+% https://jackfoxy.github.io/FsRegEx/emailregex.html
 %% regex testers
 % https://regex101.com
 % http://regexr.com
 \fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016, 2017}
 \section*{Handout 1}
 This module is about text processing, be it for web-crawlers,
-compilers, dictionaries, DNA-data and so on. When looking for a
+compilers, dictionaries, DNA-data, ad filters and so on.  When looking for a
 particular string, like $abc$ in a large text we can use the
 Knuth-Morris-Pratt algorithm, which is currently the most efficient
 general string search algorithm. But often we do \emph{not} just look
-for a particular string, but for string patterns. For example in
+for a particular string, but for string patterns. For example, in
 program code we need to identify what are the keywords (if, then,
-while, etc), what are the identifiers (variable names). A pattern for
+while, for, etc), what are the identifiers (variable names). A pattern for
 identifiers could be stated as: they start with a letter, followed by
-zero or more letters, numbers and underscores.  Also often we face the
+zero or more letters, numbers and underscores.  Often we also face the
 problem that we are given a string (for example some user input) and
 want to know whether it matches a particular pattern---be it an email
 address, for example. In this way we can exclude user input that would
 otherwise have nasty effects on our program (crashing it or making it
-go into an infinite loop, if not worse). The point is that the fast
+go into an infinite loop, if not worse). In tools like Snort, scanning
-Knuth-Morris-Pratt algorithm for strings is not good enough for such
+for computer viruses or filtering out spam usually involves scanning
-string patterns.\smallskip
+for some signature (essentially a string pattern).  The point is that
+the fast Knuth-Morris-Pratt algorithm for strings is not good enough
+for such string \emph{patterns}.\smallskip
 \defn{Regular expressions} help with conveniently specifying
 such patterns. The idea behind regular expressions is that
 they are a simple method for describing languages (or sets of
 strings)\ldots at least languages we are interested in in
 interest in studying them again in depth in this module? Well, one
 answer is in the following two graphs about regular expression
 matching in Python, Ruby and Java.
 \begin{center}
-\begin{tabular}{@{\hspace{-1mm}}c@{\hspace{-1mm}}c@{}}
+\begin{tabular}{@{\hspace{-1mm}}c@{\hspace{1mm}}c@{}}
+\begin{tikzpicture}
+\begin{axis}[
+title={Graph: $\texttt{(a*)*\,b}$ and strings
+$\underbrace{\texttt{a}\ldots \texttt{a}}_{n}$},
+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=5.5cm,
+height=4.5cm,
+legend entries={Python, Java},
+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};
+\end{axis}
+\end{tikzpicture}
+&
 \begin{tikzpicture}
 \begin{axis}[
 title={Graph: $\texttt{a?\{n\}\,a{\{n\}}}$ and strings
 $\underbrace{\texttt{a}\ldots \texttt{a}}_{n}$},
 xlabel={$n$},
 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}
-\begin{axis}[
-title={Graph: $\texttt{(a*)*\,b}$ and strings
-$\underbrace{\texttt{a}\ldots \texttt{a}}_{n}$},
-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=5.5cm,
-height=4.5cm,
-legend entries={Python, Java},
-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};
-\end{axis}
-\end{tikzpicture}
 \end{tabular}
 \end{center}
-\noindent This first graph shows that Python needs approximately 29
+\noindent This first graph shows that Python and Java need
-seconds for finding out whether a string of 28 \texttt{a}s matches the
+approximately 30 seconds to find out that the regular expression
-regular expression \texttt{a?\{28\}\,a\{28\}}.  Ruby is even slightly
+$\texttt{(a*)*\,b}$ does not match strings of 28 \texttt{a}s.
+Similarly, the second shows that Python needs approximately 29 seconds
+for finding out whether a string of 28 \texttt{a}s matches the regular
+expression \texttt{a?\{28\}\,a\{28\}}.  Ruby is even slightly
 worse.\footnote{In this example Ruby uses the slightly different
 regular expression \texttt{a?a?a?...a?a?aaa...aa}, where the
 \texttt{a?} and \texttt{a} each occur $n$ times. More such test
 cases can be found at \url{http://www.computerbytesman.com/redos/}.}
-Simlarly, Python and Java needs approximately 30 seconds to find out
+Admittedly, these regular expressions are carefully chosen to exhibit
-that the regular expression $\texttt{(a*)*\,b}$ does not match strings
+this exponential behaviour, but similar ones occur more often than one
-of 28 \texttt{a}s.  Admittedly, these regular expressions are
+wants in ``real life''. For example, on 20 July 2016 a similar regular
-carefully chosen to exhibit this exponential behaviour, but similar
+expression brought the webpage \href{http://stackexchange.com}{Stack
-ones occur more often than one wants in ``real life''. For example, on
+Exchange} to its knees:
-20 July 2016 a similar regular expression brought the webpage
-\href{http://stackexchange.com}{Stack Exchange} to its knees:
 \begin{center}
 \url{http://stackstatus.net/post/147710624694/outage-postmortem-july-20-2016}
 \end{center}
 out why Python and Ruby (and others) behave so badly when
 matching strings with evil regular expressions. But we will also look
 at a relatively simple algorithm that solves this problem much
 better than Python and Ruby do\ldots actually it will be two
 versions of the algorithm: the first one will be able to
-process strings of approximately 1,000 \texttt{a}s in 30
+process strings of approximately 1,100 \texttt{a}s in 23
 seconds, while the second version will even be able to process
-up to 7,000(!) in 30 seconds, see the graph below:
+up to 11,000(!) in 5 seconds, see the graph below:
 \begin{center}
 \begin{tikzpicture}
 \begin{axis}[
 title={Graph: $\texttt{a?\{n\}\,a{\{n\}}}$ and strings
 $\underbrace{\texttt{a}\ldots \texttt{a}}_{n}$},
 xlabel={$n$},
 x label style={at={(1.05,0.0)}},
 ylabel={time in secs},
 enlargelimits=false,
-xtick={0,3000,...,9000},
+xtick={0,3000,...,12000},
-xmax=10000,
+xmax=13000,
 ymax=32,
 ytick={0,5,...,30},
 scaled ticks=false,
 axis lines=left,
 width=7cm,
 The point of the definition of $L$ is that we can use it to
 precisely specify when a string $s$ is matched by a regular
 expression $r$, namely if and only if $s \in L(r)$. In fact we
 will write a program \pcode{match} that takes any string $s$
-and any regular expression $r$ as argument and returns
+and any regular expression $r$ as arguments and returns
 \emph{yes}, if $s \in L(r)$ and \emph{no}, if $s \not\in
 L(r)$. We leave this for the next lecture.
 There is one more feature of regular expressions that is worth
 mentioning. Given some strings, there are in general many
 sometimes contains hidden snares. They have practical importance
 (remember the shocking runtime of the regular expression matchers in
 Python, Ruby and Java in some instances and the problems in Stack
 Exchange and the Atom editor).  People who are not very familiar with
 the mathematical background of regular expressions get them
-consistently wrong (surprising given they are a supposed to be core
+consistently wrong (this is surprising given they are a supposed to be
-skill for computer scientists). The hope is that we can do better in
+core skill for computer scientists). The hope is that we can do better
-the future---for example by proving that the algorithms actually
+in the future---for example by proving that the algorithms actually
 satisfy their specification and that the corresponding implementations
 do not contain any bugs. We are close, but not yet quite there.
 Notwithstanding my fascination, I am also happy to admit that regular
 expressions have their shortcomings. There are some well-known
 ``theoretical'' shortcomings, for example recognising strings of the
 form $a^{n}b^{n}$ is not possible with regular expressions. This means
 for example if we try to regognise whether parentheses are well-nested
-is impossible with (basic) regular expressions.  I am not so bothered
+in an expression is impossible with (basic) regular expressions.  I am
-by these shortcomings. What I am bothered about is when regular
+not so bothered by these shortcomings. What I am bothered about is
-expressions are in the way of practical programming. For example, it
+when regular expressions are in the way of practical programming. For
-turns out that the regular expression for email addresses shown in
+example, it turns out that the regular expression for email addresses
-\eqref{email} is hopelessly inadequate for recognising all of them
+shown in \eqref{email} is hopelessly inadequate for recognising all of
-(despite being touted as something every computer scientist should
+them (despite being touted as something every computer scientist
-know about). The W3 Consortium (which standardises the Web) proposes
+should know about). The W3 Consortium (which standardises the Web)
-to use the following, already more complicated regular expressions for
+proposes to use the following, already more complicated regular
-email addresses:
+expressions for email addresses:
 {\small\begin{lstlisting}[language={},keywordstyle=\color{black},numbers=none]
 [a-zA-Z0-9.!#$%&'*+/=?^_`{|}~-]+@[a-zA-Z0-9-]+(?:\.[a-zA-Z0-9-]+)*
 \end{lstlisting}}
 \noindent which explains some of the crazier parts of email
 addresses. Still it is good to know that some tasks in text
 processing just cannot be achieved by using regular
 expressions. But for what we want to use them (lexing) they are
-pretty good.
+pretty good.\medskip
+\noindent
-\begin{figure}[p]
+Finally there is a joke about regular expressions:
-\lstinputlisting{../progs/crawler1.scala}
+\begin{quote}\it
+``Sometimes you have a programming problem and it seems like the
+best solution is to use regular expressions; now you have two
+problems.''
+\end{quote}
+\begin{figure}[p]\small
+\lstinputlisting[linebackgroundcolor={\ifodd\value{lstnumber}\color{capri!3}\fi}]
+{../progs/crawler1.scala}
 \caption{The Scala code for a simple web-crawler that checks
 for broken links in a web-page. It uses the regular expression
 \texttt{http\_pattern} in Line~\ref{httpline} for recognising
 URL-addresses. It finds all links using the library function
 \texttt{findAllIn} in Line~\ref{findallline}.\label{crawler1}}
 \end{figure}
-\begin{figure}[p]
-\lstinputlisting{../progs/crawler2.scala}
+\begin{figure}[p]\small
+\lstinputlisting[linebackgroundcolor={\ifodd\value{lstnumber}\color{capri!3}\fi}]
+{../progs/crawler2.scala}
 \caption{A version of the web-crawler that only follows links
 in ``my'' domain---since these are the ones I am interested in
 to fix. It uses the regular expression \texttt{my\_urls} in
 Line~\ref{myurlline} to check for my name in the links. The
 is a test whether URL is in ``my'' domain or
 not.\label{crawler2}}
 \end{figure}
-\begin{figure}[p]
+\begin{figure}[p]\small
-\lstinputlisting{../progs/crawler3.scala}
+\lstinputlisting[linebackgroundcolor={\ifodd\value{lstnumber}\color{capri!3}\fi}]
+{../progs/crawler3.scala}
 \caption{A small email harvester---whenever we download a
 web-page, we also check whether it contains any email
 addresses. For this we use the regular expression
 \texttt{email\_pattern} in Line~\ref{emailline}. The main

changeset 504	5dc452d7c08e
parent 503	f2d7b885b3e3
parent 496	5c9de27a5b30
child 507	fdbc7d0ec04f