\documentclass{article}

\usepackage{../style}

\usepackage{../langs}

\usepackage{../graphics}

\usepackage{../data}

\pgfplotsset{compat=1.11}

\begin{document}

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

This lecture is about implementing a more efficient regular

expression matcher (the plots on the right)---more efficient

\begin{center}

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

\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=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={\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=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 Having specified in the previous lecture what

\[

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

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 $\epsilon$ and $\varnothing$:

\begin{center}

\begin{tabular}{rcl}

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

$a + \epsilon$ & $\not\equiv$ & $a$\\

$\epsilon$ & $\equiv$ & $\varnothing^*$\\

$\epsilon^*$ & $\equiv$ & $\epsilon$\\

$\varnothing^*$ & $\not\equiv$ & $\varnothing$\\

\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 + \varnothing$  & $\equiv$ & $r$\\

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

$r \cdot \epsilon$ & $\equiv$ & $r$\\

$\epsilon \cdot r$     & $\equiv$ & $r$\\

$r \cdot \varnothing$ & $\equiv$ & $\varnothing$\\

$\varnothing \cdot r$ & $\equiv$ & $\varnothing$\\

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

\end{tabular}

\end{center}

\noindent which always hold no matter what the regular

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

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

example the regular expression 

\begin{equation}

(r_1 + \varnothing) \cdot \epsilon + ((\epsilon + r_2) + r_3) \cdot (r_4 \cdot \varnothing)

\label{big}

\end{equation}

\noindent If we can find an equivalent regular expression that

\begin{center}

\begin{tabular}{ll}

 & $(r_1 + \varnothing) \cdot \epsilon + ((\epsilon + r_2) + r_3) \cdot 

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

$\equiv$ & $(r_1 + \varnothing) \cdot \epsilon + \underline{((\epsilon + r_2) + r_3) \cdot 

\varnothing}$\smallskip\\

$\equiv$ & $\underline{(r_1 + \varnothing) \cdot \epsilon} + \varnothing$\smallskip\\

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

$\equiv$ & $\underline{r_1 + \varnothing}$\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'' $\epsilon$s and

$\varnothing$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 $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@ {}}

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

$nullable(\epsilon)$         & $\dn$ & $true$\\

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

$nullable(r_1 + r_2)$     & $\dn$ &  $nullable(r_1) \vee nullable(r_2)$\\ 

$nullable(r_1 \cdot r_2)$ & $\dn$ &  $nullable(r_1) \wedge nullable(r_2)$\\

$nullable(r^*)$              & $\dn$ & $true$ \\

\end{tabular}

\end{center}

\noindent The idea behind this function is that the following

property holds:

\[

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

\]

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 argument and return 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

of this function is as follows:

\begin{center}

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

  $der\, c\, (\varnothing)$      & $\dn$ & $\varnothing$\\

  $der\, c\, (\epsilon)$         & $\dn$ & $\varnothing$ \\

  $der\, c\, (d)$                & $\dn$ & if $c = d$ then $\epsilon$ else $\varnothing$\\

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

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

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

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

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

  \end{tabular}

\end{center}

\noindent The first two clauses can be rationalised as

follows: recall that $der$ should calculate a regular

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 $der$ with these two regular

expressions and compose the results again with $+$. Yes, 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 $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 $der\,c\,r_2$ for calculating the regular

If this did not make sense, here is another way to rationalise

the definition of $der$ by considering the following operation

on sets:

\[

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

\]

\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

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

\text{and} \quad Der\,a\,A = \varnothing \]

\noindent

Note that in the last case $Der$ is empty, because no string in $A$

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

property about $der$:

\[

L(der\,c\,r) = Der\,c\,(L(r))

\]

\noindent

This property clarifies what regular expression $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

$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 $der$

as follows

\begin{center}

\begin{tabular}{rll}

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

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

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

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

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

        & whether $r_4$ can recognise the\\

        & empty string\smallskip\\

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

\end{tabular}

\end{center}

\noindent Again the operation $Der$ might help to rationalise

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. 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 $Der\,b\,(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

$Der\,c\,(Der\,b\,(Der\,a\,(L(r))))$. Now if $abc$ was in the 

original set ($L(r_1)$), then in $Der\,c\,(Der\,b\,(Der\,a\,(L(r))))$ 

language we started with.

Our matching algorithm using $der$ and $nullable$ works

similarly, just using regular expression instead of sets. For

characters to strings. This can be done using the following

function, taking a string and 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\,(der\,c\,r)$ & \\

  \end{tabular}

\end{center}

\[

\]

\noindent

\[

matches\,s\,r\quad\text{if and only if}\quad s\in L(r)

\]

\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.

This algorithm was introduced by Janus Brzozowski in 1964. Its

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

Strand-1 Coursework 1).

\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 nullable and 

\end{figure}

For running the algorithm with our favourite example, the evil

regular expression $a?^{\{n\}}a^{\{n\}}$, we need to implement

the optional regular expression and the exactly $n$-times

regular expression. This can be done with the translations

\lstinputlisting[numbers=none]{../progs/app51.scala}

\noindent Running the matcher with the example, we find it is

slightly worse then the matcher in Ruby and Python.

Ooops\ldots

\begin{center}

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

    enlargelimits=false,

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

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

    scaled ticks=false,

    axis lines=left,

    width=6cm,

    height=5cm, 

    legend entries={Python,Ruby,Scala V1},  

    legend pos=outer north east,

    legend cell align=left  
]

\addplot[blue,mark=*, mark options={fill=white}] 

  table {re-python.data};

\addplot[brown,mark=pentagon*, mark options={fill=white}] 

  table {re-ruby.data};  

\addplot[red,mark=triangle*,mark options={fill=white}] 

  table {re1.data};  
\end{axis}
\end{tikzpicture}

\end{center}

\begin{center}

\begin{tabular}{rl}

1: & $a$\\

2: & $a\cdot a$\\

3: & $a\cdot a\cdot a$\\

& \ldots\\

13: & $a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a$\\

& \ldots

\end{tabular}

\end{center}

\noindent Our algorithm traverses such regular expressions at

least once every time a derivative is calculated. So having

large regular expressions will cause problems. This problem

is aggravated by $a?$ being represented as $a + \epsilon$.

$r^{\{n\}}$. In Scala we would introduce a constructor like

\begin{center}

\code{case class NTIMES(r: Rexp, n: Int) extends Rexp}

\end{center}

\begin{center}

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

    enlargelimits=false,

    xtick={0,100,...,1000},

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

    scaled ticks=false,

    axis lines=left,

    width=9.5cm,

    height=5cm, 

    legend entries={Python,Ruby,Scala V1,Scala V2},  

    legend pos=outer north east,

    legend cell align=left  
]

\addplot[blue,mark=*, mark options={fill=white}] 

  table {re-python.data};