|
2.4 Pattern MatchingThe two main pattern matching operators are m//, the match operator, and s///, the substitution operator. There is also a split operator, which takes an ordinary match operator as its first argument but otherwise behaves like a function, and is therefore documented in Chapter 3, Functions. Although we write m// and s/// here, you'll recall that you can pick your own quote characters. On the other hand, for the m// operator only, the m may be omitted if the delimiters you pick are in fact slashes. (You'll often see patterns written this way, for historical reasons.) Now that we've gone to all the trouble of enumerating these weird, quote-like operators, you might wonder what it is we've gone to all the trouble of quoting. The answer is that the string inside the quotes specifies a regular expression. We'll discuss regular expressions in the next section, because there's a lot to discuss. The matching operations can have various modifiers, some of which affect the interpretation of the regular expression inside:
These are usually written as "the /x modifier", even though the delimiter in question might not actually be a slash. In fact, any of these modifiers may also be embedded within the regular expression itself using the (?...) construct. See the section "Regular Expression Extensions" later in this chapter. The /x modifier itself needs a little more explanation. It tells the regular expression parser to ignore whitespace that is not backslashed or within a character class. You can use this modifier to break up your regular expression into (slightly) more readable parts. The # character is also treated as a metacharacter introducing a comment, just as in ordinary Perl code. Taken together, these features go a long way toward making Perl a readable language. Regular ExpressionsThe regular expressions used in the pattern matching and substitution operators are syntactically similar to those used by the UNIX egrep program. When you write a regular expression, you're actually writing a grammar for a little language. The regular expression interpreter (which we'll call the Engine) takes your grammar and compares it to the string you're doing pattern matching on. If some portion of the string can be parsed as a sentence of your little language, it says "yes". If not, it says "no". What happens after the Engine has said "yes" depends on how you invoked it. An ordinary pattern match is usually used as a conditional expression, in which case you don't care where it matched, only whether it matched. (But you can also find out where it matched if you need to know that.) A substitution command will take the part that matched and replace it with some other string of your choice. And the split operator will return (as a list) all the places your pattern didn't match. Regular expressions are powerful, packing a lot of meaning into a short space. They can therefore be quite daunting if you try to intuit the meaning of a large regular expression as a whole. But if you break it up into its parts, and if you know how the Engine interprets those parts, you can understand any regular expression. The regular expression bestiaryBefore we dive into the rules for interpreting regular expressions, let's take a look at some of the things you'll see in regular expressions. First of all, you'll see literal strings. Most characters[23] in a regular expression simply match themselves. If you string several characters in a row, they must match in order, just as you'd expect. So if you write the pattern match:
/Fred/ you can know that the pattern won't match unless the string contains the substring "Fred" somewhere. Other characters don't match themselves, but are metacharacters. (Before we explain what metacharacters do, we should reassure you that you can always match such a character literally by putting a backslash in front of it. For example, backslash is itself a metacharacter, so to match a literal backslash, you'd backslash the backslash: \\.) The list of metacharacters is:
\ | ( ) [ { ^ $ * + ? . We said that backslash turns a metacharacter into a literal character, but it does the opposite to an alphanumeric character: it turns the literal character into a sort of metacharacter or sequence. So whenever you see a two-character sequence:
\b \D \t \3 \s you'll know that the sequence matches something strange. A \b matches a word boundary, for instance, while \t matches an ordinary tab character. Notice that a word boundary is zero characters wide, while a tab character is one character wide. Still, they're alike in that they both assert that something is true about a particular spot in the string. Most of the things in a regular expression fall into the class of assertions, including the ordinary characters that simply assert that they match themselves. (To be precise, they also assert that the next thing will match one character later in the string, which is why we talk about the tab character being "one character wide". Some assertions eat up some of the string as they match, and others don't. But we usually reserve the term "assertion" for the zero-width assertions. We'll call these assertions with nonzero width atoms.) You'll also see some things that aren't assertions. Alternation is indicated with a vertical bar:
/Fred|Wilma|Barney|Betty/ That means that any of those strings can trigger a match. Grouping of various sorts is done with parentheses, including grouping of alternating substrings within a longer regular expression:
/(Fred|Wilma|Pebbles) Flintstone/ Another thing you'll see are what we call quantifiers. They say how many of the previous thing should match in a row. Quantifiers look like:
* + ? *? {2,5} Quantifiers only make sense when attached to atoms, that is, assertions that have width. Quantifiers attach only to the previous atom, which in human terms means they only quantify one character. So if you want to match three copies of "moo" in a row, you need to group the "moo" with parentheses, like this:
/(moo){3}/ That will match "moomoomoo". If you'd said /moo{3}/, it would only have matched "moooo". Since patterns are processed as double-quoted strings, the normal double-quoted interpolations will work. (See "String Literals" earlier in this chapter.) These are applied before the string is interpreted as a regular expression. One caveat though: any $ immediately followed by a vertical bar, closing parenthesis, or the end of the string will be interpreted as an end-of-line assertion rather than a variable interpolation. So if you say:
$foo = "moo"; /$foo$/; it's equivalent to saying:
/moo$/; You should also know that interpolating variables into a pattern slows down the pattern matcher considerably, because it feels it needs to recompile the pattern each time through, since the variable might have changed. The rules of regular expression matchingNow that you've seen some of the things you'll be seeing, we'll lay out the rules that the Engine uses to match your pattern against the string. The Perl Engine uses a nondeterministic finite-state automaton (NFA) to find a match. That just means that it keeps track of what it has tried and what it hasn't, and when something doesn't pan out, it backs up and tries something else. This is called backtracking. The Perl Engine is capable of trying a million things at one spot, then giving up on all those, backing up to within one choice of the beginning, and trying the million things again at a different spot. If you're cagey, you can write efficient patterns that don't do a lot of silly backtracking. The order of the rules below specifies which order the Engine tries things. So when someone trots out a stock phrase like "left-most, longest match", you'll know that overall Perl prefers left-most over longest. But the Engine doesn't realize it's preferring anything at that level. The global preferences result from a lot of localized choices. The Engine thinks locally and acts globally. Rule 1. The Engine tries to match as far left in the string as it can, such that the entire regular expression matches under Rule 2. In order to do this, its first choice is to start just before the first character (it could have started anywhere), and to try to match the entire regular expression at that point. The regular expression matches if and only if Engine reaches the end of the regular expression before it runs off the end of the string. If it matches, it quits immediately--it doesn't keep looking for a "better" match, even though the regular expression could match in many different ways. The match only has to reach the end of the regular expression; it doesn't have to reach the end of the string, unless there's an assertion in the regular expression that says it must. If it exhausts all possibilities at the first position, it realizes that its very first choice was wrong, and proceeds to its second choice. It goes to the second position in the string (between the first and second characters), and tries all the possibilities again. If it succeeds, it stops. If it fails, it continues on down the string. The pattern match as a whole doesn't fail until it has tried to match the entire regular expression at every position in the string, including after the last character in the string. Note that the positions it's trying to match at are between the characters of the string. This rule sometimes surprises people when they write a pattern like /x*/ that can match zero or more x's. If you try the pattern on a string like "fox", it will match the null string before the "f" in preference to the "x" that's later in the string. If you want it to match one or more x's, you need to tell it that by using /x+/ instead. See the quantifiers under Rule 5. A corollary to this rule is that any regular expression that can match the null string is guaranteed to match at the leftmost position in the string. Rule 2. For this rule, the whole regular expression is regarded as a set of alternatives (where the degenerate case is just a set with one alternative). If there are two or more alternatives, they are syntactically separated by the | character (usually called a vertical bar). A set of alternatives matches a string if any of the alternatives match under Rule 3. It tries the alternatives left-to-right (according to their position in the regular expression), and stops on the first match that allows successful completion of the entire regular expression. If none of the alternatives matches, it backtracks to the Rule that invoked this Rule, which is usually Rule 1, but could be Rule 4 or 6. That rule will then look for a new position at which to apply Rule 2. If there's only one alternative, then it either it matches or doesn't, and the rule still applies. (There's no such thing as zero alternatives, because a null string can always match something of zero width.) Rule 3. Any particular alternative matches if every item in the alternative matches sequentially according to Rules 4 and 5 (such that the entire regular expression can be satisfied). An item consists of either an assertion, which is covered in Rule 4, or a quantified atom, which is covered by Rule 5. Items that have choices on how to match are given "pecking order" from left to right. If the items cannot be matched in order, the Engine backtracks to the next alternative under Rule 2. Items that must be matched sequentially aren't separated in the regular expression by anything syntactic--they're merely juxtaposed in the order they must match. When you ask to match /^foo/, you're actually asking for four items to be matched one after the other. The first is a zero-width assertion, and the other three are ordinary letters that must match themselves, one after the other. The left-to-right pecking order means that in a pattern like:
/x*y*/ x gets to pick one way to match, and then y tries all its ways. If that fails, then x gets to pick its second choice, and make y try all of its ways again. And so on. The items to the right vary faster, to borrow a phrase from multi-dimensional arrays. Rule 4. An assertion must match according to this table. If the assertion does not match at the current position, the Engine backtracks to Rule 3 and retries higher-pecking-order items with different choices.
The $ and \Z assertions can match not only at the end of the string, but also one character earlier than that, if the last character of the string happens to be a newline. The positive (?=...) and negative (?!...) lookahead assertions are zero-width themselves, but assert that the regular expression represented above by ... would (or would not) match at this point, were we to attempt it. In fact, the Engine does attempt it. The Engine goes back to Rule 2 to test the subexpression, and then wipes out any record of how much string was eaten, returning only the success or failure of the subexpression as the value of the assertion. We'll show you some examples later. Rule 5. A quantified atom matches only if the atom itself matches some number of times allowed by the quantifier. (The atom is matched according to Rule 6.) Different quantifiers require different numbers of matches, and most of them allow a range of numbers of matches. Multiple matches must all match in a row, that is, they must be adjacent within the string. An unquantified atom is assumed to have a quantifier requiring exactly one match. Quantifiers constrain and control matching according to the table below. If no match can be found at the current position for any allowed quantity of the atom in question, the Engine backtracks to Rule 3 and retries higher-pecking-order items with different choices. Quantifiers are:
If a brace occurs in any other context, it is treated as a regular character. n and m are limited to integral values less than 65,536. If you use the {n} form, then there is no choice, and the atom must match exactly that number of times or not at all. Otherwise, the atom can match over a range of quantities, and the Engine keeps track of all the choices so that it can backtrack if necessary. But then the question arises as to which of these choices to try first. One could start with the maximal number of matches and work down, or the minimal number of matches and work up. The quantifiers in the left column above try the biggest quantity first. This is often called "greedy" matching. To find the greediest match, the Engine doesn't actually count down from the maximum value, which after all could be infinity. What actually happens in this case is that the Engine first counts up to find out how many atoms it's possible to match in a row in the current string, and then it remembers all the shorter choices and starts out from the longest one. This could fail, of course, in which case it backtracks to a shorter choice. If you say /.*foo/, for example, it will try to match the maximal number of "any" characters (represented by the dot) clear out to the end of the line before it ever tries looking for "foo", and then when the "foo" doesn't match there (and it can't, because there's not enough room for it at the end of the string), the Engine will back off one character at a time until it finds a "foo". If there is more than one "foo" in the line, it'll stop on the last one, and throw away all the shorter choices it could have made. By placing a question mark after any of the greedy quantifiers, they can be made to choose the smallest quantity for the first try. So if you say /.*?foo/, the .*? first tries to match 0 characters, then 1 character, then 2, and so on until it can match the "foo". Instead of backtracking backward, it backtracks forward, so to speak, and ends up finding the first "foo" on the line instead of the last. Rule 6. Each atom matches according to its type, listed below. If the atom doesn't match (or doesn't allow a match of the rest of the regular expression), the Engine backtracks to Rule 5 and tries the next choice for the atom's quantity. Atoms match according to the following types:
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
With any suggestions or questions please feel free to contact us |