Regular Expressions

Imagine you are looking for a name in a telephone directory, but you can't remember its exact spelling. You can spend ages searching through all the possible combinations, unless you have a tool that extracts the relatively small number of options that matches your search, however incomplete it may be. Regular expressions are such a tool.

Roughly speaking, a regular expression (or regexp) is a string that describes another string or a group of strings. Several applications can profit from this ability: Perl, sed, awk, egrep and even Emacs (try Ctrl-Alt-% after reading this article) to name a few.

In fact, many of you already have used some sort of regular expression. In the shell command:

ls *.pl

the characters *.pl act as a regular expression. That is, it is a string that describes all the strings composed by any number of characters of any kind (*), followed by a period (.), followed by two given characters (pl).

The standard set of rules used for composing regular expressions is able to describe all strings, no matter how complicated they are. Unfortunately, life is always more complicated. It turns out that at least two different versions of regular expressions exist: extended and basic. Moreover, not all applications support all the possible rules.

A regular expression is said to match a given string if it correctly describes it. A given regular expression can match with zero to many strings. By convention, regular expressions are written between slashes (/.../). In what follows, I use extended regular expressions.

The simplest regular expression is a plain alphanumeric string. Such a regexp matches with all strings containing its content as a substring. As an example, consider the following verse from Cenerentola, my favorite opera by G. Rossini: “Zitto, zitto, piano, piano, senza strepito e rumore.” The regexp /piano/ is said to match with the verse, because the latter contains the same characters, with the same sequence, of the regexp.

In order to better understand the examples I discuss, you can play with the following Perl script, trying variations of the regexp it contains:

#!/usr/bin/perl
$verse = "Zitto, zitto, piano, piano, senza " .
         "strepito e rumore";
if ($verse =~ /piano/) {
   print "Match!\n";
} else {
   print "Do not match!\n";
}

In Perl, the operator =~ compares two regular expressions and returns “true” if they match.

A few characters (called metacharacters) are not recognized as ordinary characters and are used for special purposes. The *, for example, is used to match zero or more times a group of characters that, in turn, is identified by a couple of parentheses defining an atom, or a group of characters that must be considered as a single entity. The regexp /( piano,)*/ matches with the sample verse because the characters “ piano,”, forming an atom, are repeated twice. If the atom is composed of a single character, parentheses may be omitted.

The meaning of the * within a regular expression is different from the one it has in the shell. In regular expressions, the * is a modifier; it describes the multiplicity of the atom on its left. So, the string “piano” is matched by p* in a shell, but not within a regular expression: /p*/ matches with p, pp, ppp and so on, and even with a null string.

To specify that an atom's multiplicity ranges between N and M, the symbol {N,M} is used. {N} matches strings with exactly N repetitions of the preceding atom; {N,} will match at least N of them. So, the following regular expressions will match:

/( piano,){0,10}/
/( piano,){1,2}/
/( piano,){2}/

Of course, the first regexp will match with “ piano, piano, piano” too.

The metacharacters + and ? are shorthands, respectively, for {1,} and {0,1}.

Matched parenthesized atoms are automatically stored into special variables (called back references) identified by the symbol \ followed by a number. The first parenthesized atom occurrence in a regular expression will be stored in \1, the second in \2 and so on. For example:

/Z(itto), z\1, ( piano,)\2/

will match the above-mentioned verse (imagine that \1 = “itto” and \2 = “piano,”).

The . metacharacter can describe any character, so the regular expression /.(itto), .\1/ matches both “Zitto, zitto” and “zitto, zitto”. However, it even matches with “Ritto, ritto”, which does not have the same meaning. To avoid being so generic, you can specify a set of possible alternatives, listing the possible characters in brackets:

/[Zz](itto), [Zz]\1/

A dash in brackets is used to specify a range of characters. For example, /[a-z]/ matches all lowercase characters, and /[A-Z]/ matches all uppercase characters. /[a-zA-Z0-9_]/ matches any alphanumeric character or an undesrcore.

The metacharacter | can be used to express different alternatives. It works like a logical OR statement. Therefore:

/Zitto|zitto/

will match with both “Zitto” and “zitto”.

The metacharacters ^ and $ match, respectively, the beginning and the end of a string. If used inside brackets, the caret is interpreted as the negation operator. So:

/[^a-z]itto/

will match Zitto, but not zitto ([^a-z] can be read as “any letter that is not a lowercase letter”).

To match a metacharacter it's enough to put a backslash (\) in front of it to tell the regexp to interpret it as an ordinary character. The \ character is often called an escape character.