Elliott Hughes | 5b80804 | 2021-10-01 10:56:10 -0700 | [diff] [blame] | 1 | .TH PCRE2MATCHING 3 "28 August 2021" "PCRE2 10.38" |
| 2 | .SH NAME |
| 3 | PCRE2 - Perl-compatible regular expressions (revised API) |
| 4 | .SH "PCRE2 MATCHING ALGORITHMS" |
| 5 | .rs |
| 6 | .sp |
| 7 | This document describes the two different algorithms that are available in |
| 8 | PCRE2 for matching a compiled regular expression against a given subject |
| 9 | string. The "standard" algorithm is the one provided by the \fBpcre2_match()\fP |
| 10 | function. This works in the same as as Perl's matching function, and provide a |
| 11 | Perl-compatible matching operation. The just-in-time (JIT) optimization that is |
| 12 | described in the |
| 13 | .\" HREF |
| 14 | \fBpcre2jit\fP |
| 15 | .\" |
| 16 | documentation is compatible with this function. |
| 17 | .P |
| 18 | An alternative algorithm is provided by the \fBpcre2_dfa_match()\fP function; |
| 19 | it operates in a different way, and is not Perl-compatible. This alternative |
| 20 | has advantages and disadvantages compared with the standard algorithm, and |
| 21 | these are described below. |
| 22 | .P |
| 23 | When there is only one possible way in which a given subject string can match a |
| 24 | pattern, the two algorithms give the same answer. A difference arises, however, |
| 25 | when there are multiple possibilities. For example, if the pattern |
| 26 | .sp |
| 27 | ^<.*> |
| 28 | .sp |
| 29 | is matched against the string |
| 30 | .sp |
| 31 | <something> <something else> <something further> |
| 32 | .sp |
| 33 | there are three possible answers. The standard algorithm finds only one of |
| 34 | them, whereas the alternative algorithm finds all three. |
| 35 | . |
| 36 | . |
| 37 | .SH "REGULAR EXPRESSIONS AS TREES" |
| 38 | .rs |
| 39 | .sp |
| 40 | The set of strings that are matched by a regular expression can be represented |
| 41 | as a tree structure. An unlimited repetition in the pattern makes the tree of |
| 42 | infinite size, but it is still a tree. Matching the pattern to a given subject |
| 43 | string (from a given starting point) can be thought of as a search of the tree. |
| 44 | There are two ways to search a tree: depth-first and breadth-first, and these |
| 45 | correspond to the two matching algorithms provided by PCRE2. |
| 46 | . |
| 47 | . |
| 48 | .SH "THE STANDARD MATCHING ALGORITHM" |
| 49 | .rs |
| 50 | .sp |
| 51 | In the terminology of Jeffrey Friedl's book "Mastering Regular Expressions", |
| 52 | the standard algorithm is an "NFA algorithm". It conducts a depth-first search |
| 53 | of the pattern tree. That is, it proceeds along a single path through the tree, |
| 54 | checking that the subject matches what is required. When there is a mismatch, |
| 55 | the algorithm tries any alternatives at the current point, and if they all |
| 56 | fail, it backs up to the previous branch point in the tree, and tries the next |
| 57 | alternative branch at that level. This often involves backing up (moving to the |
| 58 | left) in the subject string as well. The order in which repetition branches are |
| 59 | tried is controlled by the greedy or ungreedy nature of the quantifier. |
| 60 | .P |
| 61 | If a leaf node is reached, a matching string has been found, and at that point |
| 62 | the algorithm stops. Thus, if there is more than one possible match, this |
| 63 | algorithm returns the first one that it finds. Whether this is the shortest, |
| 64 | the longest, or some intermediate length depends on the way the alternations |
| 65 | and the greedy or ungreedy repetition quantifiers are specified in the |
| 66 | pattern. |
| 67 | .P |
| 68 | Because it ends up with a single path through the tree, it is relatively |
| 69 | straightforward for this algorithm to keep track of the substrings that are |
| 70 | matched by portions of the pattern in parentheses. This provides support for |
| 71 | capturing parentheses and backreferences. |
| 72 | . |
| 73 | . |
| 74 | .SH "THE ALTERNATIVE MATCHING ALGORITHM" |
| 75 | .rs |
| 76 | .sp |
| 77 | This algorithm conducts a breadth-first search of the tree. Starting from the |
| 78 | first matching point in the subject, it scans the subject string from left to |
| 79 | right, once, character by character, and as it does this, it remembers all the |
| 80 | paths through the tree that represent valid matches. In Friedl's terminology, |
| 81 | this is a kind of "DFA algorithm", though it is not implemented as a |
| 82 | traditional finite state machine (it keeps multiple states active |
| 83 | simultaneously). |
| 84 | .P |
| 85 | Although the general principle of this matching algorithm is that it scans the |
| 86 | subject string only once, without backtracking, there is one exception: when a |
| 87 | lookaround assertion is encountered, the characters following or preceding the |
| 88 | current point have to be independently inspected. |
| 89 | .P |
| 90 | The scan continues until either the end of the subject is reached, or there are |
| 91 | no more unterminated paths. At this point, terminated paths represent the |
| 92 | different matching possibilities (if there are none, the match has failed). |
| 93 | Thus, if there is more than one possible match, this algorithm finds all of |
| 94 | them, and in particular, it finds the longest. The matches are returned in |
| 95 | the output vector in decreasing order of length. There is an option to stop the |
| 96 | algorithm after the first match (which is necessarily the shortest) is found. |
| 97 | .P |
| 98 | Note that the size of vector needed to contain all the results depends on the |
| 99 | number of simultaneous matches, not on the number of parentheses in the |
| 100 | pattern. Using \fBpcre2_match_data_create_from_pattern()\fP to create the match |
| 101 | data block is therefore not advisable when doing DFA matching. |
| 102 | .P |
| 103 | Note also that all the matches that are found start at the same point in the |
| 104 | subject. If the pattern |
| 105 | .sp |
| 106 | cat(er(pillar)?)? |
| 107 | .sp |
| 108 | is matched against the string "the caterpillar catchment", the result is the |
| 109 | three strings "caterpillar", "cater", and "cat" that start at the fifth |
| 110 | character of the subject. The algorithm does not automatically move on to find |
| 111 | matches that start at later positions. |
| 112 | .P |
| 113 | PCRE2's "auto-possessification" optimization usually applies to character |
| 114 | repeats at the end of a pattern (as well as internally). For example, the |
| 115 | pattern "a\ed+" is compiled as if it were "a\ed++" because there is no point |
| 116 | even considering the possibility of backtracking into the repeated digits. For |
| 117 | DFA matching, this means that only one possible match is found. If you really |
| 118 | do want multiple matches in such cases, either use an ungreedy repeat |
| 119 | ("a\ed+?") or set the PCRE2_NO_AUTO_POSSESS option when compiling. |
| 120 | .P |
| 121 | There are a number of features of PCRE2 regular expressions that are not |
| 122 | supported or behave differently in the alternative matching function. Those |
| 123 | that are not supported cause an error if encountered. |
| 124 | .P |
| 125 | 1. Because the algorithm finds all possible matches, the greedy or ungreedy |
| 126 | nature of repetition quantifiers is not relevant (though it may affect |
| 127 | auto-possessification, as just described). During matching, greedy and ungreedy |
| 128 | quantifiers are treated in exactly the same way. However, possessive |
| 129 | quantifiers can make a difference when what follows could also match what is |
| 130 | quantified, for example in a pattern like this: |
| 131 | .sp |
| 132 | ^a++\ew! |
| 133 | .sp |
| 134 | This pattern matches "aaab!" but not "aaa!", which would be matched by a |
| 135 | non-possessive quantifier. Similarly, if an atomic group is present, it is |
| 136 | matched as if it were a standalone pattern at the current point, and the |
| 137 | longest match is then "locked in" for the rest of the overall pattern. |
| 138 | .P |
| 139 | 2. When dealing with multiple paths through the tree simultaneously, it is not |
| 140 | straightforward to keep track of captured substrings for the different matching |
| 141 | possibilities, and PCRE2's implementation of this algorithm does not attempt to |
| 142 | do this. This means that no captured substrings are available. |
| 143 | .P |
| 144 | 3. Because no substrings are captured, backreferences within the pattern are |
| 145 | not supported. |
| 146 | .P |
| 147 | 4. For the same reason, conditional expressions that use a backreference as the |
| 148 | condition or test for a specific group recursion are not supported. |
| 149 | .P |
| 150 | 5. Again for the same reason, script runs are not supported. |
| 151 | .P |
| 152 | 6. Because many paths through the tree may be active, the \eK escape sequence, |
| 153 | which resets the start of the match when encountered (but may be on some paths |
| 154 | and not on others), is not supported. |
| 155 | .P |
| 156 | 7. Callouts are supported, but the value of the \fIcapture_top\fP field is |
| 157 | always 1, and the value of the \fIcapture_last\fP field is always 0. |
| 158 | .P |
| 159 | 8. The \eC escape sequence, which (in the standard algorithm) always matches a |
| 160 | single code unit, even in a UTF mode, is not supported in these modes, because |
| 161 | the alternative algorithm moves through the subject string one character (not |
| 162 | code unit) at a time, for all active paths through the tree. |
| 163 | .P |
| 164 | 9. Except for (*FAIL), the backtracking control verbs such as (*PRUNE) are not |
| 165 | supported. (*FAIL) is supported, and behaves like a failing negative assertion. |
| 166 | .P |
| 167 | 10. The PCRE2_MATCH_INVALID_UTF option for \fBpcre2_compile()\fP is not |
| 168 | supported by \fBpcre2_dfa_match()\fP. |
| 169 | . |
| 170 | . |
| 171 | .SH "ADVANTAGES OF THE ALTERNATIVE ALGORITHM" |
| 172 | .rs |
| 173 | .sp |
| 174 | The main advantage of the alternative algorithm is that all possible matches |
| 175 | (at a single point in the subject) are automatically found, and in particular, |
| 176 | the longest match is found. To find more than one match at the same point using |
| 177 | the standard algorithm, you have to do kludgy things with callouts. |
| 178 | .P |
| 179 | Partial matching is possible with this algorithm, though it has some |
| 180 | limitations. The |
| 181 | .\" HREF |
| 182 | \fBpcre2partial\fP |
| 183 | .\" |
| 184 | documentation gives details of partial matching and discusses multi-segment |
| 185 | matching. |
| 186 | . |
| 187 | . |
| 188 | .SH "DISADVANTAGES OF THE ALTERNATIVE ALGORITHM" |
| 189 | .rs |
| 190 | .sp |
| 191 | The alternative algorithm suffers from a number of disadvantages: |
| 192 | .P |
| 193 | 1. It is substantially slower than the standard algorithm. This is partly |
| 194 | because it has to search for all possible matches, but is also because it is |
| 195 | less susceptible to optimization. |
| 196 | .P |
| 197 | 2. Capturing parentheses, backreferences, script runs, and matching within |
| 198 | invalid UTF string are not supported. |
| 199 | .P |
| 200 | 3. Although atomic groups are supported, their use does not provide the |
| 201 | performance advantage that it does for the standard algorithm. |
| 202 | .P |
| 203 | 4. JIT optimization is not supported. |
| 204 | . |
| 205 | . |
| 206 | .SH AUTHOR |
| 207 | .rs |
| 208 | .sp |
| 209 | .nf |
| 210 | Philip Hazel |
| 211 | Retired from University Computing Service |
| 212 | Cambridge, England. |
| 213 | .fi |
| 214 | . |
| 215 | . |
| 216 | .SH REVISION |
| 217 | .rs |
| 218 | .sp |
| 219 | .nf |
| 220 | Last updated: 28 August 2021 |
| 221 | Copyright (c) 1997-2021 University of Cambridge. |
| 222 | .fi |