\documentclass{article}

\usepackage{../style}

\usepackage{../langs}

\usepackage{../graphics}

\usepackage{../data}

\begin{document}

\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 particular string 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 programming code we need to identify

what are the keywords, what are the identifiers etc. 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 problem that we are given a string (for

example some user input) and want to know whether it matches a

particular pattern. 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).

\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

computer science. For example there is no convenient regular

expression for describing the English language short of

enumerating all English words. But they seem useful for

describing for example email addresses.\footnote{See ``8

Regular Expressions You Should Know''

\url{http://goo.gl/5LoVX7}} Consider the following regular

expression

\begin{equation}\label{email}

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

\end{equation}

\noindent where the first part matches one or more lowercase

letters (\pcode{a-z}), digits (\pcode{0-9}), underscores, dots

or hyphens. The \pcode{+} ensures the ``one or more''. Then

comes the \pcode{@}-sign, followed by the domain name which

must be one or more lowercase letters, digits, underscores,

dots or hyphens. Note there cannot be an underscore in the

domain name. Finally there must be a dot followed by the

toplevel domain. This toplevel domain must be 2 to 6 lowercase

letters including the dot. Example strings which follow this

pattern are:

\begin{lstlisting}[language={},numbers=none,keywordstyle=\color{black}]

niceandsimple@example.org

very.common@example.co.uk

a.little.lengthy.but.fine@dept.example.ac.uk

other.email-with-dash@example.edu

\end{lstlisting}

\noindent

But for example the following two do not:

\begin{lstlisting}[language={},numbers=none,keywordstyle=\color{black}]

user@localserver

disposable.style.email.with+symbol@example.com

\end{lstlisting}

Identifiers, or variables, in program text are often required

to satisfy the constraints that they start with a letter and

then can be followed by zero or more letters or numbers and

also can include underscores, but not as the first character.

Such identifiers can be recognised with the regular expression

\begin{center}

\pcode{[a-zA-Z] [a-zA-Z0-9_]*}

\end{center}

\noindent Possible identifiers that match this regular expression 

are \pcode{x}, \pcode{foo}, \pcode{foo_bar_1}, \pcode{A_very_42_long_object_name},

but not \pcode{_i} and also not \pcode{4you}.

Many programming language offer libraries that can be used to

validate such strings against regular expressions. Also there

are some common, and I am sure very familiar, ways of how to

construct regular expressions. For example in Scala we have: 

\begin{center}

\begin{tabular}{lp{9cm}}

\pcode{re*} & matches 0 or more occurrences of preceding 

expression\\

\pcode{re+} & matches 1 or more occurrences of preceding

expression\\

\pcode{re?} &	 matches 0 or 1 occurrence of preceding 

expression\\

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

occurrences of preceding  expression\\

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

occurences of the preceding expression\\

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

brackets\\

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

brackets\\

\pcode{...-...} & character ranges\\

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

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

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

matched text

\end{tabular}

\end{center}

\noindent With this table you can figure out the purpose of

the regular expressions in the web-crawlers shown Figures

\ref{crawler1}, \ref{crawler2} and

\ref{crawler3}.\footnote{There is an interesting twist in the

web-scraper where \pcode{re*?} is used instead of

\pcode{re*}.} Note, however, the regular expression for

http-addresses in web-pages is meant to be

\[

\pcode{"https?://[^"]*"}

\]

\noindent It specifies that web-addresses need to start with a

double quote, then comes \texttt{http} followed by an optional

\texttt{s} and so on. Usually we would have to escape the

double quotes in order to make sure we interpret the double

quote as character, not as double quote for a string. But

Scala's trick with triple quotes allows us to omit this kind

of escaping. As a result we can just write:

\[

\pcode{""""https?://[^"]*"""".r}

\]

\noindent Note also that the convention in Scala is that

\texttt{.r} converts a string into a regular expression. I

leave it to you to ponder whether this regular expression

really captures all possible web-addresses.

\subsection*{Why Study Regular Expressions?}

Regular expressions were introduced by Kleene in the 1950ies

and they have been object of intense study since then. They

are nowadays pretty much ubiquitous in computer science. I am

sure you have come across them before. Why on earth then is

there any interest in studying them again in depth in this

module? Well, one answer is in the following graph about

regular expression matching in Python and in Ruby.

\begin{center}

\begin{tikzpicture}

\begin{axis}[xlabel={\pcode{a}s},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=7cm,

    height=5cm, 

    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}

\end{center}

\noindent This graph 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 test results can be

found at \url{http://www.computerbytesman.com/redos/}.}

Admittedly, this regular expression is carefully chosen to

exhibit this exponential behaviour, but similar ones occur

more often than one wants in ``real life''. They are sometimes

called \emph{evil regular expressions} because they have the

potential to make regular expression matching engines to

topple over, like in Python and Ruby. The problem with evil

regular expressions is that they can have some serious

consequences, for example, if you use them in your

web-application. The reason is that hackers can look for these

instances where the matching engine behaves badly and then

mount a nice DoS-attack against your application. These

attacks are already have their own name: 

\emph{Regular Expression Denial of Service Attacks (ReDoS)}.

It will be instructive to look behind the ``scenes'' to find

out why Python and Ruby (and others) behave so badly when

matching 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

seconds, while the second version will even be able to process

up to 12,000 in less than 10(!) seconds, see the graph below:

\begin{center}

\begin{tikzpicture}

  \begin{axis}[xlabel={\pcode{a}s},ylabel={time in secs},

    enlargelimits=false,

    xtick={0,3000,...,12000},

    xmax=12500,

    ymax=35,

    ytick={0,5,...,30},

    scaled ticks=false,

    axis lines=left,

    width=9cm,

    height=5cm]

\addplot[green,mark=square*,mark options={fill=white}] table {re2b.data};

\addplot[black,mark=square*,mark options={fill=white}] table {re3.data};

\end{axis}

\end{tikzpicture}

\end{center}

\subsection*{Basic Regular Expressions}

The regular expressions shown above, for example for Scala, we

will call \emph{extended regular expressions}. The ones we

will mainly study in this module are \emph{basic regular

expressions}, which by convention we will just call

\emph{regular expressions}, if it is clear what we mean. The

attraction of (basic) regular expressions is that many

features of the extended ones are just syntactic sugar.

(Basic) regular expressions are defined by the following

grammar:

\begin{center}

\begin{tabular}{r@{\hspace{1mm}}r@{\hspace{1mm}}l@{\hspace{13mm}}l}

  $r$ & $::=$ &   $\varnothing$         & null\\

        & $\mid$ & $\epsilon$           & empty string / \texttt{""} / []\\

        & $\mid$ & $c$                  & single character\\

        & $\mid$ & $r_1 + r_2$          & alternative / choice\\

        & $\mid$ & $r_1 \cdot r_2$      & sequence\\

        & $\mid$ & $r^*$                & star (zero or more)\\

  \end{tabular}

\end{center}

\noindent Because we overload our notation, there are some

subtleties you should be aware of. When regular expressions

are referred to then $\varnothing$ does not stand for the

empty set: rather it is a particular pattern that does not

match any string. Similarly, in the context of regular

expressions, $\epsilon$ does not stand for the empty string

(as in many places in the literature) but for a regular

expression that matches the empty string. The letter $c$

stands for any character from the alphabet at hand. Again in

the context of regular expressions, it is a particular pattern

that can match the specified character. You should also be

careful with our overloading of the star: assuming you have

read the handout about our basic mathematical notation, you

will see that in the context of languages (sets of strings)

the star stands for an operation on languages. Here $r^*$

stands for a regular expression, which is different from the

operation on sets is defined as

\[

A^* \dn \bigcup_{0\le n} A^n

\]

We will use parentheses to disambiguate regular expressions.

Parentheses are not really part of a regular expression, and

indeed we do not need them in our code because there the tree

structure of regular expressions is always clear. But for

writing them down in a more mathematical fashion, parentheses

will be helpful. For example we will write $(r_1 + r_2)^*$,

which is different from, say $r_1 + (r_2)^*$. The former means

roughly zero or more times $r_1$ or $r_2$, while the latter

means $r_1$ or zero or more times $r_2$. This will turn out to

be two different patterns, which match in general different

strings. We should also write $(r_1 + r_2) + r_3$, which is

different from the regular expression $r_1 + (r_2 + r_3)$, but

in case of $+$ and $\cdot$ we actually do not care about the

order and just write $r_1 + r_2 + r_3$, or $r_1 \cdot r_2

\cdot r_3$, respectively. The reasons for this will become

clear shortly. In the literature you will often find that the

choice $r_1 + r_2$ is written as $r_1\mid{}r_2$ or

$r_1\mid\mid{}r_2$. Also following the convention in the

literature, we will often omit the $\cdot$ all together. This

is to make some concrete regular expressions more readable.

For example the regular expression for email addresses shown

in \eqref{email} would look like

\[

\texttt{[...]+} \;\cdot\;  \texttt{@} \;\cdot\; 

\texttt{[...]+} \;\cdot\; \texttt{.} \;\cdot\; 

\texttt{[...]\{2,6\}}

\]

\noindent

which is much less readable than \eqref{email}. Similarly for

the regular expression that matches the string $hello$ we 

should write

\[

h \cdot e \cdot l \cdot l \cdot o

\]

\noindent

but often just write {\it hello}.

If you prefer to think in terms of the implementation

of regular expressions in Scala, the constructors and

classes relate as follows\footnote{More about Scala is 

in the handout about A Crash-Course on Scala.}

\begin{center}

\begin{tabular}{rcl}

$\varnothing$ & $\mapsto$ & \texttt{NULL}\\

$\epsilon$    & $\mapsto$ & \texttt{EMPTY}\\

$c$           & $\mapsto$ & \texttt{CHAR(c)}\\

$r_1 + r_2$   & $\mapsto$ & \texttt{ALT(r1, r2)}\\

$r_1 \cdot r_2$ & $\mapsto$ & \texttt{SEQ(r1, r2)}\\

$r^*$         & $\mapsto$ & \texttt{STAR(r)}

\end{tabular}

\end{center}

A source of confusion might arise from the fact that we

use the term \emph{basic regular expression} for the regular

expressions used in ``theory'' and defined above, and

\emph{extended regular expression} for the ones used in

``practice'', for example in Scala. If runtime is not an

issue, then the latter can be seen as syntactic sugar of

the former. For example we could replace

\begin{center}

\begin{tabular}{rcl}

$r+$ & $\mapsto$ & $r\cdot r^*$\\

$r?$ & $\mapsto$ & $\epsilon + r$\\

$\backslash d$ & $\mapsto$ & $0 + 1 + 2 + \ldots + 9$\\

$[\text{\it a - z}]$ & $\mapsto$ & $a + b + \ldots + z$\\

\end{tabular}

\end{center}

\subsection*{The Meaning of Regular Expressions}

So far we have only considered informally what the

\emph{meaning} of a regular expression is. This is not good

enough for specifications of what algorithms are supposed to

do or which problems they are supposed to solve.

To define the meaning of a regular expression we will

associate with every regular expression a language, or set of

strings. This language contains all the strings the regular

expression is supposed to match. To understand what is going

on here it is crucial that you have read the handout

about basic mathematical notations.

The \defn{meaning of a regular expression} can be defined

by a recursive function called $L$ (for language), which

is defined as follows

\begin{center}

\begin{tabular}{rcl}

$L(\varnothing)$  & $\dn$ & $\varnothing$\\

$L(\epsilon)$     & $\dn$ & $\{[]\}$\\

$L(c)$            & $\dn$ & $\{"c"\}$\\

$L(r_1+ r_2)$     & $\dn$ & $L(r_1) \cup L(r_2)$\\

$L(r_1 \cdot r_2)$ & $\dn$ & $L(r_1) \,@\, L(r_2)$\\

$L(r^*)$           & $\dn$ & $(L(r))^*$\\

\end{tabular}

\end{center}

\noindent As a result we can now precisely state what the

meaning, for example, of the regular expression $h \cdot

e \cdot l \cdot l \cdot o$ is, namely

\[

L(h \cdot e \cdot  l \cdot l \cdot o) = \{"hello"\}

\]

\noindent This is expected because this regular expression 

is only supposed to match the ``$hello$''-string. Similarly if

we have the choice-regular-expression $a + b$, its meaning is

\[

L(a + b) = \{"a", "b"\}

\]

\noindent You can now also see why we do not make a difference

between the different regular expressions $(r_1 + r_2) + r_3$

and $r_1 + (r_2 + r_3)$\ldots they are not the same regular

expression, but they have the same meaning. For example

\begin{eqnarray*}

L((r_1 + r_2) + r_3) & = & L(r_1 + r_2) \cup L(r_3)\\

                     & = & L(r_1) \cup L(r_2) \cup L(r_3)\\

                     & = & L(r_1) \cup L(r_2 + r_3)\\

                     & = & L(r_1 + (r_2 + r_3))

\end{eqnarray*}

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

\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

different regular expressions that can recognise these

strings. This is obvious with the regular expression $a + b$

which can match the strings $a$ and $b$. But also the regular

expression $b + a$ would match the same strings. However,

sometimes it is not so obvious whether two regular expressions

match the same strings: for example do $r^*$ and $\epsilon + r

\cdot r^*$ match the same strings? What about $\varnothing^*$

and $\epsilon^*$? This suggests the following relation between

\defn{equivalent regular expressions}: 

\[

r_1 \equiv r_2 \;\dn\; L(r_1) = L(r_2)

\]

\noindent That means two regular expressions are said to be

equivalent if they match the same set of strings. Therefore we

do not really distinguish between the different regular

expression $(r_1 + r_2) + r_3$ and $r_1 + (r_2 + r_3)$,

because they are equivalent. I leave you to the question

whether

\[

\varnothing^* \equiv \epsilon^*

\]

\noindent holds? Such equivalences will be important for our

matching algorithm, because we can use them to simplify 

regular expressions. 

\subsection*{My Fascination for Regular Expressions}

Up until a few years ago I was not really interested in

regular expressions. They have been studied for the last 60

years (by smarter people than me)---surely nothing new can be

found out about them. I even have the vague recollection that

I did not quite understand them during my study. If I remember

correctly,\footnote{That was really a long time ago.} I got

utterly confused about $\epsilon$ and the empty

string.\footnote{Obviously the lecturer must have been bad.}

Since my study, I have used regular expressions for

implementing lexers and parsers as I have always been

interested in all kinds of programming languages and

compilers, which invariably need regular expression in some

form or shape. 

To understand my fascination nowadays with regular

expressions, you need to know that my main scientific interest

for the last 14 years has been with theorem provers. I am a

core developer of one of

them.\footnote{\url{http://isabelle.in.tum.de}} Theorem

provers are systems in which you can formally reason about

mathematical concepts, but also about programs. In this way

they can help with writing bug-free code. Theorem provers have

proved already their value in a number of systems (even in

terms of hard cash), but they are still clunky and difficult

to use by average programmers.

Anyway, in about 2011 I came across the notion of

\defn{derivatives of regular expressions}. This notion allows

one to do almost all calculations in regular language theory

on the level of regular expressions, not needing any automata.

This is important because automata are graphs and it is rather

difficult to reason about graphs in theorem provers. In

contrast, to reason about regular expressions is easy-peasy in

theorem provers. Is this important? I think yes, because

according to Kuklewicz nearly all POSIX-based regular

expression matchers are

buggy.\footnote{\url{http://www.haskell.org/haskellwiki/Regex_Posix}}

With my PhD student Fahad Ausaf I am currently working on

proving the correctness for one such matcher that was

proposed by Sulzmann and Lu in

2014.\footnote{\url{http://goo.gl/bz0eHp}} This would be an

attractive results since we will be able to prove that the

algorithm is really correct, but also that the machine code(!)

that implements this code efficiently is correct. Writing

programs in this way does not leave any room for potential