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