438 

   438 

   439 The contribution of Sulzmann and Lu is an extension of Brzozowski's

   439 The contribution of Sulzmann and Lu is an extension of Brzozowski's

   440 algorithm by a second phase (the first phase being building successive

   440 algorithm by a second phase (the first phase being building successive

   441 derivatives---see \eqref{graph:*}). In this second phase, a POSIX value 

   441 derivatives---see \eqref{graph:*}). In this second phase, a POSIX value 

   442 is generated assuming the regular expression matches  the string. 

   442 is generated assuming the regular expression matches  the string. 

   444 

   444 

   445 \begin{center}

   445 \begin{center}

   446 \begin{tikzcd}

   446 \begin{tikzcd}

   447 r_0 \arrow[r, "\backslash c_0"]  \arrow[d] & r_1 \arrow[r, "\backslash c_1"] \arrow[d] & r_2 \arrow[r, dashed] \arrow[d] & r_n \arrow[d, "mkeps" description] \\

   447 r_0 \arrow[r, "\backslash c_0"]  \arrow[d] & r_1 \arrow[r, "\backslash c_1"] \arrow[d] & r_2 \arrow[r, dashed] \arrow[d] & r_n \arrow[d, "mkeps" description] \\

   448 v_0           & v_1 \arrow[l,"inj_{r_0} c_0"]                & v_2 \arrow[l, "inj_{r_1} c_1"]              & v_n \arrow[l, dashed]         

   448 v_0           & v_1 \arrow[l,"inj_{r_0} c_0"]                & v_2 \arrow[l, "inj_{r_1} c_1"]              & v_n \arrow[l, dashed]         

   459 $\textit{nullable}$ or not. If not, we know the string does not match

   459 $\textit{nullable}$ or not. If not, we know the string does not match

   460 $r$ and no value needs to be generated. If yes, we start building the

   460 $r$ and no value needs to be generated. If yes, we start building the

   461 parse tree incrementally by \emph{injecting} back the characters into

   461 parse tree incrementally by \emph{injecting} back the characters into

   462 the values $v_n, \ldots, v_0$. We first call the function

   462 the values $v_n, \ldots, v_0$. We first call the function

   463 $\textit{mkeps}$, which builds the parse tree for how the empty string

   463 $\textit{mkeps}$, which builds the parse tree for how the empty string

   465 as

   465 as

   466 

   466 

   467 	\begin{center}

   467 	\begin{center}

   468 		\begin{tabular}{lcl}

   468 		\begin{tabular}{lcl}

   469 			$\mkeps(\ONE)$ 		& $\dn$ & $\Empty$ \\

   469 			$\mkeps(\ONE)$ 		& $\dn$ & $\Empty$ \\