94   Brzozowski introduced in 1964 a beautifully simple algorithm for

    94 Regular expressions, a useful concept in computer science

    95   regular expression matching based on the notion of derivatives of

    95 that was initially designed to match string patterns,

    96   regular expressions. In 2014, Sulzmann and Lu extended this

    96 need fast matching algorithms.

    97   algorithm to not just give a YES/NO answer for whether or not a

    97 If we do matching by naively converting

    98   regular expression matches a string, but in case it does also

    98 the regular expression to a

    99   answers with \emph{how} it matches the string.  This is important for

    99 Nondeterministic-Finite-Automaton(NFA) and simulating it,

   100   applications such as lexing (tokenising a string). The problem is to

   100 they can run into trouble on certain evil regular expression and string 

   101   make the algorithm by Sulzmann and Lu fast on all inputs without

   101 pairs.

   102   breaking its correctness. Being fast depends on a complete set of 

   102 This necessitates the introudction of a 

   103   simplification rules, some of which 

   103 method called derivatives of regular expressions\cite{Brzozowski1964}.

   104   have been put forward by Sulzmann and Lu. We have extended their

   104 With some variation introduced by Sulzmann and Lu\cite{Sulzmann2014},

   105   rules in order to obtain a tight bound on the size of regular expressions.

   105 it circumvents the problem of 

   106   We have tested these extended rules, but have not 

   106 catastrphoic backtracking elegantly when

   107   formally established their correctness. We have also not yet looked 

   107 compared to backtracking NFA regex engines.

   108   at extended regular expressions, such as bounded repetitions,

   108 We believe that such a method can help to address 

   109   negation and back-references.

   109 the status-quo where badly written code for 

   110 regular expression matching can cause a software grief.

   111 We have come up with a set of simplification rules

   112 that makes the space and time requirements below a tight bound.

   113 We have proved certain properties of the algorithm 

   114 and simplification.

   115 We have not yet worked out a proof for the correctness

   116 although test data suggested this.

   114 %Regular expressions' derivatives, which have received 

   122 The following brief introduction gives the background for 

   115 %renewed interest in the new millenium, is a beautiful....

   123 derivatives--how they are originally defined and the 

   116 While we believe derivatives of regular expressions, written

   124 variety\cite{Sulzmann2014} that is more suitable for lexing.

   117 $r\backslash s$, are a beautiful concept (in terms of ease of

   125 Regular expressions can be formalized as follows:\\

   118 implementing them in functional programming languages and in terms of

   126 \begin{center}

   119 reasoning about them formally), they have one major drawback: every

   127 	$r ::= \ZERO | \ONE | c | r_1 +r_2 | r_1 \cdot r_2 | r^*$

   120 derivative step can make regular expressions grow drastically in

   128 \end{center}

   121 size. This in turn has negative effect on the runtime of the

   129 Derivatives of regular expression can be 

   122 corresponding lexing algorithms. Consider for example the regular

   130 seen as the regular expression that corresponds to

   123 expression $(a+aa)^*$ and the short string $aaaaaaaaaaaa$. The

   131 the language derived by computing

   124 corresponding derivative contains already 8668 nodes where we assume

   132 the left quotient of the original regular language

   125 the derivative is given as a tree. The reason for the poor runtime of

   133 w.r.t a character.

   126 the derivative-based lexing algorithms is that they need to traverse

   134 Derivative of regular expression is also a 

   127 such trees over and over again. The solution is to find a complete set

   135 regular expression because 

   128 of simplification rules that keep the sizes of derivatives uniformly

   136 the left quotient of a regular language is also regular.

   129 small.

   137 With this we know such a function exist without having

   130 

   138 to worry that it might not be defined.

   131 This has been partially addressed by the function $\blexer_{simp}$,

   139 In fact, regular expressions derivatives

   132 which after  the simplification the $(a+aa)^*$ example's 8000 nodes will be

   140 are not just defined but also simple and elegant.

   133 reduced to just 6 and stays constant in each derivative step.

   141 They are composed of two recursive functions,

   134 The part that still needs more work is the correctness proof of this 

   142 and can be easily explained by intuition.

   135 function, namely,

   143 The function

   136 \begin{equation}\label{mainthm}

   144 $\nullable$ defined below,

   137 \blexers \; r \; s = \blexer \;r\;s

   145 tests whether the empty string belongs

   138 \end{equation}

   146 to the regular expression being checked.

   139 

   140 \noindent

   141 and this is what this report is mainly about. A condensed 

   142 version of the last report will be provided in the next section

   143 to help the reader understand the report, and the attempts 

   144 on the problem will follow.

   145 

   146 

   147 \section{Recapitulation of Concepts From the Last Report}

   148 

   149 \subsection*{Regular Expressions and Derivatives}

   150 Suppose (basic) regular expressions are given by the following grammar:

   151 

   152 \[			r ::=   \ZERO \mid  \ONE

   153 			 \mid  c  

   154 			 \mid  r_1 \cdot r_2

   155 			 \mid  r_1 + r_2   

   156 			 \mid r^*         

   157 \]

   158 

   159 \noindent

   160 The ingenious contribution of Brzozowski is the notion of \emph{derivatives} of

   161 regular expressions, written~$\_ \backslash \_$. It uses the auxiliary notion of

   162 $\nullable$ defined below.

   173 	\end{center}

   157 \end{center}

   158 \noindent

   159 The empty set does not contain any string and

   160 therefore not the empty string, the empty string 

   161 regular expression contains the empty string

   162 by definition, the character regular expression

   163 is the singleton that contains character only,

   164 and therefore does not contain the empty string,

   165 the alternative regular expression(or "or" expression)

   166 might have one of its children regular expressions

   167 being nullable and any one of its children being nullable

   168 would suffice. The sequence regular expression

   169 would require both children to have the empty string

   170 to compose an empty string and the Kleene star

   171 operation naturally introduced the empty string.

   172 All nice and easy.

   173 This definition is used in the derivative operation

   174 as a condition:

   189 And defines how a regular expression evolves into

   190 \noindent

   191 The function derivative, written $\backslash c$, 

   192 defines how a regular expression evolves into

   192 

   195 The most involved cases are the sequence 

   193 The main property of the derivative operation is that

   196 and star case.

   197 The sequence case says that if the first regular expression

   198 contains an empty string then second component of the sequence

   199 might be chosen as the target regular expression to be chopped

   200 off its head character.

   201 The star regular expression unwraps the iteration of

   202 regular expression and attack the star regular expression

   203 to its back again to make sure there are 0 or more iterations

   204 following this unfolded iteration.

   205 

   206 

   207 The main property of the derivative operation

   208 that enables us to reason about the correctness of

   209 an algorithm using derivatives is 

   235  

   251 Beautiful and simple definition.

   252 

   253 If we implement the above algorithm naively, however,

   254 the algorithm can be excruciatingly slow. For example, when starting with the regular

   255 expression $(a + aa)^*$ and building 12 successive derivatives

   256 w.r.t.~the character $a$, one obtains a derivative regular expression

   257 with more than 8000 nodes (when viewed as a tree). Operations like

   258 $\backslash$ and $\nullable$ need to traverse such trees and

   259 consequently the bigger the size of the derivative the slower the

   260 algorithm. 

   261 

   262 Brzozowski was quick in finding that during this process a lot useless

   263 $\ONE$s and $\ZERO$s are generated and therefore not optimal.

   264 He also introduced some "similarity rules" such

   265 as $P+(Q+R) = (P+Q)+R$ to merge syntactically 

   266 different but language-equivalent sub-regexes to further decrease the size

   267 of the intermediate regexes. 

   268 

   269 More simplifications are possible, such as deleting duplicates

   270 and opening up nested alternatives to trigger even more simplifications.

   271 And suppose we apply simplification after each derivative step, and compose

   272 these two operations together as an atomic one: $a \backslash_{simp}\,c \dn

   273 \textit{simp}(a \backslash c)$. Then we can build

   274 a matcher without having  cumbersome regular expressions.

   275 

   276 

   277 If we want the size of derivatives in the algorithm to

   278 stay even lower, we would need more aggressive simplifications.

   279 Essentially we need to delete useless $\ZERO$s and $\ONE$s, as well as

   280 deleting duplicates whenever possible. For example, the parentheses in

   281 $(a+b) \cdot c + b\cdot c$ can be opened up to get $a\cdot c + b \cdot c + b

   282 \cdot c$, and then simplified to just $a \cdot c + b \cdot c$. Another

   283 example is simplifying $(a^*+a) + (a^*+ \ONE) + (a +\ONE)$ to just

   284 $a^*+a+\ONE$. Adding these more aggressive simplification rules help us

   285 to achieve a very tight size bound, namely,

   286  the same size bound as that of the \emph{partial derivatives}. 

   287 

   288 Building derivatives and then simplify them.

   289 So far so good. But what if we want to 

   290 do lexing instead of just a YES/NO answer?

   291 This requires us to go back again to the world 

   292 without simplification first for a moment.

   293 Sulzmann and Lu~\cite{Sulzmann2014} first came up with a nice and 

   294 elegant(arguably as beautiful as the original

   295 derivatives definition) solution for this.

   296 

   238 One limitation of Brzozowski's algorithm is that it only produces a

   299 

   239 YES/NO answer for whether a string is being matched by a regular

   300 They first defined the datatypes for storing the 

   240 expression.  Sulzmann and Lu~\cite{Sulzmann2014} extended this algorithm

   301 lexing information called a \emph{value} or

   241 to allow generation of an actual matching, called a \emph{value} or

   301 function $\textit{mkeps}$, which builds the lexical value

   390 function $\textit{mkeps}$, which builds a POSIX lexical value

   323 matches $s$. For this Sulzmann and Lu defined a function that reverses

   412 matches $s$. The POSIX value is maintained throught out the process.

   413 For this Sulzmann and Lu defined a function that reverses

   348 

   438 The clauses basically do one thing--identifying the ``holes'' on 

   349 

   439 value to inject the character back into.

   350 \subsection*{Simplification of Regular Expressions}

   440 For instance, in the last clause for injecting back to a value

   351 

   441 that would turn into a new star value that corresponds to a star,

   352 The main drawback of building successive derivatives according

   442 we know it must be a sequence value. And we know that the first 

   353 to Brzozowski's definition is that they can grow very quickly in size.

   443 value of that sequence corresponds to the child regex of the star

   354 This is mainly due to the fact that the derivative operation generates

   444 with the first character being chopped off--an iteration of the star

   355 often ``useless'' $\ZERO$s and $\ONE$s in derivatives.  As a result, if

   445 that had just been unfolded. This value is followed by the already

   356 implemented naively both algorithms by Brzozowski and by Sulzmann and Lu

   446 matched star iterations we collected before. So we inject the character 

   357 are excruciatingly slow. For example when starting with the regular

   447 back to the first value and form a new value with this new iteration

   358 expression $(a + aa)^*$ and building 12 successive derivatives

   448 being added to the previous list of iterations, all under the $Stars$

   359 w.r.t.~the character $a$, one obtains a derivative regular expression

   449 top level.

   360 with more than 8000 nodes (when viewed as a tree). Operations like

   450 

   361 $\textit{der}$ and $\nullable$ need to traverse such trees and

   451 We have mentioned before that derivatives without simplification 

   362 consequently the bigger the size of the derivative the slower the

   452 can get clumsy, and this is true for values as well--they reflect

   363 algorithm. 

   453 the regular expressions size by definition.

   364 

   454 

   365 Fortunately, one can simplify regular expressions after each derivative

   455 One can introduce simplification on the regex and values, but have to

   366 step. 

   456 be careful in not breaking the correctness as the injection 

   367 Various simplifications of regular expressions are possible, such

   457 function heavily relies on the structure of the regexes and values

   368 as the simplification of $\ZERO + r$, $r + \ZERO$, $\ONE\cdot r$, $r

   458 being correct and match each other.

   369 \cdot \ONE$, and $r + r$ to just $r$.

   459 It can be achieved by recording some extra rectification functions

   370 Suppose we apply simplification after each derivative step, and compose

   460 during the derivatives step, and applying these rectifications in 

   371 these two operations together as an atomic one: $a \backslash_{simp}\,c \dn

   461 each run during the injection phase.

   372 \textit{simp}(a \backslash c)$. Then we can build values without having

   462 And we can prove that the POSIX value of how

   373 a cumbersome regular expression, and  fortunately if we are careful

   374 enough in making some extra rectifications, the POSIX value of how

   379 

   467 %Brzozowski, after giving the derivatives and simplification,

   380 If we want the size of derivatives in Sulzmann and Lu's algorithm to

   468 %did not explore lexing with simplification or he may well be 

   381 stay even lower, we would need more aggressive simplifications.

   469 %stuck on an efficient simplificaiton with a proof.

   382 Essentially we need to delete useless $\ZERO$s and $\ONE$s, as well as

   470 %He went on to explore the use of derivatives together with 

   383 deleting duplicates whenever possible. For example, the parentheses in

   471 %automaton, and did not try lexing using derivatives.

   384 $(a+b) \cdot c + b\cdot c$ can be opened up to get $a\cdot c + b \cdot c + b

   472 

   385 \cdot c$, and then simplified to just $a \cdot c + b \cdot c$. Another

   473 We want to get rid of complex and fragile rectification of values.

   386 example is simplifying $(a^*+a) + (a^*+ \ONE) + (a +\ONE)$ to just

   474 Can we not create those intermediate values $v_1,\ldots v_n$,

   387 $a^*+a+\ONE$. Adding these more aggressive simplification rules help us

   475 and get the lexing information that should be already there while

   388 to achieve a very tight size bound, namely,

   476 doing derivatives in one pass, without a second phase of injection?

   389  the same size bound as that of the \emph{partial derivatives}. 

   477 In the meantime, can we make sure that simplifications

   390 And we want to get rid of complex and fragile rectification of values.

   478 are easily handled without breaking the correctness of the algorithm?

   391 

   479 

   392 

   480 Sulzmann and Lu solved this problem by

   393 In order to implement the idea of ``spilling out alternatives'' and to

   481 introducing additional informtaion to the 

   394 make them compatible with the $\textit{inj}$-mechanism, we use

   482 regular expressions called \emph{bitcodes}.

   395 \emph{bitcodes}. They were first introduced by Sulzmann and Lu.

   483 

   396 Here bits and bitcodes (lists of bits) are defined as:

   484 \subsection*{Bit-coded Algorithm}

   485 Bits and bitcodes (lists of bits) are defined as:

   680 The main point of the bitcodes and annotated regular expressions is that

   772 In this section we introduce aggressive (in terms of size) simplification rules

   681 we can apply rather aggressive (in terms of size) simplification rules

   773 on annotated regular expressions

   682 in order to keep derivatives small. We have developed such

   774 in order to keep derivatives small. Such simplifications are promising

   683 ``aggressive'' simplification rules and generated test data that show

   775 as we have

   684 that the expected bound can be achieved. Obviously we could only

   776 generated test data that show

   777 that a good tight bound can be achieved. Obviously we could only