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

Question

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

[A-Z]
[^_]
.

即字符类（或范围）。因此我的问题是——如何使用字符范围构建 NFA？使用像“not A”、“anything else”这样的元字符然后计算重叠范围？这将导致在使用最终自动机时使用树状结构，而不仅仅是表格。

更新：请假设大小不平凡 (>>256) 字母表。

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

Answer 1

最简单的方法是：

1. 使用段作为 NFA 和 DFA 中转换的标签。例如，范围 [az] 将被表示为段[97, 122]；单个字符 'a' 会变成[97,97]; 和任何字符 '.' 会变成[minCode, maxCode].

2. 每个否定范围 [^az] 将导致从起始状态到下一个状态的两次转换。在这个例子中[minCode, 96]，[123, maxCode]应该创建两个过渡和。

3. 当通过枚举所有可能的字符 [abcz] 来表示范围时，应该创建每个字符的转换，或者代码可能首先将字符分组到范围内以优化转换次数。所以 [abcz] 会变成[a-c]|z. 因此两个转换而不是四个。

这对于 NFA 来说应该足够了。然而，当存在具有相交字符范围的转换时，将 NFA 转换为 DFA的经典幂集构造将不起作用。为了解决这个问题，只需要一个额外的泛化步骤。一旦创建了一组所有输入符号，在我们的例子中它将是一组段，它应该被转换为一组不相交的段。这可以在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 时加速匹配，每个状态的转换可能按段排序并应用二分搜索。