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
                \_/