|
y=replaceAll(x,e,e')，其中e是带捕获的正规表达式，e'是常量和引用组成的串。
先把\m形式的引用换成变量形式，方便后续变换。删除所有冗余的引用。
将e变换为等价的析取范式\(b_1 + b_2 + \cdots + b_n\)，令\(\Gamma_i\)是\(b_i\)中的变量集合。因为过程中变量可能会换名，相应的在e'里也做同样的换名。
最后构造一个等价的2FT：
首先按照和2018paper相同的思路，构造一个parsing automata A。不太一样的是，在进入long状态时，需要不确定地从n个析取支里选择一个b。然后将其改造为FT（left状态下转移输出和输入一样， long状态下的转移输出空），并且在一次最左最长匹配结束并返回left状态之前，插入一些状态完成输出。其行为大概是：
将读写头转向，对b的逆执行最长最左匹配，返回匹配串的开头
如果e'是空，执行b的最长最左匹配，期间不输出，然后返回left
如果e'是xe”。如果其中x是变量，且x在\(\Gamma\)里，则执行b的匹配，并输出x匹配的部分。否则，不输出。e'=e”, 转1。如果x是常量，借助一个临时状态，输出x，读写头不变。e'=e”, 转2。
简单来说就是对匹配串反复扫描，每次处理一个引用。
关于「输出x匹配的部分」如何实现：
因为e只带捕获，不带引用，所以其析取支b必然可以化成是\(v_1 v_2 \ldots v_n\)的形式，其中，捕获必然出现在顶层的v中。那么按照Thompson构造法构造出来的\(\varepsilon -\operatorname{NFA}\)中，x的捕获和其他部分是由\(\varepsilon\)转移隔开的。将其转换为parsing automata，再转换为FT，令x对应的部分有输出，其余转移均无输出，就可以实现只输出x匹配的部分。将这样的FT记作\(T_x\)
关于如何多次执行最长最左匹配：
因为每次读写头复位，接下来执行的操作都可能是不一样的（取决于e')，所以，匹配的方法虽然是一样的，但是得用不同的状态表示。如果e'的长度是p，则最多得有p组状态用于b逆和b的匹配，可以给他们标记为\(\operatorname{long}_i\)和\(\operatorname{long}^R_i\)以示区别。匹配的方法和原来的long是一样的，也要存下各线程的状态。
第i次扫描时，首先从\(\operatorname{long}^R_i\)开始往回匹配\(b^R\)，当执行到终止状态时，可以选择猜测匹配结束，也可以继续匹配。如果猜匹配结束，则按照e'的第i个元素的情况讨论。如果是常数x，就转移到新状态\(q_{i -\operatorname{tmp}}\)并输出x，然后从\(q_{i -\operatorname{tmp}}\)空转移到\(\operatorname{long}_i\)。如果是变量x，则转移到\(T_x\)。
当第p次扫描结束时，跳转到left。
因为parsing automata本身会记录线程，所以b的非最长最左匹配最后总是无法终止的，因此只用考虑已经找到最长最左匹配情况下的正确性。这种情况下，从匹配串尾往回最长匹配b逆，读写头最终必然停在匹配串开始处，而每次最长匹配b也必然停在匹配串尾。
有一个技术问题。在\(\operatorname{long}_i\)状态下是正向匹配，可以把禁止状态集存在状态里（类似long），所以可以保证匹配是最长的；但是在\(\operatorname{long}_i^R\)状态也就是匹配b逆时，需要继续向左匹配才能保证当前的猜测是对的，不过实际上读写头之后就会转向，不可能继续向左运行。这里的逻辑可以用alternating FT表示（不过2AFT和2FT似乎不是等价的？）。
算preimage：replaceall先转换为2FT，然后算出2FA表示的preimage，2FA再转换为FA。