正则表达式 贪婪匹配

Question

在学习正则表达式的贪婪匹配时有个疑问。以下面的例子来说,

用 a.*?b 匹配 abaab 得到的结果是 ab和aab。

如果说是尽可能少地匹配a和b之间的字符，不应该是匹配 ab和ab吗？正则表达式匹配字符串的时候，应该是从左到右的匹配吧？
那下面这个例子，

用a*?b（注意，没有.符号） 匹配 abacb
如果按照上面那样匹配的话，应该是得到 ab 和 acb吧，但是结果是 ab 和 b。

搞不太懂，请大神指点指点。感激不尽！

Answer 1

这是因为正则表达式是从左至右回溯匹配的(可能不准确，因为是否回溯是区分DFA引擎与NFA引擎的指标)。

所以正则从左至右匹配，一个个比对，直到找到最短匹配的结果，就把结果摘出，进行下一次匹配。所以你的第一个正则其实是这么匹配的:

从左至右匹配，第一个满足a.*?b的最短匹配自然是ab，然后ab被摘出，继续向后匹配，于是得到第二匹配结果aab。

第二个正则纯粹是你对*的意思理解错了，代表前面字符重复任意次，所以a*?b的最短匹配理应是a重复0次，b重复1次，于是匹配到最后一个b。

有关正则的回溯匹配详解，可以参考: https://zhuanlan.zhihu.com/p/...

Answer 2

可以看一下《高性能JavaScript》第五章理解回溯原理：
第二题，先跳过表达式a*?，表达式b匹配第一个字符'a'失败，回溯，表达式a*?匹配第一个字符'a'成功，继续，表达式b匹配第二个字符'b'成功，得出第一个匹配项 ab；继续匹配，表达式b匹配第三个字符'a'失败，回溯，表达式a*?匹配第三个字符'a'成功，表达式b匹配第四个字符'c'失败，回溯，表达式a*?匹配第四个字符'c'失败，跳过第三个字符'a'，同理跳过第四个字符'c'；继续匹配，表达式b匹配最后一个字符'b'成功，得出第二个匹配项 b。