Commit | Line | Data |
47f9c88b |
1 | =head1 NAME |
2 | |
3 | perlretut - Perl regular expressions tutorial |
4 | |
5 | =head1 DESCRIPTION |
6 | |
7 | This page provides a basic tutorial on understanding, creating and |
8 | using regular expressions in Perl. It serves as a complement to the |
9 | reference page on regular expressions L<perlre>. Regular expressions |
10 | are an integral part of the C<m//>, C<s///>, C<qr//> and C<split> |
11 | operators and so this tutorial also overlaps with |
12 | L<perlop/"Regexp Quote-Like Operators"> and L<perlfunc/split>. |
13 | |
14 | Perl is widely renowned for excellence in text processing, and regular |
15 | expressions are one of the big factors behind this fame. Perl regular |
16 | expressions display an efficiency and flexibility unknown in most |
17 | other computer languages. Mastering even the basics of regular |
18 | expressions will allow you to manipulate text with surprising ease. |
19 | |
20 | What is a regular expression? A regular expression is simply a string |
21 | that describes a pattern. Patterns are in common use these days; |
22 | examples are the patterns typed into a search engine to find web pages |
23 | and the patterns used to list files in a directory, e.g., C<ls *.txt> |
24 | or C<dir *.*>. In Perl, the patterns described by regular expressions |
25 | are used to search strings, extract desired parts of strings, and to |
26 | do search and replace operations. |
27 | |
28 | Regular expressions have the undeserved reputation of being abstract |
29 | and difficult to understand. Regular expressions are constructed using |
30 | simple concepts like conditionals and loops and are no more difficult |
31 | to understand than the corresponding C<if> conditionals and C<while> |
32 | loops in the Perl language itself. In fact, the main challenge in |
33 | learning regular expressions is just getting used to the terse |
34 | notation used to express these concepts. |
35 | |
36 | This tutorial flattens the learning curve by discussing regular |
37 | expression concepts, along with their notation, one at a time and with |
38 | many examples. The first part of the tutorial will progress from the |
39 | simplest word searches to the basic regular expression concepts. If |
40 | you master the first part, you will have all the tools needed to solve |
41 | about 98% of your needs. The second part of the tutorial is for those |
42 | comfortable with the basics and hungry for more power tools. It |
43 | discusses the more advanced regular expression operators and |
44 | introduces the latest cutting edge innovations in 5.6.0. |
45 | |
46 | A note: to save time, 'regular expression' is often abbreviated as |
47 | regexp or regex. Regexp is a more natural abbreviation than regex, but |
48 | is harder to pronounce. The Perl pod documentation is evenly split on |
49 | regexp vs regex; in Perl, there is more than one way to abbreviate it. |
50 | We'll use regexp in this tutorial. |
51 | |
52 | =head1 Part 1: The basics |
53 | |
54 | =head2 Simple word matching |
55 | |
56 | The simplest regexp is simply a word, or more generally, a string of |
57 | characters. A regexp consisting of a word matches any string that |
58 | contains that word: |
59 | |
60 | "Hello World" =~ /World/; # matches |
61 | |
7638d2dc |
62 | What is this Perl statement all about? C<"Hello World"> is a simple |
47f9c88b |
63 | double quoted string. C<World> is the regular expression and the |
7638d2dc |
64 | C<//> enclosing C</World/> tells Perl to search a string for a match. |
47f9c88b |
65 | The operator C<=~> associates the string with the regexp match and |
66 | produces a true value if the regexp matched, or false if the regexp |
67 | did not match. In our case, C<World> matches the second word in |
68 | C<"Hello World">, so the expression is true. Expressions like this |
69 | are useful in conditionals: |
70 | |
71 | if ("Hello World" =~ /World/) { |
72 | print "It matches\n"; |
73 | } |
74 | else { |
75 | print "It doesn't match\n"; |
76 | } |
77 | |
78 | There are useful variations on this theme. The sense of the match can |
7638d2dc |
79 | be reversed by using the C<!~> operator: |
47f9c88b |
80 | |
81 | if ("Hello World" !~ /World/) { |
82 | print "It doesn't match\n"; |
83 | } |
84 | else { |
85 | print "It matches\n"; |
86 | } |
87 | |
88 | The literal string in the regexp can be replaced by a variable: |
89 | |
90 | $greeting = "World"; |
91 | if ("Hello World" =~ /$greeting/) { |
92 | print "It matches\n"; |
93 | } |
94 | else { |
95 | print "It doesn't match\n"; |
96 | } |
97 | |
98 | If you're matching against the special default variable C<$_>, the |
99 | C<$_ =~> part can be omitted: |
100 | |
101 | $_ = "Hello World"; |
102 | if (/World/) { |
103 | print "It matches\n"; |
104 | } |
105 | else { |
106 | print "It doesn't match\n"; |
107 | } |
108 | |
109 | And finally, the C<//> default delimiters for a match can be changed |
110 | to arbitrary delimiters by putting an C<'m'> out front: |
111 | |
112 | "Hello World" =~ m!World!; # matches, delimited by '!' |
113 | "Hello World" =~ m{World}; # matches, note the matching '{}' |
a6b2f353 |
114 | "/usr/bin/perl" =~ m"/perl"; # matches after '/usr/bin', |
115 | # '/' becomes an ordinary char |
47f9c88b |
116 | |
117 | C</World/>, C<m!World!>, and C<m{World}> all represent the |
7638d2dc |
118 | same thing. When, e.g., the quote (C<">) is used as a delimiter, the forward |
119 | slash C<'/'> becomes an ordinary character and can be used in this regexp |
47f9c88b |
120 | without trouble. |
121 | |
122 | Let's consider how different regexps would match C<"Hello World">: |
123 | |
124 | "Hello World" =~ /world/; # doesn't match |
125 | "Hello World" =~ /o W/; # matches |
126 | "Hello World" =~ /oW/; # doesn't match |
127 | "Hello World" =~ /World /; # doesn't match |
128 | |
129 | The first regexp C<world> doesn't match because regexps are |
130 | case-sensitive. The second regexp matches because the substring |
7638d2dc |
131 | S<C<'o W'>> occurs in the string S<C<"Hello World">>. The space |
47f9c88b |
132 | character ' ' is treated like any other character in a regexp and is |
133 | needed to match in this case. The lack of a space character is the |
134 | reason the third regexp C<'oW'> doesn't match. The fourth regexp |
135 | C<'World '> doesn't match because there is a space at the end of the |
136 | regexp, but not at the end of the string. The lesson here is that |
137 | regexps must match a part of the string I<exactly> in order for the |
138 | statement to be true. |
139 | |
7638d2dc |
140 | If a regexp matches in more than one place in the string, Perl will |
47f9c88b |
141 | always match at the earliest possible point in the string: |
142 | |
143 | "Hello World" =~ /o/; # matches 'o' in 'Hello' |
144 | "That hat is red" =~ /hat/; # matches 'hat' in 'That' |
145 | |
146 | With respect to character matching, there are a few more points you |
147 | need to know about. First of all, not all characters can be used 'as |
7638d2dc |
148 | is' in a match. Some characters, called I<metacharacters>, are reserved |
47f9c88b |
149 | for use in regexp notation. The metacharacters are |
150 | |
151 | {}[]()^$.|*+?\ |
152 | |
153 | The significance of each of these will be explained |
154 | in the rest of the tutorial, but for now, it is important only to know |
155 | that a metacharacter can be matched by putting a backslash before it: |
156 | |
157 | "2+2=4" =~ /2+2/; # doesn't match, + is a metacharacter |
158 | "2+2=4" =~ /2\+2/; # matches, \+ is treated like an ordinary + |
159 | "The interval is [0,1)." =~ /[0,1)./ # is a syntax error! |
160 | "The interval is [0,1)." =~ /\[0,1\)\./ # matches |
7638d2dc |
161 | "#!/usr/bin/perl" =~ /#!\/usr\/bin\/perl/; # matches |
47f9c88b |
162 | |
163 | In the last regexp, the forward slash C<'/'> is also backslashed, |
164 | because it is used to delimit the regexp. This can lead to LTS |
165 | (leaning toothpick syndrome), however, and it is often more readable |
166 | to change delimiters. |
167 | |
7638d2dc |
168 | "#!/usr/bin/perl" =~ m!#\!/usr/bin/perl!; # easier to read |
47f9c88b |
169 | |
170 | The backslash character C<'\'> is a metacharacter itself and needs to |
171 | be backslashed: |
172 | |
173 | 'C:\WIN32' =~ /C:\\WIN/; # matches |
174 | |
175 | In addition to the metacharacters, there are some ASCII characters |
176 | which don't have printable character equivalents and are instead |
7638d2dc |
177 | represented by I<escape sequences>. Common examples are C<\t> for a |
47f9c88b |
178 | tab, C<\n> for a newline, C<\r> for a carriage return and C<\a> for a |
179 | bell. If your string is better thought of as a sequence of arbitrary |
180 | bytes, the octal escape sequence, e.g., C<\033>, or hexadecimal escape |
181 | sequence, e.g., C<\x1B> may be a more natural representation for your |
182 | bytes. Here are some examples of escapes: |
183 | |
184 | "1000\t2000" =~ m(0\t2) # matches |
185 | "1000\n2000" =~ /0\n20/ # matches |
186 | "1000\t2000" =~ /\000\t2/ # doesn't match, "0" ne "\000" |
187 | "cat" =~ /\143\x61\x74/ # matches, but a weird way to spell cat |
188 | |
189 | If you've been around Perl a while, all this talk of escape sequences |
190 | may seem familiar. Similar escape sequences are used in double-quoted |
191 | strings and in fact the regexps in Perl are mostly treated as |
192 | double-quoted strings. This means that variables can be used in |
193 | regexps as well. Just like double-quoted strings, the values of the |
194 | variables in the regexp will be substituted in before the regexp is |
195 | evaluated for matching purposes. So we have: |
196 | |
197 | $foo = 'house'; |
198 | 'housecat' =~ /$foo/; # matches |
199 | 'cathouse' =~ /cat$foo/; # matches |
47f9c88b |
200 | 'housecat' =~ /${foo}cat/; # matches |
201 | |
202 | So far, so good. With the knowledge above you can already perform |
203 | searches with just about any literal string regexp you can dream up. |
204 | Here is a I<very simple> emulation of the Unix grep program: |
205 | |
206 | % cat > simple_grep |
207 | #!/usr/bin/perl |
208 | $regexp = shift; |
209 | while (<>) { |
210 | print if /$regexp/; |
211 | } |
212 | ^D |
213 | |
214 | % chmod +x simple_grep |
215 | |
216 | % simple_grep abba /usr/dict/words |
217 | Babbage |
218 | cabbage |
219 | cabbages |
220 | sabbath |
221 | Sabbathize |
222 | Sabbathizes |
223 | sabbatical |
224 | scabbard |
225 | scabbards |
226 | |
227 | This program is easy to understand. C<#!/usr/bin/perl> is the standard |
228 | way to invoke a perl program from the shell. |
7638d2dc |
229 | S<C<$regexp = shift;>> saves the first command line argument as the |
47f9c88b |
230 | regexp to be used, leaving the rest of the command line arguments to |
7638d2dc |
231 | be treated as files. S<C<< while (<>) >>> loops over all the lines in |
232 | all the files. For each line, S<C<print if /$regexp/;>> prints the |
47f9c88b |
233 | line if the regexp matches the line. In this line, both C<print> and |
234 | C</$regexp/> use the default variable C<$_> implicitly. |
235 | |
236 | With all of the regexps above, if the regexp matched anywhere in the |
237 | string, it was considered a match. Sometimes, however, we'd like to |
238 | specify I<where> in the string the regexp should try to match. To do |
7638d2dc |
239 | this, we would use the I<anchor> metacharacters C<^> and C<$>. The |
47f9c88b |
240 | anchor C<^> means match at the beginning of the string and the anchor |
241 | C<$> means match at the end of the string, or before a newline at the |
242 | end of the string. Here is how they are used: |
243 | |
244 | "housekeeper" =~ /keeper/; # matches |
245 | "housekeeper" =~ /^keeper/; # doesn't match |
246 | "housekeeper" =~ /keeper$/; # matches |
247 | "housekeeper\n" =~ /keeper$/; # matches |
248 | |
249 | The second regexp doesn't match because C<^> constrains C<keeper> to |
250 | match only at the beginning of the string, but C<"housekeeper"> has |
251 | keeper starting in the middle. The third regexp does match, since the |
252 | C<$> constrains C<keeper> to match only at the end of the string. |
253 | |
254 | When both C<^> and C<$> are used at the same time, the regexp has to |
255 | match both the beginning and the end of the string, i.e., the regexp |
256 | matches the whole string. Consider |
257 | |
258 | "keeper" =~ /^keep$/; # doesn't match |
259 | "keeper" =~ /^keeper$/; # matches |
260 | "" =~ /^$/; # ^$ matches an empty string |
261 | |
262 | The first regexp doesn't match because the string has more to it than |
263 | C<keep>. Since the second regexp is exactly the string, it |
264 | matches. Using both C<^> and C<$> in a regexp forces the complete |
265 | string to match, so it gives you complete control over which strings |
266 | match and which don't. Suppose you are looking for a fellow named |
267 | bert, off in a string by himself: |
268 | |
269 | "dogbert" =~ /bert/; # matches, but not what you want |
270 | |
271 | "dilbert" =~ /^bert/; # doesn't match, but .. |
272 | "bertram" =~ /^bert/; # matches, so still not good enough |
273 | |
274 | "bertram" =~ /^bert$/; # doesn't match, good |
275 | "dilbert" =~ /^bert$/; # doesn't match, good |
276 | "bert" =~ /^bert$/; # matches, perfect |
277 | |
278 | Of course, in the case of a literal string, one could just as easily |
7638d2dc |
279 | use the string comparison S<C<$string eq 'bert'>> and it would be |
47f9c88b |
280 | more efficient. The C<^...$> regexp really becomes useful when we |
281 | add in the more powerful regexp tools below. |
282 | |
283 | =head2 Using character classes |
284 | |
285 | Although one can already do quite a lot with the literal string |
286 | regexps above, we've only scratched the surface of regular expression |
287 | technology. In this and subsequent sections we will introduce regexp |
288 | concepts (and associated metacharacter notations) that will allow a |
289 | regexp to not just represent a single character sequence, but a I<whole |
290 | class> of them. |
291 | |
7638d2dc |
292 | One such concept is that of a I<character class>. A character class |
47f9c88b |
293 | allows a set of possible characters, rather than just a single |
294 | character, to match at a particular point in a regexp. Character |
295 | classes are denoted by brackets C<[...]>, with the set of characters |
296 | to be possibly matched inside. Here are some examples: |
297 | |
298 | /cat/; # matches 'cat' |
299 | /[bcr]at/; # matches 'bat, 'cat', or 'rat' |
300 | /item[0123456789]/; # matches 'item0' or ... or 'item9' |
a6b2f353 |
301 | "abc" =~ /[cab]/; # matches 'a' |
47f9c88b |
302 | |
303 | In the last statement, even though C<'c'> is the first character in |
304 | the class, C<'a'> matches because the first character position in the |
305 | string is the earliest point at which the regexp can match. |
306 | |
307 | /[yY][eE][sS]/; # match 'yes' in a case-insensitive way |
308 | # 'yes', 'Yes', 'YES', etc. |
309 | |
da75cd15 |
310 | This regexp displays a common task: perform a case-insensitive |
28c3722c |
311 | match. Perl provides a way of avoiding all those brackets by simply |
47f9c88b |
312 | appending an C<'i'> to the end of the match. Then C</[yY][eE][sS]/;> |
313 | can be rewritten as C</yes/i;>. The C<'i'> stands for |
7638d2dc |
314 | case-insensitive and is an example of a I<modifier> of the matching |
47f9c88b |
315 | operation. We will meet other modifiers later in the tutorial. |
316 | |
317 | We saw in the section above that there were ordinary characters, which |
318 | represented themselves, and special characters, which needed a |
319 | backslash C<\> to represent themselves. The same is true in a |
320 | character class, but the sets of ordinary and special characters |
321 | inside a character class are different than those outside a character |
7638d2dc |
322 | class. The special characters for a character class are C<-]\^$> (and |
353c6505 |
323 | the pattern delimiter, whatever it is). |
7638d2dc |
324 | C<]> is special because it denotes the end of a character class. C<$> is |
47f9c88b |
325 | special because it denotes a scalar variable. C<\> is special because |
326 | it is used in escape sequences, just like above. Here is how the |
327 | special characters C<]$\> are handled: |
328 | |
329 | /[\]c]def/; # matches ']def' or 'cdef' |
330 | $x = 'bcr'; |
a6b2f353 |
331 | /[$x]at/; # matches 'bat', 'cat', or 'rat' |
47f9c88b |
332 | /[\$x]at/; # matches '$at' or 'xat' |
333 | /[\\$x]at/; # matches '\at', 'bat, 'cat', or 'rat' |
334 | |
353c6505 |
335 | The last two are a little tricky. In C<[\$x]>, the backslash protects |
47f9c88b |
336 | the dollar sign, so the character class has two members C<$> and C<x>. |
337 | In C<[\\$x]>, the backslash is protected, so C<$x> is treated as a |
338 | variable and substituted in double quote fashion. |
339 | |
340 | The special character C<'-'> acts as a range operator within character |
341 | classes, so that a contiguous set of characters can be written as a |
342 | range. With ranges, the unwieldy C<[0123456789]> and C<[abc...xyz]> |
343 | become the svelte C<[0-9]> and C<[a-z]>. Some examples are |
344 | |
345 | /item[0-9]/; # matches 'item0' or ... or 'item9' |
346 | /[0-9bx-z]aa/; # matches '0aa', ..., '9aa', |
347 | # 'baa', 'xaa', 'yaa', or 'zaa' |
348 | /[0-9a-fA-F]/; # matches a hexadecimal digit |
36bbe248 |
349 | /[0-9a-zA-Z_]/; # matches a "word" character, |
7638d2dc |
350 | # like those in a Perl variable name |
47f9c88b |
351 | |
352 | If C<'-'> is the first or last character in a character class, it is |
353 | treated as an ordinary character; C<[-ab]>, C<[ab-]> and C<[a\-b]> are |
354 | all equivalent. |
355 | |
356 | The special character C<^> in the first position of a character class |
7638d2dc |
357 | denotes a I<negated character class>, which matches any character but |
a6b2f353 |
358 | those in the brackets. Both C<[...]> and C<[^...]> must match a |
47f9c88b |
359 | character, or the match fails. Then |
360 | |
361 | /[^a]at/; # doesn't match 'aat' or 'at', but matches |
362 | # all other 'bat', 'cat, '0at', '%at', etc. |
363 | /[^0-9]/; # matches a non-numeric character |
364 | /[a^]at/; # matches 'aat' or '^at'; here '^' is ordinary |
365 | |
28c3722c |
366 | Now, even C<[0-9]> can be a bother to write multiple times, so in the |
47f9c88b |
367 | interest of saving keystrokes and making regexps more readable, Perl |
7638d2dc |
368 | has several abbreviations for common character classes, as shown below. |
369 | Since the introduction of Unicode, these character classes match more |
370 | than just a few characters in the ISO 8859-1 range. |
47f9c88b |
371 | |
372 | =over 4 |
373 | |
374 | =item * |
551e1d92 |
375 | |
7638d2dc |
376 | \d matches a digit, not just [0-9] but also digits from non-roman scripts |
47f9c88b |
377 | |
378 | =item * |
551e1d92 |
379 | |
7638d2dc |
380 | \s matches a whitespace character, the set [\ \t\r\n\f] and others |
47f9c88b |
381 | |
382 | =item * |
551e1d92 |
383 | |
7638d2dc |
384 | \w matches a word character (alphanumeric or _), not just [0-9a-zA-Z_] |
385 | but also digits and characters from non-roman scripts |
47f9c88b |
386 | |
387 | =item * |
551e1d92 |
388 | |
7638d2dc |
389 | \D is a negated \d; it represents any other character than a digit, or [^\d] |
47f9c88b |
390 | |
391 | =item * |
551e1d92 |
392 | |
47f9c88b |
393 | \S is a negated \s; it represents any non-whitespace character [^\s] |
394 | |
395 | =item * |
551e1d92 |
396 | |
47f9c88b |
397 | \W is a negated \w; it represents any non-word character [^\w] |
398 | |
399 | =item * |
551e1d92 |
400 | |
7638d2dc |
401 | The period '.' matches any character but "\n" (unless the modifier C<//s> is |
402 | in effect, as explained below). |
47f9c88b |
403 | |
404 | =back |
405 | |
406 | The C<\d\s\w\D\S\W> abbreviations can be used both inside and outside |
407 | of character classes. Here are some in use: |
408 | |
409 | /\d\d:\d\d:\d\d/; # matches a hh:mm:ss time format |
410 | /[\d\s]/; # matches any digit or whitespace character |
411 | /\w\W\w/; # matches a word char, followed by a |
412 | # non-word char, followed by a word char |
413 | /..rt/; # matches any two chars, followed by 'rt' |
414 | /end\./; # matches 'end.' |
415 | /end[.]/; # same thing, matches 'end.' |
416 | |
417 | Because a period is a metacharacter, it needs to be escaped to match |
418 | as an ordinary period. Because, for example, C<\d> and C<\w> are sets |
419 | of characters, it is incorrect to think of C<[^\d\w]> as C<[\D\W]>; in |
420 | fact C<[^\d\w]> is the same as C<[^\w]>, which is the same as |
421 | C<[\W]>. Think DeMorgan's laws. |
422 | |
7638d2dc |
423 | An anchor useful in basic regexps is the I<word anchor> |
47f9c88b |
424 | C<\b>. This matches a boundary between a word character and a non-word |
425 | character C<\w\W> or C<\W\w>: |
426 | |
427 | $x = "Housecat catenates house and cat"; |
428 | $x =~ /cat/; # matches cat in 'housecat' |
429 | $x =~ /\bcat/; # matches cat in 'catenates' |
430 | $x =~ /cat\b/; # matches cat in 'housecat' |
431 | $x =~ /\bcat\b/; # matches 'cat' at end of string |
432 | |
433 | Note in the last example, the end of the string is considered a word |
434 | boundary. |
435 | |
436 | You might wonder why C<'.'> matches everything but C<"\n"> - why not |
437 | every character? The reason is that often one is matching against |
438 | lines and would like to ignore the newline characters. For instance, |
439 | while the string C<"\n"> represents one line, we would like to think |
28c3722c |
440 | of it as empty. Then |
47f9c88b |
441 | |
442 | "" =~ /^$/; # matches |
7638d2dc |
443 | "\n" =~ /^$/; # matches, $ anchors before "\n" |
47f9c88b |
444 | |
445 | "" =~ /./; # doesn't match; it needs a char |
446 | "" =~ /^.$/; # doesn't match; it needs a char |
447 | "\n" =~ /^.$/; # doesn't match; it needs a char other than "\n" |
448 | "a" =~ /^.$/; # matches |
7638d2dc |
449 | "a\n" =~ /^.$/; # matches, $ anchors before "\n" |
47f9c88b |
450 | |
451 | This behavior is convenient, because we usually want to ignore |
452 | newlines when we count and match characters in a line. Sometimes, |
453 | however, we want to keep track of newlines. We might even want C<^> |
454 | and C<$> to anchor at the beginning and end of lines within the |
455 | string, rather than just the beginning and end of the string. Perl |
456 | allows us to choose between ignoring and paying attention to newlines |
457 | by using the C<//s> and C<//m> modifiers. C<//s> and C<//m> stand for |
458 | single line and multi-line and they determine whether a string is to |
459 | be treated as one continuous string, or as a set of lines. The two |
460 | modifiers affect two aspects of how the regexp is interpreted: 1) how |
461 | the C<'.'> character class is defined, and 2) where the anchors C<^> |
462 | and C<$> are able to match. Here are the four possible combinations: |
463 | |
464 | =over 4 |
465 | |
466 | =item * |
551e1d92 |
467 | |
47f9c88b |
468 | no modifiers (//): Default behavior. C<'.'> matches any character |
469 | except C<"\n">. C<^> matches only at the beginning of the string and |
470 | C<$> matches only at the end or before a newline at the end. |
471 | |
472 | =item * |
551e1d92 |
473 | |
47f9c88b |
474 | s modifier (//s): Treat string as a single long line. C<'.'> matches |
475 | any character, even C<"\n">. C<^> matches only at the beginning of |
476 | the string and C<$> matches only at the end or before a newline at the |
477 | end. |
478 | |
479 | =item * |
551e1d92 |
480 | |
47f9c88b |
481 | m modifier (//m): Treat string as a set of multiple lines. C<'.'> |
482 | matches any character except C<"\n">. C<^> and C<$> are able to match |
483 | at the start or end of I<any> line within the string. |
484 | |
485 | =item * |
551e1d92 |
486 | |
47f9c88b |
487 | both s and m modifiers (//sm): Treat string as a single long line, but |
488 | detect multiple lines. C<'.'> matches any character, even |
489 | C<"\n">. C<^> and C<$>, however, are able to match at the start or end |
490 | of I<any> line within the string. |
491 | |
492 | =back |
493 | |
494 | Here are examples of C<//s> and C<//m> in action: |
495 | |
496 | $x = "There once was a girl\nWho programmed in Perl\n"; |
497 | |
498 | $x =~ /^Who/; # doesn't match, "Who" not at start of string |
499 | $x =~ /^Who/s; # doesn't match, "Who" not at start of string |
500 | $x =~ /^Who/m; # matches, "Who" at start of second line |
501 | $x =~ /^Who/sm; # matches, "Who" at start of second line |
502 | |
503 | $x =~ /girl.Who/; # doesn't match, "." doesn't match "\n" |
504 | $x =~ /girl.Who/s; # matches, "." matches "\n" |
505 | $x =~ /girl.Who/m; # doesn't match, "." doesn't match "\n" |
506 | $x =~ /girl.Who/sm; # matches, "." matches "\n" |
507 | |
3c12f9b9 |
508 | Most of the time, the default behavior is what is wanted, but C<//s> and |
47f9c88b |
509 | C<//m> are occasionally very useful. If C<//m> is being used, the start |
28c3722c |
510 | of the string can still be matched with C<\A> and the end of the string |
47f9c88b |
511 | can still be matched with the anchors C<\Z> (matches both the end and |
512 | the newline before, like C<$>), and C<\z> (matches only the end): |
513 | |
514 | $x =~ /^Who/m; # matches, "Who" at start of second line |
515 | $x =~ /\AWho/m; # doesn't match, "Who" is not at start of string |
516 | |
517 | $x =~ /girl$/m; # matches, "girl" at end of first line |
518 | $x =~ /girl\Z/m; # doesn't match, "girl" is not at end of string |
519 | |
520 | $x =~ /Perl\Z/m; # matches, "Perl" is at newline before end |
521 | $x =~ /Perl\z/m; # doesn't match, "Perl" is not at end of string |
522 | |
523 | We now know how to create choices among classes of characters in a |
524 | regexp. What about choices among words or character strings? Such |
525 | choices are described in the next section. |
526 | |
527 | =head2 Matching this or that |
528 | |
28c3722c |
529 | Sometimes we would like our regexp to be able to match different |
47f9c88b |
530 | possible words or character strings. This is accomplished by using |
7638d2dc |
531 | the I<alternation> metacharacter C<|>. To match C<dog> or C<cat>, we |
532 | form the regexp C<dog|cat>. As before, Perl will try to match the |
47f9c88b |
533 | regexp at the earliest possible point in the string. At each |
7638d2dc |
534 | character position, Perl will first try to match the first |
535 | alternative, C<dog>. If C<dog> doesn't match, Perl will then try the |
47f9c88b |
536 | next alternative, C<cat>. If C<cat> doesn't match either, then the |
7638d2dc |
537 | match fails and Perl moves to the next position in the string. Some |
47f9c88b |
538 | examples: |
539 | |
540 | "cats and dogs" =~ /cat|dog|bird/; # matches "cat" |
541 | "cats and dogs" =~ /dog|cat|bird/; # matches "cat" |
542 | |
543 | Even though C<dog> is the first alternative in the second regexp, |
544 | C<cat> is able to match earlier in the string. |
545 | |
546 | "cats" =~ /c|ca|cat|cats/; # matches "c" |
547 | "cats" =~ /cats|cat|ca|c/; # matches "cats" |
548 | |
549 | Here, all the alternatives match at the first string position, so the |
550 | first alternative is the one that matches. If some of the |
551 | alternatives are truncations of the others, put the longest ones first |
552 | to give them a chance to match. |
553 | |
554 | "cab" =~ /a|b|c/ # matches "c" |
555 | # /a|b|c/ == /[abc]/ |
556 | |
557 | The last example points out that character classes are like |
558 | alternations of characters. At a given character position, the first |
210b36aa |
559 | alternative that allows the regexp match to succeed will be the one |
47f9c88b |
560 | that matches. |
561 | |
562 | =head2 Grouping things and hierarchical matching |
563 | |
564 | Alternation allows a regexp to choose among alternatives, but by |
7638d2dc |
565 | itself it is unsatisfying. The reason is that each alternative is a whole |
47f9c88b |
566 | regexp, but sometime we want alternatives for just part of a |
567 | regexp. For instance, suppose we want to search for housecats or |
568 | housekeepers. The regexp C<housecat|housekeeper> fits the bill, but is |
569 | inefficient because we had to type C<house> twice. It would be nice to |
da75cd15 |
570 | have parts of the regexp be constant, like C<house>, and some |
47f9c88b |
571 | parts have alternatives, like C<cat|keeper>. |
572 | |
7638d2dc |
573 | The I<grouping> metacharacters C<()> solve this problem. Grouping |
47f9c88b |
574 | allows parts of a regexp to be treated as a single unit. Parts of a |
575 | regexp are grouped by enclosing them in parentheses. Thus we could solve |
576 | the C<housecat|housekeeper> by forming the regexp as |
577 | C<house(cat|keeper)>. The regexp C<house(cat|keeper)> means match |
578 | C<house> followed by either C<cat> or C<keeper>. Some more examples |
579 | are |
580 | |
581 | /(a|b)b/; # matches 'ab' or 'bb' |
582 | /(ac|b)b/; # matches 'acb' or 'bb' |
583 | /(^a|b)c/; # matches 'ac' at start of string or 'bc' anywhere |
584 | /(a|[bc])d/; # matches 'ad', 'bd', or 'cd' |
585 | |
586 | /house(cat|)/; # matches either 'housecat' or 'house' |
587 | /house(cat(s|)|)/; # matches either 'housecats' or 'housecat' or |
588 | # 'house'. Note groups can be nested. |
589 | |
590 | /(19|20|)\d\d/; # match years 19xx, 20xx, or the Y2K problem, xx |
591 | "20" =~ /(19|20|)\d\d/; # matches the null alternative '()\d\d', |
592 | # because '20\d\d' can't match |
593 | |
594 | Alternations behave the same way in groups as out of them: at a given |
595 | string position, the leftmost alternative that allows the regexp to |
210b36aa |
596 | match is taken. So in the last example at the first string position, |
47f9c88b |
597 | C<"20"> matches the second alternative, but there is nothing left over |
7638d2dc |
598 | to match the next two digits C<\d\d>. So Perl moves on to the next |
47f9c88b |
599 | alternative, which is the null alternative and that works, since |
600 | C<"20"> is two digits. |
601 | |
602 | The process of trying one alternative, seeing if it matches, and |
7638d2dc |
603 | moving on to the next alternative, while going back in the string |
604 | from where the previous alternative was tried, if it doesn't, is called |
605 | I<backtracking>. The term 'backtracking' comes from the idea that |
47f9c88b |
606 | matching a regexp is like a walk in the woods. Successfully matching |
607 | a regexp is like arriving at a destination. There are many possible |
608 | trailheads, one for each string position, and each one is tried in |
609 | order, left to right. From each trailhead there may be many paths, |
610 | some of which get you there, and some which are dead ends. When you |
611 | walk along a trail and hit a dead end, you have to backtrack along the |
612 | trail to an earlier point to try another trail. If you hit your |
613 | destination, you stop immediately and forget about trying all the |
614 | other trails. You are persistent, and only if you have tried all the |
615 | trails from all the trailheads and not arrived at your destination, do |
616 | you declare failure. To be concrete, here is a step-by-step analysis |
7638d2dc |
617 | of what Perl does when it tries to match the regexp |
47f9c88b |
618 | |
619 | "abcde" =~ /(abd|abc)(df|d|de)/; |
620 | |
621 | =over 4 |
622 | |
551e1d92 |
623 | =item 0 |
624 | |
625 | Start with the first letter in the string 'a'. |
626 | |
627 | =item 1 |
47f9c88b |
628 | |
551e1d92 |
629 | Try the first alternative in the first group 'abd'. |
47f9c88b |
630 | |
551e1d92 |
631 | =item 2 |
47f9c88b |
632 | |
551e1d92 |
633 | Match 'a' followed by 'b'. So far so good. |
634 | |
635 | =item 3 |
636 | |
637 | 'd' in the regexp doesn't match 'c' in the string - a dead |
47f9c88b |
638 | end. So backtrack two characters and pick the second alternative in |
639 | the first group 'abc'. |
640 | |
551e1d92 |
641 | =item 4 |
642 | |
643 | Match 'a' followed by 'b' followed by 'c'. We are on a roll |
47f9c88b |
644 | and have satisfied the first group. Set $1 to 'abc'. |
645 | |
551e1d92 |
646 | =item 5 |
647 | |
648 | Move on to the second group and pick the first alternative |
47f9c88b |
649 | 'df'. |
650 | |
551e1d92 |
651 | =item 6 |
47f9c88b |
652 | |
551e1d92 |
653 | Match the 'd'. |
654 | |
655 | =item 7 |
656 | |
657 | 'f' in the regexp doesn't match 'e' in the string, so a dead |
47f9c88b |
658 | end. Backtrack one character and pick the second alternative in the |
659 | second group 'd'. |
660 | |
551e1d92 |
661 | =item 8 |
662 | |
663 | 'd' matches. The second grouping is satisfied, so set $2 to |
47f9c88b |
664 | 'd'. |
665 | |
551e1d92 |
666 | =item 9 |
667 | |
668 | We are at the end of the regexp, so we are done! We have |
47f9c88b |
669 | matched 'abcd' out of the string "abcde". |
670 | |
671 | =back |
672 | |
673 | There are a couple of things to note about this analysis. First, the |
674 | third alternative in the second group 'de' also allows a match, but we |
675 | stopped before we got to it - at a given character position, leftmost |
676 | wins. Second, we were able to get a match at the first character |
677 | position of the string 'a'. If there were no matches at the first |
7638d2dc |
678 | position, Perl would move to the second character position 'b' and |
47f9c88b |
679 | attempt the match all over again. Only when all possible paths at all |
7638d2dc |
680 | possible character positions have been exhausted does Perl give |
681 | up and declare S<C<$string =~ /(abd|abc)(df|d|de)/;>> to be false. |
47f9c88b |
682 | |
683 | Even with all this work, regexp matching happens remarkably fast. To |
353c6505 |
684 | speed things up, Perl compiles the regexp into a compact sequence of |
685 | opcodes that can often fit inside a processor cache. When the code is |
7638d2dc |
686 | executed, these opcodes can then run at full throttle and search very |
687 | quickly. |
47f9c88b |
688 | |
689 | =head2 Extracting matches |
690 | |
691 | The grouping metacharacters C<()> also serve another completely |
692 | different function: they allow the extraction of the parts of a string |
693 | that matched. This is very useful to find out what matched and for |
694 | text processing in general. For each grouping, the part that matched |
695 | inside goes into the special variables C<$1>, C<$2>, etc. They can be |
696 | used just as ordinary variables: |
697 | |
698 | # extract hours, minutes, seconds |
2275acdc |
699 | if ($time =~ /(\d\d):(\d\d):(\d\d)/) { # match hh:mm:ss format |
700 | $hours = $1; |
701 | $minutes = $2; |
702 | $seconds = $3; |
703 | } |
47f9c88b |
704 | |
705 | Now, we know that in scalar context, |
7638d2dc |
706 | S<C<$time =~ /(\d\d):(\d\d):(\d\d)/>> returns a true or false |
47f9c88b |
707 | value. In list context, however, it returns the list of matched values |
708 | C<($1,$2,$3)>. So we could write the code more compactly as |
709 | |
710 | # extract hours, minutes, seconds |
711 | ($hours, $minutes, $second) = ($time =~ /(\d\d):(\d\d):(\d\d)/); |
712 | |
713 | If the groupings in a regexp are nested, C<$1> gets the group with the |
714 | leftmost opening parenthesis, C<$2> the next opening parenthesis, |
7638d2dc |
715 | etc. Here is a regexp with nested groups: |
47f9c88b |
716 | |
717 | /(ab(cd|ef)((gi)|j))/; |
718 | 1 2 34 |
719 | |
7638d2dc |
720 | If this regexp matches, C<$1> contains a string starting with |
721 | C<'ab'>, C<$2> is either set to C<'cd'> or C<'ef'>, C<$3> equals either |
722 | C<'gi'> or C<'j'>, and C<$4> is either set to C<'gi'>, just like C<$3>, |
723 | or it remains undefined. |
724 | |
725 | For convenience, Perl sets C<$+> to the string held by the highest numbered |
726 | C<$1>, C<$2>,... that got assigned (and, somewhat related, C<$^N> to the |
727 | value of the C<$1>, C<$2>,... most-recently assigned; i.e. the C<$1>, |
728 | C<$2>,... associated with the rightmost closing parenthesis used in the |
a01268b5 |
729 | match). |
47f9c88b |
730 | |
7638d2dc |
731 | |
732 | =head2 Backreferences |
733 | |
47f9c88b |
734 | Closely associated with the matching variables C<$1>, C<$2>, ... are |
7638d2dc |
735 | the I<backreferences> C<\1>, C<\2>,... Backreferences are simply |
47f9c88b |
736 | matching variables that can be used I<inside> a regexp. This is a |
7638d2dc |
737 | really nice feature -- what matches later in a regexp is made to depend on |
47f9c88b |
738 | what matched earlier in the regexp. Suppose we wanted to look |
7638d2dc |
739 | for doubled words in a text, like 'the the'. The following regexp finds |
47f9c88b |
740 | all 3-letter doubles with a space in between: |
741 | |
7638d2dc |
742 | /\b(\w\w\w)\s\1\b/; |
47f9c88b |
743 | |
744 | The grouping assigns a value to \1, so that the same 3 letter sequence |
7638d2dc |
745 | is used for both parts. |
746 | |
747 | A similar task is to find words consisting of two identical parts: |
47f9c88b |
748 | |
749 | % simple_grep '^(\w\w\w\w|\w\w\w|\w\w|\w)\1$' /usr/dict/words |
750 | beriberi |
751 | booboo |
752 | coco |
753 | mama |
754 | murmur |
755 | papa |
756 | |
757 | The regexp has a single grouping which considers 4-letter |
7638d2dc |
758 | combinations, then 3-letter combinations, etc., and uses C<\1> to look for |
47f9c88b |
759 | a repeat. Although C<$1> and C<\1> represent the same thing, care should be |
7638d2dc |
760 | taken to use matched variables C<$1>, C<$2>,... only I<outside> a regexp |
761 | and backreferences C<\1>, C<\2>,... only I<inside> a regexp; not doing |
762 | so may lead to surprising and unsatisfactory results. |
763 | |
764 | |
765 | =head2 Relative backreferences |
766 | |
767 | Counting the opening parentheses to get the correct number for a |
353c6505 |
768 | backreference is errorprone as soon as there is more than one |
7638d2dc |
769 | capturing group. A more convenient technique became available |
770 | with Perl 5.10: relative backreferences. To refer to the immediately |
771 | preceding capture group one now may write C<\g{-1}>, the next but |
772 | last is available via C<\g{-2}>, and so on. |
773 | |
774 | Another good reason in addition to readability and maintainability |
775 | for using relative backreferences is illustrated by the following example, |
776 | where a simple pattern for matching peculiar strings is used: |
777 | |
353c6505 |
778 | $a99a = '([a-z])(\d)\2\1'; # matches a11a, g22g, x33x, etc. |
7638d2dc |
779 | |
780 | Now that we have this pattern stored as a handy string, we might feel |
781 | tempted to use it as a part of some other pattern: |
782 | |
783 | $line = "code=e99e"; |
784 | if ($line =~ /^(\w+)=$a99a$/){ # unexpected behavior! |
785 | print "$1 is valid\n"; |
786 | } else { |
787 | print "bad line: '$line'\n"; |
788 | } |
789 | |
790 | But this doesn't match -- at least not the way one might expect. Only |
791 | after inserting the interpolated C<$a99a> and looking at the resulting |
792 | full text of the regexp is it obvious that the backreferences have |
793 | backfired -- the subexpression C<(\w+)> has snatched number 1 and |
794 | demoted the groups in C<$a99a> by one rank. This can be avoided by |
795 | using relative backreferences: |
796 | |
797 | $a99a = '([a-z])(\d)\g{-1}\g{-2}'; # safe for being interpolated |
798 | |
799 | |
800 | =head2 Named backreferences |
801 | |
802 | Perl 5.10 also introduced named capture buffers and named backreferences. |
803 | To attach a name to a capturing group, you write either |
804 | C<< (?<name>...) >> or C<< (?'name'...) >>. The backreference may |
805 | then be written as C<\g{name}>. It is permissible to attach the |
806 | same name to more than one group, but then only the leftmost one of the |
807 | eponymous set can be referenced. Outside of the pattern a named |
808 | capture buffer is accessible through the C<%+> hash. |
809 | |
353c6505 |
810 | Assuming that we have to match calendar dates which may be given in one |
7638d2dc |
811 | of the three formats yyyy-mm-dd, mm/dd/yyyy or dd.mm.yyyy, we can write |
353c6505 |
812 | three suitable patterns where we use 'd', 'm' and 'y' respectively as the |
7638d2dc |
813 | names of the buffers capturing the pertaining components of a date. The |
814 | matching operation combines the three patterns as alternatives: |
815 | |
816 | $fmt1 = '(?<y>\d\d\d\d)-(?<m>\d\d)-(?<d>\d\d)'; |
817 | $fmt2 = '(?<m>\d\d)/(?<d>\d\d)/(?<y>\d\d\d\d)'; |
818 | $fmt3 = '(?<d>\d\d)\.(?<m>\d\d)\.(?<y>\d\d\d\d)'; |
819 | for my $d qw( 2006-10-21 15.01.2007 10/31/2005 ){ |
820 | if ( $d =~ m{$fmt1|$fmt2|$fmt3} ){ |
821 | print "day=$+{d} month=$+{m} year=$+{y}\n"; |
822 | } |
823 | } |
824 | |
825 | If any of the alternatives matches, the hash C<%+> is bound to contain the |
826 | three key-value pairs. |
827 | |
828 | |
829 | =head2 Alternative capture group numbering |
830 | |
831 | Yet another capturing group numbering technique (also as from Perl 5.10) |
832 | deals with the problem of referring to groups within a set of alternatives. |
833 | Consider a pattern for matching a time of the day, civil or military style: |
47f9c88b |
834 | |
7638d2dc |
835 | if ( $time =~ /(\d\d|\d):(\d\d)|(\d\d)(\d\d)/ ){ |
836 | # process hour and minute |
837 | } |
838 | |
839 | Processing the results requires an additional if statement to determine |
353c6505 |
840 | whether C<$1> and C<$2> or C<$3> and C<$4> contain the goodies. It would |
7638d2dc |
841 | be easier if we could use buffer numbers 1 and 2 in second alternative as |
353c6505 |
842 | well, and this is exactly what the parenthesized construct C<(?|...)>, |
7638d2dc |
843 | set around an alternative achieves. Here is an extended version of the |
844 | previous pattern: |
845 | |
846 | if ( $time =~ /(?|(\d\d|\d):(\d\d)|(\d\d)(\d\d))\s+([A-Z][A-Z][A-Z])/ ){ |
847 | print "hour=$1 minute=$2 zone=$3\n"; |
848 | } |
849 | |
850 | Within the alternative numbering group, buffer numbers start at the same |
851 | position for each alternative. After the group, numbering continues |
353c6505 |
852 | with one higher than the maximum reached across all the alternatives. |
7638d2dc |
853 | |
854 | =head2 Position information |
855 | |
856 | In addition to what was matched, Perl (since 5.6.0) also provides the |
857 | positions of what was matched as contents of the C<@-> and C<@+> |
47f9c88b |
858 | arrays. C<$-[0]> is the position of the start of the entire match and |
859 | C<$+[0]> is the position of the end. Similarly, C<$-[n]> is the |
860 | position of the start of the C<$n> match and C<$+[n]> is the position |
861 | of the end. If C<$n> is undefined, so are C<$-[n]> and C<$+[n]>. Then |
862 | this code |
863 | |
864 | $x = "Mmm...donut, thought Homer"; |
865 | $x =~ /^(Mmm|Yech)\.\.\.(donut|peas)/; # matches |
866 | foreach $expr (1..$#-) { |
867 | print "Match $expr: '${$expr}' at position ($-[$expr],$+[$expr])\n"; |
868 | } |
869 | |
870 | prints |
871 | |
872 | Match 1: 'Mmm' at position (0,3) |
873 | Match 2: 'donut' at position (6,11) |
874 | |
875 | Even if there are no groupings in a regexp, it is still possible to |
7638d2dc |
876 | find out what exactly matched in a string. If you use them, Perl |
47f9c88b |
877 | will set C<$`> to the part of the string before the match, will set C<$&> |
878 | to the part of the string that matched, and will set C<$'> to the part |
879 | of the string after the match. An example: |
880 | |
881 | $x = "the cat caught the mouse"; |
882 | $x =~ /cat/; # $` = 'the ', $& = 'cat', $' = ' caught the mouse' |
883 | $x =~ /the/; # $` = '', $& = 'the', $' = ' cat caught the mouse' |
884 | |
7638d2dc |
885 | In the second match, C<$`> equals C<''> because the regexp matched at the |
886 | first character position in the string and stopped; it never saw the |
47f9c88b |
887 | second 'the'. It is important to note that using C<$`> and C<$'> |
7638d2dc |
888 | slows down regexp matching quite a bit, while C<$&> slows it down to a |
47f9c88b |
889 | lesser extent, because if they are used in one regexp in a program, |
7638d2dc |
890 | they are generated for I<all> regexps in the program. So if raw |
47f9c88b |
891 | performance is a goal of your application, they should be avoided. |
7638d2dc |
892 | If you need to extract the corresponding substrings, use C<@-> and |
893 | C<@+> instead: |
47f9c88b |
894 | |
895 | $` is the same as substr( $x, 0, $-[0] ) |
896 | $& is the same as substr( $x, $-[0], $+[0]-$-[0] ) |
897 | $' is the same as substr( $x, $+[0] ) |
898 | |
7638d2dc |
899 | |
900 | =head2 Non-capturing groupings |
901 | |
353c6505 |
902 | A group that is required to bundle a set of alternatives may or may not be |
7638d2dc |
903 | useful as a capturing group. If it isn't, it just creates a superfluous |
904 | addition to the set of available capture buffer values, inside as well as |
905 | outside the regexp. Non-capturing groupings, denoted by C<(?:regexp)>, |
353c6505 |
906 | still allow the regexp to be treated as a single unit, but don't establish |
7638d2dc |
907 | a capturing buffer at the same time. Both capturing and non-capturing |
908 | groupings are allowed to co-exist in the same regexp. Because there is |
909 | no extraction, non-capturing groupings are faster than capturing |
910 | groupings. Non-capturing groupings are also handy for choosing exactly |
911 | which parts of a regexp are to be extracted to matching variables: |
912 | |
913 | # match a number, $1-$4 are set, but we only want $1 |
914 | /([+-]?\ *(\d+(\.\d*)?|\.\d+)([eE][+-]?\d+)?)/; |
915 | |
916 | # match a number faster , only $1 is set |
917 | /([+-]?\ *(?:\d+(?:\.\d*)?|\.\d+)(?:[eE][+-]?\d+)?)/; |
918 | |
919 | # match a number, get $1 = whole number, $2 = exponent |
920 | /([+-]?\ *(?:\d+(?:\.\d*)?|\.\d+)(?:[eE]([+-]?\d+))?)/; |
921 | |
922 | Non-capturing groupings are also useful for removing nuisance |
923 | elements gathered from a split operation where parentheses are |
924 | required for some reason: |
925 | |
926 | $x = '12aba34ba5'; |
927 | @num = split /(a|b)+/, $x; # @num = ('12','a','34','b','5') |
928 | @num = split /(?:a|b)+/, $x; # @num = ('12','34','5') |
929 | |
930 | |
47f9c88b |
931 | =head2 Matching repetitions |
932 | |
933 | The examples in the previous section display an annoying weakness. We |
7638d2dc |
934 | were only matching 3-letter words, or chunks of words of 4 letters or |
935 | less. We'd like to be able to match words or, more generally, strings |
936 | of any length, without writing out tedious alternatives like |
47f9c88b |
937 | C<\w\w\w\w|\w\w\w|\w\w|\w>. |
938 | |
7638d2dc |
939 | This is exactly the problem the I<quantifier> metacharacters C<?>, |
940 | C<*>, C<+>, and C<{}> were created for. They allow us to delimit the |
941 | number of repeats for a portion of a regexp we consider to be a |
47f9c88b |
942 | match. Quantifiers are put immediately after the character, character |
943 | class, or grouping that we want to specify. They have the following |
944 | meanings: |
945 | |
946 | =over 4 |
947 | |
551e1d92 |
948 | =item * |
47f9c88b |
949 | |
7638d2dc |
950 | C<a?> means: match 'a' 1 or 0 times |
47f9c88b |
951 | |
551e1d92 |
952 | =item * |
953 | |
7638d2dc |
954 | C<a*> means: match 'a' 0 or more times, i.e., any number of times |
551e1d92 |
955 | |
956 | =item * |
47f9c88b |
957 | |
7638d2dc |
958 | C<a+> means: match 'a' 1 or more times, i.e., at least once |
551e1d92 |
959 | |
960 | =item * |
961 | |
7638d2dc |
962 | C<a{n,m}> means: match at least C<n> times, but not more than C<m> |
47f9c88b |
963 | times. |
964 | |
551e1d92 |
965 | =item * |
966 | |
7638d2dc |
967 | C<a{n,}> means: match at least C<n> or more times |
551e1d92 |
968 | |
969 | =item * |
47f9c88b |
970 | |
7638d2dc |
971 | C<a{n}> means: match exactly C<n> times |
47f9c88b |
972 | |
973 | =back |
974 | |
975 | Here are some examples: |
976 | |
7638d2dc |
977 | /[a-z]+\s+\d*/; # match a lowercase word, at least one space, and |
47f9c88b |
978 | # any number of digits |
979 | /(\w+)\s+\1/; # match doubled words of arbitrary length |
980 | /y(es)?/i; # matches 'y', 'Y', or a case-insensitive 'yes' |
981 | $year =~ /\d{2,4}/; # make sure year is at least 2 but not more |
982 | # than 4 digits |
983 | $year =~ /\d{4}|\d{2}/; # better match; throw out 3 digit dates |
984 | $year =~ /\d{2}(\d{2})?/; # same thing written differently. However, |
985 | # this produces $1 and the other does not. |
986 | |
987 | % simple_grep '^(\w+)\1$' /usr/dict/words # isn't this easier? |
988 | beriberi |
989 | booboo |
990 | coco |
991 | mama |
992 | murmur |
993 | papa |
994 | |
7638d2dc |
995 | For all of these quantifiers, Perl will try to match as much of the |
47f9c88b |
996 | string as possible, while still allowing the regexp to succeed. Thus |
7638d2dc |
997 | with C</a?.../>, Perl will first try to match the regexp with the C<a> |
998 | present; if that fails, Perl will try to match the regexp without the |
47f9c88b |
999 | C<a> present. For the quantifier C<*>, we get the following: |
1000 | |
1001 | $x = "the cat in the hat"; |
1002 | $x =~ /^(.*)(cat)(.*)$/; # matches, |
1003 | # $1 = 'the ' |
1004 | # $2 = 'cat' |
1005 | # $3 = ' in the hat' |
1006 | |
1007 | Which is what we might expect, the match finds the only C<cat> in the |
1008 | string and locks onto it. Consider, however, this regexp: |
1009 | |
1010 | $x =~ /^(.*)(at)(.*)$/; # matches, |
1011 | # $1 = 'the cat in the h' |
1012 | # $2 = 'at' |
7638d2dc |
1013 | # $3 = '' (0 characters match) |
47f9c88b |
1014 | |
7638d2dc |
1015 | One might initially guess that Perl would find the C<at> in C<cat> and |
47f9c88b |
1016 | stop there, but that wouldn't give the longest possible string to the |
1017 | first quantifier C<.*>. Instead, the first quantifier C<.*> grabs as |
1018 | much of the string as possible while still having the regexp match. In |
a6b2f353 |
1019 | this example, that means having the C<at> sequence with the final C<at> |
47f9c88b |
1020 | in the string. The other important principle illustrated here is that |
1021 | when there are two or more elements in a regexp, the I<leftmost> |
1022 | quantifier, if there is one, gets to grab as much the string as |
1023 | possible, leaving the rest of the regexp to fight over scraps. Thus in |
1024 | our example, the first quantifier C<.*> grabs most of the string, while |
1025 | the second quantifier C<.*> gets the empty string. Quantifiers that |
7638d2dc |
1026 | grab as much of the string as possible are called I<maximal match> or |
1027 | I<greedy> quantifiers. |
47f9c88b |
1028 | |
1029 | When a regexp can match a string in several different ways, we can use |
1030 | the principles above to predict which way the regexp will match: |
1031 | |
1032 | =over 4 |
1033 | |
1034 | =item * |
551e1d92 |
1035 | |
47f9c88b |
1036 | Principle 0: Taken as a whole, any regexp will be matched at the |
1037 | earliest possible position in the string. |
1038 | |
1039 | =item * |
551e1d92 |
1040 | |
47f9c88b |
1041 | Principle 1: In an alternation C<a|b|c...>, the leftmost alternative |
1042 | that allows a match for the whole regexp will be the one used. |
1043 | |
1044 | =item * |
551e1d92 |
1045 | |
47f9c88b |
1046 | Principle 2: The maximal matching quantifiers C<?>, C<*>, C<+> and |
1047 | C<{n,m}> will in general match as much of the string as possible while |
1048 | still allowing the whole regexp to match. |
1049 | |
1050 | =item * |
551e1d92 |
1051 | |
47f9c88b |
1052 | Principle 3: If there are two or more elements in a regexp, the |
1053 | leftmost greedy quantifier, if any, will match as much of the string |
1054 | as possible while still allowing the whole regexp to match. The next |
1055 | leftmost greedy quantifier, if any, will try to match as much of the |
1056 | string remaining available to it as possible, while still allowing the |
1057 | whole regexp to match. And so on, until all the regexp elements are |
1058 | satisfied. |
1059 | |
1060 | =back |
1061 | |
7638d2dc |
1062 | As we have seen above, Principle 0 overrides the others -- the regexp |
47f9c88b |
1063 | will be matched as early as possible, with the other principles |
1064 | determining how the regexp matches at that earliest character |
1065 | position. |
1066 | |
1067 | Here is an example of these principles in action: |
1068 | |
1069 | $x = "The programming republic of Perl"; |
1070 | $x =~ /^(.+)(e|r)(.*)$/; # matches, |
1071 | # $1 = 'The programming republic of Pe' |
1072 | # $2 = 'r' |
1073 | # $3 = 'l' |
1074 | |
1075 | This regexp matches at the earliest string position, C<'T'>. One |
1076 | might think that C<e>, being leftmost in the alternation, would be |
1077 | matched, but C<r> produces the longest string in the first quantifier. |
1078 | |
1079 | $x =~ /(m{1,2})(.*)$/; # matches, |
1080 | # $1 = 'mm' |
1081 | # $2 = 'ing republic of Perl' |
1082 | |
1083 | Here, The earliest possible match is at the first C<'m'> in |
1084 | C<programming>. C<m{1,2}> is the first quantifier, so it gets to match |
1085 | a maximal C<mm>. |
1086 | |
1087 | $x =~ /.*(m{1,2})(.*)$/; # matches, |
1088 | # $1 = 'm' |
1089 | # $2 = 'ing republic of Perl' |
1090 | |
1091 | Here, the regexp matches at the start of the string. The first |
1092 | quantifier C<.*> grabs as much as possible, leaving just a single |
1093 | C<'m'> for the second quantifier C<m{1,2}>. |
1094 | |
1095 | $x =~ /(.?)(m{1,2})(.*)$/; # matches, |
1096 | # $1 = 'a' |
1097 | # $2 = 'mm' |
1098 | # $3 = 'ing republic of Perl' |
1099 | |
1100 | Here, C<.?> eats its maximal one character at the earliest possible |
1101 | position in the string, C<'a'> in C<programming>, leaving C<m{1,2}> |
1102 | the opportunity to match both C<m>'s. Finally, |
1103 | |
1104 | "aXXXb" =~ /(X*)/; # matches with $1 = '' |
1105 | |
1106 | because it can match zero copies of C<'X'> at the beginning of the |
1107 | string. If you definitely want to match at least one C<'X'>, use |
1108 | C<X+>, not C<X*>. |
1109 | |
1110 | Sometimes greed is not good. At times, we would like quantifiers to |
1111 | match a I<minimal> piece of string, rather than a maximal piece. For |
7638d2dc |
1112 | this purpose, Larry Wall created the I<minimal match> or |
1113 | I<non-greedy> quantifiers C<??>, C<*?>, C<+?>, and C<{}?>. These are |
47f9c88b |
1114 | the usual quantifiers with a C<?> appended to them. They have the |
1115 | following meanings: |
1116 | |
1117 | =over 4 |
1118 | |
551e1d92 |
1119 | =item * |
1120 | |
7638d2dc |
1121 | C<a??> means: match 'a' 0 or 1 times. Try 0 first, then 1. |
47f9c88b |
1122 | |
551e1d92 |
1123 | =item * |
1124 | |
7638d2dc |
1125 | C<a*?> means: match 'a' 0 or more times, i.e., any number of times, |
47f9c88b |
1126 | but as few times as possible |
1127 | |
551e1d92 |
1128 | =item * |
1129 | |
7638d2dc |
1130 | C<a+?> means: match 'a' 1 or more times, i.e., at least once, but |
47f9c88b |
1131 | as few times as possible |
1132 | |
551e1d92 |
1133 | =item * |
1134 | |
7638d2dc |
1135 | C<a{n,m}?> means: match at least C<n> times, not more than C<m> |
47f9c88b |
1136 | times, as few times as possible |
1137 | |
551e1d92 |
1138 | =item * |
1139 | |
7638d2dc |
1140 | C<a{n,}?> means: match at least C<n> times, but as few times as |
47f9c88b |
1141 | possible |
1142 | |
551e1d92 |
1143 | =item * |
1144 | |
7638d2dc |
1145 | C<a{n}?> means: match exactly C<n> times. Because we match exactly |
47f9c88b |
1146 | C<n> times, C<a{n}?> is equivalent to C<a{n}> and is just there for |
1147 | notational consistency. |
1148 | |
1149 | =back |
1150 | |
1151 | Let's look at the example above, but with minimal quantifiers: |
1152 | |
1153 | $x = "The programming republic of Perl"; |
1154 | $x =~ /^(.+?)(e|r)(.*)$/; # matches, |
1155 | # $1 = 'Th' |
1156 | # $2 = 'e' |
1157 | # $3 = ' programming republic of Perl' |
1158 | |
1159 | The minimal string that will allow both the start of the string C<^> |
1160 | and the alternation to match is C<Th>, with the alternation C<e|r> |
1161 | matching C<e>. The second quantifier C<.*> is free to gobble up the |
1162 | rest of the string. |
1163 | |
1164 | $x =~ /(m{1,2}?)(.*?)$/; # matches, |
1165 | # $1 = 'm' |
1166 | # $2 = 'ming republic of Perl' |
1167 | |
1168 | The first string position that this regexp can match is at the first |
1169 | C<'m'> in C<programming>. At this position, the minimal C<m{1,2}?> |
1170 | matches just one C<'m'>. Although the second quantifier C<.*?> would |
1171 | prefer to match no characters, it is constrained by the end-of-string |
1172 | anchor C<$> to match the rest of the string. |
1173 | |
1174 | $x =~ /(.*?)(m{1,2}?)(.*)$/; # matches, |
1175 | # $1 = 'The progra' |
1176 | # $2 = 'm' |
1177 | # $3 = 'ming republic of Perl' |
1178 | |
1179 | In this regexp, you might expect the first minimal quantifier C<.*?> |
1180 | to match the empty string, because it is not constrained by a C<^> |
1181 | anchor to match the beginning of the word. Principle 0 applies here, |
1182 | however. Because it is possible for the whole regexp to match at the |
1183 | start of the string, it I<will> match at the start of the string. Thus |
1184 | the first quantifier has to match everything up to the first C<m>. The |
1185 | second minimal quantifier matches just one C<m> and the third |
1186 | quantifier matches the rest of the string. |
1187 | |
1188 | $x =~ /(.??)(m{1,2})(.*)$/; # matches, |
1189 | # $1 = 'a' |
1190 | # $2 = 'mm' |
1191 | # $3 = 'ing republic of Perl' |
1192 | |
1193 | Just as in the previous regexp, the first quantifier C<.??> can match |
1194 | earliest at position C<'a'>, so it does. The second quantifier is |
1195 | greedy, so it matches C<mm>, and the third matches the rest of the |
1196 | string. |
1197 | |
1198 | We can modify principle 3 above to take into account non-greedy |
1199 | quantifiers: |
1200 | |
1201 | =over 4 |
1202 | |
1203 | =item * |
551e1d92 |
1204 | |
47f9c88b |
1205 | Principle 3: If there are two or more elements in a regexp, the |
1206 | leftmost greedy (non-greedy) quantifier, if any, will match as much |
1207 | (little) of the string as possible while still allowing the whole |
1208 | regexp to match. The next leftmost greedy (non-greedy) quantifier, if |
1209 | any, will try to match as much (little) of the string remaining |
1210 | available to it as possible, while still allowing the whole regexp to |
1211 | match. And so on, until all the regexp elements are satisfied. |
1212 | |
1213 | =back |
1214 | |
1215 | Just like alternation, quantifiers are also susceptible to |
1216 | backtracking. Here is a step-by-step analysis of the example |
1217 | |
1218 | $x = "the cat in the hat"; |
1219 | $x =~ /^(.*)(at)(.*)$/; # matches, |
1220 | # $1 = 'the cat in the h' |
1221 | # $2 = 'at' |
1222 | # $3 = '' (0 matches) |
1223 | |
1224 | =over 4 |
1225 | |
551e1d92 |
1226 | =item 0 |
1227 | |
1228 | Start with the first letter in the string 't'. |
47f9c88b |
1229 | |
551e1d92 |
1230 | =item 1 |
1231 | |
1232 | The first quantifier '.*' starts out by matching the whole |
47f9c88b |
1233 | string 'the cat in the hat'. |
1234 | |
551e1d92 |
1235 | =item 2 |
1236 | |
1237 | 'a' in the regexp element 'at' doesn't match the end of the |
47f9c88b |
1238 | string. Backtrack one character. |
1239 | |
551e1d92 |
1240 | =item 3 |
1241 | |
1242 | 'a' in the regexp element 'at' still doesn't match the last |
47f9c88b |
1243 | letter of the string 't', so backtrack one more character. |
1244 | |
551e1d92 |
1245 | =item 4 |
1246 | |
1247 | Now we can match the 'a' and the 't'. |
47f9c88b |
1248 | |
551e1d92 |
1249 | =item 5 |
1250 | |
1251 | Move on to the third element '.*'. Since we are at the end of |
47f9c88b |
1252 | the string and '.*' can match 0 times, assign it the empty string. |
1253 | |
551e1d92 |
1254 | =item 6 |
1255 | |
1256 | We are done! |
47f9c88b |
1257 | |
1258 | =back |
1259 | |
1260 | Most of the time, all this moving forward and backtracking happens |
7638d2dc |
1261 | quickly and searching is fast. There are some pathological regexps, |
47f9c88b |
1262 | however, whose execution time exponentially grows with the size of the |
1263 | string. A typical structure that blows up in your face is of the form |
1264 | |
1265 | /(a|b+)*/; |
1266 | |
1267 | The problem is the nested indeterminate quantifiers. There are many |
1268 | different ways of partitioning a string of length n between the C<+> |
1269 | and C<*>: one repetition with C<b+> of length n, two repetitions with |
1270 | the first C<b+> length k and the second with length n-k, m repetitions |
1271 | whose bits add up to length n, etc. In fact there are an exponential |
7638d2dc |
1272 | number of ways to partition a string as a function of its length. A |
47f9c88b |
1273 | regexp may get lucky and match early in the process, but if there is |
7638d2dc |
1274 | no match, Perl will try I<every> possibility before giving up. So be |
47f9c88b |
1275 | careful with nested C<*>'s, C<{n,m}>'s, and C<+>'s. The book |
7638d2dc |
1276 | I<Mastering Regular Expressions> by Jeffrey Friedl gives a wonderful |
47f9c88b |
1277 | discussion of this and other efficiency issues. |
1278 | |
7638d2dc |
1279 | |
1280 | =head2 Possessive quantifiers |
1281 | |
1282 | Backtracking during the relentless search for a match may be a waste |
1283 | of time, particularly when the match is bound to fail. Consider |
1284 | the simple pattern |
1285 | |
1286 | /^\w+\s+\w+$/; # a word, spaces, a word |
1287 | |
1288 | Whenever this is applied to a string which doesn't quite meet the |
1289 | pattern's expectations such as S<C<"abc ">> or S<C<"abc def ">>, |
353c6505 |
1290 | the regex engine will backtrack, approximately once for each character |
1291 | in the string. But we know that there is no way around taking I<all> |
1292 | of the initial word characters to match the first repetition, that I<all> |
7638d2dc |
1293 | spaces must be eaten by the middle part, and the same goes for the second |
353c6505 |
1294 | word. |
1295 | |
1296 | With the introduction of the I<possessive quantifiers> in Perl 5.10, we |
1297 | have a way of instructing the regex engine not to backtrack, with the |
1298 | usual quantifiers with a C<+> appended to them. This makes them greedy as |
1299 | well as stingy; once they succeed they won't give anything back to permit |
1300 | another solution. They have the following meanings: |
7638d2dc |
1301 | |
1302 | =over 4 |
1303 | |
1304 | =item * |
1305 | |
353c6505 |
1306 | C<a{n,m}+> means: match at least C<n> times, not more than C<m> times, |
1307 | as many times as possible, and don't give anything up. C<a?+> is short |
7638d2dc |
1308 | for C<a{0,1}+> |
1309 | |
1310 | =item * |
1311 | |
1312 | C<a{n,}+> means: match at least C<n> times, but as many times as possible, |
353c6505 |
1313 | and don't give anything up. C<a*+> is short for C<a{0,}+> and C<a++> is |
7638d2dc |
1314 | short for C<a{1,}+>. |
1315 | |
1316 | =item * |
1317 | |
1318 | C<a{n}+> means: match exactly C<n> times. It is just there for |
1319 | notational consistency. |
1320 | |
1321 | =back |
1322 | |
353c6505 |
1323 | These possessive quantifiers represent a special case of a more general |
1324 | concept, the I<independent subexpression>, see below. |
7638d2dc |
1325 | |
1326 | As an example where a possessive quantifier is suitable we consider |
1327 | matching a quoted string, as it appears in several programming languages. |
1328 | The backslash is used as an escape character that indicates that the |
1329 | next character is to be taken literally, as another character for the |
1330 | string. Therefore, after the opening quote, we expect a (possibly |
353c6505 |
1331 | empty) sequence of alternatives: either some character except an |
7638d2dc |
1332 | unescaped quote or backslash or an escaped character. |
1333 | |
1334 | /"(?:[^"\\]++|\\.)*+"/; |
1335 | |
1336 | |
47f9c88b |
1337 | =head2 Building a regexp |
1338 | |
1339 | At this point, we have all the basic regexp concepts covered, so let's |
1340 | give a more involved example of a regular expression. We will build a |
1341 | regexp that matches numbers. |
1342 | |
1343 | The first task in building a regexp is to decide what we want to match |
1344 | and what we want to exclude. In our case, we want to match both |
1345 | integers and floating point numbers and we want to reject any string |
1346 | that isn't a number. |
1347 | |
1348 | The next task is to break the problem down into smaller problems that |
1349 | are easily converted into a regexp. |
1350 | |
1351 | The simplest case is integers. These consist of a sequence of digits, |
1352 | with an optional sign in front. The digits we can represent with |
1353 | C<\d+> and the sign can be matched with C<[+-]>. Thus the integer |
1354 | regexp is |
1355 | |
1356 | /[+-]?\d+/; # matches integers |
1357 | |
1358 | A floating point number potentially has a sign, an integral part, a |
1359 | decimal point, a fractional part, and an exponent. One or more of these |
1360 | parts is optional, so we need to check out the different |
1361 | possibilities. Floating point numbers which are in proper form include |
1362 | 123., 0.345, .34, -1e6, and 25.4E-72. As with integers, the sign out |
1363 | front is completely optional and can be matched by C<[+-]?>. We can |
1364 | see that if there is no exponent, floating point numbers must have a |
1365 | decimal point, otherwise they are integers. We might be tempted to |
1366 | model these with C<\d*\.\d*>, but this would also match just a single |
1367 | decimal point, which is not a number. So the three cases of floating |
7638d2dc |
1368 | point number without exponent are |
47f9c88b |
1369 | |
1370 | /[+-]?\d+\./; # 1., 321., etc. |
1371 | /[+-]?\.\d+/; # .1, .234, etc. |
1372 | /[+-]?\d+\.\d+/; # 1.0, 30.56, etc. |
1373 | |
1374 | These can be combined into a single regexp with a three-way alternation: |
1375 | |
1376 | /[+-]?(\d+\.\d+|\d+\.|\.\d+)/; # floating point, no exponent |
1377 | |
1378 | In this alternation, it is important to put C<'\d+\.\d+'> before |
1379 | C<'\d+\.'>. If C<'\d+\.'> were first, the regexp would happily match that |
1380 | and ignore the fractional part of the number. |
1381 | |
1382 | Now consider floating point numbers with exponents. The key |
1383 | observation here is that I<both> integers and numbers with decimal |
1384 | points are allowed in front of an exponent. Then exponents, like the |
1385 | overall sign, are independent of whether we are matching numbers with |
1386 | or without decimal points, and can be 'decoupled' from the |
1387 | mantissa. The overall form of the regexp now becomes clear: |
1388 | |
1389 | /^(optional sign)(integer | f.p. mantissa)(optional exponent)$/; |
1390 | |
1391 | The exponent is an C<e> or C<E>, followed by an integer. So the |
1392 | exponent regexp is |
1393 | |
1394 | /[eE][+-]?\d+/; # exponent |
1395 | |
1396 | Putting all the parts together, we get a regexp that matches numbers: |
1397 | |
1398 | /^[+-]?(\d+\.\d+|\d+\.|\.\d+|\d+)([eE][+-]?\d+)?$/; # Ta da! |
1399 | |
1400 | Long regexps like this may impress your friends, but can be hard to |
1401 | decipher. In complex situations like this, the C<//x> modifier for a |
1402 | match is invaluable. It allows one to put nearly arbitrary whitespace |
1403 | and comments into a regexp without affecting their meaning. Using it, |
1404 | we can rewrite our 'extended' regexp in the more pleasing form |
1405 | |
1406 | /^ |
1407 | [+-]? # first, match an optional sign |
1408 | ( # then match integers or f.p. mantissas: |
1409 | \d+\.\d+ # mantissa of the form a.b |
1410 | |\d+\. # mantissa of the form a. |
1411 | |\.\d+ # mantissa of the form .b |
1412 | |\d+ # integer of the form a |
1413 | ) |
1414 | ([eE][+-]?\d+)? # finally, optionally match an exponent |
1415 | $/x; |
1416 | |
1417 | If whitespace is mostly irrelevant, how does one include space |
1418 | characters in an extended regexp? The answer is to backslash it |
7638d2dc |
1419 | S<C<'\ '>> or put it in a character class S<C<[ ]>>. The same thing |
47f9c88b |
1420 | goes for pound signs, use C<\#> or C<[#]>. For instance, Perl allows |
7638d2dc |
1421 | a space between the sign and the mantissa or integer, and we could add |
47f9c88b |
1422 | this to our regexp as follows: |
1423 | |
1424 | /^ |
1425 | [+-]?\ * # first, match an optional sign *and space* |
1426 | ( # then match integers or f.p. mantissas: |
1427 | \d+\.\d+ # mantissa of the form a.b |
1428 | |\d+\. # mantissa of the form a. |
1429 | |\.\d+ # mantissa of the form .b |
1430 | |\d+ # integer of the form a |
1431 | ) |
1432 | ([eE][+-]?\d+)? # finally, optionally match an exponent |
1433 | $/x; |
1434 | |
1435 | In this form, it is easier to see a way to simplify the |
1436 | alternation. Alternatives 1, 2, and 4 all start with C<\d+>, so it |
1437 | could be factored out: |
1438 | |
1439 | /^ |
1440 | [+-]?\ * # first, match an optional sign |
1441 | ( # then match integers or f.p. mantissas: |
1442 | \d+ # start out with a ... |
1443 | ( |
1444 | \.\d* # mantissa of the form a.b or a. |
1445 | )? # ? takes care of integers of the form a |
1446 | |\.\d+ # mantissa of the form .b |
1447 | ) |
1448 | ([eE][+-]?\d+)? # finally, optionally match an exponent |
1449 | $/x; |
1450 | |
1451 | or written in the compact form, |
1452 | |
1453 | /^[+-]?\ *(\d+(\.\d*)?|\.\d+)([eE][+-]?\d+)?$/; |
1454 | |
1455 | This is our final regexp. To recap, we built a regexp by |
1456 | |
1457 | =over 4 |
1458 | |
551e1d92 |
1459 | =item * |
1460 | |
1461 | specifying the task in detail, |
47f9c88b |
1462 | |
551e1d92 |
1463 | =item * |
1464 | |
1465 | breaking down the problem into smaller parts, |
1466 | |
1467 | =item * |
47f9c88b |
1468 | |
551e1d92 |
1469 | translating the small parts into regexps, |
47f9c88b |
1470 | |
551e1d92 |
1471 | =item * |
1472 | |
1473 | combining the regexps, |
1474 | |
1475 | =item * |
47f9c88b |
1476 | |
551e1d92 |
1477 | and optimizing the final combined regexp. |
47f9c88b |
1478 | |
1479 | =back |
1480 | |
1481 | These are also the typical steps involved in writing a computer |
1482 | program. This makes perfect sense, because regular expressions are |
7638d2dc |
1483 | essentially programs written in a little computer language that specifies |
47f9c88b |
1484 | patterns. |
1485 | |
1486 | =head2 Using regular expressions in Perl |
1487 | |
1488 | The last topic of Part 1 briefly covers how regexps are used in Perl |
1489 | programs. Where do they fit into Perl syntax? |
1490 | |
1491 | We have already introduced the matching operator in its default |
1492 | C</regexp/> and arbitrary delimiter C<m!regexp!> forms. We have used |
1493 | the binding operator C<=~> and its negation C<!~> to test for string |
1494 | matches. Associated with the matching operator, we have discussed the |
1495 | single line C<//s>, multi-line C<//m>, case-insensitive C<//i> and |
353c6505 |
1496 | extended C<//x> modifiers. There are a few more things you might |
1497 | want to know about matching operators. |
47f9c88b |
1498 | |
7638d2dc |
1499 | =head3 Optimizing pattern evaluation |
1500 | |
353c6505 |
1501 | We pointed out earlier that variables in regexps are substituted |
7638d2dc |
1502 | before the regexp is evaluated: |
47f9c88b |
1503 | |
1504 | $pattern = 'Seuss'; |
1505 | while (<>) { |
1506 | print if /$pattern/; |
1507 | } |
1508 | |
1509 | This will print any lines containing the word C<Seuss>. It is not as |
7638d2dc |
1510 | efficient as it could be, however, because Perl has to re-evaluate |
1511 | (or compile) C<$pattern> each time through the loop. If C<$pattern> won't be |
47f9c88b |
1512 | changing over the lifetime of the script, we can add the C<//o> |
7638d2dc |
1513 | modifier, which directs Perl to only perform variable substitutions |
47f9c88b |
1514 | once: |
1515 | |
1516 | #!/usr/bin/perl |
1517 | # Improved simple_grep |
1518 | $regexp = shift; |
1519 | while (<>) { |
1520 | print if /$regexp/o; # a good deal faster |
1521 | } |
1522 | |
7638d2dc |
1523 | |
1524 | =head3 Prohibiting substitution |
1525 | |
1526 | If you change C<$pattern> after the first substitution happens, Perl |
47f9c88b |
1527 | will ignore it. If you don't want any substitutions at all, use the |
1528 | special delimiter C<m''>: |
1529 | |
16e8b840 |
1530 | @pattern = ('Seuss'); |
47f9c88b |
1531 | while (<>) { |
16e8b840 |
1532 | print if m'@pattern'; # matches literal '@pattern', not 'Seuss' |
47f9c88b |
1533 | } |
1534 | |
353c6505 |
1535 | Similar to strings, C<m''> acts like apostrophes on a regexp; all other |
7638d2dc |
1536 | C<m> delimiters act like quotes. If the regexp evaluates to the empty string, |
47f9c88b |
1537 | the regexp in the I<last successful match> is used instead. So we have |
1538 | |
1539 | "dog" =~ /d/; # 'd' matches |
1540 | "dogbert =~ //; # this matches the 'd' regexp used before |
1541 | |
7638d2dc |
1542 | |
1543 | =head3 Global matching |
1544 | |
47f9c88b |
1545 | The final two modifiers C<//g> and C<//c> concern multiple matches. |
da75cd15 |
1546 | The modifier C<//g> stands for global matching and allows the |
47f9c88b |
1547 | matching operator to match within a string as many times as possible. |
1548 | In scalar context, successive invocations against a string will have |
1549 | `C<//g> jump from match to match, keeping track of position in the |
1550 | string as it goes along. You can get or set the position with the |
1551 | C<pos()> function. |
1552 | |
1553 | The use of C<//g> is shown in the following example. Suppose we have |
1554 | a string that consists of words separated by spaces. If we know how |
1555 | many words there are in advance, we could extract the words using |
1556 | groupings: |
1557 | |
1558 | $x = "cat dog house"; # 3 words |
1559 | $x =~ /^\s*(\w+)\s+(\w+)\s+(\w+)\s*$/; # matches, |
1560 | # $1 = 'cat' |
1561 | # $2 = 'dog' |
1562 | # $3 = 'house' |
1563 | |
1564 | But what if we had an indeterminate number of words? This is the sort |
1565 | of task C<//g> was made for. To extract all words, form the simple |
1566 | regexp C<(\w+)> and loop over all matches with C</(\w+)/g>: |
1567 | |
1568 | while ($x =~ /(\w+)/g) { |
1569 | print "Word is $1, ends at position ", pos $x, "\n"; |
1570 | } |
1571 | |
1572 | prints |
1573 | |
1574 | Word is cat, ends at position 3 |
1575 | Word is dog, ends at position 7 |
1576 | Word is house, ends at position 13 |
1577 | |
1578 | A failed match or changing the target string resets the position. If |
1579 | you don't want the position reset after failure to match, add the |
1580 | C<//c>, as in C</regexp/gc>. The current position in the string is |
1581 | associated with the string, not the regexp. This means that different |
1582 | strings have different positions and their respective positions can be |
1583 | set or read independently. |
1584 | |
1585 | In list context, C<//g> returns a list of matched groupings, or if |
1586 | there are no groupings, a list of matches to the whole regexp. So if |
1587 | we wanted just the words, we could use |
1588 | |
1589 | @words = ($x =~ /(\w+)/g); # matches, |
1590 | # $word[0] = 'cat' |
1591 | # $word[1] = 'dog' |
1592 | # $word[2] = 'house' |
1593 | |
1594 | Closely associated with the C<//g> modifier is the C<\G> anchor. The |
1595 | C<\G> anchor matches at the point where the previous C<//g> match left |
1596 | off. C<\G> allows us to easily do context-sensitive matching: |
1597 | |
1598 | $metric = 1; # use metric units |
1599 | ... |
1600 | $x = <FILE>; # read in measurement |
1601 | $x =~ /^([+-]?\d+)\s*/g; # get magnitude |
1602 | $weight = $1; |
1603 | if ($metric) { # error checking |
1604 | print "Units error!" unless $x =~ /\Gkg\./g; |
1605 | } |
1606 | else { |
1607 | print "Units error!" unless $x =~ /\Glbs\./g; |
1608 | } |
1609 | $x =~ /\G\s+(widget|sprocket)/g; # continue processing |
1610 | |
1611 | The combination of C<//g> and C<\G> allows us to process the string a |
1612 | bit at a time and use arbitrary Perl logic to decide what to do next. |
25cf8c22 |
1613 | Currently, the C<\G> anchor is only fully supported when used to anchor |
1614 | to the start of the pattern. |
47f9c88b |
1615 | |
1616 | C<\G> is also invaluable in processing fixed length records with |
1617 | regexps. Suppose we have a snippet of coding region DNA, encoded as |
1618 | base pair letters C<ATCGTTGAAT...> and we want to find all the stop |
1619 | codons C<TGA>. In a coding region, codons are 3-letter sequences, so |
1620 | we can think of the DNA snippet as a sequence of 3-letter records. The |
1621 | naive regexp |
1622 | |
1623 | # expanded, this is "ATC GTT GAA TGC AAA TGA CAT GAC" |
1624 | $dna = "ATCGTTGAATGCAAATGACATGAC"; |
1625 | $dna =~ /TGA/; |
1626 | |
d1be9408 |
1627 | doesn't work; it may match a C<TGA>, but there is no guarantee that |
47f9c88b |
1628 | the match is aligned with codon boundaries, e.g., the substring |
7638d2dc |
1629 | S<C<GTT GAA>> gives a match. A better solution is |
47f9c88b |
1630 | |
1631 | while ($dna =~ /(\w\w\w)*?TGA/g) { # note the minimal *? |
1632 | print "Got a TGA stop codon at position ", pos $dna, "\n"; |
1633 | } |
1634 | |
1635 | which prints |
1636 | |
1637 | Got a TGA stop codon at position 18 |
1638 | Got a TGA stop codon at position 23 |
1639 | |
1640 | Position 18 is good, but position 23 is bogus. What happened? |
1641 | |
1642 | The answer is that our regexp works well until we get past the last |
1643 | real match. Then the regexp will fail to match a synchronized C<TGA> |
1644 | and start stepping ahead one character position at a time, not what we |
1645 | want. The solution is to use C<\G> to anchor the match to the codon |
1646 | alignment: |
1647 | |
1648 | while ($dna =~ /\G(\w\w\w)*?TGA/g) { |
1649 | print "Got a TGA stop codon at position ", pos $dna, "\n"; |
1650 | } |
1651 | |
1652 | This prints |
1653 | |
1654 | Got a TGA stop codon at position 18 |
1655 | |
1656 | which is the correct answer. This example illustrates that it is |
1657 | important not only to match what is desired, but to reject what is not |
1658 | desired. |
1659 | |
7638d2dc |
1660 | =head3 Search and replace |
47f9c88b |
1661 | |
7638d2dc |
1662 | Regular expressions also play a big role in I<search and replace> |
47f9c88b |
1663 | operations in Perl. Search and replace is accomplished with the |
1664 | C<s///> operator. The general form is |
1665 | C<s/regexp/replacement/modifiers>, with everything we know about |
1666 | regexps and modifiers applying in this case as well. The |
1667 | C<replacement> is a Perl double quoted string that replaces in the |
1668 | string whatever is matched with the C<regexp>. The operator C<=~> is |
1669 | also used here to associate a string with C<s///>. If matching |
7638d2dc |
1670 | against C<$_>, the S<C<$_ =~>> can be dropped. If there is a match, |
47f9c88b |
1671 | C<s///> returns the number of substitutions made, otherwise it returns |
1672 | false. Here are a few examples: |
1673 | |
1674 | $x = "Time to feed the cat!"; |
1675 | $x =~ s/cat/hacker/; # $x contains "Time to feed the hacker!" |
1676 | if ($x =~ s/^(Time.*hacker)!$/$1 now!/) { |
1677 | $more_insistent = 1; |
1678 | } |
1679 | $y = "'quoted words'"; |
1680 | $y =~ s/^'(.*)'$/$1/; # strip single quotes, |
1681 | # $y contains "quoted words" |
1682 | |
1683 | In the last example, the whole string was matched, but only the part |
1684 | inside the single quotes was grouped. With the C<s///> operator, the |
1685 | matched variables C<$1>, C<$2>, etc. are immediately available for use |
1686 | in the replacement expression, so we use C<$1> to replace the quoted |
1687 | string with just what was quoted. With the global modifier, C<s///g> |
1688 | will search and replace all occurrences of the regexp in the string: |
1689 | |
1690 | $x = "I batted 4 for 4"; |
1691 | $x =~ s/4/four/; # doesn't do it all: |
1692 | # $x contains "I batted four for 4" |
1693 | $x = "I batted 4 for 4"; |
1694 | $x =~ s/4/four/g; # does it all: |
1695 | # $x contains "I batted four for four" |
1696 | |
1697 | If you prefer 'regex' over 'regexp' in this tutorial, you could use |
1698 | the following program to replace it: |
1699 | |
1700 | % cat > simple_replace |
1701 | #!/usr/bin/perl |
1702 | $regexp = shift; |
1703 | $replacement = shift; |
1704 | while (<>) { |
1705 | s/$regexp/$replacement/go; |
1706 | print; |
1707 | } |
1708 | ^D |
1709 | |
1710 | % simple_replace regexp regex perlretut.pod |
1711 | |
1712 | In C<simple_replace> we used the C<s///g> modifier to replace all |
1713 | occurrences of the regexp on each line and the C<s///o> modifier to |
1714 | compile the regexp only once. As with C<simple_grep>, both the |
1715 | C<print> and the C<s/$regexp/$replacement/go> use C<$_> implicitly. |
1716 | |
1717 | A modifier available specifically to search and replace is the |
1718 | C<s///e> evaluation modifier. C<s///e> wraps an C<eval{...}> around |
1719 | the replacement string and the evaluated result is substituted for the |
1720 | matched substring. C<s///e> is useful if you need to do a bit of |
1721 | computation in the process of replacing text. This example counts |
1722 | character frequencies in a line: |
1723 | |
1724 | $x = "Bill the cat"; |
1725 | $x =~ s/(.)/$chars{$1}++;$1/eg; # final $1 replaces char with itself |
1726 | print "frequency of '$_' is $chars{$_}\n" |
1727 | foreach (sort {$chars{$b} <=> $chars{$a}} keys %chars); |
1728 | |
1729 | This prints |
1730 | |
1731 | frequency of ' ' is 2 |
1732 | frequency of 't' is 2 |
1733 | frequency of 'l' is 2 |
1734 | frequency of 'B' is 1 |
1735 | frequency of 'c' is 1 |
1736 | frequency of 'e' is 1 |
1737 | frequency of 'h' is 1 |
1738 | frequency of 'i' is 1 |
1739 | frequency of 'a' is 1 |
1740 | |
1741 | As with the match C<m//> operator, C<s///> can use other delimiters, |
1742 | such as C<s!!!> and C<s{}{}>, and even C<s{}//>. If single quotes are |
1743 | used C<s'''>, then the regexp and replacement are treated as single |
1744 | quoted strings and there are no substitutions. C<s///> in list context |
1745 | returns the same thing as in scalar context, i.e., the number of |
1746 | matches. |
1747 | |
7638d2dc |
1748 | =head3 The split function |
47f9c88b |
1749 | |
7638d2dc |
1750 | The C<split()> function is another place where a regexp is used. |
353c6505 |
1751 | C<split /regexp/, string, limit> separates the C<string> operand into |
1752 | a list of substrings and returns that list. The regexp must be designed |
7638d2dc |
1753 | to match whatever constitutes the separators for the desired substrings. |
353c6505 |
1754 | The C<limit>, if present, constrains splitting into no more than C<limit> |
7638d2dc |
1755 | number of strings. For example, to split a string into words, use |
47f9c88b |
1756 | |
1757 | $x = "Calvin and Hobbes"; |
1758 | @words = split /\s+/, $x; # $word[0] = 'Calvin' |
1759 | # $word[1] = 'and' |
1760 | # $word[2] = 'Hobbes' |
1761 | |
1762 | If the empty regexp C<//> is used, the regexp always matches and |
1763 | the string is split into individual characters. If the regexp has |
7638d2dc |
1764 | groupings, then the resulting list contains the matched substrings from the |
47f9c88b |
1765 | groupings as well. For instance, |
1766 | |
1767 | $x = "/usr/bin/perl"; |
1768 | @dirs = split m!/!, $x; # $dirs[0] = '' |
1769 | # $dirs[1] = 'usr' |
1770 | # $dirs[2] = 'bin' |
1771 | # $dirs[3] = 'perl' |
1772 | @parts = split m!(/)!, $x; # $parts[0] = '' |
1773 | # $parts[1] = '/' |
1774 | # $parts[2] = 'usr' |
1775 | # $parts[3] = '/' |
1776 | # $parts[4] = 'bin' |
1777 | # $parts[5] = '/' |
1778 | # $parts[6] = 'perl' |
1779 | |
1780 | Since the first character of $x matched the regexp, C<split> prepended |
1781 | an empty initial element to the list. |
1782 | |
1783 | If you have read this far, congratulations! You now have all the basic |
1784 | tools needed to use regular expressions to solve a wide range of text |
1785 | processing problems. If this is your first time through the tutorial, |
1786 | why not stop here and play around with regexps a while... S<Part 2> |
1787 | concerns the more esoteric aspects of regular expressions and those |
1788 | concepts certainly aren't needed right at the start. |
1789 | |
1790 | =head1 Part 2: Power tools |
1791 | |
1792 | OK, you know the basics of regexps and you want to know more. If |
1793 | matching regular expressions is analogous to a walk in the woods, then |
1794 | the tools discussed in Part 1 are analogous to topo maps and a |
1795 | compass, basic tools we use all the time. Most of the tools in part 2 |
da75cd15 |
1796 | are analogous to flare guns and satellite phones. They aren't used |
47f9c88b |
1797 | too often on a hike, but when we are stuck, they can be invaluable. |
1798 | |
1799 | What follows are the more advanced, less used, or sometimes esoteric |
7638d2dc |
1800 | capabilities of Perl regexps. In Part 2, we will assume you are |
47f9c88b |
1801 | comfortable with the basics and concentrate on the new features. |
1802 | |
1803 | =head2 More on characters, strings, and character classes |
1804 | |
1805 | There are a number of escape sequences and character classes that we |
1806 | haven't covered yet. |
1807 | |
1808 | There are several escape sequences that convert characters or strings |
7638d2dc |
1809 | between upper and lower case, and they are also available within |
353c6505 |
1810 | patterns. C<\l> and C<\u> convert the next character to lower or |
7638d2dc |
1811 | upper case, respectively: |
47f9c88b |
1812 | |
1813 | $x = "perl"; |
1814 | $string =~ /\u$x/; # matches 'Perl' in $string |
1815 | $x = "M(rs?|s)\\."; # note the double backslash |
1816 | $string =~ /\l$x/; # matches 'mr.', 'mrs.', and 'ms.', |
1817 | |
7638d2dc |
1818 | A C<\L> or C<\U> indicates a lasting conversion of case, until |
1819 | terminated by C<\E> or thrown over by another C<\U> or C<\L>: |
47f9c88b |
1820 | |
1821 | $x = "This word is in lower case:\L SHOUT\E"; |
1822 | $x =~ /shout/; # matches |
1823 | $x = "I STILL KEYPUNCH CARDS FOR MY 360" |
1824 | $x =~ /\Ukeypunch/; # matches punch card string |
1825 | |
1826 | If there is no C<\E>, case is converted until the end of the |
1827 | string. The regexps C<\L\u$word> or C<\u\L$word> convert the first |
1828 | character of C<$word> to uppercase and the rest of the characters to |
1829 | lowercase. |
1830 | |
1831 | Control characters can be escaped with C<\c>, so that a control-Z |
1832 | character would be matched with C<\cZ>. The escape sequence |
1833 | C<\Q>...C<\E> quotes, or protects most non-alphabetic characters. For |
1834 | instance, |
1835 | |
1836 | $x = "\QThat !^*&%~& cat!"; |
1837 | $x =~ /\Q!^*&%~&\E/; # check for rough language |
1838 | |
1839 | It does not protect C<$> or C<@>, so that variables can still be |
1840 | substituted. |
1841 | |
7638d2dc |
1842 | With the advent of 5.6.0, Perl regexps can handle more than just the |
1843 | standard ASCII character set. Perl now supports I<Unicode>, a standard |
1844 | for representing the alphabets from virtually all of the world's written |
38a44b82 |
1845 | languages, and a host of symbols. Perl's text strings are Unicode strings, so |
2575c402 |
1846 | they can contain characters with a value (codepoint or character number) higher |
1847 | than 255 |
47f9c88b |
1848 | |
1849 | What does this mean for regexps? Well, regexp users don't need to know |
7638d2dc |
1850 | much about Perl's internal representation of strings. But they do need |
2575c402 |
1851 | to know 1) how to represent Unicode characters in a regexp and 2) that |
1852 | a matching operation will treat the string to be searched as a sequence |
1853 | of characters, not bytes. The answer to 1) is that Unicode characters |
1854 | greater than C<chr(255)> are represented using the C<\x{hex}> notation, |
1855 | because the \0 octal and \x hex (without curly braces) don't go further |
1856 | than 255. |
47f9c88b |
1857 | |
47f9c88b |
1858 | /\x{263a}/; # match a Unicode smiley face :) |
1859 | |
7638d2dc |
1860 | B<NOTE>: In Perl 5.6.0 it used to be that one needed to say C<use |
72ff2908 |
1861 | utf8> to use any Unicode features. This is no more the case: for |
1862 | almost all Unicode processing, the explicit C<utf8> pragma is not |
1863 | needed. (The only case where it matters is if your Perl script is in |
1864 | Unicode and encoded in UTF-8, then an explicit C<use utf8> is needed.) |
47f9c88b |
1865 | |
1866 | Figuring out the hexadecimal sequence of a Unicode character you want |
1867 | or deciphering someone else's hexadecimal Unicode regexp is about as |
1868 | much fun as programming in machine code. So another way to specify |
7638d2dc |
1869 | Unicode characters is to use the I<named character>> escape |
47f9c88b |
1870 | sequence C<\N{name}>. C<name> is a name for the Unicode character, as |
55eda711 |
1871 | specified in the Unicode standard. For instance, if we wanted to |
1872 | represent or match the astrological sign for the planet Mercury, we |
1873 | could use |
47f9c88b |
1874 | |
47f9c88b |
1875 | use charnames ":full"; # use named chars with Unicode full names |
1876 | $x = "abc\N{MERCURY}def"; |
1877 | $x =~ /\N{MERCURY}/; # matches |
1878 | |
1879 | One can also use short names or restrict names to a certain alphabet: |
1880 | |
47f9c88b |
1881 | use charnames ':full'; |
1882 | print "\N{GREEK SMALL LETTER SIGMA} is called sigma.\n"; |
1883 | |
1884 | use charnames ":short"; |
1885 | print "\N{greek:Sigma} is an upper-case sigma.\n"; |
1886 | |
1887 | use charnames qw(greek); |
1888 | print "\N{sigma} is Greek sigma\n"; |
1889 | |
7638d2dc |
1890 | A list of full names is found in the file NamesList.txt in the |
1891 | lib/perl5/X.X.X/unicore directory (where X.X.X is the perl |
1892 | version number as it is installed on your system). |
47f9c88b |
1893 | |
38a44b82 |
1894 | The answer to requirement 2), as of 5.6.0, is that a regexp uses Unicode |
2575c402 |
1895 | characters. Internally, this is encoded to bytes using either UTF-8 or a |
1896 | native 8 bit encoding, depending on the history of the string, but |
1897 | conceptually it is a sequence of characters, not bytes. See |
1898 | L<perlunitut> for a tutorial about that. |
1899 | |
1900 | Let us now discuss Unicode character classes. Just as with Unicode |
1901 | characters, there are named Unicode character classes represented by the |
1902 | C<\p{name}> escape sequence. Closely associated is the C<\P{name}> |
1903 | character class, which is the negation of the C<\p{name}> class. For |
1904 | example, to match lower and uppercase characters, |
47f9c88b |
1905 | |
47f9c88b |
1906 | use charnames ":full"; # use named chars with Unicode full names |
1907 | $x = "BOB"; |
1908 | $x =~ /^\p{IsUpper}/; # matches, uppercase char class |
1909 | $x =~ /^\P{IsUpper}/; # doesn't match, char class sans uppercase |
1910 | $x =~ /^\p{IsLower}/; # doesn't match, lowercase char class |
1911 | $x =~ /^\P{IsLower}/; # matches, char class sans lowercase |
1912 | |
86929931 |
1913 | Here is the association between some Perl named classes and the |
1914 | traditional Unicode classes: |
47f9c88b |
1915 | |
86929931 |
1916 | Perl class name Unicode class name or regular expression |
47f9c88b |
1917 | |
f5868911 |
1918 | IsAlpha /^[LM]/ |
1919 | IsAlnum /^[LMN]/ |
1920 | IsASCII $code <= 127 |
1921 | IsCntrl /^C/ |
1922 | IsBlank $code =~ /^(0020|0009)$/ || /^Z[^lp]/ |
47f9c88b |
1923 | IsDigit Nd |
f5868911 |
1924 | IsGraph /^([LMNPS]|Co)/ |
47f9c88b |
1925 | IsLower Ll |
f5868911 |
1926 | IsPrint /^([LMNPS]|Co|Zs)/ |
1927 | IsPunct /^P/ |
1928 | IsSpace /^Z/ || ($code =~ /^(0009|000A|000B|000C|000D)$/ |
08ce8fc6 |
1929 | IsSpacePerl /^Z/ || ($code =~ /^(0009|000A|000C|000D|0085|2028|2029)$/ |
f5868911 |
1930 | IsUpper /^L[ut]/ |
1931 | IsWord /^[LMN]/ || $code eq "005F" |
47f9c88b |
1932 | IsXDigit $code =~ /^00(3[0-9]|[46][1-6])$/ |
1933 | |
86929931 |
1934 | You can also use the official Unicode class names with the C<\p> and |
1935 | C<\P>, like C<\p{L}> for Unicode 'letters', or C<\p{Lu}> for uppercase |
1936 | letters, or C<\P{Nd}> for non-digits. If a C<name> is just one |
1937 | letter, the braces can be dropped. For instance, C<\pM> is the |
98f22ffc |
1938 | character class of Unicode 'marks', for example accent marks. |
32293815 |
1939 | For the full list see L<perlunicode>. |
1940 | |
fa11829f |
1941 | The Unicode has also been separated into various sets of characters |
7638d2dc |
1942 | which you can test with C<\p{...}> (in) and C<\P{...}> (not in). |
1943 | To test whether a character is (or is not) an element of a script |
353c6505 |
1944 | you would use the script name, for example C<\p{Latin}>, C<\p{Greek}>, |
7638d2dc |
1945 | or C<\P{Katakana}>. Other sets are the Unicode blocks, the names |
1946 | of which begin with "In". One such block is dedicated to mathematical |
1947 | operators, and its pattern formula is <C\p{InMathematicalOperators>}>. |
5e42d7b4 |
1948 | For the full list see L<perlunicode>. |
47f9c88b |
1949 | |
7638d2dc |
1950 | C<\X> is an abbreviation for a character class that comprises |
1951 | the Unicode I<combining character sequences>. A combining character |
1952 | sequence is a base character followed by any number of diacritics, i.e., |
1953 | signs like accents used to indicate different sounds of a letter. Using |
1954 | the Unicode full names, e.g., S<C<A + COMBINING RING>> is a combining |
47f9c88b |
1955 | character sequence with base character C<A> and combining character |
7638d2dc |
1956 | S<C<COMBINING RING>>, which translates in Danish to A with the circle |
47f9c88b |
1957 | atop it, as in the word Angstrom. C<\X> is equivalent to C<\PM\pM*}>, |
1958 | i.e., a non-mark followed by one or more marks. |
1959 | |
da75cd15 |
1960 | For the full and latest information about Unicode see the latest |
5e42d7b4 |
1961 | Unicode standard, or the Unicode Consortium's website http://www.unicode.org/ |
1962 | |
47f9c88b |
1963 | As if all those classes weren't enough, Perl also defines POSIX style |
1964 | character classes. These have the form C<[:name:]>, with C<name> the |
aaa51d5e |
1965 | name of the POSIX class. The POSIX classes are C<alpha>, C<alnum>, |
1966 | C<ascii>, C<cntrl>, C<digit>, C<graph>, C<lower>, C<print>, C<punct>, |
1967 | C<space>, C<upper>, and C<xdigit>, and two extensions, C<word> (a Perl |
1968 | extension to match C<\w>), and C<blank> (a GNU extension). If C<utf8> |
1969 | is being used, then these classes are defined the same as their |
7638d2dc |
1970 | corresponding Perl Unicode classes: C<[:upper:]> is the same as |
aaa51d5e |
1971 | C<\p{IsUpper}>, etc. The POSIX character classes, however, don't |
1972 | require using C<utf8>. The C<[:digit:]>, C<[:word:]>, and |
47f9c88b |
1973 | C<[:space:]> correspond to the familiar C<\d>, C<\w>, and C<\s> |
aaa51d5e |
1974 | character classes. To negate a POSIX class, put a C<^> in front of |
1975 | the name, so that, e.g., C<[:^digit:]> corresponds to C<\D> and under |
47f9c88b |
1976 | C<utf8>, C<\P{IsDigit}>. The Unicode and POSIX character classes can |
54c18d04 |
1977 | be used just like C<\d>, with the exception that POSIX character |
1978 | classes can only be used inside of a character class: |
47f9c88b |
1979 | |
1980 | /\s+[abc[:digit:]xyz]\s*/; # match a,b,c,x,y,z, or a digit |
54c18d04 |
1981 | /^=item\s[[:digit:]]/; # match '=item', |
47f9c88b |
1982 | # followed by a space and a digit |
47f9c88b |
1983 | use charnames ":full"; |
1984 | /\s+[abc\p{IsDigit}xyz]\s+/; # match a,b,c,x,y,z, or a digit |
1985 | /^=item\s\p{IsDigit}/; # match '=item', |
1986 | # followed by a space and a digit |
1987 | |
1988 | Whew! That is all the rest of the characters and character classes. |
1989 | |
1990 | =head2 Compiling and saving regular expressions |
1991 | |
1992 | In Part 1 we discussed the C<//o> modifier, which compiles a regexp |
1993 | just once. This suggests that a compiled regexp is some data structure |
1994 | that can be stored once and used again and again. The regexp quote |
1995 | C<qr//> does exactly that: C<qr/string/> compiles the C<string> as a |
1996 | regexp and transforms the result into a form that can be assigned to a |
1997 | variable: |
1998 | |
1999 | $reg = qr/foo+bar?/; # reg contains a compiled regexp |
2000 | |
2001 | Then C<$reg> can be used as a regexp: |
2002 | |
2003 | $x = "fooooba"; |
2004 | $x =~ $reg; # matches, just like /foo+bar?/ |
2005 | $x =~ /$reg/; # same thing, alternate form |
2006 | |
2007 | C<$reg> can also be interpolated into a larger regexp: |
2008 | |
2009 | $x =~ /(abc)?$reg/; # still matches |
2010 | |
2011 | As with the matching operator, the regexp quote can use different |
7638d2dc |
2012 | delimiters, e.g., C<qr!!>, C<qr{}> or C<qr~~>. Apostrophes |
2013 | as delimiters (C<qr''>) inhibit any interpolation. |
47f9c88b |
2014 | |
2015 | Pre-compiled regexps are useful for creating dynamic matches that |
2016 | don't need to be recompiled each time they are encountered. Using |
7638d2dc |
2017 | pre-compiled regexps, we write a C<grep_step> program which greps |
2018 | for a sequence of patterns, advancing to the next pattern as soon |
2019 | as one has been satisfied. |
47f9c88b |
2020 | |
7638d2dc |
2021 | % cat > grep_step |
47f9c88b |
2022 | #!/usr/bin/perl |
7638d2dc |
2023 | # grep_step - match <number> regexps, one after the other |
47f9c88b |
2024 | # usage: multi_grep <number> regexp1 regexp2 ... file1 file2 ... |
2025 | |
2026 | $number = shift; |
2027 | $regexp[$_] = shift foreach (0..$number-1); |
2028 | @compiled = map qr/$_/, @regexp; |
2029 | while ($line = <>) { |
7638d2dc |
2030 | if ($line =~ /$compiled[0]/) { |
2031 | print $line; |
2032 | shift @compiled; |
2033 | last unless @compiled; |
47f9c88b |
2034 | } |
2035 | } |
2036 | ^D |
2037 | |
7638d2dc |
2038 | % grep_step 3 shift print last grep_step |
2039 | $number = shift; |
2040 | print $line; |
2041 | last unless @compiled; |
47f9c88b |
2042 | |
2043 | Storing pre-compiled regexps in an array C<@compiled> allows us to |
2044 | simply loop through the regexps without any recompilation, thus gaining |
2045 | flexibility without sacrificing speed. |
2046 | |
7638d2dc |
2047 | |
2048 | =head2 Composing regular expressions at runtime |
2049 | |
2050 | Backtracking is more efficient than repeated tries with different regular |
2051 | expressions. If there are several regular expressions and a match with |
353c6505 |
2052 | any of them is acceptable, then it is possible to combine them into a set |
7638d2dc |
2053 | of alternatives. If the individual expressions are input data, this |
353c6505 |
2054 | can be done by programming a join operation. We'll exploit this idea in |
2055 | an improved version of the C<simple_grep> program: a program that matches |
7638d2dc |
2056 | multiple patterns: |
2057 | |
2058 | % cat > multi_grep |
2059 | #!/usr/bin/perl |
2060 | # multi_grep - match any of <number> regexps |
2061 | # usage: multi_grep <number> regexp1 regexp2 ... file1 file2 ... |
2062 | |
2063 | $number = shift; |
2064 | $regexp[$_] = shift foreach (0..$number-1); |
2065 | $pattern = join '|', @regexp; |
2066 | |
2067 | while ($line = <>) { |
2068 | print $line if $line =~ /$pattern/o; |
2069 | } |
2070 | ^D |
2071 | |
2072 | % multi_grep 2 shift for multi_grep |
2073 | $number = shift; |
2074 | $regexp[$_] = shift foreach (0..$number-1); |
2075 | |
2076 | Sometimes it is advantageous to construct a pattern from the I<input> |
2077 | that is to be analyzed and use the permissible values on the left |
2078 | hand side of the matching operations. As an example for this somewhat |
353c6505 |
2079 | paradoxical situation, let's assume that our input contains a command |
7638d2dc |
2080 | verb which should match one out of a set of available command verbs, |
353c6505 |
2081 | with the additional twist that commands may be abbreviated as long as |
7638d2dc |
2082 | the given string is unique. The program below demonstrates the basic |
2083 | algorithm. |
2084 | |
2085 | % cat > keymatch |
2086 | #!/usr/bin/perl |
2087 | $kwds = 'copy compare list print'; |
2088 | while( $command = <> ){ |
2089 | $command =~ s/^\s+|\s+$//g; # trim leading and trailing spaces |
2090 | if( ( @matches = $kwds =~ /\b$command\w*/g ) == 1 ){ |
2091 | print "command: '$matches'\n"; |
2092 | } elsif( @matches == 0 ){ |
2093 | print "no such command: '$command'\n"; |
2094 | } else { |
2095 | print "not unique: '$command' (could be one of: @matches)\n"; |
2096 | } |
2097 | } |
2098 | ^D |
2099 | |
2100 | % keymatch |
2101 | li |
2102 | command: 'list' |
2103 | co |
2104 | not unique: 'co' (could be one of: copy compare) |
2105 | printer |
2106 | no such command: 'printer' |
2107 | |
2108 | Rather than trying to match the input against the keywords, we match the |
2109 | combined set of keywords against the input. The pattern matching |
353c6505 |
2110 | operation S<C<$kwds =~ /\b($command\w*)/g>> does several things at the |
2111 | same time. It makes sure that the given command begins where a keyword |
2112 | begins (C<\b>). It tolerates abbreviations due to the added C<\w*>. It |
2113 | tells us the number of matches (C<scalar @matches>) and all the keywords |
7638d2dc |
2114 | that were actually matched. You could hardly ask for more. |
7638d2dc |
2115 | |
47f9c88b |
2116 | =head2 Embedding comments and modifiers in a regular expression |
2117 | |
2118 | Starting with this section, we will be discussing Perl's set of |
7638d2dc |
2119 | I<extended patterns>. These are extensions to the traditional regular |
47f9c88b |
2120 | expression syntax that provide powerful new tools for pattern |
2121 | matching. We have already seen extensions in the form of the minimal |
2122 | matching constructs C<??>, C<*?>, C<+?>, C<{n,m}?>, and C<{n,}?>. The |
2123 | rest of the extensions below have the form C<(?char...)>, where the |
2124 | C<char> is a character that determines the type of extension. |
2125 | |
2126 | The first extension is an embedded comment C<(?#text)>. This embeds a |
2127 | comment into the regular expression without affecting its meaning. The |
2128 | comment should not have any closing parentheses in the text. An |
2129 | example is |
2130 | |
2131 | /(?# Match an integer:)[+-]?\d+/; |
2132 | |
2133 | This style of commenting has been largely superseded by the raw, |
2134 | freeform commenting that is allowed with the C<//x> modifier. |
2135 | |
353c6505 |
2136 | The modifiers C<//i>, C<//m>, C<//s>, C<//x> and C<//k> (or any |
7638d2dc |
2137 | combination thereof) can also embedded in |
47f9c88b |
2138 | a regexp using C<(?i)>, C<(?m)>, C<(?s)>, and C<(?x)>. For instance, |
2139 | |
2140 | /(?i)yes/; # match 'yes' case insensitively |
2141 | /yes/i; # same thing |
2142 | /(?x)( # freeform version of an integer regexp |
2143 | [+-]? # match an optional sign |
2144 | \d+ # match a sequence of digits |
2145 | ) |
2146 | /x; |
2147 | |
2148 | Embedded modifiers can have two important advantages over the usual |
2149 | modifiers. Embedded modifiers allow a custom set of modifiers to |
2150 | I<each> regexp pattern. This is great for matching an array of regexps |
2151 | that must have different modifiers: |
2152 | |
2153 | $pattern[0] = '(?i)doctor'; |
2154 | $pattern[1] = 'Johnson'; |
2155 | ... |
2156 | while (<>) { |
2157 | foreach $patt (@pattern) { |
2158 | print if /$patt/; |
2159 | } |
2160 | } |
2161 | |
7638d2dc |
2162 | The second advantage is that embedded modifiers (except C<//k>, which |
2163 | modifies the entire regexp) only affect the regexp |
47f9c88b |
2164 | inside the group the embedded modifier is contained in. So grouping |
2165 | can be used to localize the modifier's effects: |
2166 | |
2167 | /Answer: ((?i)yes)/; # matches 'Answer: yes', 'Answer: YES', etc. |
2168 | |
2169 | Embedded modifiers can also turn off any modifiers already present |
2170 | by using, e.g., C<(?-i)>. Modifiers can also be combined into |
2171 | a single expression, e.g., C<(?s-i)> turns on single line mode and |
2172 | turns off case insensitivity. |
2173 | |
7638d2dc |
2174 | Embedded modifiers may also be added to a non-capturing grouping. |
47f9c88b |
2175 | C<(?i-m:regexp)> is a non-capturing grouping that matches C<regexp> |
2176 | case insensitively and turns off multi-line mode. |
2177 | |
7638d2dc |
2178 | |
47f9c88b |
2179 | =head2 Looking ahead and looking behind |
2180 | |
2181 | This section concerns the lookahead and lookbehind assertions. First, |
2182 | a little background. |
2183 | |
2184 | In Perl regular expressions, most regexp elements 'eat up' a certain |
2185 | amount of string when they match. For instance, the regexp element |
2186 | C<[abc}]> eats up one character of the string when it matches, in the |
7638d2dc |
2187 | sense that Perl moves to the next character position in the string |
47f9c88b |
2188 | after the match. There are some elements, however, that don't eat up |
2189 | characters (advance the character position) if they match. The examples |
2190 | we have seen so far are the anchors. The anchor C<^> matches the |
2191 | beginning of the line, but doesn't eat any characters. Similarly, the |
7638d2dc |
2192 | word boundary anchor C<\b> matches wherever a character matching C<\w> |
353c6505 |
2193 | is next to a character that doesn't, but it doesn't eat up any |
7638d2dc |
2194 | characters itself. Anchors are examples of I<zero-width assertions>. |
2195 | Zero-width, because they consume |
47f9c88b |
2196 | no characters, and assertions, because they test some property of the |
2197 | string. In the context of our walk in the woods analogy to regexp |
2198 | matching, most regexp elements move us along a trail, but anchors have |
2199 | us stop a moment and check our surroundings. If the local environment |
2200 | checks out, we can proceed forward. But if the local environment |
2201 | doesn't satisfy us, we must backtrack. |
2202 | |
2203 | Checking the environment entails either looking ahead on the trail, |
2204 | looking behind, or both. C<^> looks behind, to see that there are no |
2205 | characters before. C<$> looks ahead, to see that there are no |
2206 | characters after. C<\b> looks both ahead and behind, to see if the |
7638d2dc |
2207 | characters on either side differ in their "word-ness". |
47f9c88b |
2208 | |
2209 | The lookahead and lookbehind assertions are generalizations of the |
2210 | anchor concept. Lookahead and lookbehind are zero-width assertions |
2211 | that let us specify which characters we want to test for. The |
2212 | lookahead assertion is denoted by C<(?=regexp)> and the lookbehind |
a6b2f353 |
2213 | assertion is denoted by C<< (?<=fixed-regexp) >>. Some examples are |
47f9c88b |
2214 | |
2215 | $x = "I catch the housecat 'Tom-cat' with catnip"; |
7638d2dc |
2216 | $x =~ /cat(?=\s)/; # matches 'cat' in 'housecat' |
47f9c88b |
2217 | @catwords = ($x =~ /(?<=\s)cat\w+/g); # matches, |
2218 | # $catwords[0] = 'catch' |
2219 | # $catwords[1] = 'catnip' |
2220 | $x =~ /\bcat\b/; # matches 'cat' in 'Tom-cat' |
2221 | $x =~ /(?<=\s)cat(?=\s)/; # doesn't match; no isolated 'cat' in |
2222 | # middle of $x |
2223 | |
a6b2f353 |
2224 | Note that the parentheses in C<(?=regexp)> and C<< (?<=regexp) >> are |
47f9c88b |
2225 | non-capturing, since these are zero-width assertions. Thus in the |
2226 | second regexp, the substrings captured are those of the whole regexp |
a6b2f353 |
2227 | itself. Lookahead C<(?=regexp)> can match arbitrary regexps, but |
2228 | lookbehind C<< (?<=fixed-regexp) >> only works for regexps of fixed |
2229 | width, i.e., a fixed number of characters long. Thus |
2230 | C<< (?<=(ab|bc)) >> is fine, but C<< (?<=(ab)*) >> is not. The |
2231 | negated versions of the lookahead and lookbehind assertions are |
2232 | denoted by C<(?!regexp)> and C<< (?<!fixed-regexp) >> respectively. |
2233 | They evaluate true if the regexps do I<not> match: |
47f9c88b |
2234 | |
2235 | $x = "foobar"; |
2236 | $x =~ /foo(?!bar)/; # doesn't match, 'bar' follows 'foo' |
2237 | $x =~ /foo(?!baz)/; # matches, 'baz' doesn't follow 'foo' |
2238 | $x =~ /(?<!\s)foo/; # matches, there is no \s before 'foo' |
2239 | |
f14c76ed |
2240 | The C<\C> is unsupported in lookbehind, because the already |
2241 | treacherous definition of C<\C> would become even more so |
2242 | when going backwards. |
2243 | |
7638d2dc |
2244 | Here is an example where a string containing blank-separated words, |
2245 | numbers and single dashes is to be split into its components. |
2246 | Using C</\s+/> alone won't work, because spaces are not required between |
2247 | dashes, or a word or a dash. Additional places for a split are established |
2248 | by looking ahead and behind: |
47f9c88b |
2249 | |
7638d2dc |
2250 | $str = "one two - --6-8"; |
2251 | @toks = split / \s+ # a run of spaces |
2252 | | (?<=\S) (?=-) # any non-space followed by '-' |
2253 | | (?<=-) (?=\S) # a '-' followed by any non-space |
2254 | /x, $str; # @toks = qw(one two - - - 6 - 8) |
47f9c88b |
2255 | |
7638d2dc |
2256 | |
2257 | =head2 Using independent subexpressions to prevent backtracking |
2258 | |
2259 | I<Independent subexpressions> are regular expressions, in the |
47f9c88b |
2260 | context of a larger regular expression, that function independently of |
2261 | the larger regular expression. That is, they consume as much or as |
2262 | little of the string as they wish without regard for the ability of |
2263 | the larger regexp to match. Independent subexpressions are represented |
2264 | by C<< (?>regexp) >>. We can illustrate their behavior by first |
2265 | considering an ordinary regexp: |
2266 | |
2267 | $x = "ab"; |
2268 | $x =~ /a*ab/; # matches |
2269 | |
2270 | This obviously matches, but in the process of matching, the |
2271 | subexpression C<a*> first grabbed the C<a>. Doing so, however, |
2272 | wouldn't allow the whole regexp to match, so after backtracking, C<a*> |
2273 | eventually gave back the C<a> and matched the empty string. Here, what |
2274 | C<a*> matched was I<dependent> on what the rest of the regexp matched. |
2275 | |
2276 | Contrast that with an independent subexpression: |
2277 | |
2278 | $x =~ /(?>a*)ab/; # doesn't match! |
2279 | |
2280 | The independent subexpression C<< (?>a*) >> doesn't care about the rest |
2281 | of the regexp, so it sees an C<a> and grabs it. Then the rest of the |
2282 | regexp C<ab> cannot match. Because C<< (?>a*) >> is independent, there |
da75cd15 |
2283 | is no backtracking and the independent subexpression does not give |
47f9c88b |
2284 | up its C<a>. Thus the match of the regexp as a whole fails. A similar |
2285 | behavior occurs with completely independent regexps: |
2286 | |
2287 | $x = "ab"; |
2288 | $x =~ /a*/g; # matches, eats an 'a' |
2289 | $x =~ /\Gab/g; # doesn't match, no 'a' available |
2290 | |
2291 | Here C<//g> and C<\G> create a 'tag team' handoff of the string from |
2292 | one regexp to the other. Regexps with an independent subexpression are |
2293 | much like this, with a handoff of the string to the independent |
2294 | subexpression, and a handoff of the string back to the enclosing |
2295 | regexp. |
2296 | |
2297 | The ability of an independent subexpression to prevent backtracking |
2298 | can be quite useful. Suppose we want to match a non-empty string |
2299 | enclosed in parentheses up to two levels deep. Then the following |
2300 | regexp matches: |
2301 | |
2302 | $x = "abc(de(fg)h"; # unbalanced parentheses |
2303 | $x =~ /\( ( [^()]+ | \([^()]*\) )+ \)/x; |
2304 | |
2305 | The regexp matches an open parenthesis, one or more copies of an |
2306 | alternation, and a close parenthesis. The alternation is two-way, with |
2307 | the first alternative C<[^()]+> matching a substring with no |
2308 | parentheses and the second alternative C<\([^()]*\)> matching a |
2309 | substring delimited by parentheses. The problem with this regexp is |
2310 | that it is pathological: it has nested indeterminate quantifiers |
07698885 |
2311 | of the form C<(a+|b)+>. We discussed in Part 1 how nested quantifiers |
47f9c88b |
2312 | like this could take an exponentially long time to execute if there |
2313 | was no match possible. To prevent the exponential blowup, we need to |
2314 | prevent useless backtracking at some point. This can be done by |
2315 | enclosing the inner quantifier as an independent subexpression: |
2316 | |
2317 | $x =~ /\( ( (?>[^()]+) | \([^()]*\) )+ \)/x; |
2318 | |
2319 | Here, C<< (?>[^()]+) >> breaks the degeneracy of string partitioning |
2320 | by gobbling up as much of the string as possible and keeping it. Then |
2321 | match failures fail much more quickly. |
2322 | |
7638d2dc |
2323 | |
47f9c88b |
2324 | =head2 Conditional expressions |
2325 | |
7638d2dc |
2326 | A I<conditional expression> is a form of if-then-else statement |
47f9c88b |
2327 | that allows one to choose which patterns are to be matched, based on |
2328 | some condition. There are two types of conditional expression: |
2329 | C<(?(condition)yes-regexp)> and |
2330 | C<(?(condition)yes-regexp|no-regexp)>. C<(?(condition)yes-regexp)> is |
7638d2dc |
2331 | like an S<C<'if () {}'>> statement in Perl. If the C<condition> is true, |
47f9c88b |
2332 | the C<yes-regexp> will be matched. If the C<condition> is false, the |
7638d2dc |
2333 | C<yes-regexp> will be skipped and Perl will move onto the next regexp |
2334 | element. The second form is like an S<C<'if () {} else {}'>> statement |
47f9c88b |
2335 | in Perl. If the C<condition> is true, the C<yes-regexp> will be |
2336 | matched, otherwise the C<no-regexp> will be matched. |
2337 | |
7638d2dc |
2338 | The C<condition> can have several forms. The first form is simply an |
47f9c88b |
2339 | integer in parentheses C<(integer)>. It is true if the corresponding |
7638d2dc |
2340 | backreference C<\integer> matched earlier in the regexp. The same |
2341 | thing can be done with a name associated with a capture buffer, written |
2342 | as C<< (<name>) >> or C<< ('name') >>. The second form is a bare |
353c6505 |
2343 | zero width assertion C<(?...)>, either a lookahead, a lookbehind, or a |
7638d2dc |
2344 | code assertion (discussed in the next section). The third set of forms |
2345 | provides tests that return true if the expression is executed within |
2346 | a recursion (C<(R)>) or is being called from some capturing group, |
2347 | referenced either by number (C<(R1)>, C<(R2)>,...) or by name |
2348 | (C<(R&name)>). |
2349 | |
2350 | The integer or name form of the C<condition> allows us to choose, |
2351 | with more flexibility, what to match based on what matched earlier in the |
2352 | regexp. This searches for words of the form C<"$x$x"> or C<"$x$y$y$x">: |
47f9c88b |
2353 | |
2354 | % simple_grep '^(\w+)(\w+)?(?(2)\2\1|\1)$' /usr/dict/words |
2355 | beriberi |
2356 | coco |
2357 | couscous |
2358 | deed |
2359 | ... |
2360 | toot |
2361 | toto |
2362 | tutu |
2363 | |
2364 | The lookbehind C<condition> allows, along with backreferences, |
2365 | an earlier part of the match to influence a later part of the |
2366 | match. For instance, |
2367 | |
2368 | /[ATGC]+(?(?<=AA)G|C)$/; |
2369 | |
2370 | matches a DNA sequence such that it either ends in C<AAG>, or some |
2371 | other base pair combination and C<C>. Note that the form is |
a6b2f353 |
2372 | C<< (?(?<=AA)G|C) >> and not C<< (?((?<=AA))G|C) >>; for the |
2373 | lookahead, lookbehind or code assertions, the parentheses around the |
2374 | conditional are not needed. |
47f9c88b |
2375 | |
7638d2dc |
2376 | |
2377 | =head2 Defining named patterns |
2378 | |
2379 | Some regular expressions use identical subpatterns in several places. |
2380 | Starting with Perl 5.10, it is possible to define named subpatterns in |
2381 | a section of the pattern so that they can be called up by name |
2382 | anywhere in the pattern. This syntactic pattern for this definition |
2383 | group is C<< (?(DEFINE)(?<name>pattern)...) >>. An insertion |
2384 | of a named pattern is written as C<(?&name)>. |
2385 | |
2386 | The example below illustrates this feature using the pattern for |
2387 | floating point numbers that was presented earlier on. The three |
2388 | subpatterns that are used more than once are the optional sign, the |
2389 | digit sequence for an integer and the decimal fraction. The DEFINE |
2390 | group at the end of the pattern contains their definition. Notice |
2391 | that the decimal fraction pattern is the first place where we can |
2392 | reuse the integer pattern. |
2393 | |
353c6505 |
2394 | /^ (?&osg)\ * ( (?&int)(?&dec)? | (?&dec) ) |
7638d2dc |
2395 | (?: [eE](?&osg)(?&int) )? |
2396 | $ |
2397 | (?(DEFINE) |
2398 | (?<osg>[-+]?) # optional sign |
2399 | (?<int>\d++) # integer |
2400 | (?<dec>\.(?&int)) # decimal fraction |
2401 | )/x |
2402 | |
2403 | |
2404 | =head2 Recursive patterns |
2405 | |
2406 | This feature (introduced in Perl 5.10) significantly extends the |
2407 | power of Perl's pattern matching. By referring to some other |
2408 | capture group anywhere in the pattern with the construct |
353c6505 |
2409 | C<(?group-ref)>, the I<pattern> within the referenced group is used |
7638d2dc |
2410 | as an independent subpattern in place of the group reference itself. |
2411 | Because the group reference may be contained I<within> the group it |
2412 | refers to, it is now possible to apply pattern matching to tasks that |
2413 | hitherto required a recursive parser. |
2414 | |
2415 | To illustrate this feature, we'll design a pattern that matches if |
2416 | a string contains a palindrome. (This is a word or a sentence that, |
2417 | while ignoring spaces, interpunctuation and case, reads the same backwards |
2418 | as forwards. We begin by observing that the empty string or a string |
2419 | containing just one word character is a palindrome. Otherwise it must |
2420 | have a word character up front and the same at its end, with another |
2421 | palindrome in between. |
2422 | |
2423 | /(?: (\w) (?...Here be a palindrome...) \{-1} | \w? )/x |
2424 | |
2425 | Adding C<\W*> at either end to eliminate was is to be ignored, we already |
2426 | have the full pattern: |
2427 | |
2428 | my $pp = qr/^(\W* (?: (\w) (?1) \g{-1} | \w? ) \W*)$/ix; |
2429 | for $s ( "saippuakauppias", "A man, a plan, a canal: Panama!" ){ |
2430 | print "'$s' is a palindrome\n" if $s =~ /$pp/; |
2431 | } |
2432 | |
2433 | In C<(?...)> both absolute and relative backreferences may be used. |
2434 | The entire pattern can be reinserted with C<(?R)> or C<(?0)>. |
2435 | If you prefer to name your buffers, you can use C<(?&name)> to |
2436 | recurse into that buffer. |
2437 | |
2438 | |
47f9c88b |
2439 | =head2 A bit of magic: executing Perl code in a regular expression |
2440 | |
2441 | Normally, regexps are a part of Perl expressions. |
7638d2dc |
2442 | I<Code evaluation> expressions turn that around by allowing |
da75cd15 |
2443 | arbitrary Perl code to be a part of a regexp. A code evaluation |
7638d2dc |
2444 | expression is denoted C<(?{code})>, with I<code> a string of Perl |
47f9c88b |
2445 | statements. |
2446 | |
353c6505 |
2447 | Be warned that this feature is considered experimental, and may be |
7638d2dc |
2448 | changed without notice. |
2449 | |
47f9c88b |
2450 | Code expressions are zero-width assertions, and the value they return |
2451 | depends on their environment. There are two possibilities: either the |
2452 | code expression is used as a conditional in a conditional expression |
2453 | C<(?(condition)...)>, or it is not. If the code expression is a |
2454 | conditional, the code is evaluated and the result (i.e., the result of |
2455 | the last statement) is used to determine truth or falsehood. If the |
2456 | code expression is not used as a conditional, the assertion always |
2457 | evaluates true and the result is put into the special variable |
2458 | C<$^R>. The variable C<$^R> can then be used in code expressions later |
2459 | in the regexp. Here are some silly examples: |
2460 | |
2461 | $x = "abcdef"; |
2462 | $x =~ /abc(?{print "Hi Mom!";})def/; # matches, |
2463 | # prints 'Hi Mom!' |
2464 | $x =~ /aaa(?{print "Hi Mom!";})def/; # doesn't match, |
2465 | # no 'Hi Mom!' |
745e1e41 |
2466 | |
2467 | Pay careful attention to the next example: |
2468 | |
47f9c88b |
2469 | $x =~ /abc(?{print "Hi Mom!";})ddd/; # doesn't match, |
2470 | # no 'Hi Mom!' |
745e1e41 |
2471 | # but why not? |
2472 | |
2473 | At first glance, you'd think that it shouldn't print, because obviously |
2474 | the C<ddd> isn't going to match the target string. But look at this |
2475 | example: |
2476 | |
2477 | $x =~ /abc(?{print "Hi Mom!";})[d]dd/; # doesn't match, |
2478 | # but _does_ print |
2479 | |
2480 | Hmm. What happened here? If you've been following along, you know that |
2481 | the above pattern should be effectively the same as the last one -- |
2482 | enclosing the d in a character class isn't going to change what it |
2483 | matches. So why does the first not print while the second one does? |
2484 | |
7638d2dc |
2485 | The answer lies in the optimizations the regex engine makes. In the first |
745e1e41 |
2486 | case, all the engine sees are plain old characters (aside from the |
2487 | C<?{}> construct). It's smart enough to realize that the string 'ddd' |
2488 | doesn't occur in our target string before actually running the pattern |
2489 | through. But in the second case, we've tricked it into thinking that our |
2490 | pattern is more complicated than it is. It takes a look, sees our |
2491 | character class, and decides that it will have to actually run the |
2492 | pattern to determine whether or not it matches, and in the process of |
2493 | running it hits the print statement before it discovers that we don't |
2494 | have a match. |
2495 | |
2496 | To take a closer look at how the engine does optimizations, see the |
2497 | section L<"Pragmas and debugging"> below. |
2498 | |
2499 | More fun with C<?{}>: |
2500 | |
47f9c88b |
2501 | $x =~ /(?{print "Hi Mom!";})/; # matches, |
2502 | # prints 'Hi Mom!' |
2503 | $x =~ /(?{$c = 1;})(?{print "$c";})/; # matches, |
2504 | # prints '1' |
2505 | $x =~ /(?{$c = 1;})(?{print "$^R";})/; # matches, |
2506 | # prints '1' |
2507 | |
2508 | The bit of magic mentioned in the section title occurs when the regexp |
2509 | backtracks in the process of searching for a match. If the regexp |
2510 | backtracks over a code expression and if the variables used within are |
2511 | localized using C<local>, the changes in the variables produced by the |
2512 | code expression are undone! Thus, if we wanted to count how many times |
2513 | a character got matched inside a group, we could use, e.g., |
2514 | |
2515 | $x = "aaaa"; |
2516 | $count = 0; # initialize 'a' count |
2517 | $c = "bob"; # test if $c gets clobbered |
2518 | $x =~ /(?{local $c = 0;}) # initialize count |
2519 | ( a # match 'a' |
2520 | (?{local $c = $c + 1;}) # increment count |
2521 | )* # do this any number of times, |
2522 | aa # but match 'aa' at the end |
2523 | (?{$count = $c;}) # copy local $c var into $count |
2524 | /x; |
2525 | print "'a' count is $count, \$c variable is '$c'\n"; |
2526 | |
2527 | This prints |
2528 | |
2529 | 'a' count is 2, $c variable is 'bob' |
2530 | |
7638d2dc |
2531 | If we replace the S<C< (?{local $c = $c + 1;})>> with |
2532 | S<C< (?{$c = $c + 1;})>>, the variable changes are I<not> undone |
47f9c88b |
2533 | during backtracking, and we get |
2534 | |
2535 | 'a' count is 4, $c variable is 'bob' |
2536 | |
2537 | Note that only localized variable changes are undone. Other side |
2538 | effects of code expression execution are permanent. Thus |
2539 | |
2540 | $x = "aaaa"; |
2541 | $x =~ /(a(?{print "Yow\n";}))*aa/; |
2542 | |
2543 | produces |
2544 | |
2545 | Yow |
2546 | Yow |
2547 | Yow |
2548 | Yow |
2549 | |
2550 | The result C<$^R> is automatically localized, so that it will behave |
2551 | properly in the presence of backtracking. |
2552 | |
7638d2dc |
2553 | This example uses a code expression in a conditional to match a |
2554 | definite article, either 'the' in English or 'der|die|das' in German: |
47f9c88b |
2555 | |
47f9c88b |
2556 | $lang = 'DE'; # use German |
2557 | ... |
2558 | $text = "das"; |
2559 | print "matched\n" |
2560 | if $text =~ /(?(?{ |
2561 | $lang eq 'EN'; # is the language English? |
2562 | }) |
2563 | the | # if so, then match 'the' |
7638d2dc |
2564 | (der|die|das) # else, match 'der|die|das' |
47f9c88b |
2565 | ) |
2566 | /xi; |
2567 | |
2568 | Note that the syntax here is C<(?(?{...})yes-regexp|no-regexp)>, not |
2569 | C<(?((?{...}))yes-regexp|no-regexp)>. In other words, in the case of a |
2570 | code expression, we don't need the extra parentheses around the |
2571 | conditional. |
2572 | |
7638d2dc |
2573 | If you try to use code expressions with interpolating variables, Perl |
a6b2f353 |
2574 | may surprise you: |
2575 | |
2576 | $bar = 5; |
2577 | $pat = '(?{ 1 })'; |
2578 | /foo(?{ $bar })bar/; # compiles ok, $bar not interpolated |
2579 | /foo(?{ 1 })$bar/; # compile error! |
2580 | /foo${pat}bar/; # compile error! |
2581 | |
2582 | $pat = qr/(?{ $foo = 1 })/; # precompile code regexp |
2583 | /foo${pat}bar/; # compiles ok |
2584 | |
fa11829f |
2585 | If a regexp has (1) code expressions and interpolating variables, or |
7638d2dc |
2586 | (2) a variable that interpolates a code expression, Perl treats the |
a6b2f353 |
2587 | regexp as an error. If the code expression is precompiled into a |
2588 | variable, however, interpolating is ok. The question is, why is this |
2589 | an error? |
2590 | |
2591 | The reason is that variable interpolation and code expressions |
2592 | together pose a security risk. The combination is dangerous because |
2593 | many programmers who write search engines often take user input and |
2594 | plug it directly into a regexp: |
47f9c88b |
2595 | |
2596 | $regexp = <>; # read user-supplied regexp |
2597 | $chomp $regexp; # get rid of possible newline |
2598 | $text =~ /$regexp/; # search $text for the $regexp |
2599 | |
a6b2f353 |
2600 | If the C<$regexp> variable contains a code expression, the user could |
2601 | then execute arbitrary Perl code. For instance, some joker could |
7638d2dc |
2602 | search for S<C<system('rm -rf *');>> to erase your files. In this |
2603 | sense, the combination of interpolation and code expressions I<taints> |
47f9c88b |
2604 | your regexp. So by default, using both interpolation and code |
a6b2f353 |
2605 | expressions in the same regexp is not allowed. If you're not |
2606 | concerned about malicious users, it is possible to bypass this |
7638d2dc |
2607 | security check by invoking S<C<use re 'eval'>>: |
a6b2f353 |
2608 | |
2609 | use re 'eval'; # throw caution out the door |
2610 | $bar = 5; |
2611 | $pat = '(?{ 1 })'; |
2612 | /foo(?{ 1 })$bar/; # compiles ok |
2613 | /foo${pat}bar/; # compiles ok |
47f9c88b |
2614 | |
7638d2dc |
2615 | Another form of code expression is the I<pattern code expression>. |
47f9c88b |
2616 | The pattern code expression is like a regular code expression, except |
2617 | that the result of the code evaluation is treated as a regular |
2618 | expression and matched immediately. A simple example is |
2619 | |
2620 | $length = 5; |
2621 | $char = 'a'; |
2622 | $x = 'aaaaabb'; |
2623 | $x =~ /(??{$char x $length})/x; # matches, there are 5 of 'a' |
2624 | |
2625 | |
2626 | This final example contains both ordinary and pattern code |
7638d2dc |
2627 | expressions. It detects whether a binary string C<1101010010001...> has a |
47f9c88b |
2628 | Fibonacci spacing 0,1,1,2,3,5,... of the C<1>'s: |
2629 | |
47f9c88b |
2630 | $x = "1101010010001000001"; |
7638d2dc |
2631 | $z0 = ''; $z1 = '0'; # initial conditions |
47f9c88b |
2632 | print "It is a Fibonacci sequence\n" |
2633 | if $x =~ /^1 # match an initial '1' |
7638d2dc |
2634 | (?: |
2635 | ((??{ $z0 })) # match some '0' |
2636 | 1 # and then a '1' |
2637 | (?{ $z0 = $z1; $z1 .= $^N; }) |
47f9c88b |
2638 | )+ # repeat as needed |
2639 | $ # that is all there is |
2640 | /x; |
7638d2dc |
2641 | printf "Largest sequence matched was %d\n", length($z1)-length($z0); |
47f9c88b |
2642 | |
7638d2dc |
2643 | Remember that C<$^N> is set to whatever was matched by the last |
2644 | completed capture group. This prints |
47f9c88b |
2645 | |
2646 | It is a Fibonacci sequence |
2647 | Largest sequence matched was 5 |
2648 | |
2649 | Ha! Try that with your garden variety regexp package... |
2650 | |
7638d2dc |
2651 | Note that the variables C<$z0> and C<$z1> are not substituted when the |
47f9c88b |
2652 | regexp is compiled, as happens for ordinary variables outside a code |
7638d2dc |
2653 | expression. Rather, the code expressions are evaluated when Perl |
47f9c88b |
2654 | encounters them during the search for a match. |
2655 | |
2656 | The regexp without the C<//x> modifier is |
2657 | |
7638d2dc |
2658 | /^1(?:((??{ $z0 }))1(?{ $z0 = $z1; $z1 .= $^N; }))+$/ |
2659 | |
2660 | which shows that spaces are still possible in the code parts. Nevertheless, |
353c6505 |
2661 | when working with code and conditional expressions, the extended form of |
7638d2dc |
2662 | regexps is almost necessary in creating and debugging regexps. |
2663 | |
2664 | |
2665 | =head2 Backtracking control verbs |
2666 | |
2667 | Perl 5.10 introduced a number of control verbs intended to provide |
2668 | detailed control over the backtracking process, by directly influencing |
2669 | the regexp engine and by providing monitoring techniques. As all |
2670 | the features in this group are experimental and subject to change or |
2671 | removal in a future version of Perl, the interested reader is |
2672 | referred to L<perlre/"Special Backtracking Control Verbs"> for a |
2673 | detailed description. |
2674 | |
2675 | Below is just one example, illustrating the control verb C<(*FAIL)>, |
2676 | which may be abbreviated as C<(*F)>. If this is inserted in a regexp |
2677 | it will cause to fail, just like at some mismatch between the pattern |
2678 | and the string. Processing of the regexp continues like after any "normal" |
353c6505 |
2679 | failure, so that, for instance, the next position in the string or another |
2680 | alternative will be tried. As failing to match doesn't preserve capture |
2681 | buffers or produce results, it may be necessary to use this in |
7638d2dc |
2682 | combination with embedded code. |
2683 | |
2684 | %count = (); |
2685 | "supercalifragilisticexpialidoceous" =~ |
2686 | /([aeiou])(?{ $count{$1}++; })(*FAIL)/oi; |
2687 | printf "%3d '%s'\n", $count{$_}, $_ for (sort keys %count); |
2688 | |
353c6505 |
2689 | The pattern begins with a class matching a subset of letters. Whenever |
2690 | this matches, a statement like C<$count{'a'}++;> is executed, incrementing |
2691 | the letter's counter. Then C<(*FAIL)> does what it says, and |
2692 | the regexp engine proceeds according to the book: as long as the end of |
2693 | the string hasn't been reached, the position is advanced before looking |
7638d2dc |
2694 | for another vowel. Thus, match or no match makes no difference, and the |
2695 | regexp engine proceeds until the the entire string has been inspected. |
2696 | (It's remarkable that an alternative solution using something like |
2697 | |
2698 | $count{lc($_)}++ for split('', "supercalifragilisticexpialidoceous"); |
2699 | printf "%3d '%s'\n", $count2{$_}, $_ for ( qw{ a e i o u } ); |
2700 | |
2701 | is considerably slower.) |
47f9c88b |
2702 | |
47f9c88b |
2703 | |
2704 | =head2 Pragmas and debugging |
2705 | |
2706 | Speaking of debugging, there are several pragmas available to control |
2707 | and debug regexps in Perl. We have already encountered one pragma in |
7638d2dc |
2708 | the previous section, S<C<use re 'eval';>>, that allows variable |
a6b2f353 |
2709 | interpolation and code expressions to coexist in a regexp. The other |
2710 | pragmas are |
47f9c88b |
2711 | |
2712 | use re 'taint'; |
2713 | $tainted = <>; |
2714 | @parts = ($tainted =~ /(\w+)\s+(\w+)/; # @parts is now tainted |
2715 | |
2716 | The C<taint> pragma causes any substrings from a match with a tainted |
2717 | variable to be tainted as well. This is not normally the case, as |
2718 | regexps are often used to extract the safe bits from a tainted |
2719 | variable. Use C<taint> when you are not extracting safe bits, but are |
2720 | performing some other processing. Both C<taint> and C<eval> pragmas |
a6b2f353 |
2721 | are lexically scoped, which means they are in effect only until |
47f9c88b |
2722 | the end of the block enclosing the pragmas. |
2723 | |
2724 | use re 'debug'; |
2725 | /^(.*)$/s; # output debugging info |
2726 | |
2727 | use re 'debugcolor'; |
2728 | /^(.*)$/s; # output debugging info in living color |
2729 | |
2730 | The global C<debug> and C<debugcolor> pragmas allow one to get |
2731 | detailed debugging info about regexp compilation and |
2732 | execution. C<debugcolor> is the same as debug, except the debugging |
2733 | information is displayed in color on terminals that can display |
2734 | termcap color sequences. Here is example output: |
2735 | |
2736 | % perl -e 'use re "debug"; "abc" =~ /a*b+c/;' |
2737 | Compiling REx `a*b+c' |
2738 | size 9 first at 1 |
2739 | 1: STAR(4) |
2740 | 2: EXACT <a>(0) |
2741 | 4: PLUS(7) |
2742 | 5: EXACT <b>(0) |
2743 | 7: EXACT <c>(9) |
2744 | 9: END(0) |
2745 | floating `bc' at 0..2147483647 (checking floating) minlen 2 |
2746 | Guessing start of match, REx `a*b+c' against `abc'... |
2747 | Found floating substr `bc' at offset 1... |
2748 | Guessed: match at offset 0 |
2749 | Matching REx `a*b+c' against `abc' |
2750 | Setting an EVAL scope, savestack=3 |
2751 | 0 <> <abc> | 1: STAR |
2752 | EXACT <a> can match 1 times out of 32767... |
2753 | Setting an EVAL scope, savestack=3 |
2754 | 1 <a> <bc> | 4: PLUS |
2755 | EXACT <b> can match 1 times out of 32767... |
2756 | Setting an EVAL scope, savestack=3 |
2757 | 2 <ab> <c> | 7: EXACT <c> |
2758 | 3 <abc> <> | 9: END |
2759 | Match successful! |
2760 | Freeing REx: `a*b+c' |
2761 | |
2762 | If you have gotten this far into the tutorial, you can probably guess |
2763 | what the different parts of the debugging output tell you. The first |
2764 | part |
2765 | |
2766 | Compiling REx `a*b+c' |
2767 | size 9 first at 1 |
2768 | 1: STAR(4) |
2769 | 2: EXACT <a>(0) |
2770 | 4: PLUS(7) |
2771 | 5: EXACT <b>(0) |
2772 | 7: EXACT <c>(9) |
2773 | 9: END(0) |
2774 | |
2775 | describes the compilation stage. C<STAR(4)> means that there is a |
2776 | starred object, in this case C<'a'>, and if it matches, goto line 4, |
2777 | i.e., C<PLUS(7)>. The middle lines describe some heuristics and |
2778 | optimizations performed before a match: |
2779 | |
2780 | floating `bc' at 0..2147483647 (checking floating) minlen 2 |
2781 | Guessing start of match, REx `a*b+c' against `abc'... |
2782 | Found floating substr `bc' at offset 1... |
2783 | Guessed: match at offset 0 |
2784 | |
2785 | Then the match is executed and the remaining lines describe the |
2786 | process: |
2787 | |
2788 | Matching REx `a*b+c' against `abc' |
2789 | Setting an EVAL scope, savestack=3 |
2790 | 0 <> <abc> | 1: STAR |
2791 | EXACT <a> can match 1 times out of 32767... |
2792 | Setting an EVAL scope, savestack=3 |
2793 | 1 <a> <bc> | 4: PLUS |
2794 | EXACT <b> can match 1 times out of 32767... |
2795 | Setting an EVAL scope, savestack=3 |
2796 | 2 <ab> <c> | 7: EXACT <c> |
2797 | 3 <abc> <> | 9: END |
2798 | Match successful! |
2799 | Freeing REx: `a*b+c' |
2800 | |
7638d2dc |
2801 | Each step is of the form S<C<< n <x> <y> >>>, with C<< <x> >> the |
47f9c88b |
2802 | part of the string matched and C<< <y> >> the part not yet |
7638d2dc |
2803 | matched. The S<C<< | 1: STAR >>> says that Perl is at line number 1 |
47f9c88b |
2804 | n the compilation list above. See |
2805 | L<perldebguts/"Debugging regular expressions"> for much more detail. |
2806 | |
2807 | An alternative method of debugging regexps is to embed C<print> |
2808 | statements within the regexp. This provides a blow-by-blow account of |
2809 | the backtracking in an alternation: |
2810 | |
2811 | "that this" =~ m@(?{print "Start at position ", pos, "\n";}) |
2812 | t(?{print "t1\n";}) |
2813 | h(?{print "h1\n";}) |
2814 | i(?{print "i1\n";}) |
2815 | s(?{print "s1\n";}) |
2816 | | |
2817 | t(?{print "t2\n";}) |
2818 | h(?{print "h2\n";}) |
2819 | a(?{print "a2\n";}) |
2820 | t(?{print "t2\n";}) |
2821 | (?{print "Done at position ", pos, "\n";}) |
2822 | @x; |
2823 | |
2824 | prints |
2825 | |
2826 | Start at position 0 |
2827 | t1 |
2828 | h1 |
2829 | t2 |
2830 | h2 |
2831 | a2 |
2832 | t2 |
2833 | Done at position 4 |
2834 | |
2835 | =head1 BUGS |
2836 | |
2837 | Code expressions, conditional expressions, and independent expressions |
7638d2dc |
2838 | are I<experimental>. Don't use them in production code. Yet. |
47f9c88b |
2839 | |
2840 | =head1 SEE ALSO |
2841 | |
7638d2dc |
2842 | This is just a tutorial. For the full story on Perl regular |
47f9c88b |
2843 | expressions, see the L<perlre> regular expressions reference page. |
2844 | |
2845 | For more information on the matching C<m//> and substitution C<s///> |
2846 | operators, see L<perlop/"Regexp Quote-Like Operators">. For |
2847 | information on the C<split> operation, see L<perlfunc/split>. |
2848 | |
2849 | For an excellent all-around resource on the care and feeding of |
2850 | regular expressions, see the book I<Mastering Regular Expressions> by |
2851 | Jeffrey Friedl (published by O'Reilly, ISBN 1556592-257-3). |
2852 | |
2853 | =head1 AUTHOR AND COPYRIGHT |
2854 | |
2855 | Copyright (c) 2000 Mark Kvale |
2856 | All rights reserved. |
2857 | |
2858 | This document may be distributed under the same terms as Perl itself. |
2859 | |
2860 | =head2 Acknowledgments |
2861 | |
2862 | The inspiration for the stop codon DNA example came from the ZIP |
2863 | code example in chapter 7 of I<Mastering Regular Expressions>. |
2864 | |
a6b2f353 |
2865 | The author would like to thank Jeff Pinyan, Andrew Johnson, Peter |
2866 | Haworth, Ronald J Kimball, and Joe Smith for all their helpful |
2867 | comments. |
47f9c88b |
2868 | |
2869 | =cut |
a6b2f353 |
2870 | |