我正在探索优化基于堆栈的回溯正则表达式实现的方法（另请参见this thread）。在评论中给出了有关Perl的正则表达式匹配器的提示。从source code中，我已经发现在将正则表达式与多个替代项匹配时，它会使用trys。
例如，像/(?:foo|bar|baz|foobar)$/这样的正则表达式通常会产生类似
BRANCH
EXACT <foo>
BRANCH
EXACT <bar>
BRANCH
EXACT <baz>
BRANCH
EXACT <foobar>
EOL
而使用特里的优化版本看起来像
TRIE-EXACT
<foo>
<bar>
<baz>
<foobar>
EOL
带有
EXACT命令的四个分支分别优化为单个TRIE命令。但是，对于回溯，我不理解在执行阶段如何使用该Trie。
考虑未优化的代码和输入字符串
foobar。尝试匹配正则表达式时，第一个分支foo将成功匹配，$将失败，下一个分支bar和baz将失败，最后一个分支foobar将匹配，$将匹配，并且匹配成功完成。现在，匹配如何与Trie一起工作？根据我的理解，特里只有一种合理的隐含顺序，其中尝试重叠的条目，即最长的匹配优先。在上述示例中，这将给出正确的匹配。
但这会给
/(?:foo|foobar)barr$/和输入foobarr提供错误的结果。特里将与foobar匹配，但在随后的r上失败，因为它期望下一个b。因此，不仅必须有一种在Trie中回溯的方法，而且必须以某种方式保留分支的原始顺序，否则优化的程序在语义上将与未优化的版本不同。Perl实现如何处理这种基于树的匹配？
最佳答案
我写了这段代码的原始实现。从那时起，它已经有所变化，这在时间/空间折衷方面略有改变。
首先，我需要在您的帖子中指出一个误解，Perls regex引擎的规则不是匹配最长的字符串，而是匹配最最长的字符串，特别是
"foal"=~/(f|fo|foa|foal)/
应该匹配“ f”而不是“ foal”，因为“ f”选项是第一个。这在代码的注释中称为“单词顺序”。通过在模式中注入（？{print $＆}），可以在Perl中看到这一点：
perl -le'my $str="foal"; $str=~/(?:f|foa|fo)(?{print $&})al/'
f
foa
fo
我认为我应该解释的另一点是，代码和注释经常使用术语“状态”和“接受状态”。这是由于观察到Trie等效于非循环DFA，并且可以简单地表示为每个状态一行的表，输入字母中每个合法字符一列，并且使用另一列来跟踪是否state是“ accepting”，意思是“结束备选方案之一”，如果是，则终止于哪个分支。其他列中的值表示读取列字符后要转换为的新状态。接受状态可能会转换为更多状态，例如在一个分支与另一个分支的前缀匹配的情况下。
然后匹配归结为遍历树/状态表，当我们遇到一个接受状态时，我们将到目前为止已在Trie中读取的字符数的2个元组和与该状态相关联的单词数按入列表。最终，我们要么用完了要读取的字符串，要么遇到了向0状态的转换，这意味着我们无法进行进一步的匹配，因此可以停止。
一旦有了（长度，单词）元组的列表，就可以按单词升序浏览它们，因为此类列表通常是较短的IMO，因此每次尝试都可以简单地使用线性探测来找到最小单词。 Perl使用一种策略，它将所有可能的列表预先预编译为一个结构，因此它只需要跟踪最近接受状态的分支号，然后就可以（以某种方式昂贵）计算任何先前的接受状态。例如，下面的示例/（f | foa | fo）al /产生如下结构：
word_info N:(prev,len)= 1:(0,1) 2:(3,3) 3:(1,2)
这表明，如果我们到达分支2的“ foa”接受状态，我们已经匹配了3个字符串，并且分支3有一个先前的接受状态，依次指向1。由此我们可以重构行为希望看到，这是在“ f”，“ foa”之后再尝试“ fo”之后尝试“ al”。与其他解决方案相比，此过程有些昂贵（N ** 2），但具有预编译和可重复使用的优点，并且存储要求与正则表达式回溯引擎的工作方式非常吻合。 IMO没关系，主要问题是遇到遇到字符串时，您以某种方式跟踪它们在字符串中的接受状态，然后以正确的顺序尝试“尾部”。
您可以在扩展调试中看到很多内容：
perl -Mre=Debug,TRIE,TRIEE,TRIEM -le'my $str="foal"; $str=~/(?:f|foa|fo)(?{print $&})al/'
Compiling REx "(?:f|foa|fo)(?{print $&})al"
Looking for TRIE'able sequences. Tail node is: EVAL
- BRANCH (1) -> EXACT <f> => EVAL (First==-1,Last==-1,Cur==1,tt==END,nt==EXACT,nnt==END)
- BRANCH (4) -> EXACT <foa> => EVAL (First==1,Last==-1,Cur==4,tt==EXACT,nt==EXACT,nnt==END)
- BRANCH (7) -> EXACT <fo> => EVAL (First==1,Last==4,Cur==7,tt==EXACT,nt==EXACT,nnt==END)
- TAIL (10) <SCAN FINISHED>
make_trie start==1, first==1, last==10, tail==11 depth=1
TRIE(NATIVE): W:3 C:6 Uq:3 Min:1 Max:3
Compiling trie using table compiler
Char : f o a
State+-------------
1 : 2 . . ( 1)
2 : . 3 . ( 1) W 1
3 : . . 4 ( 1) W 3
4 : . . . ( 0) W 2
在这里，您可以看到DFA / TRIE的对等关系和字数据，以及表格的构造方式。因为只有3个合法字符，所以我们构建了一个表，该表有4列，每个合法字符一个，并且一个用于跟踪状态是否正在接受以及是否接受状态的哪个分支。第4行上的
W 2表明它正在接受交替的第二个分支。 Alloc: 22 Orig: 13 elements, Final:3. Savings of %76.92
Statecount:5 Lasttrans:4
Char : Match Base Ofs f o a
State|-----------------------------------
# 1| @ 3 + 0[ 2 . .]
# 2| W 1 @ 3 + 1[ . 3 .]
# 3| W 3 @ 3 + 2[ . . 4]
# 4| W 2 @ 0
这显示了天真表表示形式被压缩成一种压缩形式，该形式允许将一行中的零转换用于存储其他行中的非零转换。每个转换都存储在2元组的[所有者状态，转换]数组中，带有两个侧面数组，一个侧面数组存储给定状态的开始位置，另一个侧面数组存储给定状态的接受映射，状态转换涉及检查table [start_offset [state] + column_ofs] .owner_state是否与state相同，如果不相同，则可以将table [start_offset [state] + column_ofs] .new_state假定为0。有关更多详细信息，请参见Red Dragon。
word_info N:(prev,len)= 1:(0,1) 2:(3,3) 3:(1,2)
输出的这一部分显示了我们如何预先计算长度以及每个接受状态的前身分支编号。这样，我们不必在匹配时构造一个接受状态列表，而是可以在编译时将所有可能的此类列表预先计算为一个静态结构。
Final program:
1: EXACT <f> (3)
3: TRIE-EXACT<S:2/4 W:3 L:0/2 C:6/3>[o] (11)
<>
<oa>
<o>
在这里，您会看到一个有趣的优化过程，因为所有的替换都以字母“ f”开头，我们将其从trie中“删除”，然后将其变成前缀EXACT，然后是包含空字符串的trie，字母“ oa”和字母“ o”。 S：2/4表示我们从状态2开始，而不是正常状态1，正常状态1是对应于字母“ f”的状态。这样提取'f'可以在匹配过程中的其他地方使用它，这意味着我们可以使用更便宜的机器Trie查找可能的匹配项。
11: EVAL (13)
13: EXACT <al> (15)
15: END (0)
anchored "f" at 0 floating "al" at 1..3 (checking floating) minlen 3 with eval
Guessing start of match in sv for REx "(?:f|foa|fo)(?{print $&})al" against "foal"
Found floating substr "al" at offset 2...
Found anchored substr "f" at offset 0...
较早提取的“ f”用于查找模式可以匹配的字符串中的第一个可能位置。
Guessed: match at offset 0
Matching REx "(?:f|foa|fo)(?{print $&})al" against "foal"
0 <> <foal> | 1:EXACT <f>(3)
1 <f> <oal> | 3:TRIE-EXACT<S:2/4 W:3 L:0/2 C:6/3>[o](11)
1 <f> <oal> | State: 2 Accepted: Y Charid: 2 CP: 6f After State: 3
2 <fo> <al> | State: 3 Accepted: Y Charid: 3 CP: 61 After State: 4
3 <foa> <l> | State: 4 Accepted: Y Charid: 0 CP: 0 After State: 0
在这里，我们可以看到从状态2开始的遍历树。每条“已接受”行表示我们已找到可能的匹配项。最后一行显示我们读取的字符不是字母，这意味着过渡到状态0，这意味着我们可以停止。不幸的是，这没有显示与每个匹配项相关的单词号，但是您可以从状态转换表中推断出它们：1,3,2，但是我们需要“尝试”它们1,2,3。
got 3 possible matches
TRIE matched word #1, continuing
1 <f> <oal> | 11: EVAL(13)
f
1 <f> <oal> | 13: EXACT <al>(15)
failed...
TRIE matched word #2, continuing
3 <foa> <l> | 11: EVAL(13)
foa
3 <foa> <l> | 13: EXACT <al>(15)
failed...
TRIE matched word #3, continuing
only one match left, short-circuiting: #3 <o>
2 <fo> <al> | 11:EVAL(13)
fo
2 <fo> <al> | 13:EXACT <al>(15)
4 <foal> <> | 15:END(0)
Match successful!
请注意，可以在以下位置找到有关Trie编译过程不同方面的说明：
https://perl5.git.perl.org/perl.git/blob/HEAD:/regcomp.c#l2407
https://perl5.git.perl.org/perl.git/blob/HEAD:/regcomp.c#l4726
关于regex - Perl的正则表达式实现如何利用尝试？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/57439675/