CNXCT小组的博客

大清早的打QQ去，收到一位网友的信息。问得是正则表达式判断素数的。去年看到过，没记录下来。
正则表达式如下：

^1?$|^(11+?)\1+$ 可以判断素数（换成n个1的形式，n为数字的大小。比如5转换为11111；3转换为111；2转换为11。）

什么是素数？
初中学的吧。我们老师当初教我们的是“质数”。看下概念：
质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。
换句话说，只有两个正因数（1和自己）的自然数即为素数。比1大但不是素数的数称为合数。1和0既非素数也非合数。

这个正则表达式是什么意思？
【^1?$|^(11+?)\1+$】中间用【|】分开。【|】在正则语法里，表示“或”，作用于其前后两个单元。(还是不明白的看下面，明白的跳过下面这段)

比如【ab|cd】可以匹配“ab”、也可以匹配“cd”，意思是除了“ab”就是“bc”，如果想匹配“abd”、“acd”那【|】的作用域得改下，加个范围
改成【a(b|c)】(匹配结果分配组)或者【a(?:b|c)d】(匹配结果不分配组，更高效率)。

继续刚刚的正则，分为两个分支，其一为【^1?$】和【^(11+?)\1+$】。其中【^】脱字符在正则语法中，除了在中括号【[]】中都是代表开头的意思，在中括号中的表示非。
第一个分支【^1?$】匹配的是“1”或者“”(空字符串)。
第二个分支【^(11+?)\1+$】，先看下括号内的【(11+?)】匹配的是字符“1”后面接着【1+】就是1到无数个1。后面的【?】问号表示非贪婪，就是尽量少的匹配。
接着往后看【\1+】中，【\1】表示引用已匹配的第一个组的结果。也就是第一个【()】括号匹配的结果。同理【\2】就是第二个括号捕获的结果。(小提示：上面提到的【(?:)写法就是不分配组，这样引用的话，就引用不到了】)
【+】就是1到无数个了。这个表达式我们可以这么看。【(11+?)】看成数学中的1+n，其中n为大于0的正整数。外面的【\1+】也就是引用前面这个组的次数。理解成m倍，其中m为大于0的正整数。
那整个表达式就是(1+n)*m。因为n、m都大于0，那么1+n肯定大于1，最小为2，最大为无穷大；m最小为1，最大为无穷大。
那么，一个大于2的正整数的任何大于零的倍数永远都是合数，也就是非素数。

再回过头来看看这个表达式。匹配的分别为0个或1个字符串“1”，也就是数字0，数字1。和其他所有合数。整个表达式，如果成功匹配就是非素数，如果不匹配就是质数。这就是对的了。

if (preg_match('/^1?$|^(11+?)\1+$/i', $subject)) {
	#不是素数
} else {
	# 是素数
}

小提示：此鉴定是否为素数方法仅研究学习用，不能用到正式程序中，字符串过长，会造成非常恐惧大的回溯。

英文博客地址：http://blog.stevenlevithan.com/archives/algebra-with-regexes

在上面的博文中，有提到两个方程式与正则表达式，我们一起来研究下。

• 二元方程17x + 12y = 51，其表达式【^(.*)\1{16}(.*)\2{11}$】。很好理解。【(.*)】也就是0到无数个【.】点号。（这里是接着上文说的，其实，【.】点号想表示的是字符“1”）
  也就是0到无数个1,后面【\1】引用一次。后面【{16}】就是16次。作用于前面的【\1】，也就是16次引用。加上开始的【(.*)】一共正好17次。后面一个就不说了，跟这个一样。
  正则引擎会依次尝试【(.*)】中0到无数个字符“1”，0个字符“1”，1个字符“1”，2个字符“1”一直增加的尝试。直到成功，否则要尝试完所有字符“1”的最大个数(这里是51个字符“1”)。

• 二、三元方程式11x + 2y + 5z = 115，其表达式为【^(.*)\1{10}(.*)\2{1}(.*)\3{4}$】，理解就跟上面那个一样。注意【\2】、【\3】值得是第2，第3个括号捕获的内容，别看花眼了。

——————-分割线——————
上面几个有意思的数学题都是将整数转换为对应个数的字符“1”。下面这个，是转换为二进制数的。
先吃饭，以后再写。

上文中，我们聊到了一点关于PHP中（NFA PCRE）正则表达式匹配优先量词，忽略优先量词的匹配原理了。那么上文留下的问题，您的答案是什么呢？
先来看下问题。

字符串

$str = '<script>123456</script>';

正则表达式为

$strRegex1 = '%<script>.+<\/script>%';
$strRegex2 = '%<script>.+?<\/script>%';
$strRegex3 = '%<script>(?:(?!<\/script>).)+<\/script>%';

这三个正则，分别会造成几次回溯呢？？

答案：

$strRegex1 = '%<script>.+<\/script>%';    //9次，记得区别转义符号。
$strRegex2 = '%<script>.+?<\/script>%';  //5次
$strRegex3 = '%<script>(?:(?!<\/script>).)+<\/script>%';  //7次

对于第一种贪婪匹配的匹配规则，回溯的9次是正则【】对字符串“”匹配时，构成的回溯，回溯的次数，恰好是字符串的长度。
第二种非贪婪匹配规则，回溯5次，是正则【.+?】对字符串“123456”匹配时构成的回溯。回溯的次数，为字符串长度减去最小次数。也就是6-1=5次。如果正则表达式为【.*?】那么，回溯次数就是6次了。
第三种正则是零宽断言，或者叫环视。（暂且不说。）
在NFA正则引擎中，回溯是他的灵魂，所以，不管是贪婪，非贪婪，环视等写法中肯定会有回溯的出现的，这个我们无法避免（用词不太准确），但是，我们可以减少回溯的次数，或者保护其中一部分匹配的规则不进行回溯。

对于上篇BLOG上提到的鸟哥谈到一个非贪婪引起的大量回溯问题，大家可以知道，回溯，确实是浪费资源的罪魁祸首，那么，我们能否不让其回溯呢？
答案是肯定的，NFA引擎中，有个概念，叫固化分组。引用一下书上的概念

具体来说，使用「(?>…)」的匹配与正常的匹配并无差别，但是如果匹配进行到此结构之后（也就是，进行到闭括号之后），那么此结构体中的所有备用状态都会被放弃。也就是说，在固化分组匹配结束时，它已经匹配的文本已经固化为一个单元，只能作为整体而保留或放弃。括号内的子表达式中未尝试过的备用状态都不复存在了，所以回溯永远也不能选择其中的状态（至少是，当此结构匹配完成时，“锁定（locked in）”在其中的状态）。

那么，固化分组到底有什么用处呢？我们来举个例子。（找不到合适的例子，俺只好借用一下书上的例子了）
比如要处理一批数据，原来格式为123.456，后来因为浮点数显示问题，部分数据格式变为123.456000000789这种，，要求做到只保留小数点后面2-3位，但是，最后一位不能为0，这个正则如何写呢？（下面直接考虑小数点后面的数字），写出正则之后，我们还要用这个正则去匹配数据，把原来的数据替换成匹配的结果。
首先，我们可以立刻写出这样的正则【\.\d\d[1-9]?\d*】，PHP代码为

$str = preg_replace('\.(\d\d[1-9]?)\d*','\\1',$str);  //匹配结果的group1进行反向引用

很明显，这种写法，对于部分数据格式为123.456的这种格式，白白的处理了一遍，为了提高效率，我们还要对这个正则进行处理。从123.456这个字符串跟其他的比较一下，我们发现，是疑问123.456这个数据后面没数字了，所以，白白处理一遍。那好办，我们对这个正则改造一下，把后面的量词*改成+，这样对于123.45 小数点后面1，2位数字的，不会去白白处理，而且，对三位以上数字的，处理正常。其PHP代码为

$str = preg_replace('\.(\d\d[1-9]?)\d+','\\1',$str);

好了，这个正则真的没问题吗？？确定吗？上篇博文，我们了解了匹配原理，那么，我们也分析一下这个正则的匹配过程吧。
字符串"123.456",正则表达式为【\.(\d\d[1-9]?)\d+】，我们来看下
首先（小数点前123不说了），【\.】匹配"."，匹配成功，把控制权给下一个【\d】，【\d】匹配“4”成功，把控制权给第二个【\d】，这个【\d】匹配“5”成功，然后，把控制权给了【[1-9]?】，由于量词是【?】，正则表达式遵循“量词优先匹配”，而且，此处是【?】，还会留下一个回溯点。然后匹配"6"成功，然后把控制权给【\d+】，【\d+】发现后面没字符了，最遵循“后进先出”规则，回到上一个回溯点，进行匹配，这时，【[1-9]?】会交还出其匹配的字符“6”，【[1-9]?】匹配“6”成功。匹配完成了。大家发现【(\d\d[1-9]?)】匹配的结果确是"45",并不是我们想要的“456”，“6”被【\d+】匹配去了。那么，我们该如何办呢？ 能否让【[1-9]?】匹配一旦成功，不进行回溯呢？这就用到了我们上面说的"固化分组", PHP（preg_replace函数）中使用的正则引擎支持固化分组，我们根据固化分组的写法，可以把代码改成如下方式

$str = preg_replace('\.(\d\d(?>[1-9]?))\d+','\\1',$str);

改成这样的话，那字符串“123.456“是不符合要求，不会被匹配的。那我们就可以实现我们的要求了。

从上面的例子中，知道了固化分组的作用，那么对于鸟哥BLOG上写的那个非贪婪的回溯问题，我们能否也对其改造，使得其不回溯呢？
先看下鸟哥给的答案

/<script>[^<]*<\/script>/is

鸟哥写的很精悍。排除“<”之外的所有字符都符合，而且，中间部分不回溯，效率高。可是，如果中间有字符“<“的话（如下代码）

<script>
if a < b
</script>

那鸟哥的这个正则就不能匹配，就不能实现我们想要的功能了。
那我们可以根据 固化分组、环视(零宽断言)来实现这个要求，最后，CFC4N给出的正则以及PHP代码事例如下

$reg = '%<script>(?>[^<]*)(?>(?!</?script>)<[^<]*)*</script>%is';
$str = str_pad("<script>", 111111, "*");    //字符长度大于PHP回溯限制的100000
$str .= 'if a < b ; if b > c;</script>';    //随便加几个包含 < > 的测试字符
$ret = preg_replace($reg, "OK", $str);
print_r($ret);                              //打印结果 OK，证明匹配正确
var_dump(preg_last_error());                //上一次匹配错误。其输出为 int(0)

嗨，同学，你看明白了吗？

以上为小菜CFC4N的愚文，如有错误，欢迎指出。

前几天看了鸟哥的BLOG上写的关于正则表达式的回溯与递归的限制时，对贪婪、非贪婪产生的回溯有疑问，遂近段时间，仔细的学习研究了一下，现在把经验心得与大家分享一下。
（我日，这里好像被左侧的图挡着了，换行换行凑字数，换行换行凑字数，换行换行凑字数，换行换行凑字数，换行换行凑字数，换行换行凑字数，换行换行凑字数，换行换行凑字数，换行换行凑字数，换行换行凑字数，换行换行凑字数，换行换行凑字数，换行换行凑字数，换行换行凑字数，换行换行凑字数）
先扫盲一下什么是正则表达式的贪婪，什么是非贪婪？或者说什么是匹配优先量词，什么是忽略优先量词？
好吧，我也不知道概念是什么，来举个例子吧。
某同学想过滤之间的内容，那是这么写正则以及程序的。

$str = preg_replace('%<script>.+?</script>%i','',$str);//非贪婪

看起来，好像没什么问题，其实则不然。若

$str = '<script<script>alert(document.cookie)</script>>alert(document.cookie)</script>';

那么经过上面的程序处理，其结果为

$str = '<script<script>alert(document.cookie)</script>>alert(document.cookie)</script>';
$str = preg_replace('%<script>.+?</script>%i','',$str);//非贪婪
print_r($str);
//$str 输出为 <script>alert(document.cookie)</script>

仍然达不到他想要的效果。上面的就是非贪婪，也有的叫惰性。其标志非贪婪的标识为量数元字符后面加? ，比如 +?、*?、??(比较特殊，以后的BLOG中，我会写到)等。即标识非贪婪，如果不写?就是贪婪。比如

$str = '<script<script>alert(document.cookie)</script>>alert(document.cookie)</script>';
$str = preg_replace('%<script>.+</script>%i','',$str);//非贪婪
print_r($str);
//$str 输出为 <script 只有这些了，好像还是不太合适，哈，您知道如何重写那个正则吗？

以上为贪婪，非贪婪的区别介绍。下面，聊下贪婪、非贪婪引起的回溯问题。先看个小例子。
正则表达式为\w*(\d+)，字符串为cfc456n，那么，这个正则匹配的$1是多少？？

如果您回答是 456,那么，恭喜你，回答错了，其结果不是456，而是6，您知道为什么吗？

CFC4N来解释一下，当正则引擎用正则\w*(\d+)去匹配字符串cfc456n时，会先用\w*去匹配字符串cfc456n，首先，\w*会匹配字符串cfc456n的所有字符，然后再交给\d+去匹配剩下的字符串，而剩下的没了，这时，\w*规则会不情愿的吐出一个字符，给\d+去匹配，同时，在吐出字符之前，记录一个点，这个点，就是用于回溯的点，然后\d+去匹配n，发现并不能匹配成功，会再次要求\w*再吐出一个字符，\w*会先再次记录一个回溯的点，再吐出一个字符。这时，\w* 匹配的结果只有cfc45了，已经吐出6n了，\d+再去匹配6，发现匹配成功，则会通知引擎，匹配成功了，就直接显示出来了。所以，(\d+)的结果是6，而不是456。

当上面的正则表达式改为 \w*?(\d+)（注意，此处为非贪婪），字符串仍然为cfc456n，那么，这时候，正则匹配的$1是多少？？
甲同学回答：结果是 456。
嗯，是的，正确，是456，CFC4N弱弱的问下，为什么是456 呢？
我在来解释一下 为什么是456
正则表达式有条规则，是量词优先匹配，所以\w*?会先去匹配字符串cfc456，由于\w*?是非贪婪，正则引擎会用表达式\w+?每次仅匹配一个字符串,然后再将控制权交给后面的\d+去匹配下一个字符，同时，记录一个点，用于在匹配不成功的时候，返回这里，再次匹配，也就是回溯点。由于\w后面是量词是*，*表示0到无数次，所以，首先是0次，也就是\w*?匹配个空，记录回溯点，将控制权交给\d+,\d+去匹配cfc456n的第一个字符c,然后，匹配失败，于是乎，接着讲控制权交给\w*?去匹配cfc456n的c，\w*?匹配c成功，由于是非贪婪，所以，他每次只匹配一个字符，记录回溯点，然后再将控制权交给\d+匹配f,接着，\d+匹配f再失败，再把控制权给\w*?，\w*?再匹配c,记录回溯点（这时\w*?匹配结果是cfc了），再把控制权给\d+，\d+去匹配4，匹配成功，然后，由于量词是+，就是1到无数次，所以，接着往后匹配，再匹配5，成功，再接着，再匹配6，成功，再接着，继续匹配操作，下一个字符是n，匹配失败，这时，\d+会吧控制权交出去。由于\d+后面已经没有正则表达式了，所以，整个正则表达式宣告匹配完成，其结果就是 cfc456, 其中第一组结果是456。亲爱的同学，您明白刚刚的题目的结果，为什么是456了吗？

好了，您是否从上面的例子了解了贪婪，非贪婪的匹配原理了？那您是否明白您在什么时候需要使用贪婪，非贪婪去处理您的字符串了？
鸟哥的文章里讲到针对
表达式、程序为

$reg = "/<script>.*?<\/script>/is";
$str = "<script>********</script>"; //长度大于100014
$ret = preg_repalce($reg, "", $str); //返回NULL

其原因就是回溯太多了，直到造成耗尽栈空间爆栈。

再来看个例子。
字符串

$str = '<script>123456</script>';

正则表达式为

$strRegex1 = '%<script>.+<\/script>%';
$strRegex2 = '%<script>.+?<\/script>%';
$strRegex3 = '%<script>(?:(?!<\/script>).)+<\/script>%';

这三个正则，分别会造成几次回溯呢？？

答案见下篇 PHP正则表达式的效率：回溯与固化分组