正则回溯机制

一直没有仔细看这个东西，最近遇到了一点情况，觉得某些条件下还是很实用的

简介

基本信息

回溯机制，在所有的php正则匹配函数中都是存在的

实际上，官方文档给出了警告

我们可以通过var_dump(ini_get('pcre.backtrack_limit'));

正则表达式是什么

下面引用p神的话

正则表达式是一个可以被”有限状态自动机”接受的语言类。

“有限状态自动机”，其拥有有限数量的状态，每个状态可以迁移到零个或多个状态，输入字串决定执行哪个状态的迁移。

而常见的正则引擎，又被细分为DFA（确定性有限状态自动机）与NFA（非确定性有限状态自动机）。他们匹配输入的过程分别是：

DFA: 从起始状态开始，一个字符一个字符地读取输入串，并根据正则来一步步确定至下一个转移状态，直到匹配不上或走完整个输入
NFA：从起始状态开始，一个字符一个字符地读取输入串，并与正则表达式进行匹配，如果匹配不上，则进行回溯，尝试其他状态

由于NFA的执行过程存在回溯，所以其性能会劣于DFA，但它支持更多功能。大多数程序语言都使用了NFA作为正则引擎，其中也包括PHP使用的PCRE库。

条件

php7.3
- 在php7.3之上prce.jit的默认配置为1，官方说法叫使用了PCRE的JIT编译
其他语言待测

测试

测试网站

贪婪匹配

回溯出现于贪婪匹配过多的情况。如匹配串为aaab，匹配子串为.*b，匹配如下：

可以自己去网站看过程，这里就是.*匹配到了所有字符，但是正则表达式并没有走完

所以需要进行回溯

非贪婪匹配

这个时候回溯的次数会更多一些

总结

个人理解

为什么会进行回溯？

在正则表达式没到结尾的时候，字符串已经被匹配完成或者其他

回溯的条件有哪些？

第一点，产生回溯的条件是，正则表达式的子单元（暂且乱叫）需要有两个或者以上，如果只有一个，则正则表达式，直接就匹配完成，有就是有没有就是没有
第二点，前一个子单元匹配的内容需要涵盖后一个子单元

贪婪匹配和非贪婪模式差异

贪婪匹配的回溯是从字符串的最后一位开始回溯的
非贪婪模式是从字符串的第一位开始回溯的

举例

贪婪

1
2
3

if(preg_match('/SELECT.+FROM.+/is', $input)) {
    die('SQL Injection');
}

想要绕过需要在from后面添加垃圾数据

非贪婪

1
2
3

if(preg_match('/SELECT.+?FROM.+/is', $input)) {
    die('SQL Injection');
}

绕过的方式需要反过来

正则回溯机制