如何将正则表达式 "x{m, n}" 转换为 NFA？

Question

正则表达式 x{m, n} 匹配前面 x 的 m 到 n 次重复，尝试匹配尽可能多的重复。

我有一个天真的解决方案，但是节点和边的数量取决于m和n，当n很大时这是不可接受的。

那么，有什么有效的方法可以将正则表达式转换为 NFA？

Answer 1

不幸的是，NFA "count" 不是很好。您基本上必须手动将正则表达式扩展到 Thompsons 的结构可以处理的范围。例如

m{2,5} -> mm(m(m(m)?)?)?

搜索函数 SimplifyRepeat here to see Google's implementation. See this page 以获取有关实际正则表达式实现的更多信息。