作者： CFC4N

CFC4N，现居上海，在美团从事安全防护产品研发，专注网络安全与eBPF，开源项目eCapture作者。喜欢编程、游戏与技术分享，热爱生活，在博客记录技术探索与人生感悟。

PHP正则表达式的效率：回溯与固化分组

PHP正则表达式的效率：回溯与固化分组

上文中，我们聊到了一点关于PHP中（NFA PCRE）正则表达式匹配优先量词，忽略优先量词的匹配原理了。那么上文留下的问题，您的答案是什么呢？先来看下问题。字符串正则表达式为这三个正则，分别会造成几次回溯呢？？答案：对于第一种贪婪匹配的匹配规则，回溯的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代码为很明显，这种写法，对于部分数据格式为123.456的这种格式，白白的处理了一遍，为了提高效率，我们还要对这个正则进行处理。从123.456这个字符串跟其他的比较一下，我们发现，是疑问123.456这个数据后面没数字了，所以，白白处理一遍。那好办，我们对这个正则改造一下，把后面的量词*改成+，这样对于123.45 小数点后面1，2位数字的，不会去白白处理，而且，对三位以上数字的，处理正常。其PHP代码为好了，这个正则真的没问题吗？？确定吗？上篇博文，我们了解了匹配原理，那么，我们也分析一下这个正则的匹配过程吧。字符串"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函数）中使用的正则引擎支持固化分组，我们根据固化分组的写法，可以把代码改成如下方式改成这样的话，那字符串“123.456“是不符合要求，不会被匹配的。那我们就可以实现我们的要求了。从上面的例子中，知道了固化分组的作用，那么对于鸟哥BLOG上写的那个非贪婪的回溯问题，我们能否也对其改造，使得其不回溯呢？先看下鸟哥给的答案鸟哥写的很精悍。排除“

2010-06-21

+10 14 0

小议正则表达式效率：贪婪、非贪婪与回溯

小议正则表达式效率：贪婪、非贪婪与回溯

前几天看了鸟哥的BLOG上写的关于正则表达式的回溯与递归的限制时，对贪婪、非贪婪产生的回溯有疑问，遂近段时间，仔细的学习研究了一下，现在把经验心得与大家分享一下。（我日，这里好像被左侧的图挡着了，换行换行凑字数，换行换行凑字数，换行换行凑字数，换行换行凑字数，换行换行凑字数，换行换行凑字数，换行换行凑字数，换行换行凑字数，换行换行凑字数，换行换行凑字数，换行换行凑字数，换行换行凑字数，换行换行凑字数，换行换行凑字数，换行换行凑字数）先扫盲一下什么是正则表达式的贪婪，什么是非贪婪？或者说什么是匹配优先量词，什么是忽略优先量词？好吧，我也不知道概念是什么，来举个例子吧。某同学想过滤之间的内容，那是这么写正则以及程序的。看起来，好像没什么问题，其实则不然。若那么经过上面的程序处理，其结果为仍然达不到他想要的效果。上面的就是非贪婪，也有的叫惰性。其标志非贪婪的标识为量数元字符后面加? ，比如 +?、*?、??(比较特殊，以后的BLOG中，我会写到)等。即标识非贪婪，如果不写?就是贪婪。比如以上为贪婪，非贪婪的区别介绍。下面，聊下贪婪、非贪婪引起的回溯问题。先看个小例子。正则表达式为\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了吗？好了，您是否从上面的例子了解了贪婪，非贪婪的匹配原理了？那您是否明白您在什么时候需要使用贪婪，非贪婪去处理您的字符串了？鸟哥的文章里讲到针对表达式、程序为其原因就是回溯太多了，直到造成耗尽栈空间爆栈。再来看个例子。字符串正则表达式为这三个正则，分别会造成几次回溯呢？？答案见下篇 PHP正则表达式的效率：回溯与固化分组

2010-06-18

+8 12 0

端午节之后一周总结

端午节之后一周总结

本周主题：瞎扯淡。记下本周（确切的说，是上周）流水账：在当当网上买了本书《精通正则表达式》，送货速度很快，前天晚上下的订单，第二天中午就送到了。值得表扬。姐姐来我这玩，带来了一点粽子，蜜枣馅的，还有煎饼等家乡的特产，非常感谢。陪小外甥再次看了《汽车总动员》，！@#￥#%%￥……￥&%……*…… CNXCT.COM域名已经到期，忘记续费了，还好，GLEON同学没忘记，悄悄的续费了。端午在家看了新买的书《精通正则表达式》，直接从第四章匹配原理开始看，因为我买书的主要原因是想知道匹配原理。还有就是仔细的看了在非贪婪、贪婪的情况下，匹配时候的回溯详情，匹配的优先顺序，回溯的次数，效率等情况。致力做到不光写得出正则，还要写的出高效率的正则表达式最近比较懒，从过年回来，基本没运动过，上上上周，打了羽毛球。总共运动时间大约20分钟，其中，大部分时间是捡球，羽毛球老是被我抽到树枝上。想办法把羽毛球取下来，也是件麻烦事。周围没有很长的竹竿，树枝之类东西，只好从地上捡起石块砸。结果，右手胳膊酸了一周。昨天，跟几个朋友一起打升级。由于右手一直轻轻的拿鼠标，没有那么用力的捏牌，结果，今天胳膊又酸了。CFC4N想弱弱的问，难道打升级也算运动？昨天，把床上铺的床单取掉了，直接躺在竹席上，结果，夜里肚子被冰的很痛，一夜没睡好，结果，现在精神状态很差。今天看到还算是比较轰动的IT新闻，马化腾马云收编草根网站互联网大佬争夺站长，新闻的主要内容是腾讯收购草根的IT公司康盛创想，其主打产品是Discuz！，不知道是真还是假。很多网友都调侃说到“期待使用’QQ PassPort‘登陆各大BBS”，我稍微想了一下，如果实现，应该也不难。CFC4N想了一个方案，各位网友来批评指正一下。腾讯可以做一个系统，各大论坛使用者提交论坛的主域名，腾讯再根据论坛使用者的主域名分配一个私钥，然后，论坛使用者将此私钥更改到论坛程序的认证部分文件中。当用户在其中的论坛用QQ登陆的时候，直接跳转到腾讯的登陆页，登陆成功之后，返回到用户登陆前的论坛，论坛再根据私钥来解密cookie，来判断此cookie是否生效。无意中发现google对我们的BLOG www.cnxct.com 的快照更新了，而某度却还是那样。详情见下图呃。差点忘了，刚刚从QQ网络硬盘里，找出N年前收藏的工具SPXInstantScreenCapture，试用截图了，效果就是上图。其中，百度截图那张，有水印。原因是没注册，其实我有别人的注册码，只是我没用，打算中午用OD自己破解一下，很久不搞，基本的反汇编工具都生疏了。温习一下。

2010-06-17

1 0

coolcode转SyntaxHighlighter与Mysql正则表达式

coolcode转SyntaxHighlighter与Mysql正则表达式

blog的代码高亮插件原来是coolcode的，coolcode的高亮插件确实很酷，显示效果也很棒，但是占用的位子太大了。最近，我抽空改成SyntaxHighlighter。由于coolcode插件的开头标签是或者[coolcode]这样的，而SyntaxHighlighter是这样的（或者其他）。遂只能想办法把老的格式转化成新的格式。当然，肯定用到正则表达式了。原来的代码高亮开头标识为这种类型的，而SyntaxHighlighter的标识为那根据要求写的正则表达式为解释一下 [a-z]+ 匹配 php,javascript,cpp,sql,css 等，后面的.*?中的 .表示任何除了换行之外的字符，而*表示0次或者无数次，*+这些表述次数的符号后面接的?标识非贪婪模式看图，这个正则可以实现上述要求了。但是，问题还没解决，我们还有一种情况没考虑，那就是后面不一定接的就是lang="php"这样的属性啊，有可能是download，也有可能是linenum="on/off"啊，所以，我们的正则还需要改。 CFC4N把正则改为截图如下细心的朋友可能看出来图中匹配的红色框内多出了，意思也就是说，前面的需要排除掉。如何排除呢？聪明的你肯定立刻想到.这个万能字符替换成非两个符号的规则，好，CFC4N立刻修改一下。修改之后的正则为果然，匹配正常了。结果见截图。到这里，问题似乎解决了，可是，当初糊涂的我，把coolcode的两种开头标识都用了，那就是和[coolcode，那么，看官您认为这个正则该如何改写呢？没错，无非就是开头，结尾的标识考虑两种情况

2010-06-02

+2 6 0

CFC4N小试正则表达式

CFC4N小试正则表达式

朋友甲：要求根据一串字符串，反转成PHP数组，其给出的字符串为php的print_r打印出来的。我们在暂不考虑此方法是否能确保数据的准确性，以及其他意外等情况，仅根据要求写正则。其字符串为 CFC4N给出一下结果：结果是可以用的。但是发现其只能用于固定的三层嵌套，假如N层的话，无法用这个函数了，后来，我又改造一下那个正则，改为但是，并不能解决问题。。各位看官，您认为，我的误区在哪里呢？附第一个正则截图更改后正则匹配截图朋友乙：要求批量给html字符串中a标签中不包含title属性的标签添加title，而且，其title内容为<a href...>到</a>之间的文本。。 CFC4N给出答案为: 各位看官，您认为，CFC4N写的正则表达式里，哪些还可以优化呢？这个效率是不是不高？？朋友丙:要求过滤非本域名，或者非本子域名的其他域名的UBB标签链接，一旦包含，直接替换成其中间的文本，比如例子字符串如下其中，字符串中不确定有几个换行等其他字符，而且，不确定url的UBB标签中的网址中是否包含http://，不确定二级域名或者三级域名 CFC4N给出的正则以及PHP代码如下各位看官，您认为这里哪里是多余的？还可以进行哪些正则的优化来提高效率?如果没看懂，那您的疑问在哪里？朋友丁:要求读取squid的配置文件中，起作用的行，也就是没有#开头进行注释的行。其中，squid的配置文件内字符串见附件中 squid的配置文件内容 CFC4N给出正则代码如下运行截图看官们，您认为，这个正则还有哪些没注意到的点？能否正确无误的匹配到朋友丁所需要的内容？您有疑问吗？ PS：以上正则，均为PCRE引擎。。其中，PHP代码的正则递归(迭代)部分，仅限于支持递归正则的引擎代码适用。。感谢rex老大指点关于(?!)零宽断言非匹配的特性后接匹配规则可能无效的问题。

2010-05-31

3 0

Discuz7.2的暴露网站所在路径的BUG

Discuz7.2的暴露网站所在路径的BUG

报错信息： Warning: sprintf() [function.sprintf]: Too few arguments in ....\include\discuzcode.func.php on line 369 漏洞位置: \include\discuzcode.func.php 369行附近函数名称： Discuz自定义的bbcodeurl函数，此函数中使用了PHP自带的函数sprintf 漏洞原因：当用户在发帖的时候，选择使用远程图片地址，且指定了图片的宽，高，且URL中包含%百分号（比如汉字URL编码）的时候，被discuzcode.func.php程序中的discuzcode函数处理。在discuzcode函数处理图片的URL的正则替换部分，用parseimg函数进行处理，parseimg函数的三个参数全部是正则匹配的结果，三个参数依次是宽，高，URL地址。paeseimg函数又调用了bbcodeurl函数处理，并把匹配的URL当作bbcodeurl函数的第二个参数的一部分，交给bbcodeurl函数处理。的sprintf 函数的第一个参数来自用户输入的数据，程序在使用bbcodeurl函数的时候，没有检测用户输入的数据，直接把用户输入的数据作为自己参数的一部分，也就是$tags参数了。bbcodeurl函数用了sprintf函数进行字符串格式化。$tags又是第一个参数，其中，$tags字符串中的%号是格式化字符串的保留字符，以为着有几个单独的%号，就必须后接几个参数。由于程序没有判断$tags中包含几个单独的百分号，后面的参数也是固定的两个，如果URL中包含百分号的话，则导致参数的个数不对，报Warning错，就暴露了程序所在服务器的路径了(config.inc.php中的$errorreport变量限制了错误报告的对象，默认只允许报告给版主，管理人员)。影响版本： Discuz!7.2 (我只测试了这个版本) 现在时间： 2010-05-13 17:43 修复方法：等待官方补丁或者转义【%】字符即可。。临时解决办法： discuzcode.func.php中bbcodeurl函数改成如下

2010-05-13

1 0

Visual Studio 2010 全部五部广告视频。让爱延长、幸福也需要敏捷、当爱有了debug、让爱编译通过

Visual Studio 2010 全部五部广告视频。让爱延长、幸福也需要敏捷、当爱有了debug、让爱编译通过

继《Visual Studio仿优乐美广告》之后第二弹《让爱延长》煽情广告又放出啦。其男女主角都没变。女主角依然那么PL，广大程序员宅男们，接着内牛满面啊。。。。第一弹《想做你的Code》第二弹《让爱延长》第三弹《幸福也需要敏捷》第四弹《当爱有了debug》第五弹《让爱编译通过》台词：妈妈说：你什么都好，就不该是个程序员…… 完结了，不知道还有没有 Visual Studio 2010 第六弹呢？？？？

2010-04-30

2 0

让我等程序员内牛满面的视频_Visual Studio最新广告_仿优乐美广告

让我等程序员内牛满面的视频_Visual Studio最新广告_仿优乐美广告

介绍 Visual Studio2010发布了最新的广告.大打程序员煽情…… 也算是开发软件推广的一次有益尝试。至少，身为程序员的我看的内牛满面.. 下面,大家看视频吧! 内牛满面啊!!!! 做你下一行的 Code 让程序员内牛满面的Visual Studio2010 广告视频! 附:CNbeta经典评论优乐美1 原来我是你的代码啊？那样我就可以每天都打你了～优乐美2 女:我是你的什么? 男:你是我的CODE啊! 女:原来我是CODE啊?! 男:这样,我就可以天天打你了! 总结看了这广告，我决定扔了VS，去找个女友了

2010-03-26

4 0

震撼人心的新科技 – Sixth Sense

震撼人心的新科技 – Sixth Sense

美国MIT Media Lab（麻省理工学院媒体实验室）的天才学生普拉纳夫- (Prarnav Mistry)，发明了一项结合实体世界和虚拟世界的科技，令人又惊又喜；喜的是，对于未來生活，悠游於实体和虚拟之间，将更自由无限，惊的是，对于现今的人们和企业而言，这场演讲是一提醒：「讯息上身，才有未来」。以下是一段视频，长达13分52秒。但是，我相信你一定不会错过任何一秒。哪怕是它有关于科技，演讲人有浓重的印度口音，但是它如此贴近我们的生活，如此关怀人性，努力把人从“机器前的机器”里解放出来，以至于你会目不转睛地看完这段实况，而且遐想翩翩，愿意努力活到22世纪。如果说，Windows系统的图形化界面把人们从Dos系统下解放出来，用更符合直觉和人性的方法让人们对电脑进行操作是一次新技术的跨越的话，那么视频里这套Prarnav Mistry提供的第六感（Sixth Sense)装置，则是另外一次意义更为深远的腾跃。和它相比，目前甚嚣尘上的所谓“物流网”，只是这个新技术的小小注脚，无论在深度还是广度上，都无法与之比拟。网络和电脑技术，终于使得数字世界和现实世界全面融合，人类升级为真正意义上的数位人！新时代就要开始了！更多信息

2010-01-11 0 0

小试P3P协议

小试P3P协议

小试P3P协议,先是抓包163的单点登录过程,研究一下,自己在写试试.....发个截图+抓包文件,以后慢慢研究抓包文件-httpwatch查看

2009-12-09 0 0

最新评论

jeffrey

支持抓取emqx的tls报文么？

w3b5h3ll

不抛弃，不放弃

Zz

可以认为是代理功能吗？最近也在调研这个功能。大鹅项目好像是有类似的逻辑，dns配置 fallback 默认走代理。《ht

CFC4N

参考： https://github.com/gojue/ecapture/discussions/308

Wayne

你好，安卓上想使用eCapture,需要linux内额版本>=5.5 ,目前手上设备只有pixel 5 ,看官方的