Regular ExPressions

Table of Contents

• What is a Regular Expression?
• The Structure of a Regular Expression
• The Anchor Characters: ^ and $
• Matching a character with a character set
• Match any character with .
• Specifying a Range of Characters with [...]
• Exceptions in a character set
• Repeating character sets with *
• Matching a specific number of sets with \{ and \}
• Matching words with \< and \>
• Backreferences - Remembering patterns with \(, \) and \1
• Potential Problems
• Extended Regular Expressions
• POSIX character sets
• Perl Extensions

Regular Expressions and Extended Pattern Matching

Bruce Barnett

Note that this was written in 1991, before Linux. In the 1980's, it was common to have different sets of regular expression features with different features. ed(1) was different from sed(1) which was different from vi(1), etc. Note that Sun went through every utility and forced each one to use one of two distict regular expression libraries - regular or extended. I wrote this tutorial for Sun users, and some of the commands discussed are now obsolete. On Linux and other UNIX systems, you might find out that some of these features are not implemented. Your milage may vary.

Copyright © 1991, 2001, Bruce Barnett & General Electric Company

What is a Regular Expression?

Regular expressions are used when you want to search for specify lines of text containing a particular pattern. Most of the \*U utilities operate on ASCII files a line at a time. Regular expressions search for patterns on a single line, and not for patterns that start on one line and end on another.

It is simple to search for a specific word or string of characters. Almost every editor on every computer system can do this. Regular expressions are more powerful and flexible. You can search for words of a certain size. You can search for a word with four or more vowels that end with an "s." Numbers, punctuation characters, you name it, a regular expression can find it. What happens once the program you are using find it is another matter. Some just search for the pattern. Others print out the line containing the pattern. Editors can replace the string with a new pattern. It all depends on the utility.

Regular expressions confuse people because they look a lot like the file matching patterns the shell uses. They even act the same way--almost. The square brackers are similar, and the asterisk acts similar to, but not identical to the asterisk in a regular expression. In particular, the Bourne shell, C shell, find, and cpio use file name matching patterns and not regular expressions.

Remember that shell meta-characters are expanded before the shell passes the arguments to the program. To prevent this expansion, the special characters in a regular expression must be quoted when passed as an option from the shell. You already know how to do this because I covered this topic in last month's tutorial.

The Structure of a Regular Expression

There are also two types of regular expressions: the "Basic" regular expression, and the "extended" regular expression. A few utilities like awk and egrep use the extended expression. Most use the "regular" regular expression. From now on, if I talk about a "regular expression," it describes a feature in both types.

Here is a table of the Solaris (around 1991) commands that allow you to specify regular expressions:

Utility	Regular Expression Type
vi	Basic
sed	Basic
grep	Basic
csplit	Basic
dbx	Basic
dbxtool	Basic
more	Basic
ed	Basic
expr	Basic
lex	Basic
pg	Basic
nl	Basic
rdist	Basic
awk	Extended
nawk	Extended
egrep	Extended
EMACS	EMACS Regular Expressions
PERL	PERL Regular Expressions

The Anchor Characters: ^ and $

The use of "^" and "$" as indicators of the beginning or end of a line is a convention other utilities use. The vi editor uses these two characters as commands to go to the beginning or end of a line. The C shell uses "!^" to specify the first argument of the previous line, and "!$" is the last argument on the previous line.

It is one of those choices that other utilities go along with to maintain consistancy. For instance, "$" can refer to the last line of a file when using ed and sed. Cat -e marks end of lines with a "$." You might see it in other programs as well.

Matching a character with a character set

grep '^From: ' /usr/spool/mail/$USER

Match any character with .

^.$

Specifying a Range of Characters with [...]

^[0123456789]$

^[0-9]$

[A-Za-z0-9_]

1. Started with a capital letter "T."
2. Was the first word on a line
3. The second letter was a lower case letter
4. Was exactly three letters long, and
5. The third letter was a vowel

the regular expression would be "^T[a-z][aeiou] ."

Exceptions in a character set

Like the anchors in places that can't be considered an anchor, the characters "]" and "-" do not have a special meaning if they directly follow "[." Here are some examples:

Regular Expression	Matches
[]	The characters "[]"
[0]	The character "0"
[0-9]	Any number
[^0-9]	Any character other than a number
[-0-9]	Any number or a "-"
[0-9-]	Any number or a "-"
[^-0-9]	Any character except a number or a "-"
[]0-9]	Any number or a "]"
[0-9]]	Any number followed by a "]"
[0-9-z]	Any number,
	or any character between "9" and "z".
[0-9\-a\]]	Any number, or
	a "-", a "z", or a "]"

Repeating character sets with *

This explains why the pattern "^#*" is useless, as it matches any number of "#'s" at the beginning of the line, including zero. Therefore this will match every line, because every line starts with zero or more "#'s."

At first glance, it might seem that starting the count at zero is stupid. Not so. Looking for an unknown number of characters is very important. Suppose you wanted to look for a number at the beginning of a line, and there may or may not be spaces before the number. Just use "^ *" to match zero or more spaces at the beginning of the line. If you need to match one or more, just repeat the character set. That is, "[0-9]*" matches zero or more numbers, and "[0-9][0-9]*" matches one or more numbers.

Matching a specific number of sets with \{ and \}

If a backslash is placed before a "<," ">," "{," "}," "(," ")," or before a digit, the back slash turns on a special meaning. This was done because these special functions were added late in the life of regular expressions. Changing the meaning of "{" would have broken old expressions. This is a horrible crime punishable by a year of hard labor writing COBOL programs. Instead, adding a back slash added functionality without breaking old programs. Rather than complain about the unsymmetry, view it as evolution.

Having convinced you that "\{" isn't a plot to confuse you, an example is in order. The regular expression to match 4, 5, 6, 7 or 8 lower case letters is

[a-z]\{4,8\}

You must remember that modifiers like "*" and "\{1,5\}" only act as modifiers if they follow a character set. If they were at the beginning of a pattern, they would not be a modifier. Here is a list of examples, and the exceptions:

Regular Expression	Matches
_
*	Any line with an asterisk
\*	Any line with an asterisk
\\	Any line with a back slash
^*	Any line starting with an asterisk
^A*	Any line
^A\*	Any line starting with an "A*"
^AA*	Any line if it starts with one "A"
^AA*B	Any line with one or more "A"'s followed by a "B"
^A\{4,8\}B	Any line starting with 4, 5, 6, 7 or 8 "A"'s
	followed by a "B"
^A\{4,\}B	Any line starting with 4 or more "A"'s
	followed by a "B"
^A\{4\}B	Any line starting with "AAAAB"
\{4,8\}	Any line with "{4,8}"
A{4,8}	Any line with "A{4,8}"

Matching words with \< and \>

There is an easy solution. The characters "\<" and "\>" are similar to the "^" and "$" anchors, as they don't occupy a position of a character. They do "anchor" the expression between to only match if it is on a word boundary. The pattern to search for the word "the" would be "\<[tT]he\>." The character before the "t" must be either a new line character, or anything except a letter, number, or underscore. The character after the "e" must also be a character other than a number, letter, or underscore or it could be the end of line character.

Backreferences - Remembering patterns with \(, \) and \1

\([a-z]\)\([a-z]\)[a-z]\2\1

Potential Problems

The "\<" and "\>" characters were introduced in the vi editor. The other programs didn't have this ability at that time. Also the "\{min,max\}" modifier is new and earlier utilities didn't have this ability. This made it difficult for the novice user of regular expressions, because it seemed each utility has a different convention. Sun has retrofited the newest regular expression library to all of their programs, so they all have the same ability. If you try to use these newer features on other vendor's machines, you might find they don't work the same way.

The other potential point of confusion is the extent of the pattern matches. Regular expressions match the longest possible pattern. That is, the regular expression

A.*B

Extended Regular Expressions

The character "?" matches 0 or 1 instances of the character set before, and the character "+" matches one or more copies of the character set. You can't use the \{ and \} in the extended regular expressions, but if you could, you might consider the "?" to be the same as "\{0,1\}" and the "+" to be the same as "\{1,\}."

By now, you are wondering why the extended regular expressions is even worth using. Except for two abbreviations, there are no advantages, and a lot of disadvantages. Therefore, examples would be useful.

The three important characters in the expanded regular expressions are "(," "|," and ")." Together, they let you match a choice of patterns. As an example, you can egrep to print all From: and Subject: lines from your incoming mail:

egrep '^(From|Subject): ' /usr/spool/mail/$USER

(^| )the([^a-z]|$)

egrep "a[n]? (simple|easy)? problem" data

I promised to explain why the back slash characters don't work in extended regular expressions. Well, perhaps the "\{...\}" and "\<...\>" could be added to the extended expressions. These are the newest addition to the regular expression family. They could be added, but this might confuse people if those characters are added and the "\(...\)" are not. And there is no way to add that functionality to the extended expressions without changing the current usage. Do you see why? It's quite simple. If "(" has a special meaning, then "\(" must be the ordinary character. This is the opposite of the Basic regular expressions, where "(" is ordinary, and "\(" is special. The usage of the parentheses is incompatable, and any change could break old programs.

If the extended expression used "( ..|...)" as regular characters, and "\(...\|...\)" for specifying alternate patterns, then it is possible to have one set of regular expressions that has full functionality. This is exactly what GNU emacs does, by the way.

The rest of this is random notes.

Regular Expression	Class	Type	Meaning
_
.	all	Character Set	A single character (except newline)
^	all	Anchor	Beginning of line
$	all	Anchor	End of line
[...]	all	Character Set	Range of characters
*	all	Modifier	zero or more duplicates
\<	Basic	Anchor	Beginning of word
\>	Basic	Anchor	End of word
\(..\)	Basic	Backreference	Remembers pattern
\1..\9	Basic	Reference	Recalls pattern
_+	Extended	Modifier	One or more duplicates
?	Extended	Modifier	Zero or one duplicate
\{M,N\}	Extended	Modifier	M to N Duplicates
(...|...)	Extended	Anchor	Shows alteration
_
\(...\|...\)	EMACS	Anchor	Shows alteration
\w	EMACS	Character set	Matches a letter in a word
\W	EMACS	Character set	Opposite of \w

POSIX character sets

Character Group	Meaning
[:alnum:]	Alphanumeric
[:cntrl:]	Control Character
[:lower:]	Lower case character
[:space:]	Whitespace
[:alpha:]	Alphanumeric
[:digit:]	Digit
[:print:]	Printable character
[:upper:]	Upper Case Character
[:blank:]	whitespace, tabe, etc.
[:graph:]	?
[:punct:]	Puctuation
[:xdigit:]	Extended Digit

Perl Extensions

Example of PERL Extended, multi-line regular expression

m{ \(
      (	  # Start group
       [^()]+ # anything but '(' or ')'
      |   # or
        \( [^()]* \)
      )+  # end group
   \)
}x