A regular expression (regex) is a way of describing a pattern of text (rather than merely a literal substring of text) that we may want to match, extract, or replace with something else. We create such patterns using the regex language features which consists largely of literal characters (alphanumeric and a few others) that stand for themselves, and several special characters or character sequences that have particular meanings within a regex pattern.

In this first part of the tutorial we will outline the 5 basic concepts needed to understand regular expressions:

1. Concatenation: This is an implicit assumption meaning simply that we can create larger, more complex patterns by simply combining simpler patterns. For example, m/f/ is a pattern that matches the character ‘f’, and m/o/ is a pattern that matches the character ‘o’. We can combine these into m/foo/ to match the character sequence ‘foo’.
2. Alternation: The ’|’ character is a meta-character inside a regular expression. It acts as an operator that allows us to specify two or more alternative sub-patterns. For example: the pattern m/ab|cd/ will match either ‘ab’ or ‘cd’.
3. Iteration: The ’*’ meta-character is an iterative or quantitative operator that means to match zero-or-more of the previous element. For example: the pattern m/a*b/ would match ‘ab’, ‘aab’, ‘aaab’, etc., or even just ‘b’ (ie, zero-or-more ‘a’ characters followed by a ‘b’ character).
4. Grouping: Parentheses give us a way to create subexpressions that are treated as a unit. For example, if we want to match zero-or-more occurrences of the substring ‘foo’ we could specify our pattern as: m/(foo)*/. Here the * is used outside of the parentheses and applies the whole parenthesized subexpression. Parentheses also govern the scope of alternation: the pattern m/ab|cd/ means match either ‘ab’ or ‘cd’, but the pattern m/a(b|c)d/ means match an ‘a’, then either a ‘b’ or a ‘c’, and finally a ‘d’.
5. Wildcard: The dot . is wildcard character that matches any character other than a newline character (this can be changed to include the newline as well). Thus, the pattern: m/f.*bar/ will match an ‘f’ followed by zero-or-more of any characters, followed by ‘bar’.

Those are the primary concepts for regular expressions, and although there are many more meta-characters and concepts, many are derived from just these basics. Let’s consider a couple of simple examples.

If we want to read in a file line-by-line and print out only lines that have a ‘foo’ followed somewhere on the same line by ‘bar’ we could use this pattern:

    while(<>){
        print if /foo.*bar/;
    }

However, if we want to print lines that match either ‘foodbar’ or ‘footbar’ we could do this:

    while(<>){
        print if /foo(d|t)bar/;
    }

We can write quite complicated regular expressions using just the above concepts, but they would very quickly get too long to manage. For example, if we wanted to print out lines containing two digits together we could write:

    while(<>){
        print if /(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)/;
    }

As you can see, while we can do it, it won’t be a pleasant task to try to match something like an ‘f’ followed by any digit followed by any alphabetical character (regardless of case) using only alternation as in the above example.

Next week we’ll look at the character class and several shortcut sequences that will make such tasks a great deal simpler (not to mention a lot shorter as well).

*****

Last week we explored using Perl’s sort() function for simple sorting uses. This week we will take a brief look at using the sort() function efficiently when the sort fields require extraction or some computation. We will do this by demonstrating the Schwartzian Transform (named after Randal Schwartz, and often abbreviated to just ST).

Let’s consider a simple case of wanting to sort colon separated records on one or more fields. Here is some sample data:

    foo:23:bar:2.1
    bar:42:qux:3.0
    baz:19:foo:1.1
    qux:19:foo:1.2

Now, the following is one attempt to sort this data on the 3rd data field:

    #!/usr/bin/perl -w
    use strict;
    my @data   = <DATA>;
    my @sorted = sort custom @data;
    print @sorted;

    sub custom {
        (split /:/,$a)[2] cmp (split /:/,$b)[2];
    }
    __DATA__
    foo:23:bar:2.1
    bar:42:qux:3.0
    baz:19:foo:1.1
    qux:19:foo:1.2

This works but there is an efficiency problem here — when sorting a list the comparison function (custom() in this case) is called many times, and each time in the above case it is performing 2 split() operations. A far better approach is to preprocess the data so that the sort fields may be more directly accessed, and any operations performed on the data need only be performed once per record. After sorting, the data can then be post-processed to obtain the original records. Here is one way of doing that with each step separated:

    #!/usr/bin/perl -w
    use strict;
    my @data = <DATA>;
    my @pre    = map { [$_, split /:/ ] } @data;
    my @post   = sort custom @pre;
    my @sorted = map { $_->[0] } @post;
    print @sorted;

    sub custom {
        $a->[3] cmp $b->[3];
    }
    __DATA__
    foo:23:bar:2.1
    bar:42:qux:3.0
    baz:19:foo:1.1
    aux:19:foo:1.2

In the above we have first preprocessed our records into a list of anonymous arrays where the first element is the entire record and the remaining elements are the split() fields of that record. We then sort those anonymous arrays on the field we desire (in this case the third index of each anonymous array). Now our @post array contains a sorted list of anonymous arrays sorted on the correct field and we merely extract the first element of each anon array to recover our original records. The three steps above can be combined by simply passing the results of the preprocessing stage directly into the sort stage and passing those results through the post-processing stage and out into our sorted array:

    #!/usr/bin/perl -w
    use strict;
    my @data = <DATA>;
    my @sorted = map { $_->[0] }
                 sort custom
                 map { [$_, split /:/ ] } @data;
    print @sorted;

    sub custom {
        $a->[3] cmp $b->[3];
    }
    __DATA__
    foo:23:bar:2.1
    bar:42:qux:3.0
    baz:19:foo:1.1
    aux:19:foo:1.2

This ‘map/sort/map’ algorithm is what is referred to as the ST and provides a nice clean and relatively efficient way to sort on computed or extracted fields. We can also easily adjust our custom() comparison routine to sort on multiple fields as shown in last weeks column. For a more extended look at sorting, and an alternative efficient algorithm, please see the following article:

    http://www.hpl.hp.com/personal/Larry_Rosler/sort/sorting.html

Perl’s sort function is a little different than the standard built-in functions — like map() and grep() it can accept a block as a first argument, but it can also accept a named subroutine, or a reference to a subroutine. This allows you to specify the comparison method used in sorting — the default sorting method is alphabetical (ascii-betical) and the comparison operator is the ‘cmp’ operator. Thus, the following two examples are the same:

    my @sorted = sort @unsorted;
    my @sorted = sort {$a cmp $b} @unsorted;

Inside the block or subroutine you use the package-global variables $a and $b to refer to the elements being compared (these are specially exempt from the ‘use strict’ pragma for just this reason). To specify a reverse alphabetical sort you switch the variables:

    my @reverse_sorted = sort {$b cmp $a} @unsorted;

You can define any comparison method you like, but you must make sure that your block or subroutine returns only -1, 0, or 1 depending on the ordering you want (the ‘cmp’ and ’<=>’ operators are usually used for this purpose).

To sort a list numerically, we’ll use the <=> operator:

    my @ascending  = sort {$a <=> $b} @unsorted;
    my @descending = sort {$b <=> $a} @unsorted;

A hash does not give us a way to store information in an ordered fashion but we often need to print out a hash’s contents in some sorted order. If we wish to print out a hash sorted by keys (alphabetically) we can simply do this:

    my %ages = ( Andrew => 37, Sue => 41, Thomas => 9, Joey => 16);
    foreach my $name (sort keys %ages) {
        print "$name : $ages{$name}\n";
    }

But what if I wanted to produce output sorted by age from oldest to youngest rather than names (by hash values rather than keys)? That’s also very easy:

    my %ages = ( Andrew => 37, Sue => 41, Thomas => 9, Joey => 16);
    foreach my $name (sort { $ages{$b} <=> $ages{$a} } keys %ages) {
        print "$name : $ages{$name}\n";
    }

In this case, we still get a list of keys, but in the comparison block we compare the hash values for each key rather than the keys themselves — thus, we are iterating over the list of hash keys sorted in descending numerical order by the hash values for those keys. Now, let’s consider the case where we want to dual sort — that is, if two ages (values) are equal we want to order data alphabetically by the name (key). We’ll have to add some additional children to my hash to demonstrate:

    my %ages = ( Andrew => 37, Sue => 41, Thomas => 9,  Joey => 16,
                 Karen  => 11, John => 9, Kevin  => 16, Lisa => 9);
    foreach my $name (sort by_age keys %ages) {
        print "$name : $ages{$name}\n";
    }

    sub by_age {
        $ages{$b} <=> $ages{$a}
                  ||
               $a cmp $b
    }

In this case, I’ve use a separate routine ‘by_age’ instead of a block. In the routine, the <=> returns 0 if the ages are equal and this is a false value so Perl looks to the other side of the logical OR operator (||) and evaluates the ‘cmp’ operation to get the return value of the function.

Starting with version 5.6.0 of Perl you no longer have to use $a and $b as your comparison variables when you use a separate subroutine. If you prototype the subroutine with ($$) then the arguments are passed to the routine in the @_ array:

    sub by_age ($$); # declare with proto before using

    my %ages = ( Andrew => 37, Sue => 41, Thomas => 9,  Joey => 16,
                 Karen  => 11, John => 9, Kevin  => 16, Lisa => 9);
    foreach my $name (sort by_age keys %ages) {
        print "$name : $ages{$name}\n";
    }

    sub by_age ($$) {
        $ages{$_[1]} <=> $ages{$_[0]}
                     ||
               $_[0] cmp $_[1]
    }

This is slower than using $a and $b, but it means you can use sort routines defined in other packages without having namespace problems. (see: ‘perldoc -f sort’ for further documentation).

In next week’s article we will examine ways to sort more complicated data such as sorting multi-field records on any field.

*****

Hashes are quite useful as databases — you store key/value pairs and later look up the data associated with any key. Wouldn’t it be nice if we could connect a Perl hash directly to a DBM file on disk so we could easily have a persistent hash database? We can do exactly that by using the tie() function to tie a hash to a dbm file.

Perl ships with support for four types of DBM files (which ones will be compiled into your perl depend on what is available on your platform when you built perl). These are: NDBM, DB_File, GDBM, and SDBM. DB_File is the most flexible (so we will use it here), but NDBM is widespread (was used with perl 4) and SDBM libraries ship with perl so you always have at least one possibility to use.

Tieing a hash to a DBM is quite simple — you merely ‘use’ the appropriate DB module, declare a hash to tie, and call the tie() function to complete the process of associating the hash with the DBM file.

    #!/usr/bin/perl -w
    use strict;
    use DB_File; # or NDBM_File, GDBM_File, SDBM_File, AnyDBM_File
    my %dbase;
    my $file = 'phones.db';
    tie(%dbase, 'DB_File', $file) || die "can't open $file: $!";

    $dbase{andrew} = '555-1234'; # not really
    $dbase{john}   = '555-4321';

    foreach my $key (keys %dbase) {
        print "$key: $dbase{$key}\n";
    }

    untie(%dbase);
    __END__

The call to tie() takes 3 arguments: the hash to tie; the classname of the DB module, and the filename for the database (additional arguments can set flags and permissions on the database file — see the documentation for details).

The above example defines a hash and then tie()’s it to a DB_File DBM file. We then enter two key/value pairs (names and phone numbers) and iterate over the hash. The big deal is, if you run this program and then comment out the two lines assigning to the hash, you’ll find that it still prints out the same data because the data persists in the DBM file ‘phones.db’. We now have a persistent hash — it works just like any other hash, but it is stored on disk as well.

One thing that I need to mention is how we iterate over the hash. In the above example we simply used the keys() function to iterate over the list of keys in the hash. If this were a large database, this could take more memory than you desire. A better way to iterate over the hash is by using the each() function which returns key/value pairs sequentially (without building the entire list in memory):

    while( my($k, $v) = each(%dbase) ) {
        print "$k: $v\n";
    }

You can use this mechanism for all sorts of persistent data. Netscape maintains its history list of recently visited web-sites between invocations by using such a mechanism. You could build an address book application using DBM files, or you store configuration information for your application.

The DB_File module also allows you to tie() a hash to a BTREE structure (which can maintain an order on your keys) or to tie a hash to a flat text file using line numbers as keys for each line (record) in the file.

For further information see the following documentation:

    perldoc -f tie
    perldoc AnyDBM_File
    perldoc DB_File

*****

A hash (associative array) is a structure that stores data in the form of key/value pairs. The keys are unique strings, and the values can be any scalar value (string, number, or reference). In essence, a hash is a look-up table, or, in some people’s terms, a dictionary.

Hashes have a % prefix. You can assign a simple list to a hash and it will be interpreted as sequential key/value pairs. Consider a set of translations of color names from English to French:

    my %color_map = ('red', 'rouge', 'blue', 'bleu', 'green', 'vert');

In the above hash the string ‘red’ is the key for the value ‘rouge’. Perl gives us an alternative to the comma that is particularly useful in making hash assignments more readable — this is the ’=>’ or fat-comma:

    my %color_map = ( red => 'rouge', blue => 'bleu', green => 'vert');

The => operator is a synonym for an ordinary comma with one extra feature: It automatically quotes the string on the left. The second example makes it much more clear that we are assigning 3 associations to the hash rather than a 6-element list. You can access individual elements of a hash using the $ symbol and using curly braces to denote which key you want to access:

    print "$color_map{red}\n";  # prints: rouge

Now, consider a simple program that asks a user to input a color name and which then prints out the French translation. Without hashes you will probably wind up using a series if if/elsif tests to discover what color was entered and print out the appropriate translation. However, with the %color_map hash we need use a single if/else construct to see if the word has a translation in our hash and act accordingly:

    my %color_map = ( red    => 'rouge',
                      blue   => 'bleu',
                      green  => 'vert',
                      black  => 'noir',
                      purple => 'violet',
                      yellow => 'jeune',
                      white  => 'blanc',
                      brown  => 'brun',
                      grey   => 'gris',
                    );
    print "Enter a color in English: ";
    chomp( my $color = <STDIN>);
    $color = lc($color);
    if ( $color_map{$color} ) {
        print "$color translates to '$color_map{$color}'\n";
    } else {
        print "No translation available for '$color'\n";
    }

One thing to notice is that keys in a hash are case-sensitive, hence we used the lc() function to lowercase the user’s input before we looked up the color in the hash.

An important distinction between hashes and arrays are that hashes are not ordered — in the above example the key ‘red’ is not the first element in the hash. We can use the keys() function to retrieve the list of keys in a hash, and the values() function to retrieve the list of values. To walk through a hash and print out each pairing you can simply iterate over the keys:

    foreach my $key (keys %hash) {
        print "$key : $hash{$key}\n";
    }

The each() function returns key/value pairs in scalar context so you may also iterate over the hash like so:

    while( my($key, $val) = each(%hash) ) {
        print "$key : $val\n";
    }

A couple of earlier articles describe ways of using hashes and you might want to look them up in the archive (and archive link is provided below in the resources section) — see the articles dated July 20, 2000 and August 31, 2000.

*****