Perl 的正则表达式实现如何使用尝试？
How does Perl's regex implementation makes use of tries?
我正在探索优化基于堆栈的回溯正则表达式实现的方法（另请参阅 this thread). In the comments a hint about Perl's regex matcher was given. From the source code 我已经发现它在将正则表达式与多个备选方案匹配时会使用尝试。
例如，像 /(?:foo|bar|baz|foobar)$/ 这样的正则表达式通常会产生像
这样的程序
BRANCH
EXACT <foo>
BRANCH
EXACT <bar>
BRANCH
EXACT <baz>
BRANCH
EXACT <foobar>
EOL
而使用 trie 的优化版本看起来有点像
TRIE-EXACT
<foo>
<bar>
<baz>
<foobar>
EOL
四个带有 EXACT 命令的分支都被优化为一个 TRIE 命令。
但是，我不明白这个 trie 在回溯的执行阶段是如何使用的。
考虑未优化的代码和输入字符串 foobar。当尝试匹配正则表达式时，第一个分支 foo 将成功匹配， $ 将失败，下一个分支 bar 和 baz 将失败，最后一个分支 foobar匹配，$匹配，匹配成功。
现在如何使用 trie 进行匹配？根据我的理解，特里树只有一个合理的隐含顺序，其中尝试重叠条目，即最长的匹配优先。这将在上述示例中给出正确的匹配。
但是它会为 /(?:foo|foobar)barr$/ 和输入 foobarr 给出错误的结果。 trie 将匹配 foobar，但在接下来的 r 上失败，因为它期望下一个 b。所以不仅要有一种回溯的方法，而且还必须以某种方式保留分支的原始顺序，否则优化后的程序将在语义上与未优化的版本不同。
Perl 实现如何处理这种基于树的匹配？
您可以使用 re pragma 获取一些信息，以显示 perl 如何编译和使用正则表达式。例如：
$ perl -Mre=debugcolor -e '"foobarr" =~ /(?:foobar|foo)barr$/'
给出输出：
所以很明显，它把regex编译成了三个操作：
- 匹配
foo的EXACT操作（这是交替(?:foobar|foo)的公共前缀，后跟
- 一个
TRIE-EXACT操作匹配bar或空串，然后
- 一个
EXACT操作匹配barr.
然后在匹配中使用编译后的正则表达式：
- 首先
foo 匹配的 EXACT 匹配，然后
TRIE-EXACT 尝试匹配的第一个备选 bar，然后 EXACT 操作在 r 与 barr、- 引擎回溯并尝试
TRIE-EXACT 操作中的第二个单词，它匹配空字符串
- 最后一个
EXACT 操作匹配 barr。
目前这并没有回答您关于基于 trie 的匹配究竟是如何实现的问题，但我打算进一步调查！另请参阅 perldoc perlreguts 了解更多信息。
编辑：有关如何实现 trie 匹配的更多信息，请参见 regexec.c 行 #5931:
[...] the basic plan of execution of the trie is: At the beginning,
run through all the states, and find the longest-matching word. Also
remember the position of the shortest matching word. For example, this
pattern:
1 2 3 4 5
ab|a|x|abcd|abc
when matched against the string "abcde", will generate accept states
for all words except 3, with the longest matching word being 4, and
the shortest being 2 (with the position being after char 1 of the
string).
Then for each matching word, in word order (i.e. 1,2,4,5), we run the remainder of the pattern; on each try setting the current position
to the character following the word, returning to try the next word on
failure.
这应该可以解释基于 TRIE 的匹配如何设法进行词序交替。
我写了这段代码的原始实现。从那时起它发生了一些变化，这略微改变了 time/space 其工作方式的权衡。
首先，我要指出你的一个误区post，Perls正则表达式引擎的规则不是匹配最长的字符串，而是匹配最左边最长的字符串，特别是
"foal"=~/(f|fo|foa|foal)/
应该匹配 "f" 而不是 "foal" 因为 "f" 选项是第一个。这在代码的注释中称为 "word order" 。您可以通过将 (?{ print $& }) 注入到您的模式中来使用 Perl 看到这一点：
perl -le'my $str="foal"; $str=~/(?:f|foa|fo)(?{print $&})al/'
f
foa
fo
我认为我应该解释的另一点是代码和注释经常使用术语 "state" 和 "accepting state"。这来自于 Trie 等同于非循环 DFA 的观察，并且可以天真地表示为每个状态一行的 table，输入字母表中每个合法字符一列，并使用额外的列跟踪状态是否为 "accepting"，意思是 "ends one of the alternatives"，如果是，它终止交替的哪个分支。其他列中的值表示读取列字符后要转换到的新状态。一个接受状态可能会转换到更多状态，例如一个分支匹配另一个分支的前缀的情况。
匹配然后归结为遍历 tree/state table，当我们遇到一个接受状态时，我们将我们在 trie 中读取的字符数推入一个二元组和将与状态关联的单词编号放入列表中。最终我们要么 运行 无法读取字符串，要么遇到到 0 状态的转换，这意味着我们可以停止，因为没有进一步的匹配是可能的。
一旦你有了 (length,word) 的元组列表，你就可以按照单词的升序遍历它们，因为这样的列表通常很短，IMO 简单地使用线性探测来找到最小值是合理的每次尝试的话。 Perl 使用一种策略，预先将所有这些可能的列表预编译到一个结构中，因此它只需要跟踪最近接受状态的分支号，然后就可以（有点昂贵）从中计算任何先前的接受状态。例如下面的例子 /(f|foa|fo)al/ 产生这样的结构：
word_info N:(prev,len)= 1:(0,1) 2:(3,3) 3:(1,2)
这表明如果我们达到 "foa" 的接受状态，即分支 2，我们已经匹配了一个 3 字符的字符串，并且有一个分支 3 的先前接受状态，它又指向 1。来自这我们可以重建我们期望看到的行为，即在 "f"、"foa" 之后尝试 "al"，然后 "fo"。与其他解决方案相比，该过程有些昂贵 (N**2)，但具有预编译和可重用的优势，并且存储要求非常适合正则表达式回溯引擎的工作方式。 IMO 没关系，主要问题是你以某种方式跟踪遇到它们时你在字符串中的接受状态，然后以正确的顺序尝试 "tail"。
您可以在扩展调试中看到其中的大部分内容：
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 等价和单词数据，以及 table 是如何构造的。因为只有 3 个合法字符，我们构建了一个有 4 列的 table，每个合法字符一列，并且跟踪状态是否正在接受，如果是，则它接受交替的哪个分支。第 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
这显示原始 table 表示被打包成压缩形式，允许一行中的零转换用于存储其他行中的非零转换。每个转换都存储在一个 [owner-state,transition] 的二元组数组中，有两个侧数组，一个存储给定状态的开始位置，另一个存储给定状态的接受映射，状态转换涉及检查 table[start_offset[state]+column_ofs].owner_state 是否与 state 相同，如果不相同则 table[start_offset[state]+column_ofs].new_state可以假设为0，详见红龙
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 中 "remove" 把它变成前缀， EXACT ，后跟包含空字符串、字母 "oa" 和字母 "o" 的特里树。 S:2/4 意味着我们从状态 2 开始，而不是从正常状态 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 开始。每条 "Accepted" 行表示我们找到了一个可能的匹配项。最后一行显示我们正在读取一个不在我们字母表中的字符，这意味着转换到状态 0，这意味着我们可以停止。不幸的是，这并没有显示与每个匹配相关的单词编号，但是您可以从状态转换 table 中推断出它们：1,3,2，但我们需要 "try" 它们 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
我正在探索优化基于堆栈的回溯正则表达式实现的方法（另请参阅 this thread). In the comments a hint about Perl's regex matcher was given. From the source code 我已经发现它在将正则表达式与多个备选方案匹配时会使用尝试。
例如，像 /(?:foo|bar|baz|foobar)$/ 这样的正则表达式通常会产生像
BRANCH
EXACT <foo>
BRANCH
EXACT <bar>
BRANCH
EXACT <baz>
BRANCH
EXACT <foobar>
EOL
而使用 trie 的优化版本看起来有点像
TRIE-EXACT
<foo>
<bar>
<baz>
<foobar>
EOL
四个带有 EXACT 命令的分支都被优化为一个 TRIE 命令。
但是，我不明白这个 trie 在回溯的执行阶段是如何使用的。
考虑未优化的代码和输入字符串 foobar。当尝试匹配正则表达式时，第一个分支 foo 将成功匹配， $ 将失败，下一个分支 bar 和 baz 将失败，最后一个分支 foobar匹配，$匹配，匹配成功。
现在如何使用 trie 进行匹配？根据我的理解，特里树只有一个合理的隐含顺序，其中尝试重叠条目，即最长的匹配优先。这将在上述示例中给出正确的匹配。
但是它会为 /(?:foo|foobar)barr$/ 和输入 foobarr 给出错误的结果。 trie 将匹配 foobar，但在接下来的 r 上失败，因为它期望下一个 b。所以不仅要有一种回溯的方法，而且还必须以某种方式保留分支的原始顺序，否则优化后的程序将在语义上与未优化的版本不同。
Perl 实现如何处理这种基于树的匹配？
您可以使用 re pragma 获取一些信息，以显示 perl 如何编译和使用正则表达式。例如：
$ perl -Mre=debugcolor -e '"foobarr" =~ /(?:foobar|foo)barr$/'
给出输出：
所以很明显，它把regex编译成了三个操作：
- 匹配
foo的EXACT操作（这是交替(?:foobar|foo)的公共前缀，后跟 - 一个
TRIE-EXACT操作匹配bar或空串，然后 - 一个
EXACT操作匹配barr.
然后在匹配中使用编译后的正则表达式：
- 首先
foo匹配的EXACT匹配，然后 TRIE-EXACT尝试匹配的第一个备选bar，然后EXACT操作在r与barr、 匹配时失败
- 引擎回溯并尝试
TRIE-EXACT操作中的第二个单词，它匹配空字符串 - 最后一个
EXACT操作匹配barr。
目前这并没有回答您关于基于 trie 的匹配究竟是如何实现的问题，但我打算进一步调查！另请参阅 perldoc perlreguts 了解更多信息。
编辑：有关如何实现 trie 匹配的更多信息，请参见 regexec.c 行 #5931:
[...] the basic plan of execution of the trie is: At the beginning, run through all the states, and find the longest-matching word. Also remember the position of the shortest matching word. For example, this pattern:
1 2 3 4 5 ab|a|x|abcd|abcwhen matched against the string "abcde", will generate accept states for all words except 3, with the longest matching word being 4, and the shortest being 2 (with the position being after char 1 of the string).
Then for each matching word, in word order (i.e. 1,2,4,5), we run the remainder of the pattern; on each try setting the current position to the character following the word, returning to try the next word on failure.
这应该可以解释基于 TRIE 的匹配如何设法进行词序交替。
我写了这段代码的原始实现。从那时起它发生了一些变化，这略微改变了 time/space 其工作方式的权衡。
首先，我要指出你的一个误区post，Perls正则表达式引擎的规则不是匹配最长的字符串，而是匹配最左边最长的字符串，特别是
"foal"=~/(f|fo|foa|foal)/
应该匹配 "f" 而不是 "foal" 因为 "f" 选项是第一个。这在代码的注释中称为 "word order" 。您可以通过将 (?{ print $& }) 注入到您的模式中来使用 Perl 看到这一点：
perl -le'my $str="foal"; $str=~/(?:f|foa|fo)(?{print $&})al/'
f
foa
fo
我认为我应该解释的另一点是代码和注释经常使用术语 "state" 和 "accepting state"。这来自于 Trie 等同于非循环 DFA 的观察，并且可以天真地表示为每个状态一行的 table，输入字母表中每个合法字符一列，并使用额外的列跟踪状态是否为 "accepting"，意思是 "ends one of the alternatives"，如果是，它终止交替的哪个分支。其他列中的值表示读取列字符后要转换到的新状态。一个接受状态可能会转换到更多状态，例如一个分支匹配另一个分支的前缀的情况。
匹配然后归结为遍历 tree/state table，当我们遇到一个接受状态时，我们将我们在 trie 中读取的字符数推入一个二元组和将与状态关联的单词编号放入列表中。最终我们要么 运行 无法读取字符串，要么遇到到 0 状态的转换，这意味着我们可以停止，因为没有进一步的匹配是可能的。
一旦你有了 (length,word) 的元组列表，你就可以按照单词的升序遍历它们，因为这样的列表通常很短，IMO 简单地使用线性探测来找到最小值是合理的每次尝试的话。 Perl 使用一种策略，预先将所有这些可能的列表预编译到一个结构中，因此它只需要跟踪最近接受状态的分支号，然后就可以（有点昂贵）从中计算任何先前的接受状态。例如下面的例子 /(f|foa|fo)al/ 产生这样的结构：
word_info N:(prev,len)= 1:(0,1) 2:(3,3) 3:(1,2)
这表明如果我们达到 "foa" 的接受状态，即分支 2，我们已经匹配了一个 3 字符的字符串，并且有一个分支 3 的先前接受状态，它又指向 1。来自这我们可以重建我们期望看到的行为，即在 "f"、"foa" 之后尝试 "al"，然后 "fo"。与其他解决方案相比，该过程有些昂贵 (N**2)，但具有预编译和可重用的优势，并且存储要求非常适合正则表达式回溯引擎的工作方式。 IMO 没关系，主要问题是你以某种方式跟踪遇到它们时你在字符串中的接受状态，然后以正确的顺序尝试 "tail"。
您可以在扩展调试中看到其中的大部分内容：
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 等价和单词数据，以及 table 是如何构造的。因为只有 3 个合法字符，我们构建了一个有 4 列的 table，每个合法字符一列，并且跟踪状态是否正在接受，如果是，则它接受交替的哪个分支。第 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
这显示原始 table 表示被打包成压缩形式，允许一行中的零转换用于存储其他行中的非零转换。每个转换都存储在一个 [owner-state,transition] 的二元组数组中，有两个侧数组，一个存储给定状态的开始位置，另一个存储给定状态的接受映射，状态转换涉及检查 table[start_offset[state]+column_ofs].owner_state 是否与 state 相同，如果不相同则 table[start_offset[state]+column_ofs].new_state可以假设为0，详见红龙
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 中 "remove" 把它变成前缀， EXACT ，后跟包含空字符串、字母 "oa" 和字母 "o" 的特里树。 S:2/4 意味着我们从状态 2 开始，而不是从正常状态 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 开始。每条 "Accepted" 行表示我们找到了一个可能的匹配项。最后一行显示我们正在读取一个不在我们字母表中的字符，这意味着转换到状态 0，这意味着我们可以停止。不幸的是，这并没有显示与每个匹配相关的单词编号，但是您可以从状态转换 table 中推断出它们：1,3,2，但我们需要 "try" 它们 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