Diff for "RegularExpression"

Regular expressions (RE) are a computer science construct, used to determine whether a string matches some sort of pattern. There are countless variations, including both syntactic and semantic changes. Let's start with the theory.

A regular expression consists of three features:

1. Concatenation. Two regular expressions may be written next to each other. The resulting large expression will match the input string if and only if a part of the input that matches the first small expression is immediately followed by a part that matches the second small expression.

2. Union. This is basically an "or" operation. The large expression will match the input if either of the small expressions matches the input.

3. Closure. Also called "Kleene closure" (prounced "KLEE-nee"). The small expression may be "repeated" zero or more times in order to match the input.

(I'm not using precise mathematical language here. If you need formal definitions, please consult a computer science textbook instead.)

The syntax by which these features are expressed varies widely across different RE implementations. We'll start with the syntax used by the Unix command egrep, because it's probably the most common. Here are some examples of the three required features, using this syntax:

• Concatenation. RE ab matches an input string of ab.

• Union. RE a|b matches an input string of a or an input string of b. It does not match ab.

• Closure. RE a* matches the empty string, or an input string of a, or an input string of aa, etc.

Obviously, in order to have any practical use, these features must be combined together.

• RE f(oo|ee)t matches foot or feet. (The parentheses introduce a feature known as grouping.)

• RE a(0|1|2|3|4|5|6|7|8|9) matches a0 or a1 or ... or a9.

Most RE implementations have shortcuts to greatly reduce the length and ugliness of common expressions. For example, in egrep, our previous example could be written:

• RE a[0-9] matches a0 or a1 or ... or a9.

The [...] syntax is called a character class or a bracket expression, and specifies an implicit union operation. The resulting expression matches any single character that falls within the specified range. However, this relies on the ordering of characters. In the case of digits, there's not much danger; but in the case of letters of the alphabet, ASCII ordering cannot be safely assumed. Therefore, modern implementations of egrep provide class names instead:

• RE a[[:digit:]] matches a0 or a1 or ... or a9.

• RE [[:alpha:]]0 matches a0 or B0 or ....

Never try to use a range of letters in a bracket expression like [A-Z] or [a-z] unless you're operating in the C locale. Use [[:upper:]] or [[:lower:]] or [[:alpha:]] instead.

The character class [[:space:]] is particularly useful: it matches any character which is displayed as whitespace (spaces, tabs, carriage returns, etc.).

Now the bad news: there are a plethora of incompatible regular expression syntaxes and feature sets in common use. It's nearly impossible to determine what a given RE means without knowing which tool is supposed to use it. Let's take a look at some of the common ones.

• Basic Regular Expressions (BRE). This is the syntax used by the Unix commands grep and sed. In BRE syntax, all characters are literal except ., [, \, *, ^ and $. There is no union operator (apart from bracket expressions matching a single character); however, grouping is supported with \( and \).

  • BRE . matches any single character.

  • BRE [fog] matches f or o or g.

  • BRE a* matches the empty string, or a, or aa, or aaa, etc.

  • CONTRARY TO POPULAR BELIEF, you may NOT use \ in front of ERE operators such as | to make them work in a BRE. Doing this is a GNU EXTENSION only available in certain GNU programs such as GNU sed and GNU grep.

  • However, \{m,n\} syntax is supported in BRE, and means the same as {m,n} does in ERE. This is probably where GNU got the inspiration to extend this notation to the | operator.

• Extended Regular Expressions (ERE). This is the syntax used by awk and egrep (or grep -E), as well as by Bash's [[ ... =~ ... ]] operator. Even some versions of sed can handle these -- mainly GNU sed (with -r or -E) and BSD sed (with -E).

  • ERE a+ matches a or aa or .... It does not match the empty string. In other words, the + means "one or more".

  • ERE ab? is equivalent to regular expression a(b|). It matches a or ab. In other words, the ? means "optionally once".

  • ERE a{3} is equivalent to regular expression aaa. It matches aaa only. In other words, "exactly three times".

  • ERE a{3,} is equivalent to regular expression aaaa*. It matches aaa or aaaa or any longer sequence of as. In other words, "three or more times".

  • ERE a{,3} is equivalent to regular expression |a|aa|aaa. It matches the empty string or a or aa or aaa. In other words, "up to three times".

  • ERE a{3,5} is equivalent to regular expression aaa|aaaa|aaaaa. In other words, "between three and five times".

• Perl-Compatible Regular Expressions (PCRE).

• Tcl's Advanced Regular Expressions (ARE).

• Extended globs ("extglob") qualify as regular expressions; they have closure, union and grouping operators. The syntax is different from that of EREs -- extended globs use a prefix notation (where the operator appears before its operands), rather than postfix like EREs.

  • Extglob @(foo|bar) matches either foo or bar. (Union.)

  • Extglob *(foo) matches 0 or more instances of foo. (Closure.)

  • Extglob ?(foo) matches 0 or 1 instance of foo. (Like the ? operator in ERE.)

In most implementations, regular expressions are not anchored by default. This means the expression can match any part of the input string, rather than the entire input string. Thus, the BRE abc used in grep (for example) would match the input string abcdefg. If you want grep to act differently, you must specify whether your expressions are anchored at the start of a line, at the end of a line, or both:

• grep '^abc' matches an input line of abcde but not 42abc or 42abcde. The ^ at the start of a BRE or ERE causes the expression to be anchored at the start of a line.

• grep 'xyz$' matches an input line of tuvwxyz but not xyzzy. The $ at the end of a BRE or ERE anchors the expression at the end of a line.

• grep '^abc$' matches an input line of abc only. The expression is anchored at both the start and end of a line.

External Resources

Regular Expressions Tutorial