3.2.1. The Ubiquitous Backslash

\.

The backslash is typically used to match troff requests or macros that begin with a dot.

\.nf

You can also use the backslash to escape the backslash. For instance, the font change request in troff is "\f". To search for lines containing this request, you'd use the following regular expression:

\\f

Figure 3.2. Escaped metacharacters in sed

3.2.2. A Wildcard

Given that we are describing a sequence of characters, the wildcard metacharacter allows you to specify a position that any character can fill.

For instance, if we were searching a file containing a discussion of the Intel family of microprocessors, the following regular expression:

80.86

It is seldom useful to match just any character at the beginning or end of a pattern. Therefore, the wildcard character is usually preceded and followed by a literal character or other metacharacter. For example, the following regular expression might be written to search for references to chapters:

Chapter.

It searches for "the string `Chapter' followed by any character." In a search, this expression would turn up virtually the same matches as the fixed string pattern "Chapter". Look at the following example:

$ grep 'Chapter.' sample
you will find several examples in Chapter 9.
"Quote me 'Chapter and Verse'," she said. 
Chapter Ten

Searching for the string "Chapter" as opposed to "Chapter." would have matched all of the same lines. However, there is one case that would be different--if "Chapter" appeared at the end of a line. The wildcard does not match the newline, so "Chapter." would not match that line, while the fixed-string pattern would match the line.

3.2.3. Writing Regular Expressions

In other words, the place to look to correct the problem is the expression where you described the result you wanted. Either the expression is incomplete or it is improperly formulated. For instance, if a program evaluates this expression:

PAY = WEEKLY_SALARY * 52

and knows the values of these variables, it will calculate the correct result. But someone might object that the formula did not account for salespeople, who also receive a commission. To describe this instance, the expression would need to be reformulated as:

PAY = WEEKLY_SALARY * 52 + COMMISSION

You could say that whoever wrote the first expression did not fully understand the scope of the problem and thus did not describe it well. It is important to know just how detailed a description must be. If you ask someone to bring you a book, and there are multiple books in view, you need to describe more specifically the book that you want (or be content with an indeterminate selection process).

The same is true with regular expressions. A program such as grep is simple and easy to use. Understanding the elements of regular expressions is not so hard, either. Regular expressions allow you to write simple or complex descriptions of patterns. However, what makes writing regular expressions difficult (and interesting) is the complexity of the application: the variety of occurrences or contexts in which a pattern appears. This complexity is inherent in language itself, just as you can't always understand an expression by looking up each word in the dictionary.

The process of writing a regular expression involves three steps:

1. Knowing what it is you want to match and how it might appear in the text.

2. Writing a pattern to describe what you want to match.

3. Testing the pattern to see what it matches.

This process is virtually the same kind of process that a programmer follows to develop a program. Step 1 might be considered the specification, which should reflect an understanding of the problem to be solved as well as how to solve it. Step 2 is analogous to the actual coding of the program, and Step 3 involves running the program and testing it against the specification. Steps 2 and 3 form a loop that is repeated until the program works satisfactorily.

Testing your description of what you want to match ensures that the description works as expected. It usually uncovers a few surprises. Carefully examining the results of a test, comparing the output against the input, will greatly improve your understanding of regular expressions. You might consider evaluating the results of a pattern matching-operation as follows:

Hits

The lines that I wanted to match.

Misses

The lines that I didn't want to match.

Omissions

The lines that I didn't match but wanted to match.

False alarms

The lines that I matched but didn't want to match.

Trying to perfect your description of a pattern is something that you work at from opposite ends: you try to eliminate the false alarms by limiting the possible matches and you try to capture the omissions by expanding the possible matches.

Using metacharacters in patterns provides greater flexibility in extending or narrowing the range of matches. Metacharacters, used in combination with literals or other metacharacters, can be used to expand the range of matches while still eliminating the matches that you do not want.

3.2.4. Character Classes

[Ww]hat

This regular expression can match "what" or "What." It will match any line that contains this four-character string, the first character of which is either "W" or "w." Therefore, it could match "Whatever" or "somewhat."

If a file contained structured heading macros, such as .H1, .H2, .H3, etc., you could extract any of these lines with the regular expression:

\.H[12345]

This pattern matches a three-character string, where the last character is any number from 1 to 5.

The same syntax is used by the UNIX shell. Thus, you can use character classes to specify filenames in UNIX commands. For example, to extract headings from a group of chapter files, you might enter:

$ grep '\.H[123]' ch0[12]
ch01:.H1 "Contents of Distribution Tape"
ch01:.H1 "Installing the Software"
ch01:.H1 "Configuring the System"
ch01:.H2 "Specifying Input Devices"
ch01:.H3 "Using the Touch Screen"
ch01:.H3 "Using the Mouse"
ch01:.H2 "Specifying Printers"
ch02:.H1 "Getting Started"
ch02:.H2 "A Quick Tour"
.
.
.

Note that you have to quote the pattern so that it is passed on to grep rather than interpreted by the shell. The output produced by grep identifies the name of the file for each line printed. As another example of a character class, assume you want to specify the different punctuation marks that end a sentence:

.[!?;:,".].

Table 3.2. Special Characters in Character Classes

3.2.5. Repeated Occurrences of a Character

"*hypertext"*

The word "hypertext" will be matched regardless of whether it appears in quotes or not.

Also, if the literal character modified by the asterisk does exist, there could be more than one occurrence. For instance, let's examine a series of numbers:

1
5
10
50
100
500
1000
5000

The regular expression

[15]0*

would match all lines, whereas the regular expression

[15]00*

would match all but the first two lines. The first zero is a literal, but the second is modified by the asterisk, meaning it might or might not be present. A similar technique is used to match consecutive spaces because you usually want to match one or more, not zero or more, spaces. You can use the following to do that:

*

".*"

This would match all characters between the first and last quotation marks on the line plus the quotation marks. The span matched by ".*" is always the longest possible. This may not seem important now but it will be once you learn about replacing the string that was matched.

As another example, a pair of angle brackets is a common notation for enclosing formatting instructions used in markup languages, such as SGML, HTML, and Ventura Publisher.

You could print all lines with these marks by specifying:

$ grep '<.*>' sample

When used to modify a character class, the asterisk can match any number of a character in that class. For instance, look at the following five-line sample file:

I can do it
I cannot do it
I can not do it
I can't do it
I cant do it

If we wanted to match each form of the negative statement, but not the positive statement, the following regular expression would do it:

can[no']*t

The asterisk causes any of the characters in the class to be matched in any order and for any number of occurrences. Here it is:

$ grep "can[no']*t" sample
I cannot do it
I can not do it
I can't do it
I cant do it

There are four hits and one miss, the positive statement. Notice that had the regular expression tried to match any number of characters between the string "can" and "t," as in the following example:

can.*t

it would have matched all lines.

+

The plus sign metacharacter can be thought of as "at least one" of the preceding character. In fact, it better corresponds to how many people think * works.

80[234]?86

It matches the string "80" followed by a "2," a "3," a "4," or no character followed by the string "86." Don't confuse the ? in a regular expression with the ? wildcard in the shell. The shell's ? represents a single character, equivalent to . in a regular expression.

3.2.7. Positional Metacharacters

^•

(The • represents a literal tab character, which is normally invisible.) Without the ^ metacharacter, this expression would print any line containing a tab.

Normally, using vi to input text to be processed by troff, you do not want spaces appearing at the end of lines. If you want to find (and remove) them, this regular expression will match lines with one or more spaces at the end of a line:

*$

troff requests and macros must be input at the beginning of a line. They are two-character strings, preceded by a dot. If a request or macro has an argument, it is usually followed by a space. The regular expression used to search for such requests is:

^\...

This expression matches "a dot at the beginning of a line followed by any two-character string, and then followed by a space."

You can use both positional metacharacters together to match blank lines:

^$

You might use this pattern to count the number of blank lines in a file using the count option, -c, to grep:

$ grep -c '^$' ch04 
5

This regular expression is useful if you want to delete blank lines using sed. The following regular expression can be used to match a blank line even if it contains spaces:

^*$

Similarly, you can match the entire line:

^.*$

which is something you might possibly want to do with sed.

In sed (and grep), "^" and "$" are only special when they occur at the beginning or end of a regular expression, respectively. Thus "^abc" means "match the letters a, b, and c only at the beginning of the line," while "ab^c" means "match a, b, a literal ^, and then c, anywhere on the line." The same is true for the "$."

In awk, it's different; "^" and "$" are always special, even though it then becomes possible to write regular expressions that don't match anything. Suffice it to say that in awk, when you want to match either a literal "^" or "$," you should always escape it with a backslash, no matter what its position in the regular expression.

3.2.8. A Span of Characters

11*0

It will match each of the following lines:

10
110
111110
1111111111111111111111111110

These metacharacters give elasticity to a regular expression.

Now let's look at a pair of metacharacters that allow you to indicate a span and also determine the length of the span. So, you can specify the minimum and maximum number of occurrences of a literal character or regular expression.

\{n,m\}

For example, the following expression will match "1001," "10001," and "100001" but not "101" or "1000001":

10\{2,4\}1

This metacharacter pair can be useful for matching data in fixed-length fields, data that perhaps was extracted from a database. It can also be used to match formatted data such as phone numbers, U.S. social security numbers, inventory part IDs, etc. For instance, the format of a social security number is three digits, a hyphen, followed by two digits, a hyphen, and then four digits. That pattern could be described as follows:

[0-9]\{3\}-[0-9]\{2\}-[0-9]\{4\}

Similarly, a North American local phone number could be described with the following regular expression:

[0-9]\{3\}-[0-9]\{4\}

If you are using pre-POSIX awk, where you do not have braces available, you can simply repeat the character classes the appropriate number of times:

[0-9][0-9][0-9]-[0-9][0-9][0-9][0-9]

3.2.9. Alternative Operations

UNIX|LINUX

will match lines containing either the string "UNIX" or the string "LINUX". More than one alternative can be specified:

UNIX|LINUX|NETBSD

A line matching any of these three patterns will be printed by egrep.

3.2.10. Grouping Operations

BigOne(Computer)?

This expression will match the string "BigOne" by itself or followed by a single occurrence of the string "Computer". Similarly, if a term is sometime spelled out and at other times abbreviated:

$ egrep "Lab(oratorie)?s" mail.list
Bell Laboratories, Lucent Technologies
Bell Labs

You can use parentheses with a vertical bar to group alternative operations. In the following example, we use it to specify a match of the singular or plural of the word "company."

compan(y|ies)

It is important to note that applying a quantifier to a parenthesized group of characters can't be done in most versions of sed and grep, but is available in all versions of egrep and awk.

3.2.11. What's the Word? Part II

Let's reevaluate the regular expression for searching for a single word in light of the new metacharacters we've discussed. Our first attempt at writing a regular expression for grep to search for a word concluded with the following expression:

book.*

This expression is fairly simple, matching a space followed by the string "book" followed by any number of characters followed by a space. However, it does not match all possible occurrences and it does match a few nuisance words.

The following test file contains numerous occurrences of "book." We've added a notation, which is not part of the file, to indicate whether the input line should be a "hit" (>) and included in the output or a "miss" (<). We've tried to include as many different examples as possible.

$ cat bookwords
> This file tests for book in various places, such as
> book at the beginning of a line or
> at the end of a line book
> as well as the plural books and
< handbooks.  Here are some
< phrases that use the word in different ways:
> "book of the year award"
> to look for a line with the word "book"
> A GREAT book!
> A great book? No.
> told them about (the books) until it
> Here are the books that you requested
> Yes, it is a good book for children
> amazing that it was called a "harmful book" when
> once you get to the end of the book, you can't believe
< A well-written regular expression should
< avoid matching unrelated words,
< such as booky (is that a word?)
< and bookish and
< bookworm and so on.

As we search for occurrences of the word "book," there are 13 lines that should be matched and 7 lines that should not be matched. First, let's run the previous regular expression on the sample file and check the results.

$ grep 'book.*' bookwords
This file tests for book in various places, such as
as well as the plural books and
A great book? No.
told them about (the books) until it
Here are the books that you requested
Yes, it is a good book for children
amazing that it was called a "harmful book" when
once you get to the end of the book, you can't believe
such as booky (is that a word?)
and bookish and

It only prints 8 of the 13 lines that we want to match and it prints 2 of the lines that we don't want to match. The expression matches lines containing the words "booky" and "bookish." It ignores "book" at the beginning of a line and at the end of a line. It ignores "book" when there are certain punctuation marks involved.

To restrict the search even more, we must use character classes. Generally, the list of characters that might end a word are punctuation marks, such as:

? . , ! ; : '

In addition, quotation marks, parentheses, braces, and brackets might surround a word or open or close with a word:

" () {} []

You would also have to accommodate the plural or possessive forms of the word.

Thus, you would have two different character classes: before and after the word. Remember that all we have to do is list the members of the class inside square brackets. Before the word, we now have:

["[{(]

and after the word:

[]})"?!.,;:'s]

Note that putting the closing square bracket as the first character in the class makes it a member of the class rather than closing the set. Putting the two classes together, we get the expression:

["[{(]*book[]})"?!.,;:'s]*

Show this to the uninitiated, and they'll throw up their hands in despair! But now that you know the principles involved, you can not only understand this expression, but could easily reconstruct it. Let's see how it does on the sample file (we use double quotes to enclose the single quote character, and then a backslash in front of the embedded double quotes):

$ grep " [\"[{(]*book[]})\"?!.,;:'s]* " bookwords
This file tests for book in various places, such as
as well as the plural books and
A great book? No.
told them about (the books) until it
Here are the books that you requested
Yes, it is a good book for children
amazing that it was called a "harmful book" when
once you get to the end of the book, you can't believe

We eliminated the lines that we don't want but there are four lines that we're not getting. Let's examine the four lines:

book at the beginning of a line or
at the end of a line book
"book of the year award" 
A GREAT book!

All of these are problems caused by the string appearing at the beginning or end of a line. Because there is no space at the beginning or end of a line, the pattern is not matched. We can use the positional metacharacters, ^ and $. Since we want to match either a space or beginning or end of a line, we can use egrep and specify the "or" metacharacter along with parentheses for grouping. For instance, to match either the beginning of a line or a space, you could write the expression:

(^| )

(Because | and () are part of the extended set of metacharacters, if you were using sed, you'd have to write different expressions to handle each case.)

Here's the revised regular expression:

(^| )["[{(]*book[]})"?\!.,;:'s]*( |$)

Now let's see how it works:

$ egrep "(^| )[\"[{(]*book[]})\"?\!.,;:'s]*( |$)" bookwords
This file tests for book in various places, such as
book at the beginning of a line or
at the end of a line book
as well as the plural books and
"book of the year award"
to look for a line with the word "book"
A GREAT book!
A great book? No.
told them about (the books) until it
Here are the books that you requested
Yes, it is a good book for children
amazing that it was called a "harmful book" when
once you get to the end of the book, you can't believe

This is certainly a complex regular expression; however, it can be broken down into parts. This expression may not match every single instance, but it can be easily adapted to handle other occurrences that you may find.

You could also create a simple shell script to replace "book" with a command-line argument. The only problem might be that the plural of some words is not simply "s." By sleight of hand, you could handle the "es" plural by adding "e" to the character class following the word; it would work in many cases.

A Program for Making Single Replacements The MKS Toolkit, a set of UNIX utilities for DOS by Mortice Kern Systems, Inc., contains a very useful program called gres (global regular expression substitution). Just like grep, it searches for a pattern in a file; however, it allows you to specify a replacement for the string that you match. This program is in fact a simplified version of sed, and like sed, it prints all lines regardless of whether or not a replacement was made. It does not make the replacement in the file itself. You have to redirect the output from the program into a file if you want to save the changes. gres is not part of standard UNIX but it would be a nice tool to have. It can be created using a simple shell script that invokes sed to do the work. $ cat gres if [ $# -lt "3" ] then echo Usage: gres pattern replacement file exit 1 fi pattern=$1 replacement=$2 if [ -f $3 ] then file=$3 else echo $3 is not a file. exit 1 fi A="`echo | tr '\012' '\001' `" # See footnote[21] sed -e "s$A$pattern$A$replacement$A" $file Throughout the rest of the chapter, we will use gres to demonstrate the use of replacement metacharacters. Remember that whatever applies to gres applies to sed as well. Here we replace the string matched by the regular expression "A.*Z" with double zero (00). $ gres "A.*Z" "00" sample 00ippy, our dog 00iggy 00elda [21]The echo | tr ... line is a complicated but portable way to generate a Control-A character to use as the separator for the sed substitute command. Doing this greatly decreases the chance of having the separator character appear in the pattern or replacement texts.

3.2.12. Your Replacement Is Here

When using grep, it seldom matters how you match the line as long as you match it. When you want to make a replacement, however, you have to consider the extent of the match. So, what characters on the line did you actually match?

In this section, we're going to look at several examples that demonstrate the extent of a match. Then we'll use a program that works like grep but also allows you to specify a replacement string. Lastly, we will look at several metacharacters used to describe the replacement string.

3.2.13. Limiting the Extent

".*"

Let's look at a troff macro that has two quoted arguments, as shown below:

.Se "Appendix" "Full Program Listings"

To match the first argument, we might describe the pattern with the following regular expression:

\.Se ".*"

However, it ends up matching the whole line because the second quotation mark in the pattern matches the last quotation mark on the line. If you know how many arguments there are, you can specify each of them:

\.Se ".*" ".*"

Although this works as you'd expect, each line might not have the same number of arguments, causing omissions--you simply want the first argument. Here's a different regular expression that matches the shortest possible extent between two quotation marks:

"[^"]*"

It matches "a quote followed by any number of characters that do not match a quote followed by a quote":

$ gres '"[^"]*"' '00' sampleLine
.Se 00 "Full Program Listings"

Now let's look at a few lines with a dot character (.) used as a leader between two columns of numbers:

1........5
5........10
10.......20
100......200

The difficulty in matching the leader characters is that their number is variable. Let's say that you wanted to replace all of the leaders with a single tab. You might write a regular expression to match the line as follows:

[0-9][0-9]*\.\.*[0-9][0-9]*

This expression might unexpectedly match the line:

see Section 2.3

To restrict matching, you could specify the minimum number of dots that are common to all lines:

[0-9][0-9]*\.\{5,\}[0-9][0-9]*

This expression uses braces available in sed to match "a single number followed by at least five dots and then followed by a single number." To see this in action, we'll show a sed command that replaces the leader dots with a hyphen. However, we have not covered the syntax of sed's replacement metacharacters--\( and \) to save a part of a regular expression and \1 and \2 to recall the saved portion. This command, therefore, may look rather complex (it is!) but it does the job.

$ sed 's/\([0-9][0-9]*\)\.\{5,\}\([0-9][0-9]*\)/\1-\2/' sample
1-5
5-10
10-20
100-200

A similar expression can be written to match one or more leading tabs or tabs between columns of data. You could change the order of columns as well as replacing the tab with another delimiter. You should experiment on your own by making simple and complex replacements, using sed or gres.