From b5471c4fcaf1ddd66df71d17334e5d7778c8468b Mon Sep 17 00:00:00 2001 From: Ulya Trofimovich Date: Thu, 20 Dec 2018 00:06:42 +0000 Subject: [PATCH] Paper: added two output() functions that convert t-string to parse tree and offsets. --- re2c/doc/tdfa_v2/img/tnfa_construction.tex | 14 +- re2c/doc/tdfa_v2/part_1_tnfa.tex | 180 +++++++++------------ 2 files changed, 85 insertions(+), 109 deletions(-) diff --git a/re2c/doc/tdfa_v2/img/tnfa_construction.tex b/re2c/doc/tdfa_v2/img/tnfa_construction.tex index b4223c7d..495b875f 100644 --- a/re2c/doc/tdfa_v2/img/tnfa_construction.tex +++ b/re2c/doc/tdfa_v2/img/tnfa_construction.tex @@ -204,14 +204,14 @@ \node[state] (a) {$x_0$}; \node[state, right of = a] (a1) {$x_1$}; - \node[state, right of = a1] (b1) {$x_2$}; - \node[draw=none, right of = b1, xshift=-0.5in] (b) {\large{$\dots$}}; - \node[state, accepting, right of = b, xshift=-0.5in] (b2) {$x_{2n}$}; + \node[draw=none, right of = a1, xshift=-0.5in] (b) {\large{$\dots$}}; + \node[state, right of = b, xshift=-0.5in] (b1) {$x_{2n-1}$}; + \node[state, accepting, right of = b1] (b2) {$x_{2n}$}; \path - (a) edge node {$1 / -\!(2i-1) $} (a1) - (a1) edge node {$1 / -\! 2i $} (b1) - (b1) edge node {} (b) - (b) edge node {} (b2) + (a) edge node {$1 / 1\!-\!2i $} (a1) + (a1) edge node {} (b) + (b) edge node {} (b1) + (b1) edge node {$1 / -\! 2i $} (b2) ; \node [label={[label distance=0.1in, below left]270:\large{(j)}}] (a) {}; \node [label={[label distance=0.1in, below right]270: diff --git a/re2c/doc/tdfa_v2/part_1_tnfa.tex b/re2c/doc/tdfa_v2/part_1_tnfa.tex index e8cf8d37..76cb34f5 100644 --- a/re2c/doc/tdfa_v2/part_1_tnfa.tex +++ b/re2c/doc/tdfa_v2/part_1_tnfa.tex @@ -864,7 +864,7 @@ TNFA construction is given by the $F$ function defined on figure \ref{fig_tnfa}. \Fn {$\underline{\ntag(r)} \smallskip$} { $T = \{ t_1, \dots, t_n \} = T(r), n \geq 0$ \; $Q = \{x_0, \dots, x_{2n}\}$ \; - $\Delta = \{(x_{2i},1,1\!-\!2i, x_{2i+1}), (x_i, 1, -\!2i, x_{2i+2})\}_{i=0}^{n-1}$ \; + $\Delta = \{(x_{2i-2},1,1\!-\!2t_i, x_{2i-1}), (x_{2(n-i)-1}, 1, -\!2t_i, x_{2(n - i)})\}_{i=1}^{n}$ \; \Return $(\Sigma, Q, T, \Delta, x_0, x_{2n})$ \; } \end{algorithm} @@ -900,6 +900,7 @@ TNFA construction is given by the $F$ function defined on figure \ref{fig_tnfa}. \end{figure*} + \begin{figure}\label{fig_tnfa_example} \includegraphics[width=\linewidth]{img/tnfa_example.pdf} \vspace{-2em} @@ -909,88 +910,13 @@ TNFA construction is given by the $F$ function defined on figure \ref{fig_tnfa}. \end{figure} -%\begin{figure}\label{fig_tnfa} -%\includegraphics[width=\linewidth]{img/tnfa.pdf} -%\caption{ -%TNFA construction: -%(a) -- operations of concatenation, union, closure on automata, \\ -%(b) -- subautomaton for submatch IRE, -%(c) -- subautomaton for negative tags, -%(d) -- (k) -- subautomata for non-submatch IRE, \\ -%(l) -- example TNFA for RE $(a|\epsilon)^{0,3}((a^{0,\infty})|(\epsilon))$. -%} -%\end{figure} - \FloatBarrier -% \begin{align*} -% otag \big( (i, j, r) \big) = -% \begin{cases} -% \epsilon &\text{if } i = 0 \\[-0.5em] -% 2i - 1 &\text{if } i \neq 0 -% \end{cases} -% && -% ctag \big( (i, j, r) \big) = -% \begin{cases} -% \epsilon &\text{if } i = 0 \\[-0.5em] -% 2i &\text{if } i \neq 0 -% \end{cases} -% && -% ntag \big( (i, j, r) \big) = -% \begin{cases} -% \epsilon &\text{if } i = 0 \\[-0.5em] -% 1 - 2i &\text{if } i \neq 0 -% \end{cases} -% \end{align*} - -\iffalse -% \begin{align*} -% F \big( (0, 0, r_1 \mid r_2) \big) &= (\Sigma, Q_1 \cup Q_2 \cup \{ x, y \}, x, \{y\}, \Delta) \\ -% \text{where } -% & F(r_1) = (\Sigma, Q_1, x_1, \{y_1\}, \Delta_1), \; -% F(r_2) = (\Sigma, Q_2, x_2, \{y_2\}, \Delta_2) \\ -% & \Delta = \Delta_1 \cup \Delta_2 \cup \big\{ -% (x, \epsilon, \epsilon, x_1), (y_1, \epsilon, ntag(r_2), y), -% (x, \epsilon, ntag(r_1), x_2), (y_2, \epsilon, \epsilon, y) -% \big\} -% \\ -% F \big( (0, 0, r_1 \cdot r_2) \big) &= (\Sigma, Q_1 \cup Q_2 \setminus \{ x_2 \}, x_1, \{y_2\}, \Delta) \\ -% \text{where } -% & F(r_1) = (\Sigma, Q_1, x_1, \{y_1\}, \Delta_1), \; -% F(r_2) = (\Sigma, Q_2, x_2, \{y_2\}, \Delta_2) \\ -% & \Delta = \Delta_1 \cup -% \big\{ (y_1, \alpha, \beta, z) \mid (x_2, \alpha, \beta, z) \in \Delta_2 \big\} -% \\ -% F \big( (0, 0, r^{n, m}) \big) \mid n > 1 &= F \big( (0, 0, r \cdot r^{n - 1, m - 1}) -% \\ -% F \big( (0, 0, r^{0, m}) \big) &= (\Sigma, Q_1 \cup \{ x, y \}, x, \{y\}, \Delta) \\ -% \text{where } -% & F \big( (0, 0, r^{1, m}) \big) = (\Sigma, Q_1, x_1, \{y_1\}, \Delta_1) \\ -% & \Delta = \Delta_1 \cup -% \big\{ (x, \epsilon, \epsilon, x_1), (y_1, \epsilon, ntag(r_2), y), (x, \epsilon, ntag(r), y) \big\} -% \\ -% F \big( (0, 0, r^{1, \infty}) \big) &= (\Sigma, Q_1 \cup \{ y \}, x_1, \{y\}, \Delta) \\ -% \text{where } -% & F(r) = (\Sigma, Q_1, x_1, \{y_1\}, \Delta_1) \\ -% & \Delta = \Delta_1 \cup -% \big\{ (y_1, \epsilon, \epsilon, x_1), (y_1, \epsilon, \epsilon, y) \big\} -% \\ -% F \big( (0, 0, r^{1, m}) \big) \mid m \neq \infty &= (\Sigma, Q_1 \cup \hdots \cup Q_m, x_1, \{y_m\}, \Delta) \\ -% \text{where } -% & f_i = F(r) = (\Sigma, Q_i, \{y_i\}, x_i, \Delta_i) \; \forall i = \overline{1, m} \\ -% & \Delta = \Delta_1 \cup \hdots \cup \Delta_m -% \cup \{ (y_i, \epsilon, \epsilon, x_{i+1}), (y_i, \epsilon, \epsilon, y_m) \}_{i=1}^{m-1} -% \\ -% \end{align*} -\fi - - - \begin{figure*} \begin{multicols}{2} - - \setstretch{0.85} + \setstretch{0.8} + \newcommand \ff {f\!\!f} \begin{algorithm}[H] \DontPrintSemicolon \SetKwProg{Fn}{}{}{} \SetAlgoInsideSkip{medskip} \Fn {$\underline{match (\XN, \alpha_1 \dots \alpha_n)} \smallskip$} { @@ -1006,8 +932,8 @@ TNFA construction is given by the $F$ function defined on figure \ref{fig_tnfa}. } \BlankLine - \lIf {$\exists (\Xund, p, \Xund, t) \in X \mid p \in F$} { - \Return $t$ + \If {$\exists (\Xund, p, \Xund, t) \in X \mid p \in F$} { + \Return $output(t)$ } \lElse { \Return $\bot$ } @@ -1017,36 +943,23 @@ TNFA construction is given by the $F$ function defined on figure \ref{fig_tnfa}. \begin{algorithm}[H] \DontPrintSemicolon \SetKwProg{Fn}{}{}{} \SetAlgoInsideSkip{medskip} \Fn {$\underline{reach (X, \alpha)} \smallskip$} { - \Return $\{ (q, p, \epsilon, t) \mid (\Xund, q, \Xund, t) \in X \wedge - (q, \alpha, \epsilon, p) \in \Delta^\Sigma \}$ + \Return $\{ (q, p, \epsilon, t \cdot u) \mid $ \\ + $\hspace{4em} (\Xund, q, u, t) \in X \wedge (q, \alpha, \epsilon, p) \in \Delta^\Sigma \}$ } \end{algorithm} \begin{algorithm}[H] \DontPrintSemicolon \SetKwProg{Fn}{}{}{} \SetAlgoInsideSkip{medskip} \Fn {$\underline{step(k, X, P_1, P_2)} \smallskip$} { - let $\{ x_i \}_{i=1}^{n} = \{(q_i, p_i, u_i, t_i) \}_{i=1}^{n} = X$ + $\{ x_i \}_{i=1}^{n} = \{(q_i, p_i, u_i, t_i) \}_{i=1}^{n} = X$ \; - \BlankLine -% \tcc {update tag values in $X$} - \For {$i = \overline {1, n}$} { - $b_1 \dots b_m = u_i$ \; - \For {$j = \overline{1, m}$} { - \lIf {$b_j < 0$} {$t_i[b_j] = -1$} - \lElse {$t_i[b_j] = k$} - } - } - - \BlankLine -% \tcc {update $B$ and $D$ matrices} \For {$i = \overline {1, n}$} { \For {$j = \overline {1, n}$} { $(h_1, h_2, l) = precedence (x_i, x_j, P_1, P_2)$ \; $P_1' [p_i] [p_j] = h_1, \; P_2' [p_i] [p_j] = l$ \; - $P_1' [p_j] [p_i] = h_2, \; P_2' [p_j] [p_i] = -l$ \; + $P_1' [p_j] [p_i] = h_2, \; P_2' [p_j] [p_i] = -l$ } } - \BlankLine \Return $(X, P_1', P_2')$ \; } @@ -1054,10 +967,7 @@ TNFA construction is given by the $F$ function defined on figure \ref{fig_tnfa}. \columnbreak - - \newcommand \ff {f\!\!f} - - \begin{algorithm}[H] \DontPrintSemicolon \SetKwProg{Fn}{}{}{} + \begin{algorithm}[H] \DontPrintSemicolon \SetKwProg{Fn}{}{}{} \SetAlgoInsideSkip{medskip} \Fn {$\underline {precedence (x, y, P_1, P_2)} \smallskip$} { $(q, \Xund, \gamma, \Xund) = x$, where $\gamma = a_1 \dots a_n, \; n \geq 0$ \; $(p, \Xund, \delta, \Xund) = y$, where $\delta = b_1 \dots b_m, \; m \geq 0$ \; @@ -1113,14 +1023,80 @@ TNFA construction is given by the $F$ function defined on figure \ref{fig_tnfa}. \Return $(hx, hy, l)$ } \end{algorithm} - \end{multicols} +\vspace{-2em} \begin{center} \caption{Matching algorithm.} \end{center} \end{figure*} +\begin{figure*} +\begin{multicols}{2} + \setstretch{0.8} + \newcommand \outputoffsets {out\!put \Xund o\!f\!\!f\!sets} + \newcommand \outputparsetree {out\!put \Xund parse \Xund tree} + \newcommand \parsetree {parse \Xund tree} + + \begin{algorithm}[H] \DontPrintSemicolon \SetKwProg{Fn}{}{}{} + \Fn {$\underline{\outputparsetree(s)} \smallskip$} { + \Return $\parsetree(s,1)$ + } + \end{algorithm} + + \begin{algorithm}[H] \DontPrintSemicolon \SetKwProg{Fn}{}{}{} + \Fn {$\underline{\parsetree(s, i)} \smallskip$} { + \lIf {$s = \epsilon$} { + \Return $\epsilon^i$ + } + \lIf {$s = \alpha \in \Sigma$} { + \Return $\alpha^i$ + } + $a_0 \dots a_n = s$ where $n \geq 1$ \; + $j = k = 0$ \; + \While {$k < n$} { + $k' = k$ \; + $i' = (|a_{k'}| + 1) / 2$ \; + \lWhile {$|a_{k+1}| \geq 2i'$} { + $k = k + 1$ + } + $j = j + 1$ \; + \lIf {$a_{k'} < 0$} {$t_j = \varnothing^{i'}$} + \lElse {$t_j = \parsetree (a_{k'+1} \dots a_{k-1}, i')$ } + } + \Return $T^i(t_1, \dots, t_j)$ + } + \end{algorithm} + + \columnbreak + + \begin{algorithm}[H] \DontPrintSemicolon \SetKwProg{Fn}{}{}{} + \Fn {$\underline{\outputoffsets(s)} \smallskip$} { + $a_1 \dots a_n = s$ \; + $pos = 0$ \; + \For {$i = \overline {1, n}$} { + \lIf {$a_i \in \Sigma$} { + $pos = pos + 1$ + } + \Else { + $p = pos$ \; + \lIf {$a_i < 0$} {$p = -1$} + \lIf {$a_i mod 2 \equiv 0$} {$pmatch[|a_i|/2].rm \Xund so = p$} + \lElse {$pmatch[(|a_i| - 1)/2].rm \Xund eo = p$} + } + } + \Return $pmatch$ \; + } + \end{algorithm} +\end{multicols} +\vspace{-2em} +\begin{center} +\caption{Two possible $output()$ functions.} +\end{center} +\end{figure*} + + + \clearpage \pagebreak -- 2.40.0