ViewVC logotype

Contents of /code/trunk/doc/pcrepartial.3

Parent Directory Parent Directory | Revision Log Revision Log

Revision 435 - (show annotations)
Sat Sep 5 10:20:44 2009 UTC (11 years, 8 months ago) by ph10
File size: 15656 byte(s)
Further updates to partial matching.
3 PCRE - Perl-compatible regular expressions
5 .rs
6 .sp
7 In normal use of PCRE, if the subject string that is passed to
8 \fBpcre_exec()\fP or \fBpcre_dfa_exec()\fP matches as far as it goes, but is
9 too short to match the entire pattern, PCRE_ERROR_NOMATCH is returned. There
10 are circumstances where it might be helpful to distinguish this case from other
11 cases in which there is no match.
12 .P
13 Consider, for example, an application where a human is required to type in data
14 for a field with specific formatting requirements. An example might be a date
15 in the form \fIddmmmyy\fP, defined by this pattern:
16 .sp
17 ^\ed?\ed(jan|feb|mar|apr|may|jun|jul|aug|sep|oct|nov|dec)\ed\ed$
18 .sp
19 If the application sees the user's keystrokes one by one, and can check that
20 what has been typed so far is potentially valid, it is able to raise an error
21 as soon as a mistake is made, by beeping and not reflecting the character that
22 has been typed, for example. This immediate feedback is likely to be a better
23 user interface than a check that is delayed until the entire string has been
24 entered. Partial matching can also sometimes be useful when the subject string
25 is very long and is not all available at once.
26 .P
27 PCRE supports partial matching by means of the PCRE_PARTIAL_SOFT and
28 PCRE_PARTIAL_HARD options, which can be set when calling \fBpcre_exec()\fP or
29 \fBpcre_dfa_exec()\fP. For backwards compatibility, PCRE_PARTIAL is a synonym
30 for PCRE_PARTIAL_SOFT. The essential difference between the two options is
31 whether or not a partial match is preferred to an alternative complete match,
32 though the details differ between the two matching functions. If both options
33 are set, PCRE_PARTIAL_HARD takes precedence.
34 .P
35 Setting a partial matching option disables one of PCRE's optimizations. PCRE
36 remembers the last literal byte in a pattern, and abandons matching immediately
37 if such a byte is not present in the subject string. This optimization cannot
38 be used for a subject string that might match only partially.
39 .
40 .
42 .rs
43 .sp
44 A partial match occurs during a call to \fBpcre_exec()\fP whenever the end of
45 the subject string is reached successfully, but matching cannot continue
46 because more characters are needed. However, at least one character must have
47 been matched. (In other words, a partial match can never be an empty string.)
48 .P
49 If PCRE_PARTIAL_SOFT is set, the partial match is remembered, but matching
50 continues as normal, and other alternatives in the pattern are tried. If no
51 complete match can be found, \fBpcre_exec()\fP returns PCRE_ERROR_PARTIAL
52 instead of PCRE_ERROR_NOMATCH. If there are at least two slots in the offsets
53 vector, the first of them is set to the offset of the earliest character that
54 was inspected when the partial match was found. For convenience, the second
55 offset points to the end of the string so that a substring can easily be
56 extracted.
57 .P
58 For the majority of patterns, the first offset identifies the start of the
59 partially matched string. However, for patterns that contain lookbehind
60 assertions, or \eK, or begin with \eb or \eB, earlier characters have been
61 inspected while carrying out the match. For example:
62 .sp
63 /(?<=abc)123/
64 .sp
65 This pattern matches "123", but only if it is preceded by "abc". If the subject
66 string is "xyzabc12", the offsets after a partial match are for the substring
67 "abc12", because all these characters are needed if another match is tried
68 with extra characters added.
69 .P
70 If there is more than one partial match, the first one that was found provides
71 the data that is returned. Consider this pattern:
72 .sp
73 /123\ew+X|dogY/
74 .sp
75 If this is matched against the subject string "abc123dog", both
76 alternatives fail to match, but the end of the subject is reached during
77 matching, so PCRE_ERROR_PARTIAL is returned instead of PCRE_ERROR_NOMATCH. The
78 offsets are set to 3 and 9, identifying "123dog" as the first partial match
79 that was found. (In this example, there are two partial matches, because "dog"
80 on its own partially matches the second alternative.)
81 .P
82 If PCRE_PARTIAL_HARD is set for \fBpcre_exec()\fP, it returns
83 PCRE_ERROR_PARTIAL as soon as a partial match is found, without continuing to
84 search for possible complete matches. The difference between the two options
85 can be illustrated by a pattern such as:
86 .sp
87 /dog(sbody)?/
88 .sp
89 This matches either "dog" or "dogsbody", greedily (that is, it prefers the
90 longer string if possible). If it is matched against the string "dog" with
91 PCRE_PARTIAL_SOFT, it yields a complete match for "dog". However, if
92 PCRE_PARTIAL_HARD is set, the result is PCRE_ERROR_PARTIAL. On the other hand,
93 if the pattern is made ungreedy the result is different:
94 .sp
95 /dog(sbody)??/
96 .sp
97 In this case the result is always a complete match because \fBpcre_exec()\fP
98 finds that first, and it never continues after finding a match. It might be
99 easier to follow this explanation by thinking of the two patterns like this:
100 .sp
101 /dog(sbody)?/ is the same as /dogsbody|dog/
102 /dog(sbody)??/ is the same as /dog|dogsbody/
103 .sp
104 The second pattern will never match "dogsbody" when \fBpcre_exec()\fP is
105 used, because it will always find the shorter match first.
106 .
107 .
108 .SH "PARTIAL MATCHING USING pcre_dfa_exec()"
109 .rs
110 .sp
111 The \fBpcre_dfa_exec()\fP function moves along the subject string character by
112 character, without backtracking, searching for all possible matches
113 simultaneously. If the end of the subject is reached before the end of the
114 pattern, there is the possibility of a partial match, again provided that at
115 least one character has matched.
116 .P
117 When PCRE_PARTIAL_SOFT is set, PCRE_ERROR_PARTIAL is returned only if there
118 have been no complete matches. Otherwise, the complete matches are returned.
119 However, if PCRE_PARTIAL_HARD is set, a partial match takes precedence over any
120 complete matches. The portion of the string that was inspected when the longest
121 partial match was found is set as the first matching string, provided there are
122 at least two slots in the offsets vector.
123 .P
124 Because \fBpcre_dfa_exec()\fP always searches for all possible matches, and
125 there is no difference between greedy and ungreedy repetition, its behaviour is
126 different from \fBpcre_exec\fP when PCRE_PARTIAL_HARD is set. Consider the
127 string "dog" matched against the ungreedy pattern shown above:
128 .sp
129 /dog(sbody)??/
130 .sp
131 Whereas \fBpcre_exec()\fP stops as soon as it finds the complete match for
132 "dog", \fBpcre_dfa_exec()\fP also finds the partial match for "dogsbody", and
133 so returns that when PCRE_PARTIAL_HARD is set.
134 .
135 .
137 .rs
138 .sp
139 If a pattern ends with one of sequences \ew or \eW, which test for word
140 boundaries, partial matching with PCRE_PARTIAL_SOFT can give counter-intuitive
141 results. Consider this pattern:
142 .sp
143 /\ebcat\eb/
144 .sp
145 This matches "cat", provided there is a word boundary at either end. If the
146 subject string is "the cat", the comparison of the final "t" with a following
147 character cannot take place, so a partial match is found. However,
148 \fBpcre_exec()\fP carries on with normal matching, which matches \eb at the end
149 of the subject when the last character is a letter, thus finding a complete
150 match. The result, therefore, is \fInot\fP PCRE_ERROR_PARTIAL. The same thing
151 happens with \fBpcre_dfa_exec()\fP, because it also finds the complete match.
152 .P
153 Using PCRE_PARTIAL_HARD in this case does yield PCRE_ERROR_PARTIAL, because
154 then the partial match takes precedence.
155 .
156 .
158 .rs
159 .sp
160 For releases of PCRE prior to 8.00, because of the way certain internal
161 optimizations were implemented in the \fBpcre_exec()\fP function, the
162 PCRE_PARTIAL option (predecessor of PCRE_PARTIAL_SOFT) could not be used with
163 all patterns. From release 8.00 onwards, the restrictions no longer apply, and
164 partial matching with \fBpcre_exec()\fP can be requested for any pattern.
165 .P
166 Items that were formerly restricted were repeated single characters and
167 repeated metasequences. If PCRE_PARTIAL was set for a pattern that did not
168 conform to the restrictions, \fBpcre_exec()\fP returned the error code
169 PCRE_ERROR_BADPARTIAL (-13). This error code is no longer in use. The
170 PCRE_INFO_OKPARTIAL call to \fBpcre_fullinfo()\fP to find out if a compiled
171 pattern can be used for partial matching now always returns 1.
172 .
173 .
175 .rs
176 .sp
177 If the escape sequence \eP is present in a \fBpcretest\fP data line, the
178 PCRE_PARTIAL_SOFT option is used for the match. Here is a run of \fBpcretest\fP
179 that uses the date example quoted above:
180 .sp
181 re> /^\ed?\ed(jan|feb|mar|apr|may|jun|jul|aug|sep|oct|nov|dec)\ed\ed$/
182 data> 25jun04\eP
183 0: 25jun04
184 1: jun
185 data> 25dec3\eP
186 Partial match: 23dec3
187 data> 3ju\eP
188 Partial match: 3ju
189 data> 3juj\eP
190 No match
191 data> j\eP
192 No match
193 .sp
194 The first data string is matched completely, so \fBpcretest\fP shows the
195 matched substrings. The remaining four strings do not match the complete
196 pattern, but the first two are partial matches. Similar output is obtained
197 when \fBpcre_dfa_exec()\fP is used.
198 .P
199 If the escape sequence \eP is present more than once in a \fBpcretest\fP data
200 line, the PCRE_PARTIAL_HARD option is set for the match.
201 .
202 .
203 .SH "MULTI-SEGMENT MATCHING WITH pcre_dfa_exec()"
204 .rs
205 .sp
206 When a partial match has been found using \fBpcre_dfa_exec()\fP, it is possible
207 to continue the match by providing additional subject data and calling
208 \fBpcre_dfa_exec()\fP again with the same compiled regular expression, this
209 time setting the PCRE_DFA_RESTART option. You must pass the same working
210 space as before, because this is where details of the previous partial match
211 are stored. Here is an example using \fBpcretest\fP, using the \eR escape
212 sequence to set the PCRE_DFA_RESTART option (\eD specifies the use of
213 \fBpcre_dfa_exec()\fP):
214 .sp
215 re> /^\ed?\ed(jan|feb|mar|apr|may|jun|jul|aug|sep|oct|nov|dec)\ed\ed$/
216 data> 23ja\eP\eD
217 Partial match: 23ja
218 data> n05\eR\eD
219 0: n05
220 .sp
221 The first call has "23ja" as the subject, and requests partial matching; the
222 second call has "n05" as the subject for the continued (restarted) match.
223 Notice that when the match is complete, only the last part is shown; PCRE does
224 not retain the previously partially-matched string. It is up to the calling
225 program to do that if it needs to.
226 .P
227 You can set the PCRE_PARTIAL_SOFT or PCRE_PARTIAL_HARD options with
228 PCRE_DFA_RESTART to continue partial matching over multiple segments. This
229 facility can be used to pass very long subject strings to
230 \fBpcre_dfa_exec()\fP.
231 .
232 .
234 .rs
235 .sp
236 From release 8.00, \fBpcre_exec()\fP can also be used to do multi-segment
237 matching. Unlike \fBpcre_dfa_exec()\fP, it is not possible to restart the
238 previous match with a new segment of data. Instead, new data must be added to
239 the previous subject string, and the entire match re-run, starting from the
240 point where the partial match occurred. Earlier data can be discarded.
241 Consider an unanchored pattern that matches dates:
242 .sp
243 re> /\ed?\ed(jan|feb|mar|apr|may|jun|jul|aug|sep|oct|nov|dec)\ed\ed/
244 data> The date is 23ja\eP
245 Partial match: 23ja
246 .sp
247 The this stage, an application could discard the text preceding "23ja", add on
248 text from the next segment, and call \fBpcre_exec()\fP again. Unlike
249 \fBpcre_dfa_exec()\fP, the entire matching string must always be available, and
250 the complete matching process occurs for each call, so more memory and more
251 processing time is needed.
252 .P
253 \fBNote:\fP If the pattern contains lookbehind assertions, or \eK, or starts
254 with \eb or \eB, the string that is returned for a partial match will include
255 characters that precede the partially matched string itself, because these must
256 be retained when adding on more characters for a subsequent matching attempt.
257 .
258 .
260 .rs
261 .sp
262 Certain types of pattern may give problems with multi-segment matching,
263 whichever matching function is used.
264 .P
265 1. If the pattern contains tests for the beginning or end of a line, you need
266 to pass the PCRE_NOTBOL or PCRE_NOTEOL options, as appropriate, when the
267 subject string for any call does not contain the beginning or end of a line.
268 .P
269 2. Lookbehind assertions at the start of a pattern are catered for in the
270 offsets that are returned for a partial match. However, in theory, a lookbehind
271 assertion later in the pattern could require even earlier characters to be
272 inspected, and it might not have been reached when a partial match occurs. This
273 is probably an extremely unlikely case; you could guard against it to a certain
274 extent by always including extra characters at the start.
275 .P
276 3. Matching a subject string that is split into multiple segments may not
277 always produce exactly the same result as matching over one single long string,
278 especially when PCRE_PARTIAL_SOFT is used. The section "Partial Matching and
279 Word Boundaries" above describes an issue that arises if the pattern ends with
280 \eb or \eB. Another kind of difference may occur when there are multiple
281 matching possibilities, because a partial match result is given only when there
282 are no completed matches. This means that as soon as the shortest match has
283 been found, continuation to a new subject segment is no longer possible.
284 Consider again this \fBpcretest\fP example:
285 .sp
286 re> /dog(sbody)?/
287 data> dogsb\eP
288 0: dog
289 data> do\eP\eD
290 Partial match: do
291 data> gsb\eR\eP\eD
292 0: g
293 data> dogsbody\eD
294 0: dogsbody
295 1: dog
296 .sp
297 The first data line passes the string "dogsb" to \fBpcre_exec()\fP, setting the
298 PCRE_PARTIAL_SOFT option. Although the string is a partial match for
299 "dogsbody", the result is not PCRE_ERROR_PARTIAL, because the shorter string
300 "dog" is a complete match. Similarly, when the subject is presented to
301 \fBpcre_dfa_exec()\fP in several parts ("do" and "gsb" being the first two) the
302 match stops when "dog" has been found, and it is not possible to continue. On
303 the other hand, if "dogsbody" is presented as a single string,
304 \fBpcre_dfa_exec()\fP finds both matches.
305 .P
306 Because of these problems, it is probably best to use PCRE_PARTIAL_HARD when
307 matching multi-segment data. The example above then behaves differently:
308 .sp
309 re> /dog(sbody)?/
310 data> dogsb\eP\eP
311 Partial match: dogsb
312 data> do\eP\eD
313 Partial match: do
314 data> gsb\eR\eP\eP\eD
315 Partial match: gsb
316 .sp
317 .P
318 4. Patterns that contain alternatives at the top level which do not all
319 start with the same pattern item may not work as expected when
320 \fBpcre_dfa_exec()\fP is used. For example, consider this pattern:
321 .sp
322 1234|3789
323 .sp
324 If the first part of the subject is "ABC123", a partial match of the first
325 alternative is found at offset 3. There is no partial match for the second
326 alternative, because such a match does not start at the same point in the
327 subject string. Attempting to continue with the string "7890" does not yield a
328 match because only those alternatives that match at one point in the subject
329 are remembered. The problem arises because the start of the second alternative
330 matches within the first alternative. There is no problem with anchored
331 patterns or patterns such as:
332 .sp
333 1234|ABCD
334 .sp
335 where no string can be a partial match for both alternatives. This is not a
336 problem if \fPpcre_exec()\fP is used, because the entire match has to be rerun
337 each time:
338 .sp
339 re> /1234|3789/
340 data> ABC123\eP
341 Partial match: 123
342 data> 1237890
343 0: 3789
344 .sp
345 .
346 .
348 .rs
349 .sp
350 .nf
351 Philip Hazel
352 University Computing Service
353 Cambridge CB2 3QH, England.
354 .fi
355 .
356 .
358 .rs
359 .sp
360 .nf
361 Last updated: 05 September 2009
362 Copyright (c) 1997-2009 University of Cambridge.
363 .fi


Name Value
svn:eol-style native
svn:keywords "Author Date Id Revision Url"

  ViewVC Help
Powered by ViewVC 1.1.5