Annotation of embedaddon/pcre/doc/pcrematching.3, revision 1.1.1.4
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.4 ! misho 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
1.1.1.2 misho 13: .\" HREF
14: \fBpcrejit\fP
15: .\"
16: documentation is compatible with these functions.
17: .P
1.1.1.4 ! misho 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.
1.1 misho 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: .
1.1.1.2 misho 37: .
1.1 misho 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: .
1.1.1.2 misho 48: .
1.1 misho 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: .
1.1.1.2 misho 74: .
1.1 misho 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: There are a number of features of PCRE regular expressions that are not
110: supported by the alternative matching algorithm. They are as follows:
111: .P
112: 1. Because the algorithm finds all possible matches, the greedy or ungreedy
113: nature of repetition quantifiers is not relevant. Greedy and ungreedy
114: quantifiers are treated in exactly the same way. However, possessive
115: quantifiers can make a difference when what follows could also match what is
116: quantified, for example in a pattern like this:
117: .sp
118: ^a++\ew!
119: .sp
120: This pattern matches "aaab!" but not "aaa!", which would be matched by a
121: non-possessive quantifier. Similarly, if an atomic group is present, it is
122: matched as if it were a standalone pattern at the current point, and the
123: longest match is then "locked in" for the rest of the overall pattern.
124: .P
125: 2. When dealing with multiple paths through the tree simultaneously, it is not
126: straightforward to keep track of captured substrings for the different matching
127: possibilities, and PCRE's implementation of this algorithm does not attempt to
128: do this. This means that no captured substrings are available.
129: .P
130: 3. Because no substrings are captured, back references within the pattern are
131: not supported, and cause errors if encountered.
132: .P
133: 4. For the same reason, conditional expressions that use a backreference as the
134: condition or test for a specific group recursion are not supported.
135: .P
136: 5. Because many paths through the tree may be active, the \eK escape sequence,
137: which resets the start of the match when encountered (but may be on some paths
138: and not on others), is not supported. It causes an error if encountered.
139: .P
140: 6. Callouts are supported, but the value of the \fIcapture_top\fP field is
141: always 1, and the value of the \fIcapture_last\fP field is always -1.
142: .P
1.1.1.2 misho 143: 7. The \eC escape sequence, which (in the standard algorithm) always matches a
1.1.1.4 ! misho 144: single data unit, even in UTF-8, UTF-16 or UTF-32 modes, is not supported in
! 145: these modes, because the alternative algorithm moves through the subject string
! 146: one character (not data unit) at a time, for all active paths through the tree.
1.1 misho 147: .P
148: 8. Except for (*FAIL), the backtracking control verbs such as (*PRUNE) are not
149: supported. (*FAIL) is supported, and behaves like a failing negative assertion.
150: .
1.1.1.2 misho 151: .
1.1 misho 152: .SH "ADVANTAGES OF THE ALTERNATIVE ALGORITHM"
153: .rs
154: .sp
155: Using the alternative matching algorithm provides the following advantages:
156: .P
157: 1. All possible matches (at a single point in the subject) are automatically
158: found, and in particular, the longest match is found. To find more than one
159: match using the standard algorithm, you have to do kludgy things with
160: callouts.
161: .P
162: 2. Because the alternative algorithm scans the subject string just once, and
1.1.1.2 misho 163: never needs to backtrack (except for lookbehinds), it is possible to pass very
164: long subject strings to the matching function in several pieces, checking for
165: partial matching each time. Although it is possible to do multi-segment
166: matching using the standard algorithm by retaining partially matched
167: substrings, it is more complicated. The
1.1 misho 168: .\" HREF
169: \fBpcrepartial\fP
170: .\"
171: documentation gives details of partial matching and discusses multi-segment
172: matching.
173: .
174: .
175: .SH "DISADVANTAGES OF THE ALTERNATIVE ALGORITHM"
176: .rs
177: .sp
178: The alternative algorithm suffers from a number of disadvantages:
179: .P
180: 1. It is substantially slower than the standard algorithm. This is partly
181: because it has to search for all possible matches, but is also because it is
182: less susceptible to optimization.
183: .P
184: 2. Capturing parentheses and back references are not supported.
185: .P
186: 3. Although atomic groups are supported, their use does not provide the
187: performance advantage that it does for the standard algorithm.
188: .
189: .
190: .SH AUTHOR
191: .rs
192: .sp
193: .nf
194: Philip Hazel
195: University Computing Service
196: Cambridge CB2 3QH, England.
197: .fi
198: .
199: .
200: .SH REVISION
201: .rs
202: .sp
203: .nf
1.1.1.2 misho 204: Last updated: 08 January 2012
205: Copyright (c) 1997-2012 University of Cambridge.
1.1 misho 206: .fi
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to pcrematching.3 CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / pcre / doc