regex - 如何使用字符范围实现正则表达式NFA？

当您阅读诸如Regex: NFA and Thompson's algorithm之类的帖子时，一切看起来都相当简单，直到您在现实生活中意识到，不仅需要直接字符“7”或“b”，还需要:

[A-Z]
[^_]
.

即字符类(或范围)。因此，我的问题是-如何使用字符范围构建NFA？使用“非A”，“其他”之类的元字符，然后计算重叠范围？使用最终自动机时，这将导致使用树状结构，而不仅仅是表格。

更新:请假定大小字母(>> 256)不平凡。

我询问的是NFA，但稍后我也想将NFA转换为DFA。

最佳答案

最简单的方法是:

使用段作为NFA和DFA中过渡的标签。例如，范围[a-z]将被表示为[97, 122]段；单字符“a”将变成[97,97]；以及任何字符“。”将成为[minCode, maxCode]。

每个取反范围[^ a-z]都会导致从开始状态到下一个状态的两次转换。在此示例中，应创建两个过渡[minCode, 96]和[123, maxCode]。

如果通过枚举所有可能的字符[abcz]来表示范围，则应创建每个字符的过渡，或者将第一组字符编码为范围内的代码以优化过渡数量。因此[abcz]将变成[a-c]|z。因此，两个过渡而不是四个。

对于NFA，这应该足够了。但是，当存在具有相交字符范围的过渡时，将NFA转换为DFA的经典power set construction将不起作用。
要解决此问题，只需要一个附加的概括步骤。一旦创建了所有输入符号的集合，在我们的示例中，它将是一组线段，则应将其转换为一组不相交的线段。这可以在时间O(n * Log(n))中完成，其中n是使用优先级排队(PQ)的集合中的多个分段，其中分段由左组件排序。例:

  Procedure DISJOIN:
   Input  <- [97, 99] [97, 100] [98, 108]
   Output -> [97, 97] [98, 99], [100, 100], [101, 108]

步骤2。要从“设置状态”创建新的过渡，应该对算法进行如下修改:

   for each symbol in DISJOIN(input symbols)
     S <- empty set of symbols
     T <- empty "set state"
     for each state in "set state"
      for each transition in state.transitions
        I <- intersection(symbol, transition.label)
        if (I is not empty)
        {
           Add I to the set S
           Add transition.To to the T
        }

     for each segement from DISJOIN(S)
        Create transition from "set state" to T

为了在搜索过渡和输入符号C时加快匹配速度，可以按段对每个状态的过渡进行排序，并应用二进制搜索。