2

根据这个页面（和其他一些页面），DFA 正则表达式引擎可以很好地处理捕获组。我对原子组（或所有格量词）很好奇，因为我最近经常使用它们，无法想象如何做到这一点。

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

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

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

  • 从字面开始/*
  • 吃以下任何东西
    • 任何字符，除了*
    • a*后跟任何东西，但/
  • 尽可能重复这个
  • 以字面结尾*/

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

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

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

/\* .*? \*/

但也是错误的，因为它可以吃掉整条线

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

当由于后面的子表达式在垃圾上失败而进行回溯时。将上述内容放在一个原子组中可以很好地解决问题：

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

这总是有效（我希望）并且尽可能快（对于 NFA）。所以我想知道 DFA 引擎是否能以某种方式处理它。

4

1 回答 1

1

DFA 不需要处理像原子分组这样的结构。DFA 是“文本导向的”，与 NFA 不同的是“正则表达式导向”，换句话说：原子分组是一种帮助引擎完成匹配的方法，否则会导致无休止的回溯，因为 (NFA) 引擎会尝试在一个位置找到匹配的每一种排列，甚至没有匹配是可能的。

简单地说，原子分组抛弃了回溯位置。由于 DFA 不会回溯（要匹配的文本是针对正则表达式检查的，而不是像 NFA 那样针对文本的正则表达式 - DFA 为每个决策打开一个分支），丢弃不存在的东西是没有意义的。

我建议 JFFriedl 的 Mastering Regular Expressions (Google Books)，他解释了 DFA 的一般概念：

DFA 引擎：文本导向

将正则表达式导向的 NFA 引擎与在扫描字符串时跟踪所有“当前正在进行中”的匹配的引擎进行对比。在今晚的例子中，当引擎点击 t 时，它会在当前正在进行的列表中添加一个潜在的匹配项：

[...]

扫描的每个后续字符都会更新可能匹配的列表。再匹配几个字符后，情况就变成了

[...]

有两个可能的比赛正在进行中（一个替代方案，骑士，被排除）。对于接下来的 g，只有第三种选择仍然可行。一旦 h 和 t 也被扫描，引擎意识到它完全匹配并且可以返回成功。

我称之为“文本导向”匹配，因为从文本中扫描的每个字符都控制着引擎。如示例中所示，部分匹配可能是任意数量的不同但可能匹配的开始。随着后续字符的扫描，不再可行的匹配将被删除。甚至在“进行中的部分匹配”也是完整匹配的情况下。例如，如果正则表达式是 ⌈to(...)?⌋，括号内的表达式变为可选的，但它仍然是贪婪的，所以它总是被尝试。一直在这些括号内进行部分匹配时，（'to'）的完整匹配已经被确认并保留，以防更长的匹配不成功。

（来源： http: //my.safaribooksonline.com/book/programming/regular-expressions/0596528124/regex-directed-versus-text-directed/i87）

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

于 2013-11-13T07:53:38.997 回答