Annotation of embedaddon/pcre/doc/pcrematching.3, revision 1.1.1.3

1.1.1.3 ! misho       1: .TH PCREMATCHING 3 "08 January 2012" "PCRE 8.30"
1.1       misho       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
1.1.1.2   misho       9: "standard" algorithm is the one provided by the \fBpcre_exec()\fP and
                     10: \fBpcre16_exec()\fP functions. These work in the same was as Perl's matching
                     11: function, and provide a Perl-compatible matching operation. The just-in-time
                     12: (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 and
                     19: \fBpcre16_dfa_exec()\fP functions; they operate in a different way, and are not
                     20: Perl-compatible. This alternative has advantages and disadvantages compared
                     21: with the standard algorithm, and these are described below.
1.1       misho      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: .
1.1.1.2   misho      36: .
1.1       misho      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 PCRE.
                     46: .
1.1.1.2   misho      47: .
1.1       misho      48: .SH "THE STANDARD MATCHING ALGORITHM"
                     49: .rs
                     50: .sp
                     51: In the terminology of Jeffrey Friedl's book "Mastering Regular
                     52: Expressions", the standard algorithm is an "NFA algorithm". It conducts a
                     53: depth-first search of the pattern tree. That is, it proceeds along a single
                     54: path through the tree, checking that the subject matches what is required. When
                     55: there is a mismatch, the algorithm tries any alternatives at the current point,
                     56: and if they all fail, it backs up to the previous branch point in the tree, and
                     57: tries the next alternative branch at that level. This often involves backing up
                     58: (moving to the left) in the subject string as well. The order in which
                     59: repetition branches are tried is controlled by the greedy or ungreedy nature of
                     60: the quantifier.
                     61: .P
                     62: If a leaf node is reached, a matching string has been found, and at that point
                     63: the algorithm stops. Thus, if there is more than one possible match, this
                     64: algorithm returns the first one that it finds. Whether this is the shortest,
                     65: the longest, or some intermediate length depends on the way the greedy and
                     66: ungreedy repetition quantifiers are specified in the 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 back references.
                     72: .
1.1.1.2   misho      73: .
1.1       misho      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: decreasing order of length. There is an option to stop the algorithm after the
                     96: first match (which is necessarily the shortest) is found.
                     97: .P
                     98: Note that all the matches that are found start at the same point in the
                     99: subject. If the pattern
                    100: .sp
                    101:   cat(er(pillar)?)?
                    102: .sp
                    103: is matched against the string "the caterpillar catchment", the result will be
                    104: the three strings "caterpillar", "cater", and "cat" that start at the fifth
                    105: character of the subject. The algorithm does not automatically move on to find
                    106: matches that start at later positions.
                    107: .P
                    108: There are a number of features of PCRE regular expressions that are not
                    109: supported by the alternative matching algorithm. They are as follows:
                    110: .P
                    111: 1. Because the algorithm finds all possible matches, the greedy or ungreedy
                    112: nature of repetition quantifiers is not relevant. Greedy and ungreedy
                    113: quantifiers are treated in exactly the same way. However, possessive
                    114: quantifiers can make a difference when what follows could also match what is
                    115: quantified, for example in a pattern like this:
                    116: .sp
                    117:   ^a++\ew!
                    118: .sp
                    119: This pattern matches "aaab!" but not "aaa!", which would be matched by a
                    120: non-possessive quantifier. Similarly, if an atomic group is present, it is
                    121: matched as if it were a standalone pattern at the current point, and the
                    122: longest match is then "locked in" for the rest of the overall pattern.
                    123: .P
                    124: 2. When dealing with multiple paths through the tree simultaneously, it is not
                    125: straightforward to keep track of captured substrings for the different matching
                    126: possibilities, and PCRE's implementation of this algorithm does not attempt to
                    127: do this. This means that no captured substrings are available.
                    128: .P
                    129: 3. Because no substrings are captured, back references within the pattern are
                    130: not supported, and cause errors if encountered.
                    131: .P
                    132: 4. For the same reason, conditional expressions that use a backreference as the
                    133: condition or test for a specific group recursion are not supported.
                    134: .P
                    135: 5. Because many paths through the tree may be active, the \eK escape sequence,
                    136: which resets the start of the match when encountered (but may be on some paths
                    137: and not on others), is not supported. It causes an error if encountered.
                    138: .P
                    139: 6. Callouts are supported, but the value of the \fIcapture_top\fP field is
                    140: always 1, and the value of the \fIcapture_last\fP field is always -1.
                    141: .P
1.1.1.2   misho     142: 7. The \eC escape sequence, which (in the standard algorithm) always matches a
                    143: single data unit, even in UTF-8 or UTF-16 modes, is not supported in these
                    144: modes, because the alternative algorithm moves through the subject string one
                    145: character (not data unit) at a time, for all active paths through the tree.
1.1       misho     146: .P
                    147: 8. Except for (*FAIL), the backtracking control verbs such as (*PRUNE) are not
                    148: supported. (*FAIL) is supported, and behaves like a failing negative assertion.
                    149: .
1.1.1.2   misho     150: .
1.1       misho     151: .SH "ADVANTAGES OF THE ALTERNATIVE ALGORITHM"
                    152: .rs
                    153: .sp
                    154: Using the alternative matching algorithm provides the following advantages:
                    155: .P
                    156: 1. All possible matches (at a single point in the subject) are automatically
                    157: found, and in particular, the longest match is found. To find more than one
                    158: match using the standard algorithm, you have to do kludgy things with
                    159: callouts.
                    160: .P
                    161: 2. Because the alternative algorithm scans the subject string just once, and
1.1.1.2   misho     162: never needs to backtrack (except for lookbehinds), it is possible to pass very
                    163: long subject strings to the matching function in several pieces, checking for
                    164: partial matching each time. Although it is possible to do multi-segment
                    165: matching using the standard algorithm by retaining partially matched
                    166: substrings, it is more complicated. The
1.1       misho     167: .\" HREF
                    168: \fBpcrepartial\fP
                    169: .\"
                    170: documentation gives details of partial matching and discusses multi-segment
                    171: matching.
                    172: .
                    173: .
                    174: .SH "DISADVANTAGES OF THE ALTERNATIVE ALGORITHM"
                    175: .rs
                    176: .sp
                    177: The alternative algorithm suffers from a number of disadvantages:
                    178: .P
                    179: 1. It is substantially slower than the standard algorithm. This is partly
                    180: because it has to search for all possible matches, but is also because it is
                    181: less susceptible to optimization.
                    182: .P
                    183: 2. Capturing parentheses and back references are not supported.
                    184: .P
                    185: 3. Although atomic groups are supported, their use does not provide the
                    186: performance advantage that it does for the standard algorithm.
                    187: .
                    188: .
                    189: .SH AUTHOR
                    190: .rs
                    191: .sp
                    192: .nf
                    193: Philip Hazel
                    194: University Computing Service
                    195: Cambridge CB2 3QH, England.
                    196: .fi
                    197: .
                    198: .
                    199: .SH REVISION
                    200: .rs
                    201: .sp
                    202: .nf
1.1.1.2   misho     203: Last updated: 08 January 2012
                    204: Copyright (c) 1997-2012 University of Cambridge.
1.1       misho     205: .fi

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>