2.1.1 Basic Regular Expression Patterns

The simplest kind of regular expression is a sequence of simple characters. For example, to search for woodchuck, we type /woodchuck/. So the regular expression /Buttercup/ matches any string containing the substring Buttercup, for example the line I'm called little Buttercup) (recall that we are assuming a search application that returns entire lines). From here on we will put slashes around each regular expres-

sion to make it clear what is a regular expression and what is a pattern. We use the slash since this is the notation used by Perl, but the slashes are not part of the regular expressions.

The search string can consist of a single character (like /!/) or a sequence of characters (like /urgl/); The first instance of each match to the regular expression is underlined below (although a given application might choose to return more than just the first instance):

| RE | Example Patterns Matched |

| --- | --- |

| /woodchucks/ /a/ /Claire_says, / /DOROTHY/ /!/ | “interesting links to $ \underline{\text{woodchucks}} $ and lemurs” “M $ \underline{\text{ary}} $ Ann stopped by Mona's” “Dagmar, my gift please,” $ \underline{\text{Claire says,}} $ “SURRENDER $ \underline{\text{DOROTHY}} $” “You've left the burglar behind again $ \underline{\text{l}} $” said Nori |

Regular expressions are case sensitive; lowercase /s/ is distinct from uppercase /S/ (/s/ matches a lower case s but not an uppercase S). This means that the pattern /woodchucks/ will not match the string Woodchucks. We can solve this problem with the use of the square braces [ and ]. The string of characters inside the braces specify a disjunction of characters to match. For example Fig. 2.1 shows that the pattern / [ wW ]/ matches patterns containing either w or W.

The regular expression / [1234567890] / specified any single digit. While classes of characters like digits or letters are important building blocks in expressions, they can get awkward (e.g., it's inconvenient to specify

/ [ABCDEFGHIJKLMNOPQRSTUVWXYZ] /

to mean “any capital letter”). In these cases the brackets can be used with the dash (-) to specify any one character in a range. The pattern / [2-5] / specifies any one of the characters 2, 3, 4, or 5. The pattern / [b-g] / specifies one of the characters b, c, d, e, f, or g. Some other examples:

| RE | Match | Example Patterns Matched |

| --- | --- | --- |

| /[A-Z]/ /[a-z]/ /[0-9]/ | an uppercase letter a lowercase letter a single digit | “we should call it ‘Drenched Blossoms’” “ $ \underline{\text{my}} $ beans were impatient to be hoed!” “Chapter 1: Down the Rabbit Hole” |

The square braces can also be used to specify what a single character cannot be, by use of the caret ^. If the caret ^ is the first symbol after the open square brace [,

the resulting pattern is negated. For example, the pattern / [ʌə] / matches any single character (including special characters) except a. This is only true when the caret is the first symbol after the open square brace. If it occurs anywhere else, it usually stands for a caret; Fig. 2.3 shows some examples.

| RE | Match (single characters) | Example Patterns Matched |

| --- | --- | --- |

| [ ^A-Z ] [ ^Ss ] [ ^\ . ] [ e^ ] a^b | not an uppercase letter neither ‘S’ nor ‘s’ not a period either ‘e’ or ‘^’ the pattern ‘a^b’ | “O\yfn pripetchik” “I have no exquisite reason for’t” “our resident Djinn” “look up _ now” “look up $ \underline{\text{a}} $b now” |

The use of square braces solves our capitalization problem for woodchucks. But we still haven't answered our original question; how do we specify both woodchuck and woodchucks? We can't use the square brackets, because while they allow us to say "s or S", they don't allow us to say "s or nothing". For this we use the question-mark /?/, which means "the preceding character or nothing", as shown in Fig. 2.4.

| RE | Match | Example Patterns Matched |

| --- | --- | --- |

| woodchucks? colou?r | woodchuck or woodchucks color or colour | “ $ \underline{\text{woodchuck}} $”\n“ $ \underline{\text{colour}} $” |

We can think of the question-mark as meaning “zero or one instances of the previous character”. That is, it’s a way of specifying how many of something that we want. So far we haven’t needed to specify that we want more than one of something. But sometimes we need regular expressions that allow repetitions of things. For example, consider the language of (certain) sheep, which consists of strings that look like the following:

baa!

baaa!

baaaaa!

baaaaaa!

baaaaaaa!

This language consists of strings with a $b$, followed by at least two $as$, followed by an exclamation point. The set of operators that allow us to say things like “some number of $as$” are based on the asterisk or *, commonly called the Kleene * (pronounced “cleany star”). The Kleene star means “zero or more occurrences of the immediately previous character or regular expression”. So /a*/ means “any string of zero or more as”. This will match $a$ or aaaaaa but it will also match Off Minor, since the string Off Minor has zero as. So the regular expression for matching one or more $a$ is /aa*/,

meaning one a followed by zero or more as. More complex patterns can also be repeated. So / [ab]*/ means “zero or more as or bs” (not “zero or more right square braces”). This will match strings like aaaa or ababab or bbbb.

We now know enough to specify part of our regular expression for prices: multiple digits. Recall that the regular expression for an individual digit was /[0-9]/. So the regular expression for an integer (a string of digits) is /[0-9][0-9]*/. (Why isn't it iust /[0-9]*/?)

Sometimes it’s annoying to have to write the regular expression for digits twice, so there is a shorter way to specify “at least one” of some character. This is the Kleene +, which means “one or more of the previous character”. Thus the expression / [0-9]+/ is the normal way to specify “a sequence of digits”. There are thus two ways to specify the sheep language: /baaa*! / or /baa+!/.

One very important special character is the period (/ . /), a wildcard expression that matches any single character (except a carriage return):

| RE | Match | Example Patterns |

| --- | --- | --- |

| /beg.n/ | any character between beg and n | $ \underline{\text{begin, beg'n, begun}} $ |

The wildcard is often used together with the Kleene star to mean “any string of characters”. For example suppose we want to find any line in which a particular word, for example aardvark, appears twice. We can specify this with the regular expression /aardvark.*aardvark/.

Anchors are special characters that anchor regular expressions to particular places in a string. The most common anchors are the caret ∧ and the dollar-sign $. The caret ∧ matches the start of a line. The pattern /^The/ matches the word The only at the start of a line. Thus there are three uses of the caret ∧: to match the start of a line, as a negation inside of square brackets, and just to mean a caret. (What are the contexts that allow Perl to know which function a given caret is supposed to have?) The dollar sign $ matches the end of a line. So the pattern $ is a useful pattern for matching a space at the end of a line, and /^The dog\ .$ / matches a line that contains only the phrase The dog. (We have to use the backslash here since we want the . to mean “period” and not the wildcard.)

There are also two other anchors: \b matches a word boundary, while \B matches a non-boundary. Thus /\bthe\b/ matches the word the but not the word other. More technically, Perl defines a word as any sequence of digits, underscores or letters; this is based on the definition of "words" in programming languages like Perl or C. For example, /\b99\b/ will match the string 99 in There are 99 bottles of beer on the wall (because 99 follows a space) but not 99 in There are 299 bottles of beer on the wall (since 99 follows a number). But it will match 99 in $99 (since 99 follows a dollar sign ($), which is not a digit, underscore, or letter).