From 184dd83e1185a2cd4f63b74e71f30f244456ad28 Mon Sep 17 00:00:00 2001 From: Ulya Trofimovich Date: Thu, 11 Oct 2018 23:38:03 +0100 Subject: [PATCH] Paper: dropped explicit submatch indices in TNFA definition. --- re2c/doc/tdfa_v2/img/tnfa.tex | 90 +++++++++++++++++-------------- re2c/doc/tdfa_v2/part_1_tnfa.tex | 92 +++++++++++++++++--------------- 2 files changed, 99 insertions(+), 83 deletions(-) diff --git a/re2c/doc/tdfa_v2/img/tnfa.tex b/re2c/doc/tdfa_v2/img/tnfa.tex index 6a8ebb00..c800a071 100644 --- a/re2c/doc/tdfa_v2/img/tnfa.tex +++ b/re2c/doc/tdfa_v2/img/tnfa.tex @@ -27,27 +27,51 @@ \tikzset{style1/.style={draw, rectangle, rounded corners = 10, minimum width = \widd, minimum height = 0.3in, xshift = \offs}} \tikzset{style2/.style={state, accepting, xshift = \offs}} +\begin{scope}[xshift=3.3in, yshift=-7.2in] + \node[draw=none, shape=rectangle] (x) {$ + \begin{aligned} + otag \big( (i, j, r) \big) = + \begin{cases} + \epsilon &\text{if } i = 0 \\[-0.5em] + 2i - 1 &\text{if } i \neq 0 + \end{cases} + \qquad\qquad + ctag \big( (i, j, r) \big) = + \begin{cases} + \epsilon &\text{if } i = 0 \\[-0.5em] + 2i &\text{if } i \neq 0 + \end{cases} + \qquad\qquad + 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{aligned} +$}; +\end{scope} + \begin{scope}[xshift=0in] \def\offs{-0.5in} \def\widd{1.3in} \node[state] (a) {$x$}; \node[state, accepting, right of=a] (b1) {$x_1$}; - \node[style1, right of = b1] (b) {$F \big( (0, 0, r) \big)$}; + \node[style1, right of = b1] (b) {$F \big( (0, 0, r_1) \big)$}; \node[style2, right of = b] (b2) {$y_1$}; \node[state, accepting, right of=b2] (d) {$y$}; \path - (a) edge node {$\epsilon / otag(r)$} (b1) - (b2) edge node {$\epsilon / ctag(r)$} (d) + (a) edge node {$1 / otag(r) $} (b1) + (b2) edge node {$1 / ctag(r) $} (d) ; \path (a) edge [draw=none] node [below=0.15in, midway] { $\begin{aligned} - F \big( (i, j, r) \big) \mid i \neq 0 &= (\Sigma, Q, x, \{y\}, \Delta) \\ + F \big( r \big) \mid_{r \;=\; (i, \Xund, r_1) \;\wedge\; i \;\neq\; 0} &= (\Sigma, Q, x, \{y\}, \Delta) \\ \text{where } - F \big( (0, 0, r) \big) &= (\Sigma, Q_1, x_1, \{y_1\}, \Delta_1) \\ + F \big( (0, 0, r_1) \big) &= (\Sigma, Q_1, x_1, \{y_1\}, \Delta_1) \\ Q &= Q_1 \cup \{ x, y \}\\ \Delta &= \Delta_1 \cup - \big\{ (x, \epsilon, otag(r), x_1), (y_1, \epsilon, ctag(r), y) \big\} + \big\{ (x, 1, otag(r), x_1), (y_1, 1, ctag(r), y) \big\} \end{aligned}$ } (d); \end{scope} @@ -55,14 +79,14 @@ \begin{scope}[xshift=0.5in, yshift=-1.4in] \node[state] (a) {$x$}; \node[state, accepting, right of=a] (b) {$y$}; - \path (a) edge node {$\epsilon / \epsilon$} (b); + \path (a) edge node {$1 / \epsilon$} (b); \path (a) edge [draw=none] node [below=0.15in, midway] { $F \big( (0, 0, \epsilon) \big) = \big( \Sigma, \{x, y\}, x, \{y\}, - \{ (x, \epsilon, \epsilon, y) \} + \{ (x, 1, \epsilon, y) \} \big)$ } (b); \end{scope} @@ -115,10 +139,10 @@ % \node[draw, rectangle, rounded corners = 6, minimum width = 0.17in, minimum height = 0.67in, right of = b, xshift = \offs, yshift = -0.25in] (ab) {}; \node[state, accepting] (d) [below right of = b2, yshift = 0.4in] {$y$}; \path - (a) edge [bend left] node {$\epsilon / \epsilon$} (b1) - (a) edge [bend right] node [below left] {$\epsilon / ntag(r_1) $} (c1) - (b2) edge [bend left] node {$\epsilon / ntag(r_2) $} (d) - (c2) edge [bend right] node [below right] {$\epsilon / \epsilon$} (d) + (a) edge [bend left] node {$1 / \epsilon$} (b1) + (a) edge [bend right] node [below left] {$2 / ntag(r_1) $} (c1) + (b2) edge [bend left] node {$1 / ntag(r_2) $} (d) + (c2) edge [bend right] node [below right] {$1 / \epsilon$} (d) ; % \path (a) edge [draw=none] node [below=0.6in, midway] {$F \big( (0, 0, (i_1, j_1, r_1) \mid (i_2, j_2, r_2)) \big)$} (d); \path (a) edge [draw=none] node [below=0.6in, midway] { @@ -128,8 +152,8 @@ F(r_i) &= (\Sigma, Q_i, x_i, \{y_i\}, \Delta_i) \; \forall i = \overline{1,2} \\ Q &= Q_1 \cup Q_2 \cup \{ x, y \} \\ \Delta &= \Delta_1 \cup \Delta_2 \cup - \big\{ (x, \epsilon, \epsilon, x_1), (y_2, \epsilon, \epsilon, y), \\ - & (y_1, \epsilon, ntag(r_2), y), (x, \epsilon, ntag(r_1), x_2) + \big\{ (x, 1, \epsilon, x_1), (y_2, 1, \epsilon, y), \\ + & (y_1, 1, ntag(r_2), y), (x, 2, ntag(r_1), x_2) \big\} \end{aligned}$} (d); \end{scope} @@ -145,7 +169,7 @@ \node[style2, right of = b, xshift = 0.4in] (b2) {}; \path (a1) edge [draw=none] node [below=0.25in, midway] { $\begin{aligned} - F \big( (0, 0, r^{n, m}) \big) \mid n > 1 &= F \big( (0, 0, r \cdot (0, 0, r^{n-1, m-1})) \big) + F \big( (0, 0, r^{n, m}) \big) \mid_{n \;>\; 1} &= F \big( (0, 0, r \cdot (0, 0, r^{n-1, m-1})) \big) \end{aligned}$} (b2); \end{scope} @@ -161,9 +185,9 @@ \node[style2, right of = b] (b2) {$y_1$}; \path - (a) edge node {$\epsilon / \epsilon$} (b1) + (a) edge node {$1 / \epsilon$} (b1) ; - \draw (a) .. controls ($ (a) + (0, 1.5) $) and ($ (b2) + (-1, 1) $) .. node [above] {$\epsilon / ntag(r)$} (b2); + \draw (a) .. controls ($ (a) + (0, 1.5) $) and ($ (b2) + (-1, 1) $) .. node [above] {$2 / ntag(r)$} (b2); \path (a) edge [draw=none] node [below=0.3in, midway] { $\begin{aligned} F \big( (0, 0, r^{0, m}) \big) &= (\Sigma, Q, x, \{y_1\}, \Delta) \\ @@ -171,7 +195,7 @@ F \big( (0, 0, r^{1, m}) \big) &= (\Sigma, Q_1, x_1, \{y_1\}, \Delta_1) \\ Q &= Q_1 \cup \{ x \} \\ \Delta &= \Delta_1 \cup - \big\{ (x, \epsilon, \epsilon, x_1), (x, \epsilon, ntag(r), y_1) \big\} + \big\{ (x, 1, \epsilon, x_1), (x, 2, ntag(r), y_1) \big\} \end{aligned}$} (b2); \end{scope} @@ -187,9 +211,9 @@ \node[state, accepting, right of = b2] (c) {$y$}; \path - (b2) edge node {$\epsilon / \epsilon$} (c) + (b2) edge node {$1 / \epsilon$} (c) ; - \draw (b2) .. controls ($ (b2) + (1, 1.5) $) and ($ (b1) + (-1, 1.5) $) .. node [above] {$\epsilon / \epsilon$} (b1); + \draw (b2) .. controls ($ (b2) + (1, 1.5) $) and ($ (b1) + (-1, 1.5) $) .. node [above] {$2 / \epsilon$} (b1); \path (b1) edge [draw=none] node [below=0.3in, midway] { $\begin{aligned} F \big( (0, 0, r^{1, \infty}) \big) &= (\Sigma, Q, x_1, \{y\}, \Delta) \\ @@ -197,7 +221,7 @@ F(r) &= (\Sigma, Q_1, x_1, \{y_1\}, \Delta_1) \\ Q &= Q_1 \cup \{ y \} \\ \Delta &= \Delta_1 \cup - \big\{ (y_1, \epsilon, \epsilon, x_1), (y_1, \epsilon, \epsilon, y) \big\} + \big\{ (y_1, 2, \epsilon, x_1), (y_1, 1, \epsilon, y) \big\} \end{aligned}$} (c); \end{scope} @@ -221,12 +245,12 @@ \node[style2, right of = d] (d2) {$y_m$}; \path - (c2) edge node {$\epsilon / \epsilon$} (cd) - (cd) edge node {$\epsilon / \epsilon$} (d1) - (b2) edge node {$\epsilon / \epsilon$} (c1) + (c2) edge node {$2 / \epsilon$} (cd) + (cd) edge node {$2 / \epsilon$} (d1) + (b2) edge node {$2 / \epsilon$} (c1) ; - \draw (b2) .. controls ($ (b2) + (0, 2) $) and ($ (d2) + (-2, 2) $) .. node [very near start] {$\epsilon / \epsilon$} (d2); - \draw (c2) .. controls ($ (c2) + (0, 1) $) and ($ (d2) + (-2, 1) $) .. node [very near start] {$\epsilon / \epsilon$} (d2); + \draw (b2) .. controls ($ (b2) + (0, 2) $) and ($ (d2) + (-2, 2) $) .. node [very near start] {$1 / \epsilon$} (d2); + \draw (c2) .. controls ($ (c2) + (0, 1) $) and ($ (d2) + (-2, 1) $) .. node [very near start] {$1 / \epsilon$} (d2); \path (b1) edge [draw=none] node [below=0.3in, midway] { $\begin{aligned} F \big( (0, 0, r^{1, m}) \big) \mid m \neq \infty &= (\Sigma, Q, x_1, \{y_m\}, \Delta) \\ @@ -234,25 +258,13 @@ f_i &= F(r) = (\Sigma, Q_i, \{y_i\}, x_i, \Delta_i) \; \forall i = \overline{1, m} \\ Q &= Q_1 \cup \hdots \cup Q_m \\ \Delta &= \Delta_1 \cup \hdots \cup \Delta_m - \cup \big\{ (y_i, \epsilon, \epsilon, x_{i+1}), (y_i, \epsilon, \epsilon, y_m) \big\}_{i=1}^{m-1} + \cup \big\{ (y_i, 2, \epsilon, x_{i+1}), (y_i, 1, \epsilon, y_m) \big\}_{i=1}^{m-1} \end{aligned}$} (d2); \end{scope} \end{tikzpicture} -\iffalse - \begin{align*} - \\ - \\ - F \big( (0, 0, r^{n, m}) \big) \mid n > 1 &= F \big( (0, 0, r \cdot r^{n - 1, m - 1}) - \\ - \\ - \\ - \\ - \end{align*} -\fi - \end{document} diff --git a/re2c/doc/tdfa_v2/part_1_tnfa.tex b/re2c/doc/tdfa_v2/part_1_tnfa.tex index fddebbb5..dd4faccd 100644 --- a/re2c/doc/tdfa_v2/part_1_tnfa.tex +++ b/re2c/doc/tdfa_v2/part_1_tnfa.tex @@ -781,45 +781,55 @@ dotted paths correspond to frames and the table entry is in bold. is a structure $(\Sigma, Q, F, q_0, \Delta)$, where: \begin{itemize} \item[] $\Sigma$ is a finite set of symbols (\emph{alphabet}) -% \item[] $T$ is a finite set of \emph{tags} -% \item[] $P$ is a finite set of \emph{priorities} \item[] $Q$ is a finite set of \emph{states} \item[] $F \subseteq Q$ is the set of \emph{final} states \item[] $q_0 \in Q$ is the \emph{initial} state +% \item[] $T \subseteq \YN$ is a finite set of \emph{tags} +% \item[] $P \subseteq \YN$ is a finite set of \emph{priorities} + \item[] $\Delta = \Delta^\Sigma \sqcup \Delta^\epsilon$ is the \emph{transition} relation, where: \begin{itemize} - \item[] $\Delta^\Sigma \subseteq Q \times \Sigma \times \{\epsilon\} \times Q$ - \item[] $\Delta^\epsilon \subseteq Q \times \{\epsilon\} \times \big( (\YZ \times \YZ) \cup \{\epsilon\} \big) \times Q$ + \item[] $\Delta^\Sigma \subseteq Q \times \Sigma \times \{\epsilon\} \times Q$ (transitions on symbols) + \item[] $\Delta^\epsilon \subseteq Q \times \YN \times \big( \YN \cup \{\epsilon\} \big) \times Q$ ($\epsilon$-transitions) \end{itemize} -% and all $\epsilon$-transitions from the same state have different priorities: -% $\forall (x, r, \epsilon, y), (\widetilde{x}, \widetilde{r}, \epsilon, \widetilde{y}) \in \Delta^\epsilon: -% x = \widetilde{x} \wedge y = \widetilde{y} \Rightarrow r \!\neq\! \widetilde{r}$. + and the property that all $\epsilon$-transitions from the same state have different priority: + $\forall (q, n, \Xund, \Xund), (q, m, \Xund, \Xund) \in \Delta^\epsilon: n \neq m$. \end{itemize} \end{Xdef} TNFA construction is given by the $F$ function defined on figure \ref{fig_tnfa}. - \begin{align*} - otag \big( (i, j, r) \big) &= - \begin{cases} - \epsilon &\text{if } i = 0 \\[-0.5em] - (2i - 1, 2j - 1) &\text{if } i \neq 0 - \end{cases} - \\ - ctag \big( (i, j, r) \big) &= - \begin{cases} - \epsilon &\text{if } i = 0 \\[-0.5em] - (2i, 2j) \hphantom{{} - 1 {} - 1} &\text{if } i \neq 0 - \end{cases} - \\ - ntag \big( (i, j, r) \big) &= - \begin{cases} - \epsilon &\text{if } i = 0 \\[-0.5em] - (1 - 2i, 1 - 2j) &\text{if } i \neq 0 - \end{cases} - \end{align*} +\begin{figure}\label{fig_tnfa} +\includegraphics[width=\linewidth]{img/tnfa.pdf} +\caption{ +TNFA construction. +} +\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 } @@ -858,13 +868,7 @@ TNFA construction is given by the $F$ function defined on figure \ref{fig_tnfa}. % \cup \{ (y_i, \epsilon, \epsilon, x_{i+1}), (y_i, \epsilon, \epsilon, y_m) \}_{i=1}^{m-1} % \\ % \end{align*} - -\begin{figure}\label{fig_tnfa} -\includegraphics[width=\linewidth]{img/tnfa.pdf} -\caption{ -TNFA construction. -} -\end{figure} +\fi @@ -876,15 +880,15 @@ TNFA construction. \begin{algorithm}[H] \DontPrintSemicolon \SetKwProg{Fn}{}{}{} \SetAlgoInsideSkip{medskip} \Fn {$\underline{match (\XN, \alpha_1 \dots \alpha_n)} \smallskip$} { - $(\Sigma, T, P, Q, F, q_0, T, \Delta) = \XN$ \; + $(\Sigma, Q, F, q_0, T, \Delta) = \XN$ \; $X = closure(\{ (\bot, q_0, \epsilon, t_0) \}, F, \Delta)$ \; - $(X, B, D) = step(0, X, B, D)$ \; + $(X, B, D) = step(0, X, P_1, P_2)$ \; \BlankLine \For {$i = \overline{1,n}$} { $X = reach(X, \Delta, \alpha_i)$ \; - $X = closure(X, B, D)$ \; - $(X, B, D) = step(i, X, B, D)$ \; + $X = closure(X, Q, F, \Delta, P_1, P_2)$ \; + $(X, P_1, P_2) = step(i, X, P_1, P_2)$ \; } \BlankLine @@ -906,11 +910,11 @@ TNFA construction. \begin{algorithm}[H] \DontPrintSemicolon \SetKwProg{Fn}{}{}{} \SetAlgoInsideSkip{medskip} - \Fn {$\underline{step(k, X, B, D)} \smallskip$} { + \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$ \BlankLine - \tcc {update tag values in $X$} +% \tcc {update tag values in $X$} \For {$i = \overline {1, n}$} { $b_1 \dots b_m = u_i$ \; \lFor {$j = \overline{1, m}$} { @@ -919,17 +923,17 @@ TNFA construction. } \BlankLine - \tcc {update $B$ and $D$ matrices} +% \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, B, D)$ \; - $B' [p_i] [p_j] = h_1, \; D' [p_i] [p_j] = l$ \; - $B' [p_j] [p_i] = h_2, \; D' [p_j] [p_i] = -l$ \; + $(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$ \; } } \BlankLine - \Return $(X, B', D')$ \; + \Return $(X, P_1', P_2')$ \; } \end{algorithm} -- 2.40.0