Regular expressions

From Organic Design
Jump to: navigation, search

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

Reference books

Engines

Perl

See also