Regular Expressions and the PCRE Library

Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 64

Following an introduction to the notation and a description of the Perl Compatible Regular Expression Library, we describe a DLL and cover functions that provide Regular Expression support for APL+Win. Based on open source code, the DLL is self-contained. There is a tabular description of much of the PCRE notation and options at the end.

Regular Expressions¶

The regular expression notation, invented by mathematician Stephen Kleene in the 1940’s, is a powerful means to describe textual patterns; it underlies the pattern matching and searching facilities in many text-processing applications and scripting languages. While extensions to the basic notation have proliferated, the Perl language variant described here is close to a de-facto standard.

In this brief, incomplete, and simplified introduction, double quotation marks, having no special meaning in the notation, delimit both regular expressions and character strings. The contractions regex and regexes are widely used.

A regular expression defines a, possibly infinite, set of character strings. The regular expression and each of the strings it defines are said to match. The practical value of the regular expression notation is due to the compactness and manipulability of a regex definition relative to the set of strings it defines. Given a regex and a subject string, a regex matching engine attempts to discover a sub-string of the subject that matches the regex. If any such sub-string exists, the match is said to succeed; if none exists the match is said to fail. When there are multiple matching sub-strings, most engines find the longest of the leftmost matches.

A regular expression is represented as a character string satisfying certain syntactic rules.

Except for 12 non-alphanumeric meta-characters that have special meaning, most characters in a regex stand for themselves.

Any character without special meaning is a regex that matches only the character itself. So the regex “q” matches only the single string “q”. Normally case sensitive, a regex can be made case insensitive by a matcher option.

A backslash preceding a non-alphanumeric character is said to escape or quote the character, suppressing any special meaning. The regex “\*” matches only “*” and “\\” matches only “\”.

A backslash may give special meaning to a following alphanumeric. For example, “\n” is a regex that matches the newline character (hex 0C).

A catenation of regular expressions forms a regular expression that matches a catenation of strings each matching its corresponding sub-expression. So the regex “array”, the catenation of five one-character expressions, matches sub-strings of “an array language”, “anarrayofhope”, and “array of arrays”.

The period meta-character matches any single character. So the regex “s.x” matches “sax”, “six”, “sxx”, and “s.x” but not “sx” or “sabx”. The regex “s\.x” matches only “s.x”.

Characters enclosed in square brackets form a character class regex that matches a single instance of any of its enclosed characters. The regex “s[aeiou]x” matches three-character strings such as “sox”, “sax”, and “six” but not “sqx”, “s]x”, or “s[x”. If a circumflex immediately follows the left bracket, the regex matches only characters not included. The regex “[^aeiou]” matches “b”, “q”, “9”, and “^” but not “a”, “e”, or “u”.

Within a character class regex, a pair of non-meta-characters separated by a minus sign, represents a range of characters; so the character class regex “[A-Za-z]” matches any upper or lower case letter and “[^0-9]” matches all characters except digits.

Several predefined character classes are denoted by a backslash followed by certain letters. For example, “\d” is equivalent to “[0123456789]” and “\D” is equivalent to “[^0123456789]”. So “\d\d\d” matches any string of three digits while “x\Dy” matches “xay”, “x]y”, as well as “x\y” and “xDy” but no string having a digit in its second position.

A regex and a following quantifier form a regex that matches the catenation of some number of strings each matched by the base regex. A regex quantified by the question mark meta-character matches zero or once. So “\d\d\.?” matches two digit numbers with an optional trailing period.

An asterisk quantified regex matches any number of times including zero. “10*2” matches “12”, “102” and “10000002” but not “10*2” or “10abc2”.

The plus sign quantifier is similar but requires at least one match. So “10+2” doesn’t match “12” but does match “102” and “1002”.

These quantifiers are shorthand for frequently needed cases of the min-max quantifier: “regex{min,max}” matches at least min and at most max instances of regex. “\d{1,4}\.{0,1}\d{0,3}” matches “1”, “1234”, “5.” and “67.890” but not “12345”, “0.2345”, or “12..34”.

Quantifiers have higher syntactic precedence than catenation but parenthesis may be used to define their scope. So “(10)*2” matches “2”, “102”, and “10102”. “M(iss)+ippi” matches “Missippi”, and “Mississississippi” as well as the correct spelling.

Alternative sub-patterns are separated by vertical bars, which have lower precedence than catenation so parenthesis may be needed to limit the first and last alternative. “Booleans are true|false values” matches “Booleans are true” and “false values” whereas “Booleans are (true|false) values” matches “Booleans are true values” and “Booleans are false values”.

Modern regular expression notation incorporates many other pragmatically useful and convenient variations on the elements described above.

Parentheses, used to indicate syntactic grouping as described above, have other important uses.

Matching engines, in addition to reporting whether or not a pattern matches a subject string, report information about where and how the pattern matched. The positions of the ends of the matching sub-string are reported. PCRE reports such positions as the number of characters preceding the positions. In APL terms, these are the zero origin indices of the first character of the sub-string and character immediately following the sub-string.

Similarly, the matcher reports where each parenthesis enclosed sub-expression matched. When the sub-expression matched at several places, the last match is reported. So “abc(def|ghi)jkl” matches “123abcghijkl456” between positions 3 and 12. The sub-expression “def|ghi” will be reported to match between positions 6 and 9. The parentheses are said to capture the matching sub-string. Complex regexes may include many pairs, possibly nesting, of capturing parentheses. The captures are numbered left to right according to the position of the opening parenthesis. The leftmost parenthesis is assigned the number one. The number zero is associated with the entire match.

A backslash followed by a digit refers back to the sub-string captured by the correspondingly numbered parenthesis. “\s+((\w+)\s+\2\)\s+” matches a pair of identical words separated by white space. Capture 1 describes the pair of words and white space while capture 2 describes the first word.

A question mark immediately following a left parenthesis modifies the meaning of the rest of the enclosed text in various ways. When followed by a question mark followed by a colon, a left parenthesis becomes non-capturing.

The regular expressions described above all match one or more characters, at least potentially. The regular expression notation also provides so-called assertions, which never consume characters during the matching process; they succeed or fail depending on the current match position and the characters around it. The circumflex (APL’s AND primitive) succeeds only at the beginning of the subject; the dollar sign succeeds only at the end. These are used to anchor a pattern at the ends. “^\d+$” matches only strings consisting entirely of digits. “\D\d{5}$” matches only strings ending with exactly five digits. Note that some complexities involving new-line characters has been skipped.

The assertion “\b” matches only at word boundaries, i.e. positions preceeded by a non-word character and followed by a word character or vice-versa. Neither character is consumed in the match. The assertion “\B” matches only at positions that are not word boundaries. So when “(.*)\b(\w+)” is matched to “one two three”, the first capture is “one two” and the second it “three”.

A Few Examples¶

The regex “any ((T[io]m){1,3}|Di[cr]k|[HBL]arry)” matches “any Tom”, “any Tim”, “any Dick”, “any Dirk”, “any TomTom”, “any TomTim”, and “any Barry”.

“\d\d\d-\d\d-\d\d\d\d” matches a social security number.

The regex “((\(\d\d\d\))|(\d\d\d[\-\.]))?\d\d\d[\-\.]\d\d\d\d” matches telephone numbers in several styles: “555-1212”, “555.1212”, “(301)208-7217”, and “301.208.7217”. It also matches “301-208.7217”. This can be corrected by using a back reference and conditional sub-pattern as in the regex:

"^(\(\d\d\d\)|\d\d\d([\-\.]))?\d\d\d((?(2)\2|[\-.]))\d\d\d\d$"

The PCRE Library¶

The library is open-source software written by Philip Hazel of the University of Cambridge Computing Service, Copyright ©1997-2001 University of Cambridge.

Its author describes the Perl Compatible Regular Expression Library as a set of functions that implement regular expression pattern matching using the same syntax and semantics as Perl, with just a few differences. The current implementation of PCRE (release 4.x) corresponds approximately with Perl 5.8.

Its short and simple PCRE license is easily observed. Many open source software projects use the library and it is included in several Linux distributions.

The APL_PCRE DLL¶

This pre-built DLL contains the PCRE library functions and extra routines needed when using the library from APL.

The library has two central functions: pcre_compile() and pcre_exec().

Essentially, pcre_compile() accepts a regular expression string and returns a pointer to an opaque structure known as a pcre, which contains a compiled representation of the regex and tables needed for matching. A pcre is contained in storage managed by Windows and must be de-allocated when it is no longer needed. Several ancillary arguments communicate matching options and error codes.

The pcre_exec() function takes a pcre, a subject string, and a pointer to space to store the results of matching the regex to the string. These results are offsets into the string of the beginnings and ends of the matching and captured sub-strings. Additional arguments communicate an offset into the string where matching is to begin, matching options, as well as a pointer to an optional block used for certain esoteric purposes.

One extra-library routine, pcre_dispose(), frees a pcre’s storage into the storage pool used by the library. Any subsequent use of the pointer is likely to initiate a hard crash or data corruption. Failure to free a pcre will leak a small amount of storage. This is benign unless the small leak is repeated many times.

These functions are called via ⎕WCALL. The active aplw.ini file must contain the quad-wcall definitions for the pcre_...() functions and constants.

The following steps summarize the direct use of the DLL’s functions to match a regular expression and a subject string. A family of APL functions encapsulates much of this detail, making PCRE much easier to use than this outline implies.

1. Create an APL character vector containing the regular expression. This can be a quoted string or the result of other APL code.
2. Prepare a character vector containing the names of such PCRE options as may be needed.
3. Initialize three APL one item numeric vectors for the errptr and erroffset output arguments.
4. Using QUAD-WCALL, invoke pcre_compile() passing the regular expression vector, the options vector, the errptr variable, the erroffset variable, and a numeric zero for the tableptr argument. Capture the result of the call. This will be a three item numeric variable. The first item will be a pcre pointer or zero. If the first item is zero, the compilation failed. The other two result items contain the address of an error message (inside the DLL) and an offset into the regular expression related to the error. Use W_Mem to retrieve the text of the message.
5. Analyze the results of step 4. If it failed, using the error text and offset, figure out what went wrong and return to step 1. If it succeeded go on to step 6.
6. Obtain or construct an APL character vector containing the subject string.
7. Prepare a numeric vector to receive the starting and ending offsets of the matching substrings. PCRE uses the last third of this vector internally so it length should be more than three times the maximum expected number of matching and captured sub-strings. The length must be a multiple of three. PCRE refers to this as ovector.
8. Prepare an APL character vector containing the names of any required matching options. If no options are needed, pass a numeric zero instead
9. Using QUAD-WCALL, invoke pcre_exec() passing the pcre pointer, an integer zero, the subject vector, its length, an integer starting offset, the option vector or zero, the ovector, and the length of the ovector. Capture the result of the call. It should be a two item vector. The second item is the modified ovector. The first item is an integer return code. If the match succeeds, the return code will be 1 or greater and is the number of pairs of meaningful ovector items. If the call fails the return code is negative. A –1 indicates that the subject string didn’t match the pattern. Other negative numbers indicate serious errors. Consult the PCRE documents for their meaning.
10. If the match in step 9 succeeds continue with step 11. If the match fails take whatever action is appropriate for your application then continue at step 13.
11. It is convenient to reshape the meaningful leading elements of ovector into a two-column matrix. The first column contains starting offsets of matching or captured sub-strings of the subject. The second column contains their ending offsets. Offsets can be interpreted as zero origin indices of the first character and the character after the last character of a sub-string. Unused captures have offsets of –1. The first row, row zero in origin 0, describes the entire matching sub-string. Subsequent rows describe captured sub-strings in order. Their zero origin index is the same as their back-reference number. Row 1 corresponds to the string captured in Perl’s $1 variable, Row 2 to $2, and so forth.
12. Use the results of the match as appropriate for your application.
13. Repeat from step 6 to reapply the regular expression to a different subject string or with a different offset. Otherwise continue to step 14.
14. This step releases the pcre’s storage for reuse. Using QUAD-WCALL, invoke pcre_dispose() passing the pcre pointer as the sole argument. No result is returned. This pcre pointer must not be used again. Doing so will crash the interpreter or induce data corruption.

The APL_PCRE Workspace¶

Functions for Pattern Matching¶

These functions encapsulate the complexity of direct calls to the PCRE library. Functions that directly call the library are described first, followed by functions that work with the result of a match. These are followed by simple compositions of the earlier functions. The last function displays the result of matching a regex to a string for experimentation and debugging.

pcre <- Compile regex options

regex should be a character vector representing a regular expression

options may be a character vector of the single letter option codes or a number. At least a zero or an empty string must be present.

pcre will be an integer containing a pointer to a pcre in the library’s memory pool.

Syntactic errors in the regular expression are signalled as APL errors including PCRE’s description and offset.

position_matrix <- pcre offset Match subject

pcre must be a pcre pointer.

offset is the offset into the subject where matching should begin. If not present, matching starts at the beginning, which is equivalent to specifying zero.

subject should be a character vector of text to be matched.

position_matrix will be a two-column matrix with one row for each matching or captured sub-string of the subject. If the match fails, the matrix will have zero rows. The first column contains starting offsets into the subject string; the second contains ending offsets.

The regular expression is matched against the subject string beginning at the offset specified. An APL error is signaled if the library returns an error other than a failing match.

position_matrix_vector <- pcre offset MatchMultiple subject

pcre must be a pcre pointer.

offset is the offset into the subject where matching should begin. If not present, matching starts at the beginning, which is equivalent to specifying zero.

subject should be a character vector of text to be matched.

position_matrix_vector will be a vector of two-column matrices as returned by Match.

The regular expression is repeatedly matched against the subject string until matching fails. The first match begins at the offset specified. Subsequent match begins at the end of the previous match. The result contains a position matrix for each successful match. An APL error is signaled if the library returns an error other than a failing match.

Dispose pcre

pcre must be a pcre pointer returned from the PCRE library.

The pcre is freed into the storage pool used by the library. Dispose should be called exactly once for each pcre created by PCRE.

vector_of_strings <- position_matrix SplitCaptures subject_string

positon_matrix must be a matrix as returned by Match

subject_string is the subject character vector from the match

vector_of_strings will be a vector containing the sub-strings described by the position matrix.

An empty vector is returned for a zero-row position matrix.

vector_of_strings <- pcre MatchAndCapture subject

pcre must be a pcre pointer.

subject should be a character vector of text to be matched.

vector_of_strings will be a vector containing the sub-strings matched or captured

The regular expression is matched against subject to return a vector of matched and captured sub-strings. This is a simple composition of Match and SplitCaptures.

vector_of_strings <- regex options C_M_C subject

regex should be a character vector representing a regular expression

options may be a character vector of the single letter option codes or a number. At least a zero or an empty string must be present.

subject should be a character vector of text to be matched.

vector_of_strings will be a vector containing the sub-strings matched or captured.

The regular expression is compiled and matched against the subject. A vector of matched and captured sub-strings. The pcre is disposed of internally. This is a convenient composition of Compile and MatchAndCapture.

boolean_scalar <- pcre DoesMatch subject

pcre must be a pcre pointer.

subject should be a character vector of text to be matched.

boolean_scalar will be 1 if the regular expression matches the subject and 0 if it does not.

The regular expression is matched against subject to return a vector of matched and captured sub-strings. Most of the work is done by Match.

result <- regex options DemoRegex subject

regex should be a character vector representing a regular expression

options may be a character vector of the single letter option codes or a number. At least a zero or an empty string must be present.

subject should be a character vector of text to be matched.

result is a character matrix.

The regular expression is compiled and matched against the subject. The subject and match results are formatted for display. The subject is on the top line. The capture matrix is at the right of the remaining lines. Digits mark the positions matched or captured. If the match fails, there is only one line.

      '^ \s* (\w*) \s* (\d*)f \s* $' 'xi' DemoRegex '  Princeton 72F  '
  Princeton 72F
00000000000000000  0 17
..111111111......  2 11
............22... 12 14

      '^ \s* (\w*) \s* (\d*)([fc]) \s* $' 'xi' DemoRegex 'Bethesda 20c'
Bethesda 20c
000000000000  0 12
11111111....  0  8
.........22.  9 11
...........3 11 12

      '^ \s* (\w*) \s* (\d*)([fc]) \s* $' 'xi' DemoRegex 'Erehwon 20R'
'Erehwon 20R'

Functions for Replacing Sub-strings¶

These functions interpolate captured sub-strings into a template. A template is a character vector. Within a template, most characters stand for themselves. A few meta-characters are used to specify points of substitution. [ While only one is currently in use, several more are envisioned. ]

Interpolation replaces a dollar-sign followed by a digit, n, with the nth matched or captured sub-string. The sub-strings can be interpolated multiple times and in any order.

string <- template InterpolateCaptures vector_of_strings

template is a character vector.

vector_of_strings is a vector of character vectors.

string will be a character vector.

The result is a copy of the template with the $-digit meta-sequences replaced by the corresponding item of vector_of_strings. $’s not followed by a digit are not changed.

  $2 is 1st then $1. $0 else comes last' InterpolateCaptures 'all' 'one' 'two'
two is 1st then one. all else comes last

string <- pcre template MatchAndReplace subject_string

pcre is a pcre pointer.

template is a character vector.

subject_string is a character vector.

string will be a character vector.

The regular expression is matched with the subject. The matched and captured sub-strings of the subject are interpolated into the template. The result is a copy of the subject-string with the interpolated template replacing the segment that matched.

string <- pcre template ReplaceAll subject_string

pcre is a pcre pointer.

template is a character vector.

subject_string is a character vector.

string will be a character vector.

All matches are found for the regex in the subject. Copies of the template are interpolated with the captured sub-strings for each match. The result is a copy of the subject-string with the interpolated templates replacing the matching segments. Since all matching and computation of replacement positions is done before any replacement, there is no risk of replacements being made in replacement text.

More Information¶

The documentation contained in the PCRE Library distribution is the primary reference for the regular expression engine.

Jeffrey E. F. Friedl. Mastering Regular Expressions. Second Edition. O’Reilly. 2002 Almost everything one would ever want to know about the use of regular expressions.

Larry Wall, Tom Christiansen & Jon Orwant. Programming Perl. 3^rd Edition. O’Reilly. 2000. Affectionately known as the camel book, this is the standard reference for Larry Wall’s Perl language. The sections on regular expressions explain the extensions from the viewpoint of their inventor.

There are many books on regular expressions and the languages and tools that use them. Those oriented to programmers working in your application domain may be helpful. Try not to be confused by examples in different regex dialects.

Try a Google search on “regular expression tutorial”. This will locate Web tutorials intended for all levels and kinds of users. Those oriented to users of the Perl, Python, or Ruby languages may be most relevant.

Distribution Software¶

The conference digital material contains a directory that includes the following files( “xx” will be replaced by a version identifier ):

Readme.txt

Late news, installation instructions, etc.

APL_PCRE_xx.dll

A DLL containing the PCRE regular expression library and support functions for its use from APL. The DLL is most conveniently installed in the same directory as aplw.exe

APL_PCRE_xx.w3

This workspace contains cover functions for use with the DLL, a simple set of testing tools, and a set of test functions to exercise and validate the installation. The test function’s names begin with “t_” followed by an integer followed by the test’s subject. These functions are safely executable. Most produce no output unless something fails, in which case an error will be signaled. The niladic function F12 runs all the tests. The dyadic function AEM uses the APL match primitive to compare its arguments, signaling an error if they differ. The test functions use AEM extensively to compare expected to actual results. The tests are intended to be useful as examples.

APL_PCRE_xx.ini

This file contains QUAD-WCALL definitions for the DLL’s functions and constants. The definitions should be copied into your aplw.ini file.

Pcre-4.3.tar.gz

This is an unmodified copy of the PCRE distribution. It can be uncompressed and opened with WinZip. The top-level directory contains source code for the PCRE library and several text files without suffixes. You should review the AUTHORS, COPYING, LICENSE, NEWS, and README files. The doc subdirectory contains PCRE documentation in several formats. pcre.txt is a plain text version. The version in the html directory can be opened with a web browser. Begin with index.html; it links to the other files. You should arrange ready access to this primary reference documentation.

APL_PCRE_xx.zip

This contains APL2000 written source code and MSVC project files needed to rebuild or modify the DLL.

Apl_Regex_xx.doc

This document, possibly corrected, extended, or updated.

Regular Expression Reference¶

Meta-Characters

Pre-defined Character Classes

Character Classes Defined Within Square Brackets

Simple Assertions

Assertion Sub-patterns

Conditional Sub-patterns

Conditional Sub-patterns Conditions

Quantifiers

Compile and Execution Time Options

The names in the first column are PCRE’s names for bit definitions used with the pcre functions. They have QUAD-WCALL definitions in the *.INI file.

The letters in the second column can be used in the option argument to the APL Compile function. They correspond to PERL’s pattern modifier characters.

The third column indicates whether the option works at compile or execution time.

The last column briefly describes the effect of specifying the option. Consult the documentation for a more complete explanation. The options with letters in the second column are the most generally useful. The others control PCRE extensions, esoteric features, or specialized uses.