DFA

DFA（確定性有限自動機）引擎由輸入驅動。

原理

該演算法掃描輸入字串一次，並記住正規表示式中可能匹配的所有可能路徑。例如，當在模式中遇到交替時，建立兩個新路徑並獨立嘗試。當給定路徑不匹配時，將從可能性集中刪除它。

啟示

匹配時間受輸入字串大小的限制。沒有回溯，引擎可以同時找到多個匹配，甚至重疊匹配。

與 NFA 引擎型別相比，此方法的主要缺點是引擎可支援的減少的功能集。

例

將 a(b|c)a 與 abadaca 相匹配：

abadaca      a(b|c)a
^            ^        Attempt 1      ==> CONTINUE

abadaca      a(b|c)a
 ^           ^        Attempt 2      ==> FAIL
               ^      Attempt 1.1    ==> CONTINUE
                 ^    Attempt 1.2    ==> FAIL

abadaca      a(b|c)a
  ^          ^        Attempt 3      ==> CONTINUE
                   ^  Attempt 1.1    ==> MATCH

abadaca      a(b|c)a
   ^         ^        Attempt 4      ==> FAIL
               ^      Attempt 3.1    ==> FAIL
                 ^    Attempt 3.2    ==> FAIL

abadaca      a(b|c)a
    ^        ^        Attempt 5      ==> CONTINUE

abadaca      a(b|c)a
     ^       ^        Attempt 6      ==> FAIL
               ^      Attempt 5.1    ==> FAIL
                 ^    Attempt 5.2    ==> CONTINUE

abadaca      a(b|c)a
      ^      ^        Attempt 7      ==> CONTINUE
                   ^  Attempt 5.2    ==> MATCH

abadaca      a(b|c)a
       ^       ^      Attempt 7.1    ==> FAIL
                 ^    Attempt 7.2    ==> FAIL