+++ /dev/null
-.TH PCREMATCHING 3
-.SH NAME
-PCRE - Perl-compatible regular expressions
-.SH "PCRE MATCHING ALGORITHMS"
-.rs
-.sp
-This document describes the two different algorithms that are available in PCRE
-for matching a compiled regular expression against a given subject string. The
-"standard" algorithm is the one provided by the \fBpcre_exec()\fP function.
-This works in the same was as Perl's matching function, and provides a
-Perl-compatible matching operation.
-.P
-An alternative algorithm is provided by the \fBpcre_dfa_exec()\fP function;
-this operates in a different way, and is not Perl-compatible. It has advantages
-and disadvantages compared with the standard algorithm, and these are described
-below.
-.P
-When there is only one possible way in which a given subject string can match a
-pattern, the two algorithms give the same answer. A difference arises, however,
-when there are multiple possibilities. For example, if the pattern
-.sp
- ^<.*>
-.sp
-is matched against the string
-.sp
- <something> <something else> <something further>
-.sp
-there are three possible answers. The standard algorithm finds only one of
-them, whereas the alternative algorithm finds all three.
-.
-.SH "REGULAR EXPRESSIONS AS TREES"
-.rs
-.sp
-The set of strings that are matched by a regular expression can be represented
-as a tree structure. An unlimited repetition in the pattern makes the tree of
-infinite size, but it is still a tree. Matching the pattern to a given subject
-string (from a given starting point) can be thought of as a search of the tree.
-There are two ways to search a tree: depth-first and breadth-first, and these
-correspond to the two matching algorithms provided by PCRE.
-.
-.SH "THE STANDARD MATCHING ALGORITHM"
-.rs
-.sp
-In the terminology of Jeffrey Friedl's book "Mastering Regular
-Expressions", the standard algorithm is an "NFA algorithm". It conducts a
-depth-first search of the pattern tree. That is, it proceeds along a single
-path through the tree, checking that the subject matches what is required. When
-there is a mismatch, the algorithm tries any alternatives at the current point,
-and if they all fail, it backs up to the previous branch point in the tree, and
-tries the next alternative branch at that level. This often involves backing up
-(moving to the left) in the subject string as well. The order in which
-repetition branches are tried is controlled by the greedy or ungreedy nature of
-the quantifier.
-.P
-If a leaf node is reached, a matching string has been found, and at that point
-the algorithm stops. Thus, if there is more than one possible match, this
-algorithm returns the first one that it finds. Whether this is the shortest,
-the longest, or some intermediate length depends on the way the greedy and
-ungreedy repetition quantifiers are specified in the pattern.
-.P
-Because it ends up with a single path through the tree, it is relatively
-straightforward for this algorithm to keep track of the substrings that are
-matched by portions of the pattern in parentheses. This provides support for
-capturing parentheses and back references.
-.
-.SH "THE ALTERNATIVE MATCHING ALGORITHM"
-.rs
-.sp
-This algorithm conducts a breadth-first search of the tree. Starting from the
-first matching point in the subject, it scans the subject string from left to
-right, once, character by character, and as it does this, it remembers all the
-paths through the tree that represent valid matches. In Friedl's terminology,
-this is a kind of "DFA algorithm", though it is not implemented as a
-traditional finite state machine (it keeps multiple states active
-simultaneously).
-.P
-Although the general principle of this matching algorithm is that it scans the
-subject string only once, without backtracking, there is one exception: when a
-lookaround assertion is encountered, the characters following or preceding the
-current point have to be independently inspected.
-.P
-The scan continues until either the end of the subject is reached, or there are
-no more unterminated paths. At this point, terminated paths represent the
-different matching possibilities (if there are none, the match has failed).
-Thus, if there is more than one possible match, this algorithm finds all of
-them, and in particular, it finds the longest. There is an option to stop the
-algorithm after the first match (which is necessarily the shortest) is found.
-.P
-Note that all the matches that are found start at the same point in the
-subject. If the pattern
-.sp
- cat(er(pillar)?)
-.sp
-is matched against the string "the caterpillar catchment", the result will be
-the three strings "cat", "cater", and "caterpillar" that start at the fourth
-character of the subject. The algorithm does not automatically move on to find
-matches that start at later positions.
-.P
-There are a number of features of PCRE regular expressions that are not
-supported by the alternative matching algorithm. They are as follows:
-.P
-1. Because the algorithm finds all possible matches, the greedy or ungreedy
-nature of repetition quantifiers is not relevant. Greedy and ungreedy
-quantifiers are treated in exactly the same way. However, possessive
-quantifiers can make a difference when what follows could also match what is
-quantified, for example in a pattern like this:
-.sp
- ^a++\ew!
-.sp
-This pattern matches "aaab!" but not "aaa!", which would be matched by a
-non-possessive quantifier. Similarly, if an atomic group is present, it is
-matched as if it were a standalone pattern at the current point, and the
-longest match is then "locked in" for the rest of the overall pattern.
-.P
-2. When dealing with multiple paths through the tree simultaneously, it is not
-straightforward to keep track of captured substrings for the different matching
-possibilities, and PCRE's implementation of this algorithm does not attempt to
-do this. This means that no captured substrings are available.
-.P
-3. Because no substrings are captured, back references within the pattern are
-not supported, and cause errors if encountered.
-.P
-4. For the same reason, conditional expressions that use a backreference as the
-condition or test for a specific group recursion are not supported.
-.P
-5. Because many paths through the tree may be active, the \eK escape sequence,
-which resets the start of the match when encountered (but may be on some paths
-and not on others), is not supported. It causes an error if encountered.
-.P
-6. Callouts are supported, but the value of the \fIcapture_top\fP field is
-always 1, and the value of the \fIcapture_last\fP field is always -1.
-.P
-7. The \eC escape sequence, which (in the standard algorithm) matches a single
-byte, even in UTF-8 mode, is not supported because the alternative algorithm
-moves through the subject string one character at a time, for all active paths
-through the tree.
-.P
-8. Except for (*FAIL), the backtracking control verbs such as (*PRUNE) are not
-supported. (*FAIL) is supported, and behaves like a failing negative assertion.
-.
-.SH "ADVANTAGES OF THE ALTERNATIVE ALGORITHM"
-.rs
-.sp
-Using the alternative matching algorithm provides the following advantages:
-.P
-1. All possible matches (at a single point in the subject) are automatically
-found, and in particular, the longest match is found. To find more than one
-match using the standard algorithm, you have to do kludgy things with
-callouts.
-.P
-2. Because the alternative algorithm scans the subject string just once, and
-never needs to backtrack, it is possible to pass very long subject strings to
-the matching function in several pieces, checking for partial matching each
-time. The
-.\" HREF
-\fBpcrepartial\fP
-.\"
-documentation gives details of partial matching.
-.
-.
-.SH "DISADVANTAGES OF THE ALTERNATIVE ALGORITHM"
-.rs
-.sp
-The alternative algorithm suffers from a number of disadvantages:
-.P
-1. It is substantially slower than the standard algorithm. This is partly
-because it has to search for all possible matches, but is also because it is
-less susceptible to optimization.
-.P
-2. Capturing parentheses and back references are not supported.
-.P
-3. Although atomic groups are supported, their use does not provide the
-performance advantage that it does for the standard algorithm.
-.
-.
-.SH AUTHOR
-.rs
-.sp
-.nf
-Philip Hazel
-University Computing Service
-Cambridge CB2 3QH, England.
-.fi
-.
-.
-.SH REVISION
-.rs
-.sp
-.nf
-Last updated: 29 September 2009
-Copyright (c) 1997-2009 University of Cambridge.
-.fi
projects / vuplus_xbmc / blobdiff