NFA

NFA（非确定性有限自动机）引擎由该模式驱动。

原理

正则表达式模式被解析为树。

当前位置指针被设定为输入字符串的开始，和一个匹配试图在这个位置。如果匹配 fais，则位置增加到字符串中的下一个字符，并尝试从该位置开始另一个匹配。重复此过程，直到找到匹配或达到输入字符串的结尾。

对于每次匹配尝试

该算法通过对给定的起始位置执行模式树的遍历来工作。当它在树中前进时，它通过消耗匹配的字符来更新当前输入位置。

如果算法遇到与当前位置的输入字符串不匹配的树节点，则必须回溯。这是通过返回树中的父节点，将当前输入位置重置为进入父节点时的值以及尝试下一个备用分支来执行的。

如果算法设法退出树，则报告成功匹配。否则，当尝试所有可能性时，匹配失败。

优化

正则表达式引擎通常会应用一些优化以获得更好的性能。例如，如果他们确定匹配必须以给定字符开头，则他们将仅在输入字符串中出现该字符的那些位置处尝试匹配。

例

将 a(b|c)a 与输入字符串 abeacab 相匹配：

模式树可能看起来像：

CONCATENATION
    EXACT: a
    ALTERNATION
        EXACT: b
        EXACT: c
    EXACT: a

匹配过程如下：

a(b|c)a      abeacab
^            ^

a 在输入字符串中找到，使用它并继续到模式树中的下一个项目：交替。尝试第一种可能性：精确的 b。

a(b|c)a      abeacab
  ^           ^

b 被找到，所以交替成功，消耗它并继续到串联中的下一个项目：一个确切的 a：

a(b|c)a      abeacab
      ^        ^

a 是不是在预期位置找到。回溯到交替，将输入位置重置为第一次进入交替时的值，并尝试第二种选择：

a(b|c)a      abeacab
    ^         ^

c 是不是在这个位置找到。回溯到串联。此时没有其他可能尝试，因此在字符串的开头没有匹配。

在下一个输入位置尝试第二个匹配：

a(b|c)a      abeacab
^             ^

a 与那里不匹配。在下一个位置尝试另一个匹配：

a(b|c)a      abeacab
^              ^

也没有运气。前进到下一个位置。

a(b|c)a      abeacab
^               ^

a 匹配，所以消耗它并输入交替：

a(b|c)a      abeacab
  ^              ^

b 不匹配。尝试第二种选择：

a(b|c)a      abeacab
    ^            ^

c 匹配，所以消耗它并前进到串联中的下一个项目：

a(b|c)a      abeacab
      ^           ^

a 匹配，并且已到达树的末尾。举报一个成功的匹配：

a(b|c)a      abeacab
                \_/