如果 Regex 描述常规语言 - 为什么要进行灾难性回溯？
if Regex describes regular language - Why Catastrophic Backtracking?
我想知道为什么 Catastrophic Backtracking with Whosebugs can occur, considering regex describe a regular language and these can recognized by a finite automaton。据我所知，有限自动机的内存消耗是恒定的。
有限状态自动机和正则表达式能够描述同一组语言并不意味着它们的工作方式相同。是的，它们在作用域上是等价的，你可以找到匹配相同语言的任何正则表达式（和反向）的有限状态自动机，但这种翻译并不容易。
正则表达式可以简单地转换为 nondeterministic finite automaton, but executing those can take a long time (they do backtracking as well). You could equally convert them into deterministic finite automatons，但它们的存储空间并不像 NFA 那样小。
这只是一个权衡。您以什么格式描述您的常规语言，以及使用什么算法将其与您的输入相匹配？使用回溯评估的正则表达式工作得很好。您可以构建导致灾难性回溯的正则表达式只是一个小麻烦 - 您还可以为不会发生的相同语言构建不同的表达式。您甚至可以自动检测灾难性回溯，并重写表达式，但代价是每次编译正则表达式时都要完成这项任务的成本太高，因此留给了程序员。
大多数实现它们称为正则表达式的东西的库和工具实际上并没有实现正则表达式。例如，反向引用在真正的正则表达式中是不可能的。此外，大多数工具实际上并不使用 DFA 转换来实现正则表达式（即使正则表达式实际上是正则表达式），而是使用效率低得多的技术。
关于后一点的讨论，参见例如https://swtch.com/~rsc/regexp/regexp1.html
我想知道为什么 Catastrophic Backtracking with Whosebugs can occur, considering regex describe a regular language and these can recognized by a finite automaton。据我所知，有限自动机的内存消耗是恒定的。
有限状态自动机和正则表达式能够描述同一组语言并不意味着它们的工作方式相同。是的，它们在作用域上是等价的，你可以找到匹配相同语言的任何正则表达式（和反向）的有限状态自动机，但这种翻译并不容易。
正则表达式可以简单地转换为 nondeterministic finite automaton, but executing those can take a long time (they do backtracking as well). You could equally convert them into deterministic finite automatons，但它们的存储空间并不像 NFA 那样小。
这只是一个权衡。您以什么格式描述您的常规语言，以及使用什么算法将其与您的输入相匹配？使用回溯评估的正则表达式工作得很好。您可以构建导致灾难性回溯的正则表达式只是一个小麻烦 - 您还可以为不会发生的相同语言构建不同的表达式。您甚至可以自动检测灾难性回溯，并重写表达式，但代价是每次编译正则表达式时都要完成这项任务的成本太高，因此留给了程序员。
大多数实现它们称为正则表达式的东西的库和工具实际上并没有实现正则表达式。例如，反向引用在真正的正则表达式中是不可能的。此外，大多数工具实际上并不使用 DFA 转换来实现正则表达式（即使正则表达式实际上是正则表达式），而是使用效率低得多的技术。
关于后一点的讨论，参见例如https://swtch.com/~rsc/regexp/regexp1.html