Regular expressions

In computing, a regular expression is a string that is used to describe or match a set of strings, according to certain syntax rules. A regular expression is simply a string that describes a pattern.

There are two types, text-directed or regex-directed engine. You can do the test by applying the regex regex|regex not to the string regex not. If the resulting match is only regex, the engine is regex-directed. If the result is regex not, then it is text-directed. The reason behind this is that the regex-directed engine is "eager". Perl and PHP are regex-directed engines, they will always match at the earliest possible point in the string. See How Regexes Work for details.

Regular expressions generally involve two stages in parsing, the first stage involves variable substitution, in the second stage the pattern and string are sent to the RE engine.

Regular expression engines are token engines where a token is an assertion or an atom. An assertion tests some property of the string, zero width assertions such as \b are termed assertions whereas assertions with nonzero-width are atoms, such as any ASCII or binary character. Internally the token engine matches from left to right a string to a regular expression pattern consuming the string whether the match is satisfied or not.

When a regexp can match a string in several different ways, we can use the principles above to predict which way the regexp will match

• Principle 0: Taken as a whole, any regexp will be matched at the earliest possible position in the string.

• Principle 1: In an alternation a|b|c... , the leftmost alternative that allows a match for the whole regexp will be the one used.

• Principle 2: The maximal matching quantifiers ?, * , + and {n,m} will in general match as much of the string as possible while still allowing the whole regexp to match.

• Principle 3: If there are two or more elements in a regexp, the leftmost greedy quantifier, if any, will match as much of the string as possible while still allowing the whole regexp to match. The next leftmost greedy quantifier, if any, will try to match as much of the string remaining available to it as possible, while still allowing the whole regexp to match. And so on, until all the regexp elements are satisfied.

An example

"Hello World" =~ m/World/;  # matches

What is this perl statement all about? "Hello World" is a simple double quoted string. World is the regular expression and the // enclosing m/World/ tells perl to search a string for a match. The operator =~ associates the string with the regexp match and produces a true value if the regexp matched, or false if the regexp did not match. In our case, World matches the second word in "Hello World" , so the expression is true.

Wikipedia provides a useful overview of regular expressions and their history.

Tutorials

• Perl regular expressions quick start
• Perl regular expressions tutorial
• Regular expression info
• Tips for learning regular expressions

Reference books

• Mastering regular expressions

Engines

• Perl compatible regular expressions (PCRE)
• TRE Regular expression engine in C
• DEELX Regular expression engine in C++/DEELX

Perl

• Wikipedia:Regular expression
• Wikipedia Perl 6 Rules
• How Regexes Work
• Perl 6 regex FAQ

See also

• How to execute the Perl interpreter
• Useful regular expression pattern library repository
• txt2re.com - a useful regular expression generator tool
• Regular expressions cheatsheet
• A regular expression to check if a number is prime
• Good old regular expressions - two awesome regex examples from The Unix Programming Environment book