Efficiency of using regular expressions in PHP Detailed explanation of greedy, non-greedy and backtracking (with code)

This time I will bring you a detailed explanation of the efficient greedy, non-greedy and backtracking of using regularity in PHP (with code), and the efficiency greedy, non-greedy and backtracking of using regularity in PHPNotes What are they? Here are actual cases. Let’s take a look.

Let’s first understand what greed is in regular expressions, and what is non-greedy? Or what is matching priority quantifier and what is ignoring priority quantifier?

Okay, I don’t know what the concept is, let’s give an example.

A student wanted to filter the content between them. This is how he wrote the regular rules and procedures.

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

It seems that there is no problem, but in fact it is not. If

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

, then after the above program processing, the result is

$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>

still cannot achieve the desired effect. The above is non-greed, and some are called laziness. The non-greedy sign is the quantity meta character followed by ?, such as +?, *?, ?? (more special, I will write about it in future blogs), etc. That means non-greedy. If you don’t write ?, it means greedy. For example,

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

The above is an introduction to the difference between greedy and non-greedy. Next, let’s talk about backtracking problems caused by greed and non-greed. Let’s look at a small example first.

The regular expression is \w*(\d+), The string is cfc456n, then, what is the $1 matched by this regular expression? ?

If your answer is 456, then congratulations, your answer is wrong. The result is not 456, but 6. Do you know why?

CFC4N will explain that when the regular engine uses regular \w*(\d+) to match the string cfc456n, it will first use \w* to match the string cfc456n. First, \w* will match the character All the characters in the string cfc456n are then handed over to \d+ to match the remaining string, and the rest is gone. At this time, the \w* rule will reluctantly spit out a character for \d+ to match. At the same time, Before spitting out characters, record a point. This point is the point used for backtracking. Then \d+ matches n. If it is found that the match cannot be successful, \w* will be asked to spit out another character again. \w* will record it again first. A point to backtrack and spit out one more character. At this time, the matching result of \w* is only cfc45, and 6n has been spit out. \d+ matches 6 again. If it is found that the match is successful, the engine will be notified that the match is successful, and it will be displayed directly. Therefore, the result of (\d+) is 6, not 456.

When the above regular expression is changed to \w*?(\d+) (note that this is non-greedy), the string is still cfc456n. So, at this time, what is the $1 of the regular match? ?

Student A answered: The result is 456.

Well, yes, correct, it is 456. CFC4N would like to ask, why is it 456?

Let me explain why it is 456

There is a rule in regular expressions that quantifiers are matched first, so \w*? will match the string cfc456 first, because \w*? Whether greedy or not, the regular engine will use the expression \w+? to only match one string at a time, and then transfer control to the following \d+ to match the next character. At the same time, it will record a point for unsuccessful matching. At this time, return here and match again, which is the backtracking point. Since \w is followed by the quantifier *, * represents 0 to countless times, so the first is 0 times, that is, \w*? matches an empty space, records the traceback point, and hands control to \d+,\d+ to match cfc456n The first character c of , then, the matching fails, so the control is handed over to \w*? to match the c of cfc456n, \w*? matches c successfully, because it is not greedy, so it only matches each time A character, record the traceback point, and then give control to \d+match f, then, \d+ match f and fail again, then give control to \w*?, \w*? then match c, record the traceback point ( At this time \w*? The matching result is cfc), and then give control to \d+, \d+ matches 4, and the match is successful. Then, since the quantifier is +, it means 1 to countless times, so it continues to match, Match 5 again, success, then match 6 again, success, then continue the matching operation, the next character is n, the match fails, at this time, \d+ will hand over the control. Since there is no regular expression after \d+, the entire regular expression is declared to be matched, and the result is cfc456, of which the first set of results is 456. Dear classmate, do you understand the result of the question just now, why is it 456?

Okay, have you understood the principles of greedy and non-greedy matching from the above example? Do you understand when you need to use greedy or non-greedy to process your string?

Niao Ge’s article talks about expressions and programs as

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

The reason is that there are too many backtraces, until the stack space is exhausted and the stack explodes.

再来看个例子。

字符串

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

正则表达式为

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

相信看了本文案例你已经掌握了方法，更多精彩请关注php中文网其它相关文章！

推荐阅读：

用正则匹配单个字符的详细解析

正则的位置匹配使用详解

The above is the detailed content of Efficiency of using regular expressions in PHP Detailed explanation of greedy, non-greedy and backtracking (with code). For more information, please follow other related articles on the PHP Chinese website!