From 96a1d27df4bf5dc04a9748829990872b0b4f88a8 Mon Sep 17 00:00:00 2001 From: Ulya Trofimovich Date: Thu, 11 Oct 2018 07:08:48 +0100 Subject: [PATCH] Paper: handle (e) as (e){1,1} to avoid collapsing multiple submatch groups into one. Previously we collapsed ((e)) into (e). --- re2c/doc/tdfa_v2/img/mark_enum.tex | 287 +++++++++++++++-------------- re2c/doc/tdfa_v2/part_1_tnfa.tex | 129 ++++--------- 2 files changed, 183 insertions(+), 233 deletions(-) diff --git a/re2c/doc/tdfa_v2/img/mark_enum.tex b/re2c/doc/tdfa_v2/img/mark_enum.tex index fc1ca763..5c308ff6 100644 --- a/re2c/doc/tdfa_v2/img/mark_enum.tex +++ b/re2c/doc/tdfa_v2/img/mark_enum.tex @@ -22,42 +22,34 @@ % $(\epsilon|a^{0,\infty})(a|\epsilon)^{0,\infty}$ -\begin{scope}[xshift=0.5in, yshift=0in] +\small{ + +\begin{scope}[xshift=0.7in, yshift=0in] \node (a) {{ $\begin{aligned} - & mark (((\epsilon|a^{0,\infty})(a|\epsilon)^{0,3} ))) = \big[ \\ - & \quad mark ( (\epsilon|a^{0,\infty})(a|\epsilon)^{0,3} ) ) = \big[ \\ + & mark ((\epsilon|a^{0,\infty})(a|\epsilon)^{0,3} )) = \big[ \\ % - & \quad\quad mark ( (\epsilon|a^{0,\infty}) ) = \big[ \\ + & \quad mark ( (\epsilon|a^{0,\infty}) ) = \\ + & \quad mark ( (\epsilon|a^{0,\infty})^{1,1} ) = \big[ \\ & \quad\quad mark ( \epsilon|a^{0,\infty} ) = \big[ \\ - & \quad\quad\quad\quad mark ( \epsilon ) = (0,0,\epsilon), \\ - & \quad\quad\quad\quad mark ( a^{0,\infty} ) = \big[ \\ - & \quad\quad\quad\quad\quad mark ( a ) = (0,0,a) \\ - & \quad\quad\quad\quad \big] = (0,0,(0,0,a)^{0,\infty}) \\ - & \quad\quad\quad \big] = (0,0,(0,0,\epsilon) \mid (0,0,(0,0,a)^{0,\infty})) \\ - & \quad\quad \big] = (1,1,(0,0,\epsilon)|(0,0,(0,0,a)^{0,\infty})) \\ + & \quad\quad\quad mark ( \epsilon ) = (0,0,\epsilon), \\ + & \quad\quad\quad mark ( a^{0,\infty} ) = \big[ \\ + & \quad\quad\quad\quad mark ( a ) = (0,0,a) \\ + & \quad\quad\quad \big] = (0,0,(0,0,a)^{0,\infty}) \\ + & \quad\quad \big] = (0,0,(0,0,\epsilon) \mid (0,0,(0,0,a)^{0,\infty})) \\ + & \quad \big] = (1,0,(1,1,(0,0,\epsilon) \mid (0,0,(0,0,a)^{0,\infty}))^{1,1}) \\ % - & \quad\quad mark ( (a|\epsilon)^{0,3} ) = \big[ \\ - & \quad\quad\quad mark ( (a|\epsilon) ) = \big[ \\ - & \quad\quad\quad\quad mark ( a|\epsilon ) = \big [ \\ - & \quad\quad\quad\quad\quad mark ( a ) = (0,0,a) \\ - & \quad\quad\quad\quad\quad mark ( \epsilon ) = (0,0,\epsilon) \\ - & \quad\quad\quad\quad \big] = (0,0,(0,0,a) \mid (0,0,\epsilon)) \\ - & \quad\quad\quad \big] = (1,1,(0,0,a) \mid (0,0,\epsilon)) \\ - & \quad\quad \big] = (1,0,(1,1,(0,0,a) \mid (0,0,\epsilon))^{0,3}) \\ + & \quad mark ( (a|\epsilon)^{0,3} ) = \big[ \\ + & \quad\quad mark ( a|\epsilon ) = \big [ \\ + & \quad\quad\quad mark ( a ) = (0,0,a) \\ + & \quad\quad\quad mark ( \epsilon ) = (0,0,\epsilon) \\ + & \quad\quad \big] = (0,0,(0,0,a) \mid (0,0,\epsilon)) \\ + & \quad \big] = (1,0,(1,1,(0,0,a) \mid (0,0,\epsilon))^{0,3}) \\ % - & \quad\big] = (1,0, - (1,1,(0,0,\epsilon) \mid (0,0,(0,0,a)^{0,\infty})) \\ - & \quad\quad\quad\quad \cdot (1,0,(1,1,(0,0,a) \mid (0,0,\epsilon))^{0,3}) - ) \\ - & \big] = (1,1, - (1,1,(0,0,\epsilon) \mid (0,0,(0,0,a)^{0,\infty})) \\ + & \big] = (1,0, + (1,0,(1,1,(0,0,\epsilon) \mid (0,0,(0,0,a)^{0,\infty}))^{1,1}) \\ & \quad\quad\quad \cdot (1,0,(1,1,(0,0,a) \mid (0,0,\epsilon))^{0,3}) - ) \\ -% -% & \IRE ((\epsilon|a^{0,\infty})(a|\epsilon)^{0,3} )) = \\ -% & \quad\quad\quad = (1,1, (2,2,(0,0,\epsilon) \mid (0,0,(0,0,a)^{0,\infty})) \\ -% & \quad\quad\quad\quad\quad\quad \cdot (3,0,(4,3,(0,0,a) \mid (0,0,\epsilon))^{0,3})) + ) \end{aligned}$ }}; \end{scope} @@ -65,53 +57,58 @@ \begin{scope}[xshift=4in, yshift=0in] \node (a) {{ $\begin{aligned} - & enum (1,1,(1,1, - (1,1,(0,0,\epsilon) \mid (0,0,(0,0,a)^{0,\infty})) \\ - & \quad\quad\quad\quad\quad \cdot (1,0,(1,1,(0,0,a) \mid (0,0,\epsilon))^{0,3}))) = \big[ \\ - & \quad enum (2,2,(1,1,(0,0,\epsilon) \mid (0,0,(0,0,a)^{0,\infty}))) = \big[ \\ - & \quad\quad enum (3,3,(0,0,\epsilon)) = (3,3,(0,0,\epsilon)) \\ - & \quad\quad enum (3,3,(0,0,(0,0,a)^{0,\infty})) = \big[ \\ - & \quad\quad\quad enum (3,3,(0,0,a)) = (3,3,(0,0,a)) \\ - & \quad\quad \big] = (3,3,(0,0,(0,0,a)^{0,\infty})) \\ - & \quad \big] = (3,3,(2,2,(0,0,\epsilon) \mid (0,0,(0,0,a)^{0,\infty}))) \\ + & enum (1,1, \; (1,0, + (1,0,(1,1,(0,0,\epsilon) \mid (0,0,(0,0,a)^{0,\infty}))^{1,1}) \\ + & \quad\quad\quad\quad\quad\quad \cdot (1,0,(1,1,(0,0,a) \mid (0,0,\epsilon))^{0,3}) + ) \;) = \big[ \\ + % + & \quad enum (2,1, \; (1,0,(1,1,(0,0,\epsilon) \mid (0,0,(0,0,a)^{0,\infty}))^{1,1}) \;) = \big[ \\ + & \quad\quad enum (3,1, \; (1,1,(0,0,\epsilon) \mid (0,0,(0,0,a)^{0,\infty})) \;) = \big[ \\ + & \quad\quad\quad enum (4,2, \; (0,0,\epsilon)) = (4,2, \; (0,0,\epsilon) \;) \\ + & \quad\quad\quad enum (4,2, \; (0,0,(0,0,a)^{0,\infty}) \;) = \big[ \\ + & \quad\quad\quad\quad enum (4,2, \; (0,0,a)) = (4,2, \; (0,0,a) \;) \\ + & \quad\quad\quad \big] = (4,2, \; (0,0,(0,0,a)^{0,\infty}) \;) \\ + & \quad\quad \big] = (4,2, \; (3,1,(0,0,\epsilon) \mid (0,0,(0,0,a)^{0,\infty})) \;) \\ + & \quad \big] = (4,2, \; (2,0,(3,1,(0,0,\epsilon) \mid (0,0,(0,0,a)^{0,\infty}))^{1,1}) \;) \\ % - & \quad enum (3,3, (1,0,(1,1,(0,0,a) \mid (0,0,\epsilon))^{0,3}) ) = \big[ \\ - & \quad\quad enum (4,3, (1,1,(0,0,a) \mid (0,0,\epsilon)) ) = \big[ \\ - & \quad\quad\quad enum (5,4, (0,0,a) ) = (0,0,a) \\ - & \quad\quad\quad enum (5,4, (0,0,\epsilon) ) = (0,0,\epsilon) \\ - & \quad\quad \big] = (5,4,(4,3,(0,0,a) \mid (0,0,\epsilon))) \\ - & \quad \big] = (5,4,(3,0,(4,3,(0,0,a) \mid (0,0,\epsilon))^{0,3})) \\ + & \quad enum (4,2, \; (1,0,(1,1,(0,0,a) \mid (0,0,\epsilon))^{0,3}) \;) = \big[ \\ + & \quad\quad enum (5,2, \; (1,1,(0,0,a) \mid (0,0,\epsilon)) \;) = \big[ \\ + & \quad\quad\quad enum (6,3, \; (0,0,a) ) = (6, 3, \; (0,0,a) \;) \\ + & \quad\quad\quad enum (6,3, \; (0,0,\epsilon) ) = (6, 3, \; (0,0,\epsilon) \;) \\ + & \quad\quad \big] = (6,3, \; (5,2,(0,0,a) \mid (0,0,\epsilon)) \;) \\ + & \quad \big] = (6,3, \; (4,0,(5,2,(0,0,a) \mid (0,0,\epsilon))^{0,3}) \;) \\ % - & \big] = (5,4,(1,1, - (2,2,(0,0,\epsilon) \mid (0,0,(0,0,a)^{0,\infty})) \\ - & \quad\quad\quad\quad\quad \cdot (3,0,(4,3,(0,0,a) \mid (0,0,\epsilon))^{0,3}) - )) \\ - \\ \\ \\ \\ \\ \\ \\ + & \big] = (6,3, \; (1,0, + (2,0,(3,1,(0,0,\epsilon) \mid (0,0,(0,0,a)^{0,\infty}))^{1,1}) \\ + & \quad\quad\quad\quad\quad \cdot (4,0,(5,2,(0,0,a) \mid (0,0,\epsilon))^{0,3}) + ) \;) \\ \end{aligned}$ }}; \end{scope} -\begin{scope}[xshift=2.5in, yshift=-2.9in] - \node (c) {{ - $\begin{aligned} - & \IRE ((\epsilon|a^{0,\infty})(a|\epsilon)^{0,3} )) - = (1,1, (2,2,(0,0,\epsilon) \mid (0,0,(0,0,a)^{0,\infty})) - \cdot (3,0,(4,3,(0,0,a) \mid (0,0,\epsilon))^{0,3})) - \end{aligned}$ - }}; -\end{scope} +%\begin{scope}[xshift=2.5in, yshift=-2.4in] +% \node (c) {{ +% $\begin{aligned} +% & \IRE ((\epsilon|a^{0,\infty})(a|\epsilon)^{0,3} )) +% = (1,0, (2,0,(3,1,(0,0,\epsilon) \mid (0,0,(0,0,a)^{0,\infty}))^{1,1}) +% \cdot (4,0,(5,2,(0,0,a) \mid (0,0,\epsilon))^{0,3})) +% \end{aligned}$ +% }}; +%\end{scope} -\begin{scope}[xshift=4in, yshift=-1.35in] - \graph [tree layout, grow=down, fresh nodes] { - "${(1, 1, \cdot)}_{\Lambda}$" -- { - "${(2, 2, |)}_{1}$" -- { - "${(0, 0, \epsilon)}_{1.1}$", - "${(0, 0, \{0,\infty\})}_{1.2}$" -- { - "${(0, 0, a)}_{1.2.1}$" +\begin{scope}[xshift=2.4in, yshift=-1.95in] + \graph [tree layout, grow=down, fresh nodes, level distance=0.35in] { + "${(1, 0, \cdot)}_{\Lambda}$" -- { + "${(2, 0, \{1,1\})}_{1}$" -- { + "${(3, 1, |)}_{1.1}$" -- { + "${(0, 0, \epsilon)}_{1.1.1}$", + "${(0, 0, \{0,\infty\})}_{1.1.2}$" -- { + "${(0, 0, a)}_{1.1.2.1}$" + } } }, - "${(3, 0, \{0,3\})}_{2}$" -- { - "${(4, 3, |)}_{2.1}$" -- { + "${4, 0, \{0,3\})}_{2}$" -- { + "${(5, 2, |)}_{2.1}$" -- { "${(0, 0, a)}_{2.1.1}$", "${(0, 0, \epsilon)}_{2.1.2}$" } @@ -122,125 +119,141 @@ \newcommand\xsp[1]{\hphantom{\hspace{#1em}\hspace{-0.2em}}} -\begin{scope}[xshift=0in, yshift=-3.3in, sibling distance=0.6in] +\begin{scope}[xshift=-0.1in, yshift=-3.6in, sibling distance=0.5in, level distance=0.35in] \node[xshift=-0.2in, draw=none] {$s:$}; \graph [tree layout, grow=down, fresh nodes] { a1/"${T}^{1}_{\Lambda}$" -- { a11/"${T}^{2}_{1}$" -- { - a111/"${\varnothing}^{0}_{1.1}$", - a112/"${T}^{0}_{1.2}$" -- { - a1121/"${a}^{0}_{1.2.1}$" + a111/"${T}^{3}_{1.1}$" -- { + a1111/"${\varnothing}^{0}_{1.1.1}$", + a1112/"${T}^{0}_{1.1.2}$" -- { + a11121/"${a}^{0}_{1.1.2.1}$" + } } }, - a12/"${T}^{3}_{2}$" -- { - a121/"${\varnothing}^{4}_{2.1}$" + a12/"${T}^{4}_{2}$" -- { + a121/"${\varnothing}^{5}_{2.1}$" } } }; - \node at (a1) {\xsp{2.5}\footnotesize{$\#1$}}; - \node at (a11) {\xsp{2.5}\footnotesize{$\#1$}}; - \node at (a111) {\xsp{3.0}\footnotesize{$\#\infty$}}; - \node at (a112) {\xsp{3.0}\footnotesize{$\#\infty$}}; - \node at (a1121) {\xsp{3.5}\footnotesize{$\#\infty$}}; - \node at (a12) {\xsp{2.5}\footnotesize{$\#0$}}; - \node at (a121) {\xsp{3.0}\footnotesize{$\#\!-\!\!1$}}; - - \node[yshift=-1.5in, draw=none] - {\small{${T}^{1} \big( + \node at (a1) {\xsp{2.5}\footnotesize{$\#1$}}; + \node at (a11) {\xsp{2.5}\footnotesize{$\#1$}}; + \node at (a111) {\xsp{2.5}\footnotesize{$\#1$}}; + \node at (a1111) {\xsp{3.5}\footnotesize{$\#\infty$}}; + \node at (a1112) {\xsp{3.5}\footnotesize{$\#\infty$}}; + \node at (a11121) {\xsp{4.0}\footnotesize{$\#\infty$}}; + \node at (a12) {\xsp{2.5}\footnotesize{$\#0$}}; + \node at (a121) {\xsp{3.0}\footnotesize{$\#\!-\!\!1$}}; + + \node[yshift=-1.65in, draw=none] + {${T}^{1} \big( {T}^{2} \big( - {\varnothing}^{0}, - {T}^{0}({a}^{0}) + {T}^{3} ( + {\varnothing}^{0}, + {T}^{0}({a}^{0}) + ) \big), - {T}^{3}( - {\varnothing}^{4} + {T}^{4}( + {\varnothing}^{5} ) - \big)$}}; + \big)$}; \end{scope} -\begin{scope}[xshift=1.9in, yshift=-3.3in, sibling distance=0.6in] +\begin{scope}[xshift=1.6in, yshift=-3.6in, sibling distance=0.5in, level distance=0.35in] \node[xshift=-0.2in, draw=none] {$t:$}; \graph [tree layout, grow=down, fresh nodes] { a1/"${T}^{1}_{\Lambda}$" -- { a11/"${T}^{2}_{1}$" -- { - a111/"${\varnothing}^{0}_{1.1}$", - a112/"${T}^{0}_{1.2}$" -- { - a1121/"${\varnothing}^{0}_{1.2.1}$" + a111/"${T}^{3}_{1.1}$" -- { + a1111/"${\varnothing}^{0}_{1.1.1}$", + a1112/"${T}^{0}_{1.1.2}$" -- { + a11121/"${\varnothing}^{0}_{1.1.2.1}$" + } } }, - a12/"${T}^{3}_{2}$" -- { - a121/"${T}^{4}_{2.1}$" -- { + a12/"${T}^{4}_{2}$" -- { + a121/"${T}^{5}_{2.1}$" -- { a1211/"${a}^{0}_{2.1.1}$", a1212/"${\varnothing}^{0}_{2.1.2}$" } } } }; - \node at (a1) {\xsp{2.5}\footnotesize{$\#1$}}; - \node at (a11) {\xsp{2.5}\footnotesize{$\#0$}}; - \node at (a111) {\xsp{3.0}\footnotesize{$\#\infty$}}; - \node at (a112) {\xsp{3.0}\footnotesize{$\#\infty$}}; - \node at (a1121) {\xsp{3.5}\footnotesize{$\#\infty$}}; - \node at (a12) {\xsp{2.5}\footnotesize{$\#1$}}; - \node at (a121) {\xsp{3.0}\footnotesize{$\#1$}}; - \node at (a1211) {\xsp{3.5}\footnotesize{$\#\infty$}}; - \node at (a1212) {\xsp{3.5}\footnotesize{$\#\infty$}}; - - \node[yshift=-1.5in, draw=none] - {\small{${T}^{1}\big( + \node at (a1) {\xsp{2.5}\footnotesize{$\#1$}}; + \node at (a11) {\xsp{2.5}\footnotesize{$\#0$}}; + \node at (a111) {\xsp{2.5}\footnotesize{$\#0$}}; + \node at (a1111) {\xsp{3.5}\footnotesize{$\#\infty$}}; + \node at (a1112) {\xsp{3.5}\footnotesize{$\#\infty$}}; + \node at (a11121) {\xsp{4.0}\footnotesize{$\#\infty$}}; + \node at (a12) {\xsp{2.5}\footnotesize{$\#1$}}; + \node at (a121) {\xsp{3.0}\footnotesize{$\#1$}}; + \node at (a1211) {\xsp{3.5}\footnotesize{$\#\infty$}}; + \node at (a1212) {\xsp{3.5}\footnotesize{$\#\infty$}}; + + \node[xshift=0.4in, yshift=-1.65in, draw=none] + {${T}^{1}\big( {T}^{2}( - {\varnothing}^{0}, - {T}^{0}({\varnothing}^{0}) + {T}^{3}( + {\varnothing}^{0}, + {T}^{0}({\varnothing}^{0}) + ), ), - {T}^{3}\big( - {T}^{4}({a}^{0},{\varnothing}^{0}) + {T}^{4}\big( + {T}^{5}({a}^{0},{\varnothing}^{0}) \big) - \big)$}}; + \big)$}; \end{scope} -\begin{scope}[xshift=4.1in, yshift=-3.3in, sibling distance=0.6in] +\begin{scope}[xshift=4in, yshift=-3.6in, sibling distance=0.5in, level distance=0.35in] \node[xshift=-0.2in, draw=none] {$u:$}; \graph [tree layout, grow=down, fresh nodes] { a1/"${T}^{1}_{\Lambda}$" -- { a11/"${T}^{2}_{1}$" -- { - a111/"${\epsilon}^{0}_{1.1}$", - a112/"${\varnothing}^{0}_{1.2}$" + a111/"${T}^{3}_{1.1}$" -- { + a1111/"${\epsilon}^{0}_{1.1.1}$", + a1112/"${\varnothing}^{0}_{1.1.2}$" + } }, - a12/"${T}^{3}_{2}$" -- { - a121/"${T}^{4}_{2.1}$" -- { + a12/"${T}^{4}_{2}$" -- { + a121/"${T}^{5}_{2.1}$" -- { a1211/"${a}^{0}_{2.1.1}$", a1212/"${\varnothing}^{0}_{2.1.2}$" }, - a122/"${T}^{4}_{2.2}$" -- { + a122/"${T}^{5}_{2.2}$" -- { a1221/"${\varnothing}^{0}_{2.2.1}$", a1222/"${\epsilon}^{0}_{2.2.2}$" } } } }; - \node at (a1) {\xsp{2.5}\footnotesize{$\#1$}}; - \node at (a11) {\xsp{2.5}\footnotesize{$\#0$}}; - \node at (a111) {\xsp{3.0}\footnotesize{$\#\infty$}}; - \node at (a112) {\xsp{3.0}\footnotesize{$\#\infty$}}; - \node at (a12) {\xsp{2.5}\footnotesize{$\#1$}}; - \node at (a121) {\xsp{3.0}\footnotesize{$\#1$}}; - \node at (a1211) {\xsp{3.5}\footnotesize{$\#\infty$}}; - \node at (a1212) {\xsp{3.5}\footnotesize{$\#\infty$}}; - \node at (a122) {\xsp{3.0}\footnotesize{$\#0$}}; - \node at (a1221) {\xsp{3.5}\footnotesize{$\#\infty$}}; - \node at (a1222) {\xsp{3.5}\footnotesize{$\#\infty$}}; - - \node[xshift=0.2in, yshift=-1.5in, draw=none] - {\small{${T}^{1}\big( + \node at (a1) {\xsp{2.5}\footnotesize{$\#1$}}; + \node at (a11) {\xsp{2.5}\footnotesize{$\#0$}}; + \node at (a111) {\xsp{2.5}\footnotesize{$\#0$}}; + \node at (a1111) {\xsp{3.5}\footnotesize{$\#\infty$}}; + \node at (a1112) {\xsp{3.5}\footnotesize{$\#\infty$}}; + \node at (a12) {\xsp{2.5}\footnotesize{$\#1$}}; + \node at (a121) {\xsp{3.0}\footnotesize{$\#1$}}; + \node at (a1211) {\xsp{3.5}\footnotesize{$\#\infty$}}; + \node at (a1212) {\xsp{3.5}\footnotesize{$\#\infty$}}; + \node at (a122) {\xsp{3.0}\footnotesize{$\#0$}}; + \node at (a1221) {\xsp{3.5}\footnotesize{$\#\infty$}}; + \node at (a1222) {\xsp{3.5}\footnotesize{$\#\infty$}}; + + \node[xshift=0.3in, yshift=-1.35in, draw=none] + {${T}^{1}\big( {T}^{2}( - {\epsilon}^{0}, - {\varnothing}^{0} + {T}^{3}( + {\epsilon}^{0}, + {\varnothing}^{0} + ) ), - {T}^{3}\big( - {T}^{4}({a}^{0},{\varnothing}^{0}), - {T}^{4}({\varnothing}^{0}, {\epsilon}^{0}) + {T}^{4}\big( + {T}^{5}({a}^{0},{\varnothing}^{0}), + {T}^{5}({\varnothing}^{0}, {\epsilon}^{0}) \big) - \big)$}}; + \big)$}; \end{scope} +} \end{tikzpicture} diff --git a/re2c/doc/tdfa_v2/part_1_tnfa.tex b/re2c/doc/tdfa_v2/part_1_tnfa.tex index 221b57e2..fddebbb5 100644 --- a/re2c/doc/tdfa_v2/part_1_tnfa.tex +++ b/re2c/doc/tdfa_v2/part_1_tnfa.tex @@ -379,41 +379,43 @@ The function $\IRE : \XR_\Sigma \rightarrow \XIR_\Sigma$ transforms REs into IRE It is defined via a composition of two functions, $mark$ that transforms REs into IREs with submatch indices in the boolean range $\{0, 1\}$, and $enum$ that substitutes boolean indices with consecutive numbers: -$\IRE(e) = r$ where $(\Xund, \Xund, r) = enum(1, 1, mark((e)))$. -Note the extra pair of parentheses around $e$: -according to the POSIX standard the root sub-RE is always the submatch group number zero, -even if it has no explicit parentheses. +$\IRE(e) = r$ where $(\Xund, \Xund, r) = enum(1, 1, mark(e))$. +Note that we consider $(e)$ as a special case of repetition $(e)^{1,1}$: +this allows us to handle all parenthesized sub-RE uniformly. +An example of constructing an IRE from a RE is given on figure \ref{fig_mark_enum}. +The reverse transformation is also possible by erasing all indices +and adding parentheses around subexpressions with nonzero explicit submatch index. +Therefore RE and IRE are equivalent representations. \begin{align*} &\begin{aligned} mark &: \XR_\Sigma \longrightarrow \XIR_\Sigma \\ - mark &(x) = (0, 0, x) \\ - &\text{where } x \in \{\epsilon, \alpha\} - \\ + mark &(x) \mid_{x \in \{\epsilon, \alpha\}} = (0, 0, x) \\ % - mark &(e_1 \circ e_2) = (i, 0, + mark &(e_1 \circ e_2) \mid_{\circ \in \{|,\cdot\}} = (i, 0, (i, j_1, r_1) \circ (i, j_2, r_2) ) \\ - &\text{where } \circ \in \{|,\cdot\} \\ - &\space{\hphantom{where }}(i_1, j_1, r_1) = mark(e_1) \\ - &\space{\hphantom{where }}(i_2, j_2, r_1) = mark(e_2) \\ + &\text{where } (i_1, j_1, r_1) = mark(e_1) \\ + &\space{\hphantom{where }}(i_2, j_2, r_2) = mark(e_2) \\ &\space{\hphantom{where }}i = i_1 \vee i_2 \\ % - mark &(e^{n, m}) = (i, 0, (i, j, r)^{n, m}) \\ + mark &(e^{n, m}) \mid_{e = (e_1)} = (1, 0, (1, 1, r)) \\ + &\text{where } (\Xund, \Xund, r) = mark(e_1) \\ + % + mark &(e^{n, m}) \mid_{e \neq (e_1)} = (i, 0, (i, j, r)) \\ &\text{where } (i, j, r) = mark(e) \\ % - mark &((e)) = (1, 1, r) \\ - &\text{where } (\Xund, \Xund, r) = mark(e) + mark &((e)) = mark((e)^{1, 1}) \end{aligned} % &&\begin{aligned} enum &: \YZ \times \YZ \times \XIR_\Sigma \longrightarrow \YZ \times \YZ \times \XIR_\Sigma \\ - enum &(\bar{i}, \bar{j}, (i, j, x)) = (\bar{i} + i, \bar{j} + j, (\bar{i} \times i, \bar{j} \times j, x)) \\ - &\text{where } x \in \{\epsilon, \alpha\} + enum &(\bar{i}, \bar{j}, (i, j, x)) \mid_{x \in \{\epsilon, \alpha\}} + = (\bar{i} + i, \bar{j} + j, (\bar{i} \times i, \bar{j} \times j, x)) \\ - enum &(\bar{i}, \bar{j}, (i, j, r_1 \circ r_2)) = (i_2, j_2, (\bar{i} \times i, \bar{j} \times j, \bar{r}_1 \circ \bar{r}_2)) \\ - &\text{where } \circ \in \{|,\cdot\} \\ - &\space{\hphantom{where }}(i_1, j_1, \bar{r}_1) = enum(\bar{i} + i, \bar{j} + j, r_1) \\ + enum &(\bar{i}, \bar{j}, (i, j, r_1 \circ r_2)) \mid_{\circ \in \{|,\cdot\}} + = (i_2, j_2, (\bar{i} \times i, \bar{j} \times j, \bar{r}_1 \circ \bar{r}_2)) \\ + &\text{where } (i_1, j_1, \bar{r}_1) = enum(\bar{i} + i, \bar{j} + j, r_1) \\ &\space{\hphantom{where }}(i_2, j_2, \bar{r}_2) = enum(i_1, j_1, r_2) \\ enum &(\bar{i}, \bar{j}, (i, j, r^{n,m})) = (i_1, j_1, (\bar{i} \times i, \bar{j} \times j, \bar{r}^{n,m})) \\ @@ -422,81 +424,6 @@ even if it has no explicit parentheses. \end{aligned} \end{align*} -An example of constructing an IRE from a RE is given on figure \ref{fig_mark_enum}. -The reverse transformation is also possible: -we can transform IRE back to RE -by erasing all indices -and adding parentheses around subexpressions with nonzero explicit submatch index. -Therefore RE and IRE are equivalent representations. -\\ - -%\iffalse -%Below is an example of IRE construction for RE $(\epsilon|a^{0,\infty})(\epsilon|a)^{0,\infty} )$ -%(the resulting IRE can be seen on figure \ref{fig_parse_trees}): -% -% \begin{align*} -% &\begin{aligned} -% & mark ( (\epsilon|a^{0,\infty})(\epsilon|a)^{0,\infty} ) ) = \big[ \\ -% % -% & \quad mark ( (\epsilon|a^{0,\infty}) ) = \big[ \\ -% & \quad mark ( \epsilon|a^{0,\infty} ) = \big[ \\ -% & \quad\quad\quad mark ( \epsilon ) = (0,0,\epsilon), \\ -% & \quad\quad\quad mark ( a^{0,\infty} ) = \big[ \\ -% & \quad\quad\quad\quad mark ( a ) = (0,0,a) \\ -% & \quad\quad\quad \big] = (0,0,(0,0,a)^{0,\infty}) \\ -% & \quad\quad \big] = (0,0,(0,0,\epsilon) \mid (0,0,(0,0,a)^{0,\infty})) \\ -% & \quad \big] = (1,1,(0,0,\epsilon)|(0,0,(0,0,a)^{0,\infty})) \\ -% % -% & \quad mark ( (\epsilon|a)^{0,\infty} ) = \big[ \\ -% & \quad\quad mark ( (\epsilon|a) ) = \big[ \\ -% & \quad\quad\quad mark ( \epsilon|a ) = \big [ \\ -% & \quad\quad\quad\quad mark ( \epsilon ) = (0,0,\epsilon) \\ -% & \quad\quad\quad\quad mark ( a ) = (0,0,a) \\ -% & \quad\quad\quad \big] = (0,0,(0,0,\epsilon)|(0,0,a)) \\ -% & \quad\quad \big] = (1,1,(0,0,\epsilon) \mid (0,0,a)) \\ -% & \quad \big] = (1,0,(1,1,(0,0,\epsilon) \mid (0,0,a))^{0,\infty}) \\ -% % -% & \big] = (1,1, -% (1,1,(0,0,\epsilon) \mid (0,0,(0,0,a)^{0,\infty})) \\ -% & \quad\quad\quad \cdot (1,0,(1,1,(0,0,\epsilon) \mid (0,0,a))^{0,\infty}) -% ) -% \end{aligned} -% % -% &&\begin{aligned} -% & enum (1,1,(1,1, -% (1,1,(0,0,\epsilon) \mid (0,0,(0,0,a)^{0,\infty})) \\ -% & \quad\quad\quad\quad\quad \cdot (1,0,(1,1,(0,0,\epsilon) \mid (0,0,a))^{0,\infty}))) = \big[ \\ -% & \quad enum (2,2,(1,1,(0,0,\epsilon) \mid (0,0,(0,0,a)^{0,\infty}))) = \big[ \\ -% & \quad\quad enum (3,3,(0,0,\epsilon)) = (3,3,(0,0,\epsilon)) \\ -% & \quad\quad enum (3,3,(0,0,(0,0,a)^{0,\infty})) = \big[ \\ -% & \quad\quad\quad enum (3,3,(0,0,a)) = (3,3,(0,0,a)) \\ -% & \quad\quad \big] = (3,3,(0,0,(0,0,a)^{0,\infty})) \\ -% & \quad \big] = (3,3,(2,2,(0,0,\epsilon) \mid (0,0,(0,0,a)^{0,\infty}))) \\ -% % -% & \quad enum (3,3, (1,0,(1,1,(0,0,\epsilon) \mid (0,0,a))^{0,\infty}) ) = \big[ \\ -% & \quad\quad enum (4,3, (1,1,(0,0,\epsilon) \mid (0,0,a)) ) = \big[ \\ -% & \quad\quad\quad enum (5,4, (0,0,\epsilon) ) = (0,0,\epsilon) \\ -% & \quad\quad\quad enum (5,4, (0,0,a) ) = (0,0,a) \\ -% & \quad\quad \big] = (5,4,(4,3,(0,0,\epsilon) \mid (0,0,a))) \\ -% & \quad \big] = (5,4,(3,0,(4,3,(0,0,\epsilon) \mid (0,0,a))^{0,\infty})) \\ -% % -% & \big] = (5,4,(1,1, -% (2,2,(0,0,\epsilon) \mid (0,0,(0,0,a)^{0,\infty})) \\ -% & \quad\quad\quad\quad\quad \cdot (3,0,(4,3,(0,0,\epsilon) \mid (0,0,a))^{0,\infty}) -% )) -% \end{aligned} -% \end{align*} -%\fi - -\begin{figure}\label{fig_mark_enum} -\includegraphics[width=\linewidth]{img/mark_enum.pdf} -\caption{ -An example of constructing IRE for RE $(\epsilon|a^{0,\infty})(a|\epsilon)^{0,3}$ using $mark$ and $enum$\\ -and some examples of IPT for the resulting IRE and string ``$a$''. -S-norm of each subtree is marked with $\#$. -} -\end{figure} - Just like REs denote sets of PTs, IREs denote sets of \emph{IPTs} --- \emph{indexed parse trees}. The only difference between PTs and IPTs is that each node of an IPT has an associated number --- the implicit submatch index inherited from the corresponding IRE node (denoted with a superscript). @@ -507,8 +434,6 @@ and $\IPT(r, w) = \{ t \in \IPT(r) \mid str(t) = w \}$ is the set of all IPTs fo % Examples of IPTs can be seen on figure \ref{fig_mark_enum}. -\FloatBarrier - \begin{Xdef} \emph{Indexed parse trees (IPT)} over finite alphabet $\Sigma$, denoted $\XIT_\Sigma$, are: \begin{enumerate} @@ -558,6 +483,8 @@ just the relevant parts of them. IPTs have two definitions of norm, one for $Pos$ and one for $Sub$, which we call \emph{p-norm} and \emph{s-norm} respectively: +\FloatBarrier + \begin{Xdef}\label{tnorm_of_IPTs} The \emph{p-norm} and \emph{s-norm} of an IPT $t$ at position $p$ are: \begin{align*} @@ -634,6 +561,15 @@ $\IPT_{min}(r,w) = \{ t \in \IPT(r,w) \mid \forall u \in \IPT(r,w) : t \sim u \v S-order $\prec$ is a strict weak order on IPTs. \end{XThe} +\begin{figure}\label{fig_mark_enum} +\includegraphics[width=\linewidth]{img/mark_enum.pdf} +\caption{ +An example of constructing IRE for RE $(\epsilon|a^{0,\infty})(a|\epsilon)^{0,3}$ using $mark$ and $enum$\\ +and some examples of IPT for the resulting IRE and string ``$a$''. +S-norm of each subtree is marked with $\#$. +} +\end{figure} + What is the relation between the total p-order $<$ and the partial s-order $\prec$ on IPTs? Can we say that p-order is an extension of s-order on non-comparable IPTs? We show by the means of a counterexample that the answer to the above question is negative. @@ -662,6 +598,7 @@ it will only add more details. In the rest of the paper the words ``order'' and ``norm`` refer to s-order and s-norm. +\FloatBarrier \section{Parenthesized expressions} -- 2.40.0