Regular Expressions

Regular Expressions
(last updated: Jul 26, 2009) — print

This document describes the syntax of so-called Perl compatible regular expressions which enhance the POSIX-extended variety used in other software programs.

A regular expression is a string representing a pattern used for matching some portion(s) of a target string. Regular expressions are very general and as a consequence, very complex with many different types of operations represented as special characters, or meta-characters.

Regular expression atoms

Regular expression syntax is usually described in a grammatical form, but we'll describe it more loosely from bottom up, the way you would created one. At the bottom are the basic components, called atoms. Here is a a non-exhaustive list:

Single characters. A single character with no special significance represents that character in the target string. The characters with special significance (i.e. operator characters) are these:
```
^ . [ $ ( ) | * + ? { \
```
A non-alphanumeric character acts as the literal character (whether special or not) by escaping it, namely, adding \ in front of it.
Wild card. The . (period) special character matches any single character except \n (newline).
Bracket Expressions. A bracket expression represents a character set via a list of characters enclosed by the square brackets: '[' and ']'. It normally matches the target string with any single character from the list.
If the character list begins with '^', it matches any single character not from the rest of the list.
If two characters in the list are separated by '–', this is shorthand for the (inclusive) range of characters between those two. It is illegal for two ranges to share an endpoint, e.g. a-c-e. Ranges are collating-sequence dependent and should be avoided for portability.
Most special characters lose their special status and become literals within brackets. Additionally,
- – is literal at the end or beginning of a bracket expression
- ^ is literal if not at the beginning of a bracket expression
The backslash character, \, retains its meaning in bracket expressions, permitting the usage of the special escape sequences: such as \n, \t, \w, \d, etc.
Control characters. A backslash, \, followed by one of the characters a, b, f, n, r, t, v represents the ANSI-C interpretation of the control character
Escape character sets. These are special sequences representing commonly used character sets:
- \w is word (program identifier) character: [A-Za-z0-9_]
- \W is non-word character: [^A-Za-z0-9_]
- \s is a whitespace character: [ \f\n\r\t]
- \S is a non-whitespace character: [^ \f\n\r\t]
- \d is a digit character: [0-9]
- \D is a non-digit character: [^0-9]
Anchors. These are special sequences which match an empty substring:
- ^ matches at the beginning of the target string
- $ matches at the end of the target string
- \b matches on a word boundary, i.e., the previous or subsequent character is not a word character
Recursive expansion. Any regular expression surrounded by parentheses is an atom:
```
( regular_expression )
```

Quantifiers

Regular expressions use quantifiers to generate unbounded matching possibilities and other matching amount specifications. An atom can optionally be followed by one of these quantifiers:

* representing 0 or more occurrences of the atom,
+ representing 1 or more occurrence of the atom,
? representing 0 or 1 occurrences of the atom,
the bound {n} representing exactly n occurrences of the atom,
the bound {m,n} representing between m and n occurrences of the atom.

The quantifier can optionally be followed by "?" indicating that the match be minimal (non-greedy, reluctant) as opposed to the default maximal (greedy) match.

Full regular expressions

An atom optionally followed by a quantifier is called a piece.

The juxtaposition (concatenation) of pieces is called a branch. A target string matches a branch if some substring combination matches each corresponding piece.

A regular expression is a choice of branches represented by a string where the branches are separated by the | character. A choice is matched if one or more of the branches match.

For example, these are atoms:

a     b     [abc]     (a|b+c)   [^bc]

these, in addition to all above, are pieces:

a*    c+    (ca*b)*   (a|b+c){3}

these, in addition to all above, are branches:

aba   a*b*  [ab]*c*   (a|b+c){3,10}(b|a+c){4}

these, in addition to all above, are regular expressions:

a*b|ab*     a|b+|c*   ((ab|ba){3,10}[cd]|aa*bc)+

Regular Expression usage

Regular expressions are used commonly in programming contexts for these four types of operations:

validate: determine if a string matches a pattern, giving a boolean (yes/no) result
extract: extract portion(s) of a string which match a pattern
substitute: substitute portion(s) of a string which match a pattern by a replacement string
split: remove portions which match a pattern, thereby obtaining a list list of strings

Validation Examples

When regular expression patterns are used in practice, they match a string if some portion of the string matches the pattern. In order to require that the entire string matches the pattern, it is common to use the ^ and $ anchors.

pattern	description
`.\|\n`	matches any character
`[a-zA-Z]`	matches any letter
`[a-z]{4}`	matches a lower-case four-letter word
`[^^-]`	matches any character except `^` or `-`
`^[a-zA-Z]+$`	is a word of letters
`^[a-zA-Z_]\w*$`	is a Java identifier
`^[\d.]+$`	is a string of digits or dots
`^\s*$`	is whitespace sequence or empty
`^\s+\|\s+$`	is a leading or terminating whitespace sequence
`^(I\|you\|them)$`	is one of these three words
`^\S+$`	is a non-whitespace sequence
`^[+-]?([1-9]\d*)?\d$`	is a signed integer (no leading zeros)
`^[+-]?\d*\.\d{1,6}$`	is a signed 1-6 place decimal number
`^([1-9]\d*)?\d(\.\d{2})?$`	is an unsigned decimal number with or without 2-place decimal

Extracting Matched Portions

The parentheses are used in regular expression patterns to identify exactly which portions of the string match which portions of the pattern. For example, given:

string: abbabccd
reg.expr. pattern: ((a(b+))+)(c*)

The matched portions of the string are taken by the order of left parentheses, and so we would get:

abbab, ab, b, cc

The fact that the (a(b+)) repeated pattern matches both the abb and ab substrings is cause for confusion, but the last match is taken as the matching string.

Minimal match

The greedy and minimal (non-greedy) quantifiers differ only in terms of extraction of the matched portion. For example, consider the string AABBBB matched against these two patterns:

^(\w+)(B+)$          (greedy)
^(\w+?)(B+)$         (minimal)

In the former case, \w+ would match AABBB leaving a single B to match B+. In the latter case \w+ would minimally match only AA, leaving BBBB to match B+.