Return to pcrematching.3 CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / pcre / doc

pcre 8.34

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