我有一定的形式语言背景，最近我发现 Java 和其他语言使用的是扩展正则语言。由于我的背景，当我为 Pattern 调用编译时，我总是假设使用 Java 这样的语言。它在后台生成了 DFA 或 Transducer。因此，我一直假设无论我的正则表达式多么丑陋，无论我的正则表达式、Pattern.matches 或类似方法在线性时间内运行多长时间。但这个假设似乎是 incorrect .
A post我读到似乎暗示某些 Regex 表达式确实在线性时间内运行，但我并不完全相信或信任一个人。
我最终会编写自己的 Java 正式正则表达式库(我发现的现有库只有 GNU GPL 许可证)，但与此同时我对 Java/C# 正则表达式的时间复杂度有一些疑问。想保证我读的内容elsewhere是正确的。
问题:
- 像\sRT\s. 这样的形式化语言，Java/C# 中正则表达式的匹配方法会解决线性或非线性时间的成员关系问题吗？
- 一般来说，我如何知道给定正则语言的表达式成员问题是否是正则表达式的线性时间？
我进行文本分析，发现 Java 正则表达式不是 DFA 真是令人沮丧。
最佳答案
Because of my background, I had always assumed in languages like Java when I call compile for Pattern it produced a DFA or Transducer in the background.
这种信念在学术界很普遍。实际上，正则表达式编译不会生成 DFA 然后执行它。我在这方面只有少量经验；我在 1990 年代曾短暂参与过 Microsoft JavaScript 实现中的正则表达式编译系统。我们选择将“正则”表达式编译成简单的特定领域字节码语言，然后为该语言构建解释器。
正如您所注意到的，这可能会导致重复回溯在输入长度上具有指数级的不良时间行为，但编译状态的构造在表达式的大小上基本上是线性的。
那么让我用另外两个问题来反驳你的问题——我注意到这些是真正的问题，而不是修辞。
1) 每个实际上 正则表达式都对应于一个具有 n 个状态的 NDFA。相应的 DFA 可能需要叠加多达 2n 个状态。那么，是什么阻止了构建 DFA 所花费的时间在病理情况下呈指数增长？运行时间在输入中可能是线性的，但如果运行时间在模式大小上呈指数增长，那么基本上您只是用一种非线性换取另一种非线性。
2) 现在所谓的“正则”表达式已经不是那种东西了；他们可以做括号匹配。它们对应于下推自动机，而不是非确定性有限自动机。是否存在为“正则”表达式构造相应下推自动机的线性算法？
关于c# - 扩展正则语言框架中正则语言的算法复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20528505/