Regular Expression
In computing, a regular expression is a specific pattern that provides concise and flexible means to “match” (specify and recognize) strings of text, such as particular characters, words, or patterns of characters. Common abbreviations for “regular expression” include regex and regexp.
Basic Concepts
A regular expression, often called a pattern, is an expression that specifies a set of strings. To specify such sets of strings, rules are often more concise than lists of a set’s members. For example, the set containing the three strings “Handel”, “Händel”, and “Haendel” can be specified by the pattern H(ä|ae?)ndel (or alternatively, it is said that the pattern matches each of the three strings). In most formalisms, if there exists at least one regex that matches a particular set then there exist an infinite number of such expressions. Most formalisms provide the following operations to construct regular expressions.
Boolean “or”
A vertical bar separates alternatives. For example, gray|grey can match “gray” or “grey”.
Quantification
A quantifier after a token (such as a character) or group specifies how often that preceding element is allowed to occur. The most common quantifiers are the question mark ?, the asterisk * (derived from the Kleene star), and the plus sign + (Kleene cross).
- ? The question mark indicates there is zero or one of the preceding element. For example, colou?r matches both “color” and “colour”.
- * The asterisk indicates there is zero or more of the preceding element. For example, ab*c matches “ac”, “abc”, “abbc”, “abbbc”, and so on.
- + The plus sign indicates there is one or more of the preceding element. For example, ab+c matches “abc”, “abbc”, “abbbc”, and so on, but not “ac”.
Grouping
Parentheses are used to define the scope and precedence of the operators (among other uses). For example, gray|grey and gr(a|e)y are equivalent patterns which both describe the set of “gray” or “grey”.
Formal Language Theory
Regular expressions describe regular languages in formal language theory. They have the same expressive power as regular grammars.
Formal Definition
Regular expressions consist of constants and operator symbols that denote sets of strings and operations over these sets, respectively. The following definition is standard, and found as such in most textbooks on formal language theory. Given a finite alphabet Σ, the following constants are defined as regular expressions:
- (empty set) ∅ denoting the set ∅.
- (empty string) ε denoting the set containing only the “empty” string, which has no characters at all.
- (literal character)
ain Σ denoting the set containing only the character a.
Given regular expressions R and S, the following operations over them are defined to produce regular expressions:
- (concatenation) RS denoting the set { αβ | α in set described by expression R and β in set described by S }. For example {“ab”, “c”}{“d”, “ef”} = {“abd”, “abef”, “cd”, “cef”}.
- (alternation) R | S denoting the set union of sets described by R and S. For example, if R describes {“ab”, “c”} and S describes {“ab”, “d”, “ef”}, expression R | _S_describes {“ab”, “c”, “d”, “ef”}.
- (Kleene star) R* denoting the smallest superset of set described by R that contains ε and is closed under string concatenation. This is the set of all strings that can be made by concatenating any finite number (including zero) of strings from set described by R. For example, {“0”,“1”}* is the set of all finite binary strings(including the empty string), and {“ab”, “c”}* = {ε, “ab”, “c”, “abab”, “abc”, “cab”, “cc”, “ababab”, “abcab”, … }.
To avoid parentheses it is assumed that the Kleene star has the highest priority, then concatenation and then alternation. If there is no ambiguity then parentheses may be omitted. For example, (ab)c can be written as abc, and a|(b(c*)) can be written as a|bc*. Many textbooks use the symbols ∪, +, or ∨ for alternation instead of the vertical bar.
Examples:
a|b*denotes {ε, “a”, “b”, “bb”, “bbb”, …}(a|b)*denotes the set of all strings with no symbols other than “a” and “b”, including the empty string: {ε, “a”, “b”, “aa”, “ab”, “ba”, “bb”, “aaa”, …}ab*(c|ε)denotes the set of strings starting with “a”, then zero or more “b"s and finally optionally a “c”: {“a”, “ac”, “ab”, “abc”, “abb”, “abbc”, …}
Expressive power and compactness
The formal definition of regular expressions is purposely parsimonious and avoids defining the redundant quantifiers ? and +, which can be expressed as follows: a+ = aa*, and a? = (a|ε). Sometimes the complement operator is added, to give a generalized regular expression; here Rc matches all strings over Σ* that do not match R. In principle, the complement operator is redundant, as it can always be circumscribed by using the other operators. However, the process for computing such a representation is complex, and the result may require expressions of a size that is double exponentially larger.
Regular expressions in this sense can express the regular languages, exactly the class of languages accepted by deterministic finite automata. There is, however, a significant difference in compactness. Some classes of regular languages can only be described by deterministic finite automata whose size grows exponentially in the size of the shortest equivalent regular expressions. The standard example here is the languages Lk consisting of all strings over the alphabet {a,b} whose kth-from-last letter equals a. On one hand, a regular expression describing L4 is given by (a | b)_*_a( a | b )( a | b )( a | b ).
On the other hand, it is known that every deterministic finite automaton accepting the language Lk must have at least 2k states. Luckily, there is a simple mapping from regular expressions to the more general nondeterministic finite automata (NFAs) that does not lead to such a blowup in size; for this reason NFAs are often used as alternative representations of regular languages. NFAs are a simple variation of the type-3 grammars of the Chomsky hierarchy.
Finally, it is worth noting that many real-world “regular expression” engines implement features that cannot be described by the regular expressions in the sense of formal language theory; see below for more on this.
Deciding equivalence of regular expressions
As seen in many of the examples above, there is more than one way to construct a regular expression to achieve the same results.
It is possible to write an algorithm which for two given regular expressions decides whether the described languages are essentially equal, reduces each expression to a minimal deterministic finite state machine, and determines whether they are isomorphic (equivalent).
The redundancy can be eliminated by using Kleene star and set union to find an interesting subset of regular expressions that is still fully expressive, but perhaps their use can be restricted. This is a surprisingly difficult problem. As simple as the regular expressions are, there is no method to systematically rewrite them to some normal form. The lack of axiom in the past led to the star height problem. In 1991, Dexter Kozen axiomatized regular expressions with Kleene algebra.
Regular expressions come in various styles. The table below provides a comprehensive list of metacharacters and their behaviors in the context of regular expressions:
| Character | Description |
|---|---|
| ^ | Matches the beginning of the input string. If the Multiline property of the RegExp object is set, ^ also matches the position right after a “\n” or “\r”. |
| $ | Matches the end of the input string. If the Multiline property of the RegExp object is set, $ also matches the position right before a “\n” or “\r”. |
| * | Matches the preceding subexpression zero or more times. For example, zo* matches “z” as well as “zoo”. * is equivalent to {0,}. |
| + | Matches the preceding subexpression one or more times. For example, zo+ matches “zo” and “zoo”, but not “z”. + is equivalent to {1,}. |
| ? | Matches the preceding subexpression zero or one time. For example, do(es)? matches “do” or the “do” in “does”. ? is equivalent to {0,1}. |
| {n} | n is a non-negative integer. Matches exactly n times. For example, o{2} does not match the “o” in “Bob”, but matches both o’s in “food”. |
| {n,} | n is a non-negative integer. Matches at least n times. For example, o{2,} does not match the “o” in “Bob”, but matches every o in “foooood”. o{1,} is equivalent to o+, and o{0,} is equivalent to o*. |
| {n,m} | m and n are non-negative integers where n <= m. Matches at least n and at most m times. For example, o{1,3} matches the first three o’s in “fooooood”. o{0,1} is equivalent to o?. Note that there cannot be a space between the comma and the numbers. |
| ? | When this character immediately follows any of the other quantifiers (*, +, ?, {n}, {n,}, {n,m}), the match becomes non-greedy (lazy). A non-greedy match matches as little of the searched string as possible, whereas the default greedy match matches as much as possible. For example, in the string “oooo”, o+? matches a single “o”, while o+ matches all four. |
| . | Matches any single character except “\n”. To match any character including “\n”, use a pattern such as “(.|\n)”. |
| (pattern) | Matches pattern and captures the match. The captured match can be retrieved from the resulting Matches collection, using the SubMatches collection in VBScript, or the $0…$9 properties in JScript. To match the parenthesis characters themselves, use “\(" or "\)”. |
| (?:pattern) | Matches pattern but does not capture the result; that is, it is a non-capturing match that is not stored for later use. This is useful when combining parts of a pattern with the “or” operator “(|)”. For example, “industr(?:y|ies)” is a more economical expression than “industry|industries”. |
| (?=pattern) | Positive lookahead. Matches the search string at any point where a string matching pattern begins. This is a non-capturing match; it does not need to be captured for later use. For example, “Windows(?=95|98|NT|2000)” matches the “Windows” in “Windows2000” but not the “Windows” in “Windows3.1”. A lookahead consumes no characters: after a match, the search for the next match begins immediately after the last match, not after the characters making up the lookahead. |
| (?!pattern) | Negative lookahead. Matches the search string at any point where a string not matching pattern begins. This is a non-capturing match; it does not need to be captured for later use. For example, “Windows(?!95|98|NT|2000)” matches the “Windows” in “Windows3.1” but not the “Windows” in “Windows2000”. A lookahead consumes no characters: after a match, the search for the next match begins immediately after the last match, not after the characters making up the lookahead. |
| (?<=pattern) | Positive lookbehind. Similar to positive lookahead, but in the opposite direction. For example, “(?<=95|98|NT|2000)Windows” matches the “Windows” in “2000Windows” but not the “Windows” in “3.1Windows”. |
| (?<!pattern) | Negative lookbehind. Similar to negative lookahead, but in the opposite direction. For example, “(?<!95|98|NT|2000)Windows” matches the “Windows” in “3.1Windows” but not the “Windows” in “2000Windows”. |
| x|y | Matches either x or y. For example, “z|food” matches “z” or “food”, and “(z|f)ood” matches “zood” or “food”. |
| [xyz] | A character set. Matches any one of the enclosed characters. For example, “[abc]” matches the “a” in “plain”. |
| [^xyz] | A negated character set. Matches any character not enclosed. For example, “[^abc]” matches the “p” in “plain”. |
| [a-z] | A range of characters. Matches any character in the specified range. For example, “[a-z]” matches any lowercase letter from “a” to “z”. |
| [^a-z] | A negated character range. Matches any character not in the specified range. For example, “[^a-z]” matches any character outside the range “a” to “z”. |
| \b | Matches a word boundary, that is, the position between a word and a space. For example, “er\b” matches the “er” in “never” but not the “er” in “verb”. |
| \B | Matches a non-word boundary. For example, “er\B” matches the “er” in “verb” but not the “er” in “never”. |
| \cx | Matches the control character indicated by x. For example, \cM matches a Control-M or carriage return. The value of x must be one of A-Z or a-z; otherwise, c is treated as a literal “c”. |
| \d | Matches a digit character. Equivalent to [0-9]. |
| \D | Matches a non-digit character. Equivalent to [^0-9]. |
| \f | Matches a form feed character. Equivalent to \x0c and \cL. |
| \n | Matches a newline character. Equivalent to \x0a and \cJ. |
| \r | Matches a carriage return character. Equivalent to \x0d and \cM. |
| \s | Matches any whitespace character, including spaces, tabs, form feeds, and so on. Equivalent to [ \f\n\r\t\v]. |
| \S | Matches any non-whitespace character. Equivalent to [^ \f\n\r\t\v]. |
| \t | Matches a tab character. Equivalent to \x09 and \cI. |
| \v | Matches a vertical tab character. Equivalent to \x0b and \cK. |
| \w | Matches any word character, including the underscore. Equivalent to “[A-Za-z0-9_]”. |
| \W | Matches any non-word character. Equivalent to “[^A-Za-z0-9_]”. |
| \xn | Matches n, where n is a hexadecimal escape value. Hexadecimal escape values must be exactly two digits long. For example, “\x41” matches “A”, while “\x041” is equivalent to “\x04” followed by “1”. ASCII codes can be used in regular expressions. |
| \num | Matches num, where num is a positive integer referring to a captured match. For example, “(.)\1” matches two consecutive identical characters. |
| \n | Identifies either an octal escape value or a backreference. If at least n captured subexpressions precede it, \n is a backreference. Otherwise, if n is an octal digit (0-7), \n is an octal escape value. |
| \nm | Identifies either an octal escape value or a backreference. If at least nm captured subexpressions precede it, \nm is a backreference. If at least n captures precede it, \n is a backreference followed by a literal “m”. If neither condition is met, and n and m are both octal digits (0-7), \nm matches the octal escape value nm. |
| \nml | If n is an octal digit (0-3) and m and l are both octal digits (0-7), matches the octal escape value nml. |
| \un | Matches n, where n is a Unicode character represented by four hexadecimal digits. For example, “\u00A9” matches the copyright symbol (©). |
The Disqus comment system is loading ...
If the message does not appear, please check your Disqus configuration.