Regular Expressions 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