当您阅读诸如 Regex: NFA and Thompson's algorithm 之类的帖子时一切看起来都相当简单,直到您意识到在现实生活中您不仅需要像“7”或“b”这样的直接字符,而且还需要:
[A-Z]
[^_]
.
即字符类(或范围)。因此我的问题是——如何使用字符范围构建 NFA?使用像“not A”、“anything else”这样的元字符,然后计算重叠范围?这将导致在使用最终自动机时使用树状结构,而不仅仅是表格。
更新:请假设大小不平凡(>> 256)字母表。
我问的是 NFA,但后来我也想将 NFA 转换为 DFA。
最佳答案
最简单的方法是:
[97, 122]
;单个字符 'a' 将变成 [97,97]
;和任何字符 '.'会变成[minCode, maxCode]
. [minCode, 96]
和 [123, maxCode]
应该创建。 [a-c]|z
.因此两个转换而不是四个。 这对于 NFA 来说应该足够了。然而经典power set construction当存在具有相交字符范围的转换时,将 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 时加速匹配,每个状态的转换可能按段排序并应用二分搜索。
关于regex - 如何使用字符范围实现正则表达式 NFA?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20767047/