582 tells us how about the empty string matches : among the regular expressions in \\$(0+0+0 + 0 + 1 \cdot 1 \cdot 1) \cdot r^* + (0+0+0  + 1 + 0) \cdot r*) +((0+1+0  + 0 + 0) \cdot r*+(0+0+0  + 1 + 0) \cdot r* )$, \\

   582 tells us how about the empty string matches 

   583 we choose the left most nullable one, which is composed of a sequence of an alternative and a star. In that alternative $0+0+0 + 0 + 1 \cdot 1 \cdot 1$ we take the rightmost choice.

   583 \[(0+0+0 + 0 + 1 \cdot 1 \cdot 1) \cdot r^*  \],

   584 

   584 a sequence of 2 empty regular expressions, the first one is an alternative, we take the rightmost alternative 

   585 Using the value $v_3$, the character c, and the regular expression $r_2$, we can recover how $r_2$ matched the string $[c]$ : we inject $c$ back to $v_3$, and get \\ $v_2 = Left(Seq(Right(Right(Right(Seq(Empty, Seq(Empty, c)))))), Stars [])$, \\

   585 to get that empty regular expression. The second one is a star, which iterates 0 times to form the second

   586 which tells us how $r_2$ matched $c$. After this we inject back the character $b$, and get\\ $v_1 = Seq(Right(Right(Right(Seq(Empty, Seq(b, c)))))), Stars [])$ for how $r_1= (1+0+1 \cdot b + 0 + 1 \cdot b \cdot c) \cdot r*$ matched  the string $bc$ before it split into 2 pieces. Finally, after injecting character a back to $v_1$, we get  the parse tree $v_0= Stars [Right(Right(Right(Seq(a, Seq(b, c)))))]$ for how r matched $abc$.

   586 empty regular expression.

   587 We omit the details of injection function, which is provided by Sulzmann and Lu's paper \cite{Sulzmann2014}. 

   587 

   588 Readers might have noticed that the parse tree information as actually already available when doing derivatives. For example, immediately after the operation $\backslash a$ we know that if we want to match a string that starts with a, we can either take the initial match to be 

   588 Using the value $v_3$, the character c, and the regular expression $r_2$, 

   589 we can recover how $r_2$ matched the string $[c]$ : 

   590  $\textit{inj} r_2 c v_3$ gives us\[ v_2 = Left(Seq(Right(Seq(Empty, Seq(Empty, c))), Stars []))\],

   591 which tells us how $r_2$ matched $c$. After this we inject back the character $b$, and get

   592 \[ v_1 = Seq(Right(Seq(Empty, Seq(b, c))), Stars [])\]

   593  for how 

   594  \[r_1= (1+0+1 \cdot b + 0 + 1 \cdot b \cdot c) \cdot r*\]

   595   matched  the string $bc$ before it split into 2 pieces. 

   596   Finally, after injecting character $a$ back to $v_1$, 

   597   we get  the parse tree $v_0= Stars [Right(Seq(a, Seq(b, c)))]$ for how $r$ matched $abc$.

   598 %We omit the details of injection function, which is provided by Sulzmann and Lu's paper \cite{Sulzmann2014}. 

   599 Readers might have noticed that the parse tree information 

   600 is actually already available when doing derivatives. 

   601 For example, immediately after the operation $\backslash a$ we know that if we want to match a string that starts with $a$,

   602  we can either take the initial match to be 

   594 In order to differentiate between these choices, we just need to remember their positions--$a$ is on the left, $ab$ is in the middle , and $abc$ is on the right. Which one of these alternatives is chosen later does not affect their relative position because our algorithm does not change this order. There is no need to traverse this information twice. This leads to a new approach of lexing-- if we store the information for parse trees  in the corresponding regular expression pieces, update this information when we do derivative operation on them, and collect the information when finished with derivatives and calling $mkeps$ for deciding which branch is POSIX, we can generate the parse tree in one pass, instead of doing an n-step backward transformation.This leads to Sulzmann and Lu's novel idea of using bit-codes on derivatives.

   608 In order to differentiate between these choices, 

   609 we just need to remember their positions--$a$ is on the left, $ab$ is in the middle , and $abc$ is on the right. 

   610 Which one of these alternatives is chosen later does not affect their relative position because our algorithm 

   611 does not change this order. If this parsing information can be determined and does

   612 not change because of later derivatives,

   613 there is no point in traversing this information twice. This leads to a new approach of lexing-- if we store the information for parse trees  in the corresponding regular expression pieces, update this information when we do derivative operation on them, and collect the information when finished with derivatives and calling $mkeps$ for deciding which branch is POSIX, we can generate the parse tree in one pass, instead of doing an n-step backward transformation.This leads to Sulzmann and Lu's novel idea of using bit-codes on derivatives.

   608 is that we can introduce simplification without making the algorithm crash or impossible to reason about.

   627 is that we can introduce simplification without making the algorithm crash or overly complex to reason about.

   609 The reason why we need simplification is due to the shortcoming of a naive algorithm using Brzozowski's definition only. 

   628 The reason why we need simplification is due to the shortcoming of the previous algorithm.