1<html> 2<head> 3<title>pcre2matching specification</title> 4</head> 5<body bgcolor="#FFFFFF" text="#00005A" link="#0066FF" alink="#3399FF" vlink="#2222BB"> 6<h1>pcre2matching man page</h1> 7<p> 8Return to the <a href="index.html">PCRE2 index page</a>. 9</p> 10<p> 11This page is part of the PCRE2 HTML documentation. It was generated 12automatically from the original man page. If there is any nonsense in it, 13please consult the man page, in case the conversion went wrong. 14<br> 15<ul> 16<li><a name="TOC1" href="#SEC1">PCRE2 MATCHING ALGORITHMS</a> 17<li><a name="TOC2" href="#SEC2">REGULAR EXPRESSIONS AS TREES</a> 18<li><a name="TOC3" href="#SEC3">THE STANDARD MATCHING ALGORITHM</a> 19<li><a name="TOC4" href="#SEC4">THE ALTERNATIVE MATCHING ALGORITHM</a> 20<li><a name="TOC5" href="#SEC5">ADVANTAGES OF THE ALTERNATIVE ALGORITHM</a> 21<li><a name="TOC6" href="#SEC6">DISADVANTAGES OF THE ALTERNATIVE ALGORITHM</a> 22<li><a name="TOC7" href="#SEC7">AUTHOR</a> 23<li><a name="TOC8" href="#SEC8">REVISION</a> 24</ul> 25<br><a name="SEC1" href="#TOC1">PCRE2 MATCHING ALGORITHMS</a><br> 26<P> 27This document describes the two different algorithms that are available in 28PCRE2 for matching a compiled regular expression against a given subject 29string. The "standard" algorithm is the one provided by the <b>pcre2_match()</b> 30function. This works in the same as Perl's matching function, and provide a 31Perl-compatible matching operation. The just-in-time (JIT) optimization that is 32described in the 33<a href="pcre2jit.html"><b>pcre2jit</b></a> 34documentation is compatible with this function. 35</P> 36<P> 37An alternative algorithm is provided by the <b>pcre2_dfa_match()</b> function; 38it operates in a different way, and is not Perl-compatible. This alternative 39has advantages and disadvantages compared with the standard algorithm, and 40these are described below. 41</P> 42<P> 43When there is only one possible way in which a given subject string can match a 44pattern, the two algorithms give the same answer. A difference arises, however, 45when there are multiple possibilities. For example, if the pattern 46<pre> 47 ^<.*> 48</pre> 49is matched against the string 50<pre> 51 <something> <something else> <something further> 52</pre> 53there are three possible answers. The standard algorithm finds only one of 54them, whereas the alternative algorithm finds all three. 55</P> 56<br><a name="SEC2" href="#TOC1">REGULAR EXPRESSIONS AS TREES</a><br> 57<P> 58The set of strings that are matched by a regular expression can be represented 59as a tree structure. An unlimited repetition in the pattern makes the tree of 60infinite size, but it is still a tree. Matching the pattern to a given subject 61string (from a given starting point) can be thought of as a search of the tree. 62There are two ways to search a tree: depth-first and breadth-first, and these 63correspond to the two matching algorithms provided by PCRE2. 64</P> 65<br><a name="SEC3" href="#TOC1">THE STANDARD MATCHING ALGORITHM</a><br> 66<P> 67In the terminology of Jeffrey Friedl's book "Mastering Regular Expressions", 68the standard algorithm is an "NFA algorithm". It conducts a depth-first search 69of the pattern tree. That is, it proceeds along a single path through the tree, 70checking that the subject matches what is required. When there is a mismatch, 71the algorithm tries any alternatives at the current point, and if they all 72fail, it backs up to the previous branch point in the tree, and tries the next 73alternative branch at that level. This often involves backing up (moving to the 74left) in the subject string as well. The order in which repetition branches are 75tried is controlled by the greedy or ungreedy nature of the quantifier. 76</P> 77<P> 78If a leaf node is reached, a matching string has been found, and at that point 79the algorithm stops. Thus, if there is more than one possible match, this 80algorithm returns the first one that it finds. Whether this is the shortest, 81the longest, or some intermediate length depends on the way the alternations 82and the greedy or ungreedy repetition quantifiers are specified in the 83pattern. 84</P> 85<P> 86Because it ends up with a single path through the tree, it is relatively 87straightforward for this algorithm to keep track of the substrings that are 88matched by portions of the pattern in parentheses. This provides support for 89capturing parentheses and backreferences. 90</P> 91<br><a name="SEC4" href="#TOC1">THE ALTERNATIVE MATCHING ALGORITHM</a><br> 92<P> 93This algorithm conducts a breadth-first search of the tree. Starting from the 94first matching point in the subject, it scans the subject string from left to 95right, once, character by character, and as it does this, it remembers all the 96paths through the tree that represent valid matches. In Friedl's terminology, 97this is a kind of "DFA algorithm", though it is not implemented as a 98traditional finite state machine (it keeps multiple states active 99simultaneously). 100</P> 101<P> 102Although the general principle of this matching algorithm is that it scans the 103subject string only once, without backtracking, there is one exception: when a 104lookaround assertion is encountered, the characters following or preceding the 105current point have to be independently inspected. 106</P> 107<P> 108The scan continues until either the end of the subject is reached, or there are 109no more unterminated paths. At this point, terminated paths represent the 110different matching possibilities (if there are none, the match has failed). 111Thus, if there is more than one possible match, this algorithm finds all of 112them, and in particular, it finds the longest. The matches are returned in 113the output vector in decreasing order of length. There is an option to stop the 114algorithm after the first match (which is necessarily the shortest) is found. 115</P> 116<P> 117Note that the size of vector needed to contain all the results depends on the 118number of simultaneous matches, not on the number of parentheses in the 119pattern. Using <b>pcre2_match_data_create_from_pattern()</b> to create the match 120data block is therefore not advisable when doing DFA matching. 121</P> 122<P> 123Note also that all the matches that are found start at the same point in the 124subject. If the pattern 125<pre> 126 cat(er(pillar)?)? 127</pre> 128is matched against the string "the caterpillar catchment", the result is the 129three strings "caterpillar", "cater", and "cat" that start at the fifth 130character of the subject. The algorithm does not automatically move on to find 131matches that start at later positions. 132</P> 133<P> 134PCRE2's "auto-possessification" optimization usually applies to character 135repeats at the end of a pattern (as well as internally). For example, the 136pattern "a\d+" is compiled as if it were "a\d++" because there is no point 137even considering the possibility of backtracking into the repeated digits. For 138DFA matching, this means that only one possible match is found. If you really 139do want multiple matches in such cases, either use an ungreedy repeat 140("a\d+?") or set the PCRE2_NO_AUTO_POSSESS option when compiling. 141</P> 142<P> 143There are a number of features of PCRE2 regular expressions that are not 144supported or behave differently in the alternative matching function. Those 145that are not supported cause an error if encountered. 146</P> 147<P> 1481. Because the algorithm finds all possible matches, the greedy or ungreedy 149nature of repetition quantifiers is not relevant (though it may affect 150auto-possessification, as just described). During matching, greedy and ungreedy 151quantifiers are treated in exactly the same way. However, possessive 152quantifiers can make a difference when what follows could also match what is 153quantified, for example in a pattern like this: 154<pre> 155 ^a++\w! 156</pre> 157This pattern matches "aaab!" but not "aaa!", which would be matched by a 158non-possessive quantifier. Similarly, if an atomic group is present, it is 159matched as if it were a standalone pattern at the current point, and the 160longest match is then "locked in" for the rest of the overall pattern. 161</P> 162<P> 1632. When dealing with multiple paths through the tree simultaneously, it is not 164straightforward to keep track of captured substrings for the different matching 165possibilities, and PCRE2's implementation of this algorithm does not attempt to 166do this. This means that no captured substrings are available. 167</P> 168<P> 1693. Because no substrings are captured, backreferences within the pattern are 170not supported. 171</P> 172<P> 1734. For the same reason, conditional expressions that use a backreference as the 174condition or test for a specific group recursion are not supported. 175</P> 176<P> 1775. Again for the same reason, script runs are not supported. 178</P> 179<P> 1806. Because many paths through the tree may be active, the \K escape sequence, 181which resets the start of the match when encountered (but may be on some paths 182and not on others), is not supported. 183</P> 184<P> 1857. Callouts are supported, but the value of the <i>capture_top</i> field is 186always 1, and the value of the <i>capture_last</i> field is always 0. 187</P> 188<P> 1898. The \C escape sequence, which (in the standard algorithm) always matches a 190single code unit, even in a UTF mode, is not supported in these modes, because 191the alternative algorithm moves through the subject string one character (not 192code unit) at a time, for all active paths through the tree. 193</P> 194<P> 1959. Except for (*FAIL), the backtracking control verbs such as (*PRUNE) are not 196supported. (*FAIL) is supported, and behaves like a failing negative assertion. 197</P> 198<P> 19910. The PCRE2_MATCH_INVALID_UTF option for <b>pcre2_compile()</b> is not 200supported by <b>pcre2_dfa_match()</b>. 201</P> 202<br><a name="SEC5" href="#TOC1">ADVANTAGES OF THE ALTERNATIVE ALGORITHM</a><br> 203<P> 204The main advantage of the alternative algorithm is that all possible matches 205(at a single point in the subject) are automatically found, and in particular, 206the longest match is found. To find more than one match at the same point using 207the standard algorithm, you have to do kludgy things with callouts. 208</P> 209<P> 210Partial matching is possible with this algorithm, though it has some 211limitations. The 212<a href="pcre2partial.html"><b>pcre2partial</b></a> 213documentation gives details of partial matching and discusses multi-segment 214matching. 215</P> 216<br><a name="SEC6" href="#TOC1">DISADVANTAGES OF THE ALTERNATIVE ALGORITHM</a><br> 217<P> 218The alternative algorithm suffers from a number of disadvantages: 219</P> 220<P> 2211. It is substantially slower than the standard algorithm. This is partly 222because it has to search for all possible matches, but is also because it is 223less susceptible to optimization. 224</P> 225<P> 2262. Capturing parentheses, backreferences, script runs, and matching within 227invalid UTF string are not supported. 228</P> 229<P> 2303. Although atomic groups are supported, their use does not provide the 231performance advantage that it does for the standard algorithm. 232</P> 233<P> 2344. JIT optimization is not supported. 235</P> 236<br><a name="SEC7" href="#TOC1">AUTHOR</a><br> 237<P> 238Philip Hazel 239<br> 240Retired from University Computing Service 241<br> 242Cambridge, England. 243<br> 244</P> 245<br><a name="SEC8" href="#TOC1">REVISION</a><br> 246<P> 247Last updated: 19 January 2024 248<br> 249Copyright © 1997-2024 University of Cambridge. 250<br> 251<p> 252Return to the <a href="index.html">PCRE2 index page</a>. 253</p> 254