+ 和 * 之间的 Tcl 贪婪子表达式差异

Question

我正在尝试理解 Tcl 子表达式匹配和 "greediness" 并且完全不知道发生了什么。参考 http://wiki.tcl.tk/396:

中的示例

%regexp -inline (.*?)(n+)(.*) ennui
en e n {} 
%regexp -inline ^(.*?)(n+)(.*)$ ennui
ennui e nn ui

尽管我并不完全理解 "nested expressions"（括号表示的是什么，对吗？）匹配，但我决定从小处着手，尝试区分 * 和 + 作为贪婪运算符:

% regexp -inline (.*)(u*)(.*) ennui
ennui ennui {} {}
% regexp -inline (.*)(u+)(.*) ennui
ennui enn u i

如果 * 匹配零个或多个，而 + 匹配一个或多个，我不明白这两个命令之间的输出差异。为什么 u* 和 u+ 在同一个字符串上会产生两个不同的结果？

我觉得这是一个极其重要的细微差别 - 如果我能掌握这个简单模式中发生的事情 match/regex，我的生活就会变得完整。帮助！

提前致谢。

Answer 1

(.*)(u*)(.*) 和 (.*)(u+)(.*) 不同的原因是第二个正则表达式 至少需要 1 个 u。

Tcl 中的 ARE 正则表达式使用回溯（与大多数 NFA 一样）。使用 (.*)，引擎从头到尾抓取整个字符串，并开始回溯以查找它是否可以容纳下一个子模式。

在第一个表达式中，u 是可选的（由于 * 可以为 0），因此，贪婪的 .* 决定它不会产生任何字符。然后，最后的.*也可以匹配0个字符，同样，不需要给那个组任何字符。

在第二个表达式中，u 是必须的，必须至少出现一次。因此，引擎会抓取第一个 .* 的所有字符串，然后回溯并找到 u。因此，它将起始序列放入第 1 组，并用 (u+) 匹配并捕获 u。由于 u 只有 1，所以最后的 (.*) 匹配并捕获字符串的其余部分。

Answer 2

@stribizhev 的回答几乎解释了一切。至于你的非贪婪版本——末尾的问号告诉引擎它不应该消耗整个字符串，而是抓住尽可能少的匹配并从那里继续。

Answer 3

关于非贪婪。 Tcl 正则表达式有一个怪癖：表达式中的 first 量词设置 whole 表达式的贪婪度。（参见 re_syntax manual page 的 "Matching" 部分，密切注意单词“preference”）：

A branch has the same preference as the first quantified atom in it which has a preference.

%regexp -inline (.*?)(n+)(.*) ennui
en e n {}

第一个子表达式从第一个字符开始匹配，但不包括第一个 n。第二部分匹配一个n。第三部分匹配第一个和第二个之间的零个字符 n.

我有点惊讶第一个子表达式捕获了一个 e 而不是在第一个 n 之前捕获了零个字符，但这可以用 [=50= 的更高优先级来解释] 与正则表达式引擎匹配：

In the event that an RE could match more than one substring of a given string, the RE matches the one starting earliest in the string.

锚定表达式的结果也让我感到惊讶：我本以为 e n nui 而不是 e nn ui。添加 $ 锚点似乎已经放弃了表达式对最短匹配的偏好。

Tcl greedy subexpression difference between + and *