DFA正则引擎能处理原子组吗？

Question

根据此页 (和其他一些)，deal引擎可以很好地处理捕获组。我对原子群(或拥有式量词)很好奇，因为我最近经常使用它们，无法想象这是如何做到的。

我不同意答案的第一部分：

DFA不需要处理像原子分组这样的构造.原子分组是帮助引擎完成匹配的一种方法，否则会导致无休止的回溯。

原子组不仅对NFA引擎的速度很重要，而且还允许编写更简单、更容易出错的正则表达式。假设我需要在程序中找到所有C风格的多行注释。精确的正则表达式应该是：

• 从文字/*开始
• 吃以下中的任何东西
  • 除*外的任何字符
  • 一个*跟在/后面

​

• 尽可能多地重复这一点
• 以文字*/结尾

这听起来有点复杂，正则表达式

/\* ( [^*] | \*[^/] )+ \*/

是复杂和错误的(它不能正确处理/* foo **/ )。使用不情愿的(懒惰的)量词更好

/\* .*? \*/

但也错了，因为它可以吃掉整条线

/* foo */ @#$!!**@#$ /* bar */

当回溯由于后面的子表达式在垃圾上失败时发生。将上述内容放在原子组中很好地解决了这个问题：

(?> /\* .*? \*/ )

这总是有效的(我希望)，并尽可能快(对NFA)。所以我想知道DFA引擎是否能应付得来。

Answer 1

DFA不需要处理像原子分组这样的构造。DFA是“文本导向的”，与NFA不同，NFA是"regex导向的“，换句话说:原子分组是帮助引擎完成匹配的一种方法，否则会导致无穷无尽的回溯，因为(NFA)引擎尝试在某个位置查找匹配的每一个可能的排列，甚至不可能匹配。

简单地说，原子分组抛弃了回溯位置。由于DFA没有回溯(要匹配的文本是对照regex检查的，而不是针对文本的正则表达式，比如NFA -- DFA为每个决策打开一个分支)，因此丢弃没有意义的东西。

我建议J.F.Friedl的精通正则表达式(谷歌图书)，他解释了DFA的一般思想：

DFA引擎:文本导向 将regex引导的NFA引擎与一个引擎进行对比，该引擎在扫描字符串时跟踪所有匹配的“当前正在进行中”的匹配。在今晚的例子中，当引擎命中t时，它会在当前正在进行的项目列表中添加一个潜在的匹配项： ..。 扫描的每个后续字符都会更新可能匹配的列表。在再匹配几个字符之后，情况就变成了 ..。 有两种可能的匹配正在进行中(另一种选择，骑士，排除了)。在接下来的g中，只有第三种选择仍然可行。一旦h和t也被扫描，引擎就会意识到它有一个完全匹配并且可以返回成功。 我称之为“文本导向”匹配，因为从文本中扫描的每个字符控制引擎。如本例所示，部分匹配可能是任意数量不同但可能的匹配的开始。当扫描后续字符时，不再可行的匹配项将被剪除。甚至在某些情况下，“部分比赛正在进行”也是完全匹配。如果正则表达式为⌈to(…)?⌋，例如，带括号的表达式变为可选的，但它仍然是贪婪的，所以总是尝试。在这些括号内，部分匹配一直在进行，一个完全匹配(“to”)已经被确认，以备更长时间的匹配无法进行。

(资料来源：http://my.safaribooksonline.com/book/programming/regular-expressions/0596528124/regex-directed-versus-text-directed/i87)

关于捕获组和DFAs:据我能够从您的链接中了解到，这些方法不是纯DFA引擎，而是DFA和NFA的混合体。