% !TEX program = xelatex

\documentclass{article}

\usepackage{../style}

\usepackage{../langs}

\usepackage{../graphics}

\usepackage{../data}

\begin{document}

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

  2014, 2015, 2016, 2017, 2018, 2019, 2020}

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

%\noindent

%{\bf Checklist}

%

%\begin{itemize}

%  \item You have understood the derivative-based matching algorithm.

%  \item You know how the derivative is related to the meaning of regular

%  expressions.

%  \item You can extend the algorithm to non-basic regular expressions.

%\end{itemize}\bigskip\bigskip\bigskip

\noindent

This lecture is about implementing a more efficient regular expression

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

matchers from regular expression libraries in Ruby, Python, JavaScript

and Java (the plots on the left). For this consider some experimental

data: The first pair of plots shows the running time for the

regular expression $(a^*)^*\cdot b$ and strings composed of $n$

\pcode{a}s, like

\[

\underbrace{\pcode{a}\ldots\pcode{a}}_{n} 

\]

\noindent

This means the regular expression actually does not match the strings.

The second pair of plots shows the running time for the regular

expressions of the form $a^?{}^{\{n\}}\cdot a^{\{n\}}$ and corresponding

strings composed of $n$ \pcode{a}s (this time the regular expressions

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}

Graphs: $(a^*)^* \cdot b$ and strings $\underbrace{a\ldots a}_{n}$

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

\begin{tikzpicture}[baseline=(current bounding box.north)]

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

    height=5cm, 

    legend entries={Java 8, Python, JavaScript},  

    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};

\end{axis}

\end{tikzpicture}

&

\begin{tikzpicture}[baseline=(current bounding box.north)]

  \begin{axis}[

    xlabel={$n$},

    x label style={at={(1.1,0.0)}},

    %%xtick={0,1000000,...,5000000}, 

    ylabel={time in secs},

    enlargelimits=false,

    ymax=35,

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

    axis lines=left,

    %scaled ticks=false,

    width=6.5cm,

    height=5cm,

    legend entries={Our matcher},  

    legend pos=north east,

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

\end{center}\bigskip

\begin{center}

Graphs: $a^{?\{n\}} \cdot a^{\{n\}}$ and strings $\underbrace{a\ldots a}_{n}$\\

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

\begin{tikzpicture}

\begin{axis}[

    xlabel={$n$},

    x label style={at={(1.05,0.0)}},

    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}[

    xlabel={$n$},

    x label style={at={(1.1,0.05)}},

    ylabel={\small time in secs},

    enlargelimits=false,

    xtick={0,2500,...,11000},

    xmax=12000,

    ymax=35,

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

    scaled ticks=false,

    axis lines=left,

    width=6.5cm,

    height=5cm,

    legend entries={Our matcher},  

    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}

\bigskip

\noindent

In what follows we will use these regular expressions and strings as

running examples. There will be several versions (V1, V2, V3,\ldots)

of our matcher.\footnote{The corresponding files are

  \texttt{re1.scala}, \texttt{re2.scala} and so on. As usual, you can

  find the code on KEATS.}

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 for 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

string $s$, only, which are both finite objects. Before we explain 

the matching algorithm, 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 whether their 

\emph{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 They 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 critical 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 (that usually means smaller), then this might potentially make

our matching algorithm run faster. We can look for such a simpler, but

equivalent, regular expression $r'$ because whether a string $s$ is in

$L(r)$ or in $L(r')$ does not matter as long as $r\equiv r'$. Yes?

In the example above you will see that the regular expression in

\eqref{big} 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.

Finally here are three equivalences between regular expressions which are

not so obvious:

\begin{center}

\begin{tabular}{rcl}

$r^*$  & $\equiv$ & $\ONE + r\cdot r^*$\\

$(r_1 + r_2)^*$  & $\equiv$ & $r_1^* \cdot (r_2\cdot r_1^*)^*$\\

$(r_1 \cdot r_2)^*$ & $\equiv$ & $\ONE + r_1\cdot (r_2 \cdot r_1)^* \cdot r_2$\\

\end{tabular}

\end{center}

\noindent

We will not use them in our algorithm, but feel free to convince

yourself that they actually hold. As an aside, there has been a lot of

research about questions like: Can one always decide when two regular

expressions are equivalent or not? What does an algorithm look like to

decide this efficiently? So in general it is not a trivial problem.

\subsection*{The Matching Algorithm}

The algorithm we will introduce below consists of two parts. One is the

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

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, ofr example in Scala; 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 mindful 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 a 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}

  $\textit{der}\, c\, (\ZERO)$      & $\dn$ & $\ZERO$\\

  $\textit{der}\, c\, (\ONE)$         & $\dn$ & $\ZERO$ \\

  $\textit{der}\, c\, (d)$                & $\dn$ & if $c = d$ then $\ONE$ else $\ZERO$\\

  $\textit{der}\, c\, (r_1 + r_2)$        & $\dn$ & $\textit{der}\, c\, r_1 + \textit{der}\, c\, r_2$\\

  $\textit{der}\, c\, (r_1 \cdot r_2)$  & $\dn$  & if $\textit{nullable} (r_1)$\\

  & & then $(\textit{der}\,c\,r_1) \cdot r_2 + \textit{der}\, c\, r_2$\\ 

  & & else $(\textit{der}\, c\, r_1) \cdot r_2$\\

  $\textit{der}\, c\, (r^*)$          & $\dn$ & $(\textit{der}\,c\,r) \cdot (r^*)$

  \end{tabular}

\end{center}

\noindent The first two clauses can be rationalised as follows: recall

that $\textit{der}$ should calculate a regular expression so that

provided  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, as it can match the empty string.

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 have to recursively

call $\textit{der}$ with these two regular 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

construct the regular expression for $s$ by calling $\textit{der}$ with

$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

the choice $\textit{der}\,c\,r_2$ for calculating the regular

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

regular expression $\textit{der}\,c\,r_2$ in the result. The $*$-case

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

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

single copy of $r$. Therefore we call recursively $\textit{der}\,c\,r$

and ``append'' $r^*$ in order to match the rest of $s$. Still

makes sense?

If all this did not make sense yet, here is another way to explain the

definition of $\textit{der}$ by considering the following operation on

sets:

\begin{equation}\label{Der}

\textit{Der}\,c\,A\;\dn\;\{s\,|\,c\!::\!s \in A\}

\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

\[ \textit{Der}\,f\,A = \{oo, rak\}\quad,\quad 

   \textit{Der}\,b\,A = \{ar\} \quad \text{and} \quad 

   \textit{Der}\,a\,A = \{\} 

\]

\noindent

Note that in the last case $\textit{Der}$ is empty, because no string in $A$

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

property about $\textit{der}$:

\[

L(\textit{der}\,c\,r) = \textit{Der}\,c\,(L(r))

\]

\noindent

This property clarifies what regular expression $\textit{der}$ calculates,

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

$\textit{der}\,c\,r$ can match.

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

the regular expression $r_1$ then we can iteratively apply $\textit{der}$

as follows

\begin{center}

\begin{tabular}{rll}

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

Step 1: & build derivative of $a$ and $r_1$ & $(r_2 = \textit{der}\,a\,r_1)$\smallskip\\

Step 2: & build derivative of $b$ and $r_2$ & $(r_3 = \textit{der}\,b\,r_2)$\smallskip\\

Step 3: & build derivative of $c$ and $r_3$ & $(r_4 = \textit{der}\,c\,r_3)$\smallskip\\

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

        & test 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}

\noindent Again the operation $\textit{Der}$ might help to rationalise

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

do not know yet---but let us assume it is. Then $\textit{Der}\,a\,L(r_1)$

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

strings, that means we build $\textit{Der}\,b\,(\textit{Der}\,a\,(L(r_1)))$.

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

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

$\textit{Der}\,c\,(\textit{Der}\,b\,(\textit{Der}\,a\,(L(r_1))))$. Now if $abc$ was in the 

original set ($L(r_1)$), then $\textit{Der}\,c\,(\textit{Der}\,b\,(\textit{Der}\,a\,(L(r_1))))$ 

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

language we started with.

Our matching algorithm using $\textit{der}$ and $\textit{nullable}$ works

similarly, just using regular expressions instead of sets. In order to

define our algorithm we need to extend the notion of derivatives from single

characters to strings. This can be done using the following

function, taking a string and a regular expression as input and

a regular expression as output.

\begin{center}

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

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

  $\textit{ders}\, (c\!::\!s)\, r$ & $\dn$ & $\textit{ders}\,s\,(\textit{der}\,c\,r)$ & \\

  \end{tabular}

\end{center}

\noindent This function iterates $\textit{der}$ taking one character at

the time from the original string until the string is exhausted.

Having $\textit{der}s$ in place, we can finally define our matching

algorithm:

\[