The Tricky Bits

Much trickier than the syntax of regular expressions is their sneaky semantics. The three aspects of pattern-matching behavior that seem to cause folks the most trouble are greed, eagerness, and backtracking (and also how these three interact with each other).

Greed is the principle that if a quantifier (like *) can match a varying number of times, it will prefer to match as long a substring as it can. This is explained in Recipe 6.15.

Eagerness is the notion that the leftmost match wins. The engine is very eager to return you a match as quickly as possible, sometimes even before you are expecting it. Consider the match "Fred" =~ /x*/. If asked to explain this in plain language, you might say "Does the string "Fred" contain any x 's?" If so, you might be surprised to learn that it seems to. That's because /x*/ doesn't truly mean "any x's", unless your idea of "any" includes nothing at all. Formally, it means zero or more of them, and in this case, zero sufficed for the eager matcher.

A more illustrative example of eagerness would be the following:

$string = "good food";
$string =~ s/o*/e/;

Can you guess which of the following is in $string after that substitution?

good food
geod food
geed food
geed feed
ged food
ged fed
egood food

The answer is the last one because the earliest point at which zero or more occurrences of "o" could be found was right at the beginning of the string. Surprised? Regular expressions can do that to you.

Can you guess what adding /g modifier to make the substitution global will do? Think of it this way: that string has many places where zero or more instances of "o" occur  - eight, to be precise. The answer is "egeede efeede".

Here's another example of where greed takes a back seat to eagerness:

% echo ababacaca | perl -ne 'print "$&\n" if /(a|ba|b)+(a|ac)+/'
ababa

That's because Perl uses what's called a traditional NFA,[2] a non-deterministic finite automaton. This kind of matching engine is not guaranteed to return the longest overall match, just the longest, leftmost match. You might think of Perl's greed as being left-to-right directed, not globally greedy.

[2] As opposed to a POSIX-style NFA. See Mastering Regular Expressions for the differences.

But it doesn't have to be that way. Here's an example using awk, a language that Perl borrows a lot from:

% echo ababacaca | 
    awk 'match($0,/(a|ba|b)+(a|ac)+/) { print substr($0, RSTART, RLENGTH) }'
ababacaca

Choosing how to implement pattern matching depends mainly on two factors: are the expressions nonregular (do they use backreferences), and what needs to be returned (yes/no, range of whole match, ranges of subexpressions). Tools like awk, egrep, and lex use regular expressions and only need a yes/no answer or the range of the whole match. This is exactly what DFAs can support, and because DFAs are faster and simpler, these tools have traditionally used DFA implementations. Pattern matching within programs and libraries, such as ed, regex, and perl, is another kettle of fish; typically, we need to support nonregular expressions and we need to know what parts of the string were matched by various parts of the pattern. This is a much harder problem with potentially exponential run times. The natural algorithm for this problem is an NFA, and therein lies both a problem and an opportunity. The problem is that NFAs are slow. The opportunity is that significant performance gains can be made by rewriting the patterns to exploit how the particular NFA implementation runs. This is a major part of Jeffrey Friedl's book, Mastering Regular Expressions.

The last and most powerful of the three tricky bits in pattern matching is backtracking. For a pattern to match, the entire regular expression must match, not just part of it. So if the beginning of a pattern containing a quantifier succeeds in a way that causes later parts in the pattern to fail, the matching engine backs up and tries to find another match for the beginning part  - that's why it's called backtracking. Essentially, it means that the engine is going to try different possibilities, systematically investigating alternate matches until it finds one that works. In some pattern matching implementations, you keep backtracking in case other submatches make the overall match longer. Perl's matcher doesn't do that; as soon as one possibility works, it uses that  - until and unless something later on in the pattern fails, forcing a backtrack to retry another possible way of matching. This is discussed in Recipe 6.16.

Pattern-Matching Modifiers

Pattern-matching modifiers are a lot easier to list and learn than the different metacharacters. Here's a brief summary of them:

/i and /g are the most commonly used modifiers. The pattern /ram/i matches "ram", "RAM", "Ram", and so forth. Backreferences will be checked case-insensitively if this modifier is on; see Recipe 6.16 for an example. This comparison can be made aware of the user's current locale settings if the use locale pragma has been invoked. As currently implemented, /i slows down a pattern match because it disables several performance optimizations.

The /g modifier is used with s/// to replace every match, not just the first one. /g is also used with m// in loops to find (but not replace) every matching occurrence:

while (m/(\d+)/g) {
    print "Found number $1\n";
}

Used in list context, /g pulls out all matches:

@numbers = m/(\d+)/g;

That finds only non-overlapping matches. You have to be much sneakier to get overlapping ones by making a zero-width look-ahead with the (?=...) construct. Because it's zero-width, the match engine hasn't advanced at all. Within the look-ahead, capturing parentheses are used to grab the thing anyway. Although we've saved something, Perl notices we haven't made any forward progress on the /g so bumps us forward one character position.

This shows the difference:

$digits = "123456789";
@nonlap = $digits =~ /(\d\d\d)/g;
@yeslap = $digits =~ /(?=(\d\d\d))/g;
print "Non-overlapping:  @nonlap\n";
print "Overlapping:      @yeslap\n";
Non-overlapping:  123 456 789
Overlapping:      123 234 345 456 567 678 789

The /s and /m modifiers are used when matching strings with embedded newlines. /s makes dot match "\n", something it doesn't normally do; it also makes the match ignore the value of the old, deprecated $* variable. /m makes ^ and $ match after and before "\n" respectively. They are useful with paragraph slurping mode as explained in the introduction to Chapter 8, File Contents, and in Recipe 6.6.

The /e switch is used so that the right-hand part is run as code and its return value is used as the replacement string. s/(\d+)/sprintf("%#x", $1)/ge would convert all numbers into hex, changing, for example, 2581 into 0xb23.

Because different countries have different ideas of what constitutes an alphabet, the POSIX standard provides systems (and thus programs) with a standard way of representing alphabets, character set ordering, and so on. Perl gives you access to some of these through the use locale pragma; see the perllocale manpage for more information. When use locale is in effect, the \w character class includes accented and other exotic characters. The case-changing \u, \U, \l, and \L (and the corresponding uc, ucfirst, etc. functions) escapes also respect use locale, so will be turned into with \u if the locale says it should.

Special Variables

Perl sets special variables as the result of certain kinds of matches: $1, $2, $3, and so on ad infinitum (Perl doesn't stop at $9) are set when a pattern contains back-references (parentheses around part of the pattern). Each left parenthesis as you read left to right in the pattern begins filling a new, numbered variable. The variable $+ contains the contents of the last backreference of the last successful match. This helps you tell which of several alternate matches was found (for example, if /(x.*y)|(y.*z)/ matches, $+ contains whichever of $1 or $2 got filled). $& contains the complete text matched in the last successful pattern match. $' and $` are the strings before and after the successful match, respectively:

$string = "And little lambs eat ivy";
$string =~ /l[^s]*s/;
print "($`) ($&) ($')\n";
(And ) (little lambs) ( eat ivy)

$`, $&, and $' are tempting, but dangerous. Their very presence anywhere in a program slows down every pattern match because the engine must populate these variables for every match. This is true even if you use one of these variables only once, or, for that matter, if you never actually use them at all but merely mention them. As of release 5.005, $& is no longer as expensive.

All this power may make patterns seem omnipotent. Surprisingly enough, this is not (quite) the case. Regular expressions are fundamentally incapable of doing some things. For some of those, special modules lend a hand. Regular expressions are unable to deal with balanced input, that is, anything that's arbitrarily nested, like matching parentheses, matching HTML tags, etc. For that, you have to build up a real parser, like the HTML::Parser recipes in Chapter 20, Web Automation. Another thing Perl patterns can't do yet is fuzzy matches; Recipe 6.13 shows how to use a module to work around that.

To learn far more about regular expressions than you ever thought existed, check out Mastering Regular Expressions, written by Jeffrey Friedl and published by O'Reilly & Associates. This book is dedicated to explaining regular expressions from a practical perspective. It not only covers general regular expressions and Perl patterns well, it also compares and contrasts these with those used in other popular languages.