62 For example, the regular expression $aa \cdot a^*+ a \cdot a^*$ contains two terms, 

    62 For example, the regular expression 

    63 which expresses two possibilities it will match future input.

    63 \[

    64 It will either match 2 $a$'s, then 0 or more $a$'s, in other words, at least 2 more $a$'s

    64 	aa \cdot a^*+ a \cdot a^* + aa\cdot a^*

    65 \begin{figure}\label{string_3parts1}

    65 \]

    66 \begin{center}

    66 contains three terms, 

    67 \begin{tikzpicture}[every node/.append style={draw, rounded corners, inner sep=10pt}]

    67 expressing three possibilities it will match future input.

    68     \node [rectangle split, rectangle split horizontal, rectangle split parts=3]

    68 The first and the third terms are identical, which means we can eliminate

    69         {Consumed Input

    69 the latter as we know it will not be picked up by $\bmkeps$.

    70         \nodepart{two} Expects $aa$

    70 In $\bsimps$, the $\distinctBy$ function takes care of this.

    71          \nodepart{three} Then expects $a^*$};

    71 The criteria $\distinctBy$ uses for removing a duplicate

    72 

    72 $a_2$ in the list

    73 \begin{center}

    74 	$rs_a@[a_1]@rs_b@[a_2]@rs_c$

    75 \end{center}

    76 is that 

    77 \begin{center}

    78 	$\rerase{a_1} = \rerase{a_2}$.

    79 \end{center}

    80 It can be characterised as the $LD$ 

    81 rewrite rule in \ref{rrewriteRules}.\\

    82 The problem , however, is that identical components

    83 in two slightly different regular expressions cannot be removed:

    84 \begin{figure}[H]

    85 \[

    86 	(a+b+d) \cdot r_1 + (a+c+e) \cdot r_1 \stackrel{?}{\rightsquigarrow} (a+b+d) \cdot r_1 + (c+e) \cdot r_1

    87 \]

    88 \caption{Desired simplification, but not done in $\blexersimp$}\label{partialDedup}

    89 \end{figure}

    90 \noindent

    91 A simplification like this actually

    92 cannot be omitted,

    93 as without it the size could blow up even with our $\simp$ function:

    94 \begin{figure}[H]

    95 \centering

    96 \begin{tikzpicture}

    97 \begin{axis}[

    98     %xlabel={$n$},

    99     myplotstyle,

   100     xlabel={input length},

   101     ylabel={size},

   102     ]

   103 \addplot[blue,mark=*, mark options={fill=white}] table {bsimpExponential.data};

   104 \end{axis}

    74 \end{center}

   106 \caption{Runtime of $\blexersimp$ for matching 

    75 \end{figure}

   107 	$\protect((a^* + (aa)^* + \ldots + (aaaaa)^* )^*)^*$ 

    76 \noindent

   108 	with strings 

    77 Or it will match at least 1 more $a$:

   109 	of the form $\protect\underbrace{aa..a}_{n}$.}\label{blexerExp}

    78 \begin{figure}\label{string_3parts2}

   110 \end{figure}

    79 \begin{center}

   111 \noindent

    80 \begin{tikzpicture}[every node/.append style={draw, rounded corners, inner sep=10pt}]

   112 We would like to apply the rewriting at some stage

    81     \node [rectangle split, rectangle split horizontal, rectangle split parts=3]

   113 \begin{figure}[H]

    82         {Consumed

    83         \nodepart{two} Expects $a$

    84          \nodepart{three} Then expects $a^*$};

    85 

    86 \end{tikzpicture}

    87 \end{center}

    88 \end{figure}

    89 If these two possibilities are identical, we can eliminate

    90 the second one as we know the second one corresponds to 

    91 a match that is not $\POSIX$.

    92 

    93 

    94 If two identical regexes 

    95 happen to be grouped into different sequences, one cannot use

    96 the $a + a \rightsquigarrow a$ rule to eliminate them, even if they 

    97 are "parallel" to each other:

    99 (a+b) \cdot r_1 + (a+c) \cdot r_2 \rightsquigarrow (a+b) \cdot r_1 + (c) \cdot r_2

   115 	(a+b+d) \cdot r_1  \longrightarrow a \cdot r_1 + b \cdot r_1 + d \cdot r_1

   101 and that's because they are followed by possibly 

   117 \caption{Desired simplification, but not done in $\blexersimp$}\label{desiredSimp}

   102 different "suffixes" $r_1$ and $r_2$, and if 

   118 \end{figure}

   103 they do turn out to be different then doing 

   119 \noindent

   104 \[

   120 in our $\simp$ function,

   105 (a+b) \cdot r_1 + (a+c) \cdot r_2 \rightsquigarrow (a+b) \cdot r_1 + (c) \cdot r_2

   121 so that it makes the simplification in \ref{partialDedup} possible.

   106 \]

   122 For example,

   107 might cause a possible match where the string is in $L(a \cdot r_2)$ to be lost.

   123 can a function like the below one be used?

   108 

   124 %TODO: simp' that spills things

   109 Here is an example for this.

   125 

   110 Assume we have the derivative regex 

   126 Unfortunately,

   111 \[( r_1  +  r_2  +  r_3)\cdot r+ 

   127 if we introduce them in our

   112 ( r_1  +  r_5  +  r_6)\cdot( r_1  +  r_2  +  r_3)^*

   128 setting we would lose the POSIX property of our calculated values. 

   113 \]

   129 For example given the regular expression 

   114 

   130 \begin{center}

   115 occurring in an intermediate step in our bit-coded lexing algorithm.

   131 	$(a + ab)(bc + c)$

   116 

   132 \end{center}

   117 In this expression, there will be 6 "parallel" terms if we break up regexes 

   133 and the string

   118 of shape $(a+b)\cdot c$ using the distributivity law (into $ac + bc$).

   134 \begin{center}

   119 \begin{align}

   135 	$ab$,

   120 (\nonumber \\

   136 \end{center}

   121  r_1  + &    \label{term:1} \\

   137 then our algorithm generates the following

   122  r_2  + &  \label{term:2} \\

   138 correct POSIX value

   123  r_3 &  \label{term:3} \\

   139 \begin{center}

   124 &	)\cdot r\; + \; (\nonumber \\

   140 	$\Seq \; (\Right \; ab) \; (\Right \; c)$.

   125  r_1  + & \label{term:4} \\

   141 \end{center}

   126  r_5  + & \label{term:5} \\

   142 Essentially it matches the string with the longer Right-alternative

   127  r_6 \label{term:6}\\

   143 in the first sequence (and

   128 &      )\cdot r\nonumber

   144 then the 'rest' with the character regular expression $c$ from the second sequence).

   129 \end{align}

   145 If we add the simplification above, then we obtain the following value

   130 

   146 \begin{center}

   131 They have been labelled, and each label denotes  

   147 	$\Left \; (\Seq \; a \; (\Left \; bc))$

   132 one term, for example, \ref{term:1} denotes

   148 \end{center}

   133 \[

   149 where the $\Left$-alternatives get priority. 

   134  r_1 \cdot r

   150 However this violates the POSIX rules.

   135 \]

   151 The reason for getting this undesired value

   136 \noindent

   152 is that the new rule splits this regular expression up into 

   137 and \ref{term:3} denotes

   153 \begin{center}

   138 \[

   154 	$a\cdot(b c + c) + ab \cdot (bc + c)$,

   139  r_3\cdot r.

   155 \end{center}

   140 \]

   156 which becomes a regular expression with a 

   141 From a lexer's point of view, \ref{term:4} will never 

   157 totally different structure--the original

   142 be picked up in later phases of matching because there

   158 was a sequence, and now it becomes an alternative.

   143 is a term \ref{term:1} giving identical matching information.

   159 With an alternative the maximum munch rule no longer works.\\

   144 The first term \ref{term:1} will match a string in $L(r_1 \cdot  r)$, 

   160 A method to reconcile this is to do the 

   145 and so on for term \ref{term:2}, \ref{term:3}, etc.

   161 transformation in \ref{desiredSimp} ``non-invasively'',

   146 

   162 meaning that we traverse the list of regular expressions

   147 \mybox{previous input $\ldots$}\mybox{$aaa$ }\mybox{rest of input $\ldots$}

   163 \begin{center}

   148 \begin{center}\label{string_2parts}

   164 	$rs_a@[a]@rs_c$

   149 

   165 \end{center}

   150 \begin{tikzpicture}[every node/.append style={draw, rounded corners, inner sep=10pt}]

   166 in the alternative

   151     \node [rectangle split, rectangle split horizontal, rectangle split parts=2]

   167 \begin{center}

   152         {$r_{x1}$

   168 	$\sum ( rs_a@[a]@rs_c)$

   153          \nodepart{two} $r_1\cdot r$ };

   169 \end{center}

   154 %\caption{term 1 \ref{term:1}'s matching configuration}

   170 using  a function similar to $\distinctBy$,

   155 \end{tikzpicture}

   171 but this time 

   156 

   172 we allow a more general list rewrite:

   157 \end{center}

   173 	\begin{mathpar}

   158 For term 1 \ref{term:1}, whatever was before the current

   174 		\inferrule{\vspace{0mm} }{rs_a@[a]@rs_c 

   159 input position was fully matched and the regex corresponding

   175 			\stackrel{s}{\rightsquigarrow }

   160 to it reduced to $\ONE$, 

   176 		rs_a@[\textit{prune} \; a \; rs_a]@rs_c }

   161 and in the next input token, it will start on $r_1\cdot r$.

   177 	\end{mathpar}

   162 The resulting value will be something of a similar configuration:

   178 %L \; a_1' = L \; a_1 \setminus (\cup_{a \in rs_a} L \; a)

   163 \begin{center}\label{value_2parts}

   179 where $\textit{prune} \;a \; acc$ traverses $a$

   164 %\caption{term 1 \ref{term:1}'s matching configuration}

   180 without altering the structure of $a$, removing components in $a$

   165 \begin{tikzpicture}[every node/.append style={draw, rounded corners, inner sep=10pt}]

   181 that have appeared in the accumulator $acc$.

   166     \node [rectangle split, rectangle split horizontal, rectangle split parts=2]

   182 For example

   167         {$v_{x1}$

   183 \begin{center}

   168          \nodepart{two} $v_{r_1\cdot r}$ };

   184 	$\textit{prune} \;\;\; (r_a+r_f+r_g+r_h)r_d \;\; \; [(r_a+r_b+r_c)r_d, (r_e+r_f)r_d] $

   169 \end{tikzpicture}

   185 \end{center}

   170 \end{center}

   186 should be equal to 

   171 For term 2 \ref{term:2} we have a similar value partition:

   187 \begin{center}

   172 \begin{center}\label{value_2parts2}

   188 	$(r_g+r_h)r_d$

   173 %\caption{term 1 \ref{term:1}'s matching configuration}

   189 \end{center}

   174 \begin{tikzpicture}[every node/.append style={draw, rounded corners, inner sep=10pt}]

   190 because $r_gr_d$ and 

   175     \node [rectangle split, rectangle split horizontal, rectangle split parts=2]

   191 $r_hr_d$ are the only terms

   176         {$v_{x2}$

   192 that have not appeared in the accumulator list 

   177          \nodepart{two} $v_{r_2\cdot r}$ };

   193 \begin{center}

   178 \end{tikzpicture}

   194 $[(r_a+r_b+r_c)r_d, (r_e+r_f)r_d]$.

   179 \end{center}

   195 \end{center}

   180 \noindent

   196 We implemented 

   181 and so on.

   197 function $\textit{prune}$ in Scala,

   182 We note that for term 4 \ref{term:4} its result value 

   198 and incorporated into our lexer,

   183 after any position beyond  the current one will always

   199 by replacing the $\simp$ function 

   184 be the same:

   200 with a stronger version called $\bsimpStrong$

   185 \begin{center}\label{value_2parts4}

   201 that prunes regular expressions.

   186 %\caption{term 1 \ref{term:1}'s matching configuration}

   202 We call this lexer $\blexerStrong$.

   187 \begin{tikzpicture}[every node/.append style={draw, rounded corners, inner sep=10pt}]

   203 $\blexerStrong$ is able to drastically reduce the

   188     \node [rectangle split, rectangle split horizontal, rectangle split parts=2]

   204 internal data structure size which could

   189         {$v_{x4}$

   205 trigger exponential behaviours in

   190          \nodepart{two} $v_{r_1\cdot r}$ };

   206 $\blexersimp$.

   191 \end{tikzpicture}

   207 \begin{figure}[H]

   192 \end{center}

   193 And $\POSIX$ rules says that we can eliminate at least one of them.

   194 Our algorithm always puts the regex with the longest initial sub-match at the left of the 

   195 alternatives, so we safely throw away \ref{term:4}.

   196 The fact that term 1 and 4 are not immediately in the same alternative

   197 expression does not prevent them from being two duplicate matches at

   198 the current point of view.

   199 To implement this idea into an algorithm, we define a "pruning function"

   200 $\textit{prune}$, that takes away parts of all terms in $r$ that belongs to

   201 $\textit{acc}$, which acts as an element

   202 is a stronger version of $\textit{distinctBy}$.

   203 Here is a concise version of it (in the style of Scala):

   204 \begin{figure}[H]

   205 \begin{lstlisting}

   206 def distinctByPlus(rs: List[ARexp], acc: Set[Rexp] = Set()) : 

   207 List[ARexp] =  rs match {

   208   case Nil => Nil

   209   case r :: rs =>

   210     if(acc.contains(erase(r)))

   211       distinctByPlus(rs, acc)

   212     else 

   213       prune(r, acc) :: distinctByPlus(rs, prune(r, acc) +: acc)

   214 }

   215 

   216 \end{lstlisting}

   217 \caption{the distinctByPlus function}

   218 \end{figure}

   219 But for the function $\textit{prune}$ there is a difficulty:

   220 how could one define the $L$ function in a "computable" way,

   221 so that they generate a (lazy infinite) set of strings in $L(r)$.

   222 We also need a function that tests whether $L(r_1) \subseteq L(r_2)$

   223 is true.

   224 For the moment we cut corners and do not define these two functions

   225 as they are not used by Antimirov (and will probably not contribute

   226 to a bound better than Antimirov's cubic bound).

   227 Rather, we do not try to eliminate in every instance of regular expressions

   228 that have "language duplicates", but only eliminate the "exact duplicates".

   229 For this we need to break up terms $(a+b)\cdot c$ into two

   230 terms $a\cdot c$ and $b\cdot c$ before we add them to the accumulator:

   231 \begin{figure}[H]

   232 \begin{lstlisting}

   233 def distinctWith(rs: List[ARexp], 

   234                 pruneFunction: (ARexp, Set[Rexp]) => ARexp, 

   235                 acc: Set[Rexp] = Set()) : List[ARexp] = 

   236   rs match{

   237     case Nil => Nil

   238     case r :: rs => 

   239       if(acc(erase(r)))

   240         distinctWith(rs, pruneFunction, acc)

   241       else {

   242         val pruned_r = pruneFunction(r, acc)

   243         pruned_r :: 

   244         distinctWith(rs, 

   245           pruneFunction, 

   246           turnIntoTerms(erase(pruned_r)) ++: acc

   247         )

   248       }

   249   }

   250 \end{lstlisting}

   251 \caption{A Stronger Version of $\textit{distinctBy}$}

   252 \end{figure}

   253 \noindent

   254 This process is done by the function $\textit{turnIntoTerms}$:

   255 \begin{figure}

   256 \begin{verbatim}

   257 def turnIntoTerms(r: Rexp): List[Rexp] = r match {

   258   case SEQ(r1, r2)  => if(isOne(r1)) 

   259                           turnIntoTerms(r2) 

   260                        else 

   261                           turnIntoTerms(r1).map(r11 => SEQ(r11, r2))

   262   case ALTS(r1, r2) => turnIntoTerms(r1) ::: turnIntoTerms(r2)

   263   case ZERO => Nil

   264   case _ => r :: Nil

   265 }

   266 \end{verbatim}

   267 \caption{function that breaks up regular expression into "atomic" terms}

   268 \end{figure}

   269 

   270 \noindent

   271 The pruning function can be defined recursively:

   272 \begin{figure}

   273 \begin{verbatim}

   274 def prune7(r: ARexp, acc: Set[Rexp]) : ARexp = r match{

   275   case AALTS(bs, rs) => rs.map(r => prune7(r, acc)).filter(_ != ZERO) match

   276   {

   277     case Nil => AZERO

   278     case r::Nil => fuse(bs, r)

   279     case rs1 => AALTS(bs, rs1)

   280   }

   281   case ASEQ(bs, r1, r2) => prune7(r1, acc.map(r => removeSeqTail(r, erase(r2)))) match {

   282     case AZERO => AZERO

   283     case r1p if(isOne(erase(r1p))) => fuse(bs ++ mkepsBC(r1p), r2)

   284     case r1p => ASEQ(bs, r1p, r2)

   285   }

   286   case r => if(acc(erase(r))) AZERO else r

   287 }

   288 \end{verbatim}

   289 \caption{pruning function}

   290 \end{figure}

   291 

   292 

   293 

   294 \begin{figure}

   319            of the form $\underbrace{aa..a}_{n}$.}

   232 	   of the form $\underbrace{aa..a}_{n}$.}

   348 The most tricky part of lexing for the $~r$ regex

   526 The most tricky part of lexing for the $~r$ regular expression

   351  structure of the regex:

   529  structure of the regular expression:

   355 But for the $~r$ regex, $s$ is a member of it if and only if

   533 But for the $~r$ regular expression, $s$ is a member of it if and only if

   358 is a match for the not regex, it is not possible to generate how the string $s$ matched

   536 is a match for the not regular expression, it is not possible to generate how the string $s$ matched

   363 We could give a partial value when there is a partial match for the regex inside

   541 We could give a partial value when there is a partial match for the regular expression inside