perlreguts - Perl 正则表达式引擎描述。
本文档试图阐明正则表达式引擎的内部机制及其工作原理。正则表达式引擎在 Perl 代码库中占了相当大的比例，但相对来说理解起来比较困难。本文档是试图解决这种情况的微薄尝试。它源于作者的经验、源代码中的注释、关于正则表达式引擎的其他论文、perl5-porters 邮件列表上的反馈，以及其他一些地方。
注意！ 应该清楚地理解，本文档中讨论的行为和结构代表了作者在撰写本文档时对引擎的理解。它不是 API 定义，它纯粹是针对那些想要修改正则表达式引擎或了解正则表达式引擎工作原理的人的内部指南。阅读本文档的读者应该详细了解 Perl 的正则表达式语法及其用法。如果您想了解 Perl 正则表达式的基础知识，请参见 perlre。如果您想用自己的引擎替换正则表达式引擎，请参见 perlreapi。
关于是否应该说“regexp”还是“regex”，存在一些争议。在本文件中，我们将使用术语“regex”，除非有特殊原因不使用，在这种情况下，我们将解释原因。
在谈论正则表达式时，我们需要区分它们的源代码形式和它们的内部形式。在本文件中，当我们谈论它们的文本形式（源代码形式）时，我们将使用术语“模式”，当我们谈论它们的内部表示时，我们将使用术语“程序”。这些对应于 Mark Jason Dominus 在其关于“Rx”的论文中使用的术语“S-regex”和“B-regex”（"REFERENCES" 中的 [1]）。
正则表达式引擎是一个程序，它接受用一种迷你语言指定的约束集，然后将这些约束应用于目标字符串，并确定该字符串是否满足这些约束。有关该语言的完整定义，请参见 perlre。
用不太宏大的术语来说，这项工作的第一个部分是将模式转换为计算机可以有效地用来在字符串中找到匹配点的形式，而第二部分是执行搜索本身。
为了做到这一点，我们需要通过解析文本生成一个程序。然后，我们需要执行该程序以找到字符串中匹配的点。并且我们需要高效地完成整个过程。
虽然这有点令人困惑，有些人反对这种术语，但值得一看多年来一直存在于 regexp.h 中的一条注释
这本质上是对非确定性有限状态机（也称为语法图表或解析技术中的“铁路正常形式”）的线性编码。
术语“铁路正规式”有点深奥，“语法图/图表”或“铁路图/图表”是更常见的术语。尽管如此，它提供了一个有用的正则表达式程序的思维模型：每个节点可以被认为是一段轨道，有一个入口和大多数情况下只有一个出口点（有一些轨道会分叉，但统计上并不多），整个结构形成一个具有单个入口和单个出口点的布局。匹配过程可以被认为是一辆沿着轨道行驶的汽车，通过系统的确切路线由在每个可能的连接点读取的字符决定。汽车可以在任何时候从轨道上掉下来，但它只能在与轨道匹配的情况下继续前进。
因此，模式/foo(?:\w+|\d+|\s+)bar/可以被认为是以下图表
[start]
|
<foo>
|
+-----+-----+
| | |
<\w+> <\d+> <\s+>
| | |
+-----+-----+
|
<bar>
|
[end]事实是，如今 Perl 的正则表达式比这种结构复杂得多，但以这种方式可视化它可以帮助你在尝试定位时获得方向，并且它与当前的实现非常接近。
更准确地说，我们将说一个正则表达式程序是对一个图的编码。图中的每个节点对应于原始正则表达式模式的一部分，例如一个文字字符串或一个分支，并且有一个指向表示要匹配的下一个组件的节点的指针。由于“节点”和“操作码”在 Perl 源代码中已经有了其他含义，因此我们将正则表达式程序中的节点称为“regop”。
该程序由一个regnode结构数组表示，其中一个或多个结构代表程序的单个 regop。结构regnode是最小的结构，它有一个与所有其他较大结构共享的字段结构。（在这篇文档之外，“regnode”一词有时用于表示“regop”，这可能会造成混淆。）
除了BRANCH之外的所有regop的“next”指针都实现连接；一个两端都有BRANCH的“next”指针连接着两个备选方案。[这里我们有一个微妙的语法依赖关系：单个BRANCH（与它们的集合相反）由于运算符优先级的原因，永远不会与任何东西连接。]
某些类型的regop的操作数是一个文字字符串；对于其他类型，它是一个指向子程序的regop。特别是，BRANCH节点的操作数是分支的第一个regop。
注意：正如铁路隐喻所暗示的那样，这不是树结构：分支的尾部连接到BRANCH集合后面的东西。它就像一条单线铁路轨道，在进入车站或铁路场时分裂，并在从另一侧出来时重新连接。
regop的基本结构在regexp.h中定义如下
struct regnode {
U8 flags; /* Various purposes, sometimes overridden */
U8 type; /* Opcode value as specified by regnodes.h */
U16 next_off; /* Offset in size regnode */
};其他更大的regnode类结构在regcomp.h中定义。它们几乎就像子类，因为它们与regnode具有相同的字段，可能在结构中包含额外的字段，并且在某些情况下，某些基本字段的特定含义（和名称）被覆盖。以下是更完整的描述。
regnode_1regnode_2regnode_1结构具有相同的头部，后面跟着一个四字节参数；regnode_2结构包含两个两个字节的参数
regnode_1 U32 arg1;
regnode_2 U16 arg1; U16 arg2;regnode_stringregnode_string结构用于文字字符串，在头部之后是一个字节长度，然后是字符串数据。字符串在尾部用零字节填充，以便节点的总长度是四字节的倍数
regnode_string char string[1];
U8 str_len; /* overrides flags */regnode_charclass方括号字符类由regnode_charclass结构表示，该结构具有一个四字节参数，然后是一个 32 字节（256 位）位图，指示 Latin1 范围内哪些字符包含在该类中。
regnode_charclass U32 arg1;
char bitmap[ANYOF_BITMAP_SIZE];各种以ANYOF_开头的标志用于特殊情况。上面 Latin1 匹配和运行时才知道的内容存储在"Perl 的 pprivate 结构"中。
regnode_charclass_posixl还有一种更大的字符类结构形式，用于在/l匹配下表示 POSIX 字符类，称为regnode_charclass_posixl，它有一个额外的 32 位位图，指示哪些 POSIX 字符类已被包含。
regnode_charclass_posixl U32 arg1;
char bitmap[ANYOF_BITMAP_SIZE];
U32 classflags;regnodes.h 定义了一个名为PL_regnode_arg_len[]的数组，它以size regnode（4 字节）为单位给出每个操作码的大小。一个宏用于根据其str_len字段计算EXACT节点的大小。
regops 定义在regnodes.h中，该文件由regcomp.pl从regcomp.sym生成。目前，可能的不同 regops 的最大数量限制为 256，其中大约四分之一已被使用。
一组宏使访问字段更容易、更一致。这些包括OP()，用于确定regnode类结构的类型；NEXT_OFF()，它是指向下一个节点的偏移量（稍后详细介绍）；ARG()、ARG1()、ARG2()、ARG_SET()以及用于读取和设置参数的等效项；以及STR_LEN()、STRING()和OPERAND()，用于操作字符串和带有 regop 的类型。
正则表达式引擎中有两个不同的“下一个 regnode”概念，在你的思考中区分它们很重要，因为它们在许多地方在概念上重叠，但在它们不重叠的地方，差异至关重要。对于大多数 regnode 类型，这两个概念在实践中是（几乎）相同的。这两种类型是REGNODE_AFTER，它在编译期间被大量使用，但在执行期间只偶尔使用，以及regnext，它在执行期间被大量使用，而在编译期间只偶尔使用。
这是编译后的正则表达式程序中的“位置上下一个 regnode”。对于较小的 regnode 类型，它在幕后是regnode_ptr+1，但由于 regnode 的大小各不相同并且会随着时间的推移而改变，因此我们提供了隐藏这些细节的宏。
它在编译阶段被大量使用，但在执行阶段只被少数几个选定的 regnode 类型使用。它也大量用于调试正则表达式程序的代码。
有一些宏可以选择使用，这些宏可以根据情况尽可能高效地计算它。规范宏是REGNODE_AFTER()，它是最强大的，应该处理我们遇到的任何情况，但也可能是最慢的。对于你知道当前 regnode 大小是恒定的，并且你知道它的类型或操作码的特殊情况，还有两个额外的宏。在这种情况下，你可以使用REGNODE_AFTER_opcode()或REGNODE_AFTER_type()。
在旧版本的正则表达式引擎中，REGNODE_AFTER() 被称为 NEXTOPER，但发现这会造成混淆，因此进行了重命名。还有一个 REGNODE_BEFORE()，但它不安全，不应在新的代码中使用。
这是一个可以通过向前跳跃 regnode 的 NEXT_OFF() 成员的值来访问的 regnode，或者在少数情况下，对于更长的跳跃，可以通过 regnode_1 结构的 arg1 字段来访问。子例程 regnext() 透明地处理了这一点。在大多数情况下，regnode 的 regnext 是在当前 regnode 成功匹配后应该执行的 regnode，但在某些情况下，这可能不成立。在循环控制和分支控制 regnode 类型中，regnext 可能表示一些特殊含义，对于 BRANCH 节点，regnext 是如果当前节点执行失败应该执行的下一个 BRANCH，而一些循环控制 regnode 将 regnext 设置为循环的末尾，以便在当前迭代无法匹配时跳到它们的清理部分。
大多数 regnode 类型不会在执行流程中创建分支，并且除了优化之外，"下一个" 的两个概念是相同的。例如，在编译阶段，SBOL 操作码的 regnext 和 REGNODE_AFTER 是相同的。主要区别在于 BRANCH regnode，其中 REGNODE_AFTER 表示分支中模式的开始，而 regnext 表示如果当前分支无法匹配则链接到下一个 BRANCH，如果它是最后一个分支则为 0。量词的循环逻辑也类似地利用了这两种类型之间的区别，REGNODE_AFTER 是循环结构的内部，而 regnext 指向循环的末尾。
在编译过程中，引擎可能无法知道给定节点的 regnext 是什么，因此在编译期间，regnext 仅在必须使用且已知正确的情况下使用。在编译阶段的最后，我们遍历正则表达式程序并根据需要更正 regnext 数据，并执行各种优化，这些优化可能会导致在构建过程中所需的 regnode 变得冗余，或者我们可能会用更小的 regnode 替换一个大的 regnode 并用 OPTIMIZED regnode 填充间隙。因此，我们可能会从类似以下内容开始
BRANCH
EXACT "foo"
BRANCH
EXACT "bar"
EXACT "!"并用类似以下内容替换它
TRIE foo|bar
OPTIMIZED
OPTIMIZED
OPTIMIZED
EXACT "!"TRIE 节点的 REGNODE_AFTER 将是一个 OPTIMIZED regnode，理论上 regnext 将与 REGNODE_AFTER 相同。但将 OPTIMIZED regnode 作为 noop 执行三次效率低下，因此优化器修复了 regnext，以便在执行阶段跳过此类节点。
在执行阶段，我们几乎完全使用 regnext()，并且仅在 REGNODE_AFTER 对给定 regnode 类型具有明确定义的含义的特殊情况下使用 REGNODE_AFTER。例如，/x+/ 会导致
PLUS
EXACT "x"
ENDPLUS regnode 的 regnext 是 END regnode，PLUS regnode 的 REGNODE_AFTER 是 EXACT regnode。EXACT regnode 的 regnext 和 REGNODE_AFTER 是 END regnode。
从广义上讲，将字符串与模式进行匹配涉及以下步骤
这些步骤在 Perl 程序的实际执行中发生的位置取决于模式是否涉及插值任何字符串变量。如果发生插值，则编译在运行时发生。如果没有，则编译在编译时执行。（/o 修饰符会改变这一点，qr// 在某种程度上也会改变这一点。）引擎并不真正关心这一点。
此代码主要位于 regcomp.c 中，以及头文件 regcomp.h、regexp.h 和 regnodes.h。
编译从pregcomp()开始，它主要是一个初始化包装器，将工作委托给另外两个例程进行繁重的工作：第一个是reg()，它是解析的起点；第二个是study_chunk()，负责优化。
pregcomp()中的初始化主要涉及创建和填充一个特殊结构RExC_state_t（定义在regcomp.c中）。regcomp.h中几乎所有内部使用的例程都将指向其中一个结构的指针作为其第一个参数，名称为pRExC_state。此结构用于存储编译状态，并包含许多字段。同样，还有许多宏对该变量进行操作：任何看起来像RExC_xxxx的东西都是一个对该指针/结构进行操作的宏。
reg()是解析过程的开始。它负责解析任意一段模式，直到字符串的结尾或模式中遇到的第一个右括号。这意味着它可以用来解析顶层正则表达式，或任何分组括号内的部分。它还处理 Perl 正则表达式具有的“特殊括号”。例如，在解析/x(?:foo)y/时，reg()将在某个时刻被调用来解析从“?”符号到包括“)”的字符。
此外，reg()还负责解析模式中的一个或多个分支，并通过正确设置其下一个指针来“完成它们”。为了进行解析，它会反复调用regbranch()，regbranch()负责处理它看到的第一个|符号之前的部分。
regbranch()反过来调用regpiece()，regpiece()处理后跟量词的“事物”。为了解析“事物”，会调用regatom()。这是最低级别的例程，它解析出常量字符串、字符类以及各种特殊符号，例如$。如果regatom()遇到“（”字符，它会反过来调用reg()。
过去，解析过程涉及两个主要阶段：第一个阶段计算编译程序的大小，第二个阶段实际进行编译。但现在只有一个主要阶段，它基于输入模式的长度进行初始粗略估计，并在解析过程中根据需要增加，最后修剪到实际使用的数量。
然而，在解析过程中，可能会发生各种情况导致解析必须从头开始。例如，如果程序变得非常大，以至于其中的跳转无法容纳在正常的 16 位空间内。有两个特殊的 regop 可以保存更大的跳转目标，即 BRANCHJ 和 LONGBRANCH。解析会重新开始，并使用这些 regop 代替正常的较短 regop。无论何时需要重新开始解析，函数都会返回失败并设置一个标志，指示需要执行的操作。该标志会传递到顶层例程，该例程会采取适当的操作并从头开始重新解析。如果需要更长的跳转，则会在 RExC_state_t 结构中设置 RExC_use_BRANCHJ 标志，函数在决定如何执行分支之前会检查该标志。
在大多数情况下，发现问题的函数会设置因果标志并立即返回失败。 "解析复杂情况" 包含一个关于此工作原理的明确示例。在其他情况下，例如对编号的括号分组的向前引用，我们需要完成解析才能知道该编号分组是否实际出现在模式中。在这些情况下，解析只是在最后重新进行，并了解其中包含多少个分组。
regtail() 例程由 reg() 和 regbranch() 调用，以正确地“设置尾指针”。在执行时，当我们到达分支的末尾时，我们需要转到分组括号后面的节点。然而，在解析时，我们直到到达末尾才知道末尾在哪里，因此当我们到达末尾时，必须返回并相应地更新偏移量。regtail 用于简化此过程。
解析过程的一个细微之处意味着像 /foo/ 这样的正则表达式最初被解析为一个包含单个分支的交替。只有在之后，优化器才会将单个分支交替转换为更简单的形式。
调用图如下所示
reg() # parse a top level regex, or inside of
# parens
regbranch() # parse a single branch of an alternation
regpiece() # parse a pattern followed by a quantifier
regatom() # parse a simple pattern
regclass() # used to handle a class
reg() # used to handle a parenthesised
# subpattern
....
...
regtail() # finish off the branch
...
regtail() # finish off the branch sequence. Tie each
# branch's tail to the tail of the
# sequence
# (NEW) In Debug mode this is
# regtail_study().语法形式可能类似于以下内容
atom : constant | class
quant : '*' | '+' | '?' | '{min,max}'
_branch: piece
| piece _branch
| nothing
branch: _branch
| _branch '|' branch
group : '(' branch ')'
_piece: atom | group
piece : _piece
| _piece quant上述描述的含义是，包含嵌套括号的模式将导致调用图循环遍历reg()、regbranch()、regpiece()、regatom()、reg()、regbranch()等，直到到达最深层的嵌套。所有上述例程都返回指向regnode的指针，该指针通常是添加到程序中的最后一个regnode。但是，一个复杂之处是，reg()对于解析(?:)语法以嵌入修饰符返回NULL，并设置标志TRYAGAIN。TRYAGAIN向上传播，直到被捕获，在某些情况下被regatom()捕获，但在其他情况下则被regbranch()无条件捕获。因此，它永远不会被regbranch()返回给reg()。此标志允许检测诸如(?i)+之类的模式作为错误（*量词在正则表达式中没有跟随任何内容；在 m/(?i)+ <-- HERE / 中用 <-- HERE 标记*）。
另一个复杂之处是，如果程序需要存储 Unicode，则用于程序的表示形式会有所不同，但直到解析过程的中途才能确定是否需要存储 Unicode。程序的 Unicode 表示形式更大，并且不能像以前那样有效地匹配。（有关详细信息，请参见下面的“Unicode 和本地化支持”部分。）如果模式包含文字 Unicode，则很明显程序需要存储 Unicode。否则，解析器会乐观地假设可以使用更有效的表示形式，并在此基础上开始调整大小。但是，如果它随后在模式中遇到必须以 Unicode 存储的内容，例如表示字符文字的\x{...}转义序列，则意味着所有先前计算的大小都需要重新计算，使用适合 Unicode 表示形式的值。这是解析需要重新启动的另一个实例，它可以立即完成，并且确实完成了。该函数返回失败，并设置标志RESTART_UTF8（通过使用宏REQUIRE_UTF8封装）。此重启请求以类似的方式向上传播调用链，直到它在Perl_re_op_compile()中被“捕获”，该函数将模式标记为包含 Unicode，并重新启动大小调整过程。运行时代码块中的构造也可能需要 Unicode 表示形式，这由S_compile_runtime_code()向Perl_re_op_compile()返回 false 来表示。
之前重启是通过在 regatom() 中使用 longjmp 跳回到 Perl_re_op_compile() 中的 setjmp 来实现的，但这被证明是有问题的，因为后者是一个包含许多自动变量的大函数，这些变量与 setjmp 的紧急控制流交互不好。
从 Perl 5.9.x 开发版本开始，你可以使用 use re Debug => 'PARSE' 来查看有关解析过程的一些跟踪信息。我们将从一些简单的模式开始，逐步构建更复杂的模式。
因此，当我们解析 /foo/ 时，我们会看到类似下面的表格。左侧显示正在解析的内容，数字表示下一个 regop 将放置的位置。右侧的内容是图表的跟踪输出。名称选择得比较短，以减少屏幕上的密度。'tsdy' 是 regtail() 的一种特殊形式，它执行一些额外的分析。
>foo< 1 reg
brnc
piec
atom
>< 4 tsdy~ EXACT <foo> (EXACT) (1)
~ attach to END (3) offset to 2生成的程序如下所示
1: EXACT <foo>(3)
3: END(0)如你所见，即使我们解析了一个分支和一个片段，它最终只是一个原子。最终的程序向我们展示了事物是如何工作的。我们有一个 EXACT regop，后面跟着一个 END regop。括号中的数字表示节点的 regnext 所在的位置。END regop 的 regnext 未使用，因为 END regop 表示我们已成功匹配。左侧的数字表示 regop 在 regnode 数组中的位置。
现在让我们尝试一个更难的模式。我们将添加一个量词，因此现在我们有了模式 /foo+/。我们将看到 regbranch() 调用 regpiece() 两次。
>foo+< 1 reg
brnc
piec
atom
>o+< 3 piec
atom
>< 6 tail~ EXACT <fo> (1)
7 tsdy~ EXACT <fo> (EXACT) (1)
~ PLUS (END) (3)
~ attach to END (6) offset to 3最终我们得到以下程序
1: EXACT <fo>(3)
3: PLUS(6)
4: EXACT <o>(0)
6: END(0)现在我们有一个特殊情况。EXACT regop 的 regnext 为 0。这是因为如果它匹配，它应该尝试再次匹配自身。PLUS regop 处理 EXACT regop 的实际失败，并采取适当的措施（如果 EXACT 至少匹配一次，则转到 regnode 6，否则失败）。
现在让我们来看一个更复杂的例子：/x(?:foo*|b[a][rR])(foo|bar)$/
>x(?:foo*|b... 1 reg
brnc
piec
atom
>(?:foo*|b[... 3 piec
atom
>?:foo*|b[a... reg
>foo*|b[a][... brnc
piec
atom
>o*|b[a][rR... 5 piec
atom
>|b[a][rR])... 8 tail~ EXACT <fo> (3)
>b[a][rR])(... 9 brnc
10 piec
atom
>[a][rR])(f... 12 piec
atom
>a][rR])(fo... clas
>[rR])(foo|... 14 tail~ EXACT <b> (10)
piec
atom
>rR])(foo|b... clas
>)(foo|bar)... 25 tail~ EXACT <a> (12)
tail~ BRANCH (3)
26 tsdy~ BRANCH (END) (9)
~ attach to TAIL (25) offset to 16
tsdy~ EXACT <fo> (EXACT) (4)
~ STAR (END) (6)
~ attach to TAIL (25) offset to 19
tsdy~ EXACT <b> (EXACT) (10)
~ EXACT <a> (EXACT) (12)
~ ANYOF[Rr] (END) (14)
~ attach to TAIL (25) offset to 11
>(foo|bar)$< tail~ EXACT <x> (1)
piec
atom
>foo|bar)$< reg
28 brnc
piec
atom
>|bar)$< 31 tail~ OPEN1 (26)
>bar)$< brnc
32 piec
atom
>)$< 34 tail~ BRANCH (28)
36 tsdy~ BRANCH (END) (31)
~ attach to CLOSE1 (34) offset to 3
tsdy~ EXACT <foo> (EXACT) (29)
~ attach to CLOSE1 (34) offset to 5
tsdy~ EXACT <bar> (EXACT) (32)
~ attach to CLOSE1 (34) offset to 2
>$< tail~ BRANCH (3)
~ BRANCH (9)
~ TAIL (25)
piec
atom
>< 37 tail~ OPEN1 (26)
~ BRANCH (28)
~ BRANCH (31)
~ CLOSE1 (34)
38 tsdy~ EXACT <x> (EXACT) (1)
~ BRANCH (END) (3)
~ BRANCH (END) (9)
~ TAIL (END) (25)
~ OPEN1 (END) (26)
~ BRANCH (END) (28)
~ BRANCH (END) (31)
~ CLOSE1 (END) (34)
~ EOL (END) (36)
~ attach to END (37) offset to 1生成的程序
1: EXACT <x>(3)
3: BRANCH(9)
4: EXACT <fo>(6)
6: STAR(26)
7: EXACT <o>(0)
9: BRANCH(25)
10: EXACT <ba>(14)
12: OPTIMIZED (2 nodes)
14: ANYOF[Rr](26)
25: TAIL(26)
26: OPEN1(28)
28: TRIE-EXACT(34)
[StS:1 Wds:2 Cs:6 Uq:5 #Sts:7 Mn:3 Mx:3 Stcls:bf]
<foo>
<bar>
30: OPTIMIZED (4 nodes)
34: CLOSE1(36)
36: EOL(37)
37: END(0)在这里我们可以看到一个更复杂的程序，其中包含各种优化。在 regnode 10，我们看到一个示例，其中只有一个字符的字符类被转换为 EXACT 节点。我们还可以看到整个交替是如何被转换为 TRIE-EXACT 节点的。因此，一些 regnode 被标记为已优化。我们可以看到 $ 符号已被转换为 EOL regop，这是一段特殊的代码，用于查找 \n 或字符串的结尾。
BRANCH 的下一个指针很有趣，因为它指向如果分支失败应该执行的位置。在执行时，如果引擎尝试从分支遍历到不是分支的 regnext，那么引擎将知道整个分支集都失败了。
正则表达式引擎可能是一个强大的工具。在长字符串和复杂模式上，它最终可能需要做很多工作才能找到匹配项，甚至更多工作才能确定没有匹配项。考虑以下模式的情况。
'ababababababababababab' =~ /(a|b)*z/(a|b)* 部分可以在字符串中的每个字符处匹配，然后每次都失败，因为字符串中没有 z。因此，显然我们可以避免使用正则表达式引擎，除非字符串中存在 z。同样，在类似的模式中
/foo(\w+)bar/在这种情况下，我们知道字符串必须包含一个 foo，后面必须跟着 bar。我们可以使用 fbm_instr() 中实现的快速 Boyer-Moore 匹配来查找这些字符串的位置。如果它们不存在，那么我们不需要诉诸更昂贵的正则表达式引擎。更好的是，如果它们存在，我们可以使用它们的位置来减少正则表达式引擎需要覆盖的搜索空间，以确定整个模式是否匹配。
模式的各个方面可以用来促进这些方面的优化
锚定固定字符串
浮动固定字符串
最小和最大长度要求
起始类
行首/行尾位置
另一种可以发生的优化形式是解析后的“窥孔”优化，其中低效的结构被更有效的结构替换。在解析过程中用于标记分支结束和组结束的 TAIL regops 就是这种情况。这些 regops 在构建过程中用作占位符，并且“始终匹配”，因此可以通过使指向 TAIL 的内容指向 TAIL 指向的内容来“优化掉”，从而“跳过”节点。
另一种可以发生的优化是“EXACT 合并”，即两个连续的 EXACT 节点合并成一个 regop。这种更激进的形式是，EXACT BRANCH ... EXACT 形式的分支序列可以转换为 TRIE-EXACT regop。
所有这些都在例程 study_chunk() 中发生，该例程使用特殊结构 scan_data_t 来存储它执行的分析，并在执行过程中进行“窥孔”优化。
study_chunk() 中涉及的代码非常神秘。小心。:-)
正则表达式的执行通常涉及两个阶段，第一个是在字符串中找到我们应该从哪里开始匹配的起点，第二个是运行 regop 解释器。
如果我们能确定没有有效的起点，那么我们就不费心运行解释器。同样，如果我们从分析阶段知道我们无法检测到到起始位置的快捷方式，我们将直接进入解释器。
两个入口点是 re_intuit_start() 和 pregexec()。这些例程之间存在着某种乱伦关系，它们的函数之间存在重叠，并且 pregexec() 甚至可能自己调用 re_intuit_start()。尽管如此，perl 源代码的其他部分可能会调用其中一个或两个。
解释器本身的执行曾经是递归的，但由于 Dave Mitchell 在 5.9.x 开发轨道上的努力，这种情况已经改变：现在在堆上维护一个内部堆栈，并且例程是完全迭代的。这可能会很棘手，因为代码对它存储的状态非常保守，结果是代码中的两行连续行实际上可能由于模拟递归而运行在完全不同的上下文中。
re_intuit_start() 负责处理由 study_chunk() 执行的分析结果（如 "窥孔优化和分析" 中所述）确定的起点和无匹配优化。
此例程的基本结构是尝试找到模式可能匹配的起点和/或终点，并确保字符串足够长以匹配模式。它尝试使用更有效的方法而不是效率较低的方法，并且可能涉及对约束的相当大的交叉检查以找到与字符串匹配的位置。例如，它可能会尝试确定给定的固定字符串不仅必须存在，而且必须在字符串结尾之前一定数量的字符，或者其他任何东西。
它调用了几个其他例程，例如 fbm_instr()，它执行快速 Boyer Moore 匹配，以及 find_byclass()，它负责使用程序中的第一个强制性 regop 查找起点。
当优化标准满足时，reg_try() 被调用以执行匹配。
pregexec() 是运行正则表达式的主要入口点。它包含对初始化正则表达式解释器状态的支持，如果需要，运行 re_intuit_start()，以及根据需要在字符串的不同起始位置运行解释器。当需要使用正则表达式解释器时，pregexec() 会调用 regtry()。
regtry() 是正则表达式解释器的入口点。它期望作为参数一个指向 regmatch_info 结构体的指针和一个指向字符串的指针。它返回一个整数 1 表示成功，0 表示失败。它基本上是围绕 regmatch() 的一个设置包装器。
regmatch 是解释器的主要“递归循环”。它基本上是一个巨大的 switch 语句，它实现了一个状态机，其中可能的状态是 regops 本身，以及一些额外的中间状态和失败状态。一些状态被实现为子程序，但大部分是内联代码。
在处理包含无法使用 8 位字符集表示的字符的字符串时，perl 使用一个内部表示，它是 Unicode 的 UTF-8 编码[2] 的一个宽松版本。它使用单个字节来表示 ASCII 字符集中的字符，并使用两个或多个字节的序列来表示所有其他字符。（有关 UTF-8 和 perl 编码（utf8）之间关系的更多信息，请参见 perlunitut。对于本次讨论，差异并不重要。）
无论你如何看待，Unicode 支持在正则表达式引擎中都会很痛苦。当你有 256 个可能的字符时可能有效的技巧，在处理 UTF-8 字符集的大小时往往无法扩展。你可以在 ASCII 中理所当然地认为的事情，在 Unicode 中可能不成立。例如，在 ASCII 中，可以安全地假设 sizeof(char1) == sizeof(char2)，但在 UTF-8 中则不然。Unicode 大小写折叠比 ASCII 的简单规则复杂得多，即使不使用 Unicode，而只使用本地化的单字节编码，事情也会变得棘手（例如，LATIN SMALL LETTER SHARP S (U+00DF, ß) 应该在本地化的不区分大小写的匹配中匹配 'SS'）。
更糟糕的是，UTF-8 支持是正则表达式引擎（以及 perl）的后期添加，这必然使事情变得更加复杂。显然，从一开始就设计一个支持 Unicode 的正则表达式引擎比将其改造为不支持 Unicode 的引擎更容易。
几乎所有涉及查看输入字符串的 regops 都有两种情况，一种用于 UTF-8，另一种不使用。事实上，情况往往比这更复杂，因为模式也可能是 UTF-8。
在进行更改时，必须注意确保在编译时和执行时都正确处理 UTF-8，包括字符串和模式不匹配时。
在 perlreapi 中描述的 regexp 结构对所有正则表达式引擎都是通用的。它的两个字段用于编译模式的正则表达式引擎的私有使用。它们是 intflags 和 pprivate 成员。pprivate 是指向任意结构的空指针，其使用和管理由编译引擎负责。perl 永远不会修改这两个值中的任何一个。对于库存引擎，pprivate 指向的结构称为 regexp_internal。
它的 pprivate 和 intflags 字段包含特定于每个引擎的数据。
有两个结构用于存储编译后的正则表达式。一个是在 perlreapi 中描述的 regexp 结构，它由当前使用的引擎填充，并且它的某些字段由 perl 读取以实现诸如 qr// 的字符串化之类的事情。
另一个结构由 regexp 结构的 pprivate 指向，并且除了同一个结构中的 intflags 之外，被认为是编译正则表达式的正则表达式引擎的属性；
regexp 结构包含 perl 需要了解的所有数据，以便正确地使用正则表达式。它包括有关 perl 可以用来确定是否应该真正使用正则表达式引擎的优化的数据，以及在各种上下文中正确执行模式所需的各种其他控制信息，例如模式是否以某种方式锚定，或者在编译期间使用了哪些标志，或者程序是否包含 perl 需要知道的特殊结构。
此外，它包含两个字段，这些字段用于编译模式的正则表达式引擎的私有使用。它们是 intflags 和 pprivate 成员。pprivate 是指向任意结构的空指针，其使用和管理由编译引擎负责。perl 永远不会修改这两个值中的任何一个。
如前所述，对于默认引擎，pprivate 将是指向一个 regexp_internal 结构的指针，该结构包含已编译的程序以及正则表达式引擎实现专用的任何其他数据。
pprivate 结构以下结构用作 perl 正则表达式引擎的 pprivate 结构。由于它是特定于 perl 的，因此对于其他引擎实现来说，它仅仅具有好奇价值。
typedef struct regexp_internal {
regnode *regstclass;
struct reg_data *data;
struct reg_code_blocks *code_blocks;
U32 proglen;
U32 name_list_idx;
regnode program[1];
} regexp_internal;属性描述如下
regstclass由 re_intuit_start() 使用的特殊 regop，用于检查模式是否可以在特定位置匹配。例如，如果正则表达式引擎知道模式必须以 'Z' 开头，那么它可以扫描字符串直到找到一个 'Z'，然后从那里启动正则表达式引擎。处理此操作的例程称为 find_by_class()。有时此字段指向程序中嵌入的 regop，有时它指向由优化器构建的独立合成 regop。
data此字段指向一个 reg_data 结构，该结构定义如下
struct reg_data {
U32 count;
U8 *what;
void* data[1];
};此结构用于处理正则表达式引擎在对已编译产品进行克隆或释放操作期间需要专门处理的数据结构。数据数组中的每个元素在 what 数组中都有一个对应的元素。在编译期间，需要存储特殊结构的 regop 将使用 add_data() 例程在每个数组中添加一个元素，然后将索引存储在 regop 中。
在现代 perl 中，此结构的第 0 个元素是保留的，并且永远不会用于存储任何有用的东西。这是为了允许需要索引到此数组中的东西来表示“无值”。
code_blocks此可选结构用于管理模式中的 (?{}) 结构。它由以下结构组成。
/* record the position of a (?{...}) within a pattern */
struct reg_code_block {
STRLEN start;
STRLEN end;
OP *block;
REGEXP *src_regex;
};
/* array of reg_code_block's plus header info */
struct reg_code_blocks {
int refcnt; /* we may be pointed to from a regex
and from the savestack */
int count; /* how many code blocks */
struct reg_code_block *cb; /* array of reg_code_block's */
};proglen以 regop 为单位存储已编译程序的长度。
name_list_idx这是数据数组中的索引，其中存储了一个 AV，该 AV 包含模式中任何命名捕获缓冲区的名称（如果有）。这仅在正则表达式引擎的调试版本中使用，以及当 RXp_PAREN_NAMES(prog) 为真时使用。如果没有此类数据，它将为 0。
program已编译的程序。内联到结构中，因此整个结构可以被视为单个块。
由 Yves Orton 于 2006 年撰写。
摘录自 Perl，并包含 Ronald J. Kimball、Dave Mitchell、Dominic Dunlop、Mark Jason Dominus、Stephen McCamant 和 David Landgren 的贡献和建议。
目前由 Perl 5 维护者维护。
与 Perl 相同的条款。