\documentclass{article}

\usepackage{../style}

\usepackage{../langs}

\usepackage{../graphics}

\usepackage{../data}

\begin{document}

\fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016}

\section*{Handout 2 (Regular Expression Matching)}

This lecture is about implementing a more efficient regular expression

matcher (the plots on the right)---more efficient than the matchers

from regular expression libraries in Ruby, Python and Java (the plots

on the left). The first pair of plots show the running time for the

regular expressions $a^?{}^{\{n\}}\cdot a^{\{n\}}$ and strings composed

of $n$ \pcode{a}s. The second pair of plots show the running time

for the regular expression $(a^*)^*\cdot b$ and also strings composed

of $n$ \pcode{a}s (meaning this regular expression actually does not

match the strings).  To see the substantial differences in the left

and right plots below, note the different scales of the $x$-axes. 

\begin{center}

\begin{tabular}{@{}cc@{}}

\begin{tikzpicture}

\begin{axis}[

    ylabel={\small time in secs},

    enlargelimits=false,

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

    xmax=33,

    ymax=35,

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

    scaled ticks=false,

    axis lines=left,

    width=5cm,

    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}

&

\begin{tikzpicture}

  \begin{axis}[

    ylabel={\small time in secs},

    enlargelimits=false,

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

    xmax=12500,

    ymax=35,

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

    scaled ticks=false,

    axis lines=left,

    width=6.5cm,

    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{tabular}

\end{center}

\begin{center}

\begin{tabular}{@{}cc@{}}

\begin{tikzpicture}

\begin{axis}[

    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=5cm,

    height=5cm, 

    legend entries={Java},  

    legend pos=north west,

    legend cell align=left]

\addplot[blue,mark=*, mark options={fill=white}] table {re-java.data};

\end{axis}

\end{tikzpicture}

&

\begin{tikzpicture}

  \begin{axis}[

    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=6.5cm,

    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{tabular}

\end{center}\medskip

\noindent

We will use these regular expressions and strings

as running examples.

Having specified in the previous lecture what

problem our regular expression matcher is supposed to solve,

namely for any given regular expression $r$ and string $s$

answer \textit{true} if and only if

\[

s \in L(r)

\]

\noindent we can look at an algorithm to solve this problem. Clearly

we cannot use the function $L$ directly for this, because in general

the set of strings $L$ returns is infinite (recall what $L(a^*)$ is).

In such cases there is no way we can implement an exhaustive test for

whether a string is member of this set or not. In contrast our

matching algorithm will operate on the regular expression $r$ and

the matching algorithm, however, let us have a closer look at what it

means when two regular expressions are equivalent.

\subsection*{Regular Expression Equivalences}

We already defined in Handout 1 what it means for two regular

expressions to be equivalent, namely if their meaning is the

same language:

\[

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

\]

\noindent

It is relatively easy to verify that some concrete equivalences

hold, for example

\begin{center}

\begin{tabular}{rcl}

$(a + b)  + c$ & $\equiv$ & $a + (b + c)$\\

$a + a$        & $\equiv$ & $a$\\

$a + b$        & $\equiv$ & $b + a$\\

$(a \cdot b) \cdot c$ & $\equiv$ & $a \cdot (b \cdot c)$\\

$c \cdot (a + b)$ & $\equiv$ & $(c \cdot a) + (c \cdot b)$\\

\end{tabular}

\end{center}

\noindent

but also easy to verify that the following regular expressions

are \emph{not} equivalent

\begin{center}

\begin{tabular}{rcl}

$a \cdot a$ & $\not\equiv$ & $a$\\

$a + (b \cdot c)$ & $\not\equiv$ & $(a + b) \cdot (a + c)$\\

\end{tabular}

\end{center}

\noindent I leave it to you to verify these equivalences and

non-equivalences. It is also interesting to look at some

corner cases involving $\ONE$ and $\ZERO$:

\begin{center}

\begin{tabular}{rcl}

$a \cdot \ZERO$ & $\not\equiv$ & $a$\\

$a + \ONE$ & $\not\equiv$ & $a$\\

$\ONE$ & $\equiv$ & $\ZERO^*$\\

$\ONE^*$ & $\equiv$ & $\ONE$\\

$\ZERO^*$ & $\not\equiv$ & $\ZERO$\\

\end{tabular}

\end{center}

\noindent Again I leave it to you to make sure you agree

with these equivalences and non-equivalences. 

For our matching algorithm however the following seven

equivalences will play an important role:

\begin{center}

\begin{tabular}{rcl}

$r + \ZERO$  & $\equiv$ & $r$\\

$\ZERO + r$  & $\equiv$ & $r$\\

$r \cdot \ONE$ & $\equiv$ & $r$\\

$\ONE \cdot r$     & $\equiv$ & $r$\\

$r \cdot \ZERO$ & $\equiv$ & $\ZERO$\\

$\ZERO \cdot r$ & $\equiv$ & $\ZERO$\\

$r + r$ & $\equiv$ & $r$

\end{tabular}

\end{center}

\noindent which always hold no matter what the regular expression $r$

looks like. The first two are easy to verify since $L(\ZERO)$ is the

empty set. The next two are also easy to verify since $L(\ONE) =

\{[]\}$ and appending the empty string to every string of another set,

leaves the set unchanged. Be careful to fully comprehend the fifth and

sixth equivalence: if you concatenate two sets of strings and one is

the empty set, then the concatenation will also be the empty set. To

see this, check the definition of $\_ @ \_$ for sets. The last

equivalence is again trivial.

What will be important later on is that we can orient these

equivalences and read them from left to right. In this way we

can view them as \emph{simplification rules}. Consider for 

example the regular expression 

\begin{equation}

(r_1 + \ZERO) \cdot \ONE + ((\ONE + r_2) + r_3) \cdot (r_4 \cdot \ZERO)

\label{big}

\end{equation}

\noindent If we can find an equivalent regular expression that is

simpler (smaller for example), then this might potentially make our

matching algorithm run faster. We can look for such a simpler regular

expression $r'$ because whether a string $s$ is in $L(r)$ or in

$L(r')$ with $r\equiv r'$ will always give the same answer. In the

example above you will see that the regular expression is equivalent

to just $r_1$. You can verify this by iteratively applying the

simplification rules from above:

\begin{center}

\begin{tabular}{ll}

 & $(r_1 + \ZERO) \cdot \ONE + ((\ONE + r_2) + r_3) \cdot 

(\underline{r_4 \cdot \ZERO})$\smallskip\\

$\equiv$ & $(r_1 + \ZERO) \cdot \ONE + \underline{((\ONE + r_2) + r_3) \cdot 

\ZERO}$\smallskip\\

$\equiv$ & $\underline{(r_1 + \ZERO) \cdot \ONE} + \ZERO$\smallskip\\

$\equiv$ & $(\underline{r_1 + \ZERO}) + \ZERO$\smallskip\\

$\equiv$ & $\underline{r_1 + \ZERO}$\smallskip\\

$\equiv$ & $r_1$\

\end{tabular}

\end{center}

\noindent In each step, I underlined where a simplification

rule is applied. Our matching algorithm in the next section

will often generate such ``useless'' $\ONE$s and

$\ZERO$s, therefore simplifying them away will make the

algorithm quite a bit faster.

\subsection*{The Matching Algorithm}

The algorithm we will define below consists of two parts. One

is the function $\textit{nullable}$ which takes a regular expression as

argument and decides whether it can match the empty string

(this means it returns a boolean in Scala). This can be easily

defined recursively as follows:

\begin{center}

\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}

$\textit{nullable}(\ZERO)$      & $\dn$ & $\textit{false}$\\

$\textit{nullable}(\ONE)$         & $\dn$ & $\textit{true}$\\

$\textit{nullable}(c)$                & $\dn$ & $\textit{false}$\\

$\textit{nullable}(r_1 + r_2)$     & $\dn$ &  $\textit{nullable}(r_1) \vee \textit{nullable}(r_2)$\\ 

$\textit{nullable}(r_1 \cdot r_2)$ & $\dn$ &  $\textit{nullable}(r_1) \wedge \textit{nullable}(r_2)$\\

$\textit{nullable}(r^*)$              & $\dn$ & $\textit{true}$ \\

\end{tabular}

\end{center}

\noindent The idea behind this function is that the following

property holds:

\[

\textit{nullable}(r) \;\;\text{if and only if}\;\; []\in L(r)

\]

\noindent Note on the left-hand side of the if-and-only-if we

have a function we can implement; on the right we have its

specification (which we cannot implement in a programming

language).

The other function of our matching algorithm calculates a

\emph{derivative} of a regular expression. This is a function

which will take a regular expression, say $r$, and a

character, say $c$, as arguments and returns a new regular

expression. Be careful that the intuition behind this function

is not so easy to grasp on first reading. Essentially this

function solves the following problem: if $r$ can match a

string of the form $c\!::\!s$, what does the regular

expression look like that can match just $s$? The definition

of this function is as follows:

\begin{center}

\begin{tabular}{l@ {\hspace{2mm}}c@ {\hspace{2mm}}l}

  \end{tabular}

\end{center}

\noindent The first two clauses can be rationalised as

expression so that given the ``input'' regular expression can

match a string of the form $c\!::\!s$, we want a regular

expression for $s$. Since neither $\ZERO$ nor $\ONE$

can match a string of the form $c\!::\!s$, we return

$\ZERO$. In the third case we have to make a

case-distinction: In case the regular expression is $c$, then

clearly it can recognise a string of the form $c\!::\!s$, just

that $s$ is the empty string. Therefore we return the

$\ONE$-regular expression. In the other case we again

return $\ZERO$ since no string of the $c\!::\!s$ can be

matched. Next come the recursive cases, which are a bit more

involved. Fortunately, the $+$-case is still relatively

straightforward: all strings of the form $c\!::\!s$ are either

matched by the regular expression $r_1$ or $r_2$. So we just

expressions and compose the results again with $+$. Makes

sense? 

The $\cdot$-case is more complicated: if $r_1\cdot r_2$

matches a string of the form $c\!::\!s$, then the first part

must be matched by $r_1$. Consequently, it makes sense to

$r_1$ and ``appending'' $r_2$. There is however one exception

to this simple rule: if $r_1$ can match the empty string, then

all of $c\!::\!s$ is matched by $r_2$. So in case $r_1$ is

nullable (that is can match the empty string) we have to allow

expression that can match $s$. Therefore we have to add the

is again simple: if $r^*$ matches a string of the form

$c\!::\!s$, then the first part must be ``matched'' by a

on sets:

\begin{equation}\label{Der}

\end{equation}

\noindent This operation essentially transforms a set of

strings $A$ by filtering out all strings that do not start

with $c$ and then strips off the $c$ from all the remaining

strings. For example suppose $A = \{f\!oo, bar, f\!rak\}$ then

\]

\noindent

starts with $a$. With this operation we can state the following

\[

\]

\noindent

namely take the set of strings that $r$ can match (that is $L(r)$),

filter out all strings not starting with $c$ and strip off the $c$

from the remaining strings---this is exactly the language that

If we want to find out whether the string $abc$ is matched by

as follows

\begin{center}

\begin{tabular}{rll}

Input: $r_1$, $abc$\medskip\\

Step 4: & the string is exhausted; test & ($\textit{nullable}(r_4)$)\\

        & whether $r_4$ can recognise the\\

        & empty string\smallskip\\

Output: & result of this test $\Rightarrow \textit{true} \,\text{or}\, \textit{false}$\\        

\end{tabular}

\end{center}

this algorithm. We want to know whether $abc \in L(r_1)$. We

builds the set where all the strings not starting with $a$ are

filtered out. Of the remaining strings, the $a$ is stripped

off. So we should still have $bc$ in the set.

Then we continue with filtering out all strings not

starting with $b$ and stripping off the $b$ from the remaining

Finally we filter out all strings not starting with $c$ and

strip off $c$ from the remaining string. This is

must contain the empty string. If not, then $abc$ was not in the 

language we started with.

characters to strings. This can be done using the following

a regular expression as output.

\begin{center}

\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}}

  $\textit{ders}\, []\, r$     & $\dn$ & $r$ & \\

  \end{tabular}

\end{center}

the time from the original string until it is exhausted.

algorithm:

\[

\]

\noindent

and we can claim that

\[

\]

\noindent holds, which means our algorithm satisfies the

specification. Of course we can claim many things\ldots

whether the claim holds any water is a different question,

which for example is the point of the Strand-2 Coursework.

main attractions are simplicity and being fast, as well as

being easily extendable for other regular expressions such as

$r^{\{n\}}$, $r^?$, $\sim{}r$ and so on (this is subject of

\subsection*{The Matching Algorithm in Scala}

Another attraction of the algorithm is that it can be easily

implemented in a functional programming language, like Scala.

Given the implementation of regular expressions in Scala shown

in the first lecture and handout, the functions and subfunctions

for \pcode{matches} are shown in Figure~\ref{scala1}.

\begin{figure}[p]

\lstinputlisting{../progs/app5.scala}

\caption{Scala implementation of the \textit{nullable} and 

  derivative functions. These functions are easy to

  implement in functional languages, because their built-in pattern 

  matching and recursion allow us to mimic the mathematical

  definitions very closely.\label{scala1}}

\end{figure}