1编码

考虑\(y =\operatorname{replaceAll} (x, e_1, e_2)\)。设\(\Sigma\)是字母表，\(\Gamma\)是\(e_1\)和\(e_2\)共同的变量集。假设\(e_1\)是带变量捕获的确定型正则表达式，\(e_2 \in L ((\Sigma \cup \Gamma)^{\ast})\)且每个变量最多出现一次（此限制可以取消，在第2节会说明）。

对\(e_1\)应用Glushkov NFA构造法得到NFA \(A_1 = (Q, F, \delta, \Sigma, q_0)\)，根据确定型正则表达式的定义，\(A_1\)实际上是DFA。此时\(A_1\)的状态集Q包含初始状态\(q_0\)以及状态\(q_i\)，\(q_i\)表示在\(e_1\)中第i次出现的字符a，令所有包含a的此次出现的变量捕获为\(\Gamma_i\)。

构造一个不确定性Streaming String Transducer(NSST)模拟这一过程。设NSST \(T = (Q', \Sigma, \Sigma, \{ \operatorname{acc} \} \cup \Gamma, E, q_0', F')\)。其中acc是用于replace过程的累积变量。\(Q'\)和parsing automata[3]基本一致，F‘定义为：\(F' (q) =\operatorname{acc}, \operatorname{iff}q = (-, \operatorname{left}, -)\)，即当且仅当停机于left状态时，T的输出是acc中累积的串。\(E \subseteq Q' \times \Sigma \times Q' \times A\)。E可以分成状态转移和变量更新两部分，其中，状态的转移和parsing automata完全一致。变量更新的方法如下：

• 若从状态\((-, \operatorname{left}, -)\)读入字符a，转移到状态\((-, \operatorname{left}, -)\)，则\(A (\operatorname{acc}) =\operatorname{acc}.a\)，对其他变量，A(x)=x。

• 若从状态\((-, \operatorname{left}, -)\)读入字符a，转移到状态\((q_i, \operatorname{long}, -)\)，则对所有\(\Gamma_i\)中的变量x，有A(x)=x.a，其他变量不变。

• 若从状态\((q_j, \operatorname{long}, -)\)读入字符a，转移到状态\((q_i, \operatorname{long}, -)\)，如果\(q_j 、q_i\)分别是某个Kleene Star的终止和起始字符（因为是确定型正则表达式，这是可以确定的），则设此Star中捕获的变量集为P，对所有\(\Gamma_i \backslash P\)中的变量x，有\(A (x) = x.a\)，对\(\Gamma_i \cap P\)中的所有变量y有\(A (y) = a\)，对\(P\backslash \Gamma_i\)中的所有变量z有\(A (z) = \varepsilon\)。如果不是，则对所有\(\Gamma_i\)中的变量x有\(A (x) = x.a\)

• 若从状态\((-, \operatorname{long}, -)\)读入字符a，转移到状态\((q_0, \operatorname{left}, -)\)，假设\(e_2 = a_1 a_2 \ldots a_n\)，其中\(a_i\)要么是字符要么是变量，则\(A (\operatorname{acc}) =\operatorname{acc}.a_1 .a_2 \ldots a_n\)，对其余的所有变量x，有\(A (x) = \varepsilon\)。

引理 1. T是functional NSST。

证明. 从语义的角度看，对于确定型的正则表达式以及一定的替换模式，replaceAll得到的串是惟一的。此外，容易发现虽然F是偏函数，但是对任何输入，T总是会有输出。因此T代表了\(\Sigma\)上的一个全函数

推论 2. T的preimage可判定

证明. 根据[2]，functional NSST和DSST[1]等价，从而和2FT等价，从而可判定。

直接的NSST判定算法尚需思考。

2限制

上面的方法主要有两点限制：确定型正则表达式以及copyless条件要求的不重复使用变量。

实际上第二个限制是可以workaround的，上面为了简洁加了限制。假设一个变量x在\(e_2\)里有多于一次的引用，比如说\(e_2 = a_1 x a_2 x \ldots a_n x a_{n + 1}\)，那么这n个对x的引用可以看成是n个不同的变量\(x_1, x_2, \ldots, x_n\)。此时，\(e_1\)中的x的捕获组可以看成是这n个变量的捕获的叠加。

具体地，在构造上述NSST的时候，当转移E将更新变量x时，换为同时更新变量\(x_1, x_2, \ldots, x_n\)，这些变量的更新方法都和原来更新x时一致。

当需要更新acc时也同理。这样，就可以容许任意的\(e_2\)。

至于DREG，有此限制的主要原因是，DREG的匹配过程是确定的，并且在每一步，都可以确定当前匹配到\(e_1\)的哪个子表达式。这和把一般的正则表达式化成DFA不一样，后者只是匹配是确定的，但不能对应到子表达式。确定当前子表达式至关重要，因为必须确定当前输入的字符属于哪些捕获组。

DREG的表达力不如REG，所以这个限制会带来一些问题。而且使用REG也会引入匹配不惟一的问题。即使限制贪婪匹配策略，也不能完全消除不确定性。

参考文献