Introduction to regular expressions

Regular expression (or in short regex) is a very useful tool that is used to describe a search pattern for matching the text. Regex is nothing but a sequence of some characters that defines a search pattern. Regex is used for parsing, filtering, validating, and extracting meaningful information from large text, such as logs and output generated from other programs.

We find regular expressions in day-to-day use on many websites. For example, while searching for your favorite recipe on search engines, while filling up forms and entering data such as username and passwords, and so on. While setting up a password on many sites, we encounter password validation errors, such as password must contain one digit or at least one uppercase letter or at least one special character, and so on. All these checks can be done using regular expressions. A few more typical examples of regular expressions are validating phone numbers or validating postal/zip/pin codes.

A bit of history of regular expressions

Renowned mathematician Stephen Kleene built a model in the year 1956 using finite automata for simple algebra. He described regular languages using his mathematical notation called regular sets. Computer programmers started using regular expressions in the 1970s when the Unix operating system and some of its text editors and text processing utilities such as ed, sed, emacs, lex, vi, grep, awk, and so on were built. Regular expressions gained more popularity with the arrival of Perl and Tcl scripting languages in the 1980s and 1990s. Since then, all the popular programming languages, such as Java, Python, Ruby, R, PHP, and .NET have built very good support of regular expressions.

Various flavors of regular expressions

All the programming and scripting languages have built-in support for regular expressions these days. The basic rules to define and execute regular expressions are pretty much the same across all the languages. However, these regex implementations have their own flavors that differ from each other at the advanced level. We will cover regular expressions using Java in this book.

Some of the popular flavors of regular expressions are as follows:

• .NET
• Java
• Perl
• PCRE (PHP)
• JavaScript
• VBScript
• Python
• R
• Ruby
• std::regex
• boost::regex
• Basic Regular Expressions (BRE) - used by Unix utilities ed, vi, sed, grep, and so on
• Extended Regular Expressions (ERE) - used by Unix utilities sed, grep, awk, and so on

What type of problems need regular expressions to solve

Some programmers wonder why they even need to learn regular expressions. Here are some use cases:

• While searching for some text at times, there are cases where we don't know the value of the text upfront. We just know some rules or patterns of the text. For example, searching for a MAC address in a log message, searching for IP address in a web server access log, or searching for a 10-digit mobile number that may be optionally preceded by 0 or +<2 digit country code>.
• Sometimes, the length of the text we are trying to extract is unknown, for example, searching URLs that start with http:// or https:// in a CSV file.
• Sometimes, we need to split a given text on delimiters of a variable type and length and generate tokens.
• Sometimes, we need to extract text that falls between two or more search patterns.
• Often, we need to validate the various forms of user inputs, such as bank account number, passwords, usernames, credit card info, phone number, date of birth, and so on.
• There are situations where you only want to capture all the repeated words from a line.
• To convert input text into certain predefined formats, such as inserting a comma after every three digits or removing commas inside parentheses only.
• To do a global search replace while skipping all the escaped characters.

The basic rules of regular expressions

Many of you are familiar with wild cards (in the Unix world, it is called glob pattern) matching of text. Here:

• ? matches any single character
• * matches any sequence of characters
• [abc] matches any one character inside square brackets, so it will match a, b, or c

The regular expression pattern goes many steps farther than wild cards, where one can set many rules in a regex pattern, such as the following:

• Match a character or a group of characters optionally (0 or 1 times)
• Use quantifiers in regex patterns to match variable length text
• Use a character class to match one of the listed characters or match a range of characters
• Use a negated character class to match any character except those matched by the character class
• Match only certain character categories, such as match only digits, only upper case letters, or only punctuation characters
• Match a character or a group of characters for a specific length.
• Match a length range, such as allow only six to 10 digits in the input or match an input of a minimum of eight characters
• Use Boolean "OR" in an alternation to match one of the few alternative options
• Use groups in regex patterns and capture substrings that we want to extract or replace from a given input
• Alter the behavior of matching by keeping it greedy (eager), lazy (reluctant), or possessive
• Use back references and forward references of groups that we capture
• Use zero-width assertions such as the following:
  • Start and end anchors
  • Word boundary
  • Lookahead and lookbehind assertions
  • Start a match from the end of a previous match

For example, in a regex to match a or b we can use the following alternation:

a|b

To match one or more instances of the digit 5, we can use the following:

5+

To match any substring that starts with p and ends with w, we can use the following:

p.*w

Constructs of the standard regular expression and meta characters

Let's get familiar with core constructs of regular expressions and some reserve meta characters that have a special meaning in regular expressions. We shall cover these constructs in detail in the coming chapters:

Symbol	Meaning	Example
. (dot or period)	Matches any character other than newline.	Matches #, @, A, f, 5, or .
* (asterisk)	* matches zero or more occurrences of the preceding character or group.	m* matches 0 or more occurrences of the letter m.
+ (plus)	+ matches one or more occurrences of the preceding element.	m+ matches one or more occurrences of the letter m.
? (question mark)	? means optional match. It is used to match zero or one occurrence of the preceding element. It is also used for lazy matching (which will be covered in the coming chapters).	nm? means match n or nm, as m is an optional match here.
| (pipe)	| means alternation. It is used to match one of the elements separated by |	m|n|p means match either the letter m or the letter n or the letter p
^ (cap)	^ is called anchor, that matches start of the line	^m matches m only when it is the first character of the string that we are testing against the regular expression. Also, note that you do not use ^ in the middle of a regular expression.
$ (dollar)	$ is called anchor that matches line end.	m$ matches m only at line end.
\b (backslash followed by the letter b)	Alphabets, numbers, and underscore are considered word characters. \b asserts word boundary, which is the position just before and after a word.	\bjava\b matches the word, java . So, it will not match javascript since the word, javascript, will fail to assert \b after java in the regex.
\B (backslash followed by uppercase B)	\B asserts true where \b doesn't, that is, between two word characters.	For the input text, abc, \B will be asserted at two places: Between a and b. Between b and c.
(...) a sub-pattern inside round parentheses	This is for grouping a part of text that can be used to capture a certain substring or for setting precedence.	m(ab)*t matches m, followed by zero or more occurrences of the substring, ab, followed by t.
{min,max}	A quantifier range to match the preceding element between the minimum and the maximum number.	mp{2,4} matches m followed 2 to 4 occurrences of the letter p.
[...]	This is called a character class.	[A-Z] matches any uppercase English alphabet.
\d (backslash followed by the letter d)	This will match any digit.	\d matches any digit in the 0-9 range.
\D (backslash followed by uppercase D)	This matches any character that is not a digit.	\D matches a, $, or _.
\s (backslash followed by the letter s)	Matches any whitespace, including tab, space, or newline.	\s matches [ \t\n].
\S (backslash followed by uppercase S)	Matches any non-whitespace.	\S matches the opposite of \s
\w (backslash followed by the letter w)	Matches any word character that means all alphanumeric characters or underscore.	\w will match [a-zA-Z0-9_], so it will match any of these strings: "abc", "a123", or "pq_12_ABC"
\W (backslash followed by the letter W)	Matches any non-word character, including whitespaces. In regex, any character that is not matched by \w can be matched using \W.	It will match any of these strings: "+/=", "$", or " !~"

Some basic regular expression examples

Let's look at some basic examples of regular expressions:

    ab*c

This will match a, followed by zero or more b, followed by c.

    ab+c

This will match a followed by one or more b, followed by c.

    ab?c

This will match a followed by zero or one b, followed by c. Thus, it will match both abc or ac.

    ^abc$

This will match abc in a line, and the line must not have anything other than the string abc due to the use of the start and end anchors on either side of the regex.

    a(bc)*z

This will match a, followed by zero or more occurrences of the string bc, followed by z. Thus, it will match the following strings: az, abcz, abcbcz, abcbcbcz, and so on.

    ab{1,3}c

This will match a, followed by one to three occurrences of b, followed by c. Thus, it will match following strings: abc, abbc, and abbbc.

    red|blue

This will match either the string red or the string blue.

    \b(cat|dog)\b

This will match either the string cat or the string dog, ensuring both cat and dog must be complete words; thus, it will fail the match if the input is cats or dogs.

    [0-9]

This is a character class with a character range. The preceding example will match a digit between 0 and 9.

    [a-zA-Z0-9]

This is a character class with a character range. The preceding example will match any alpha-numeric character.

    ^\d+$

This regex will match an input containing only one or more digits.

    ^\d{4,8}$

This regex will allow an input containing four to eight digits only. For example, 1234, 12345, 123456, and 12345678 are valid inputs.

    ^\d\D\d$

This regex not only allows only one digit at the start and end but also enforces that between these two digits there must be one non-digit character. For example, 1-5, 3:8, 8X2, and so on are valid inputs.

    ^\d+\.\d+$

This regex matches a floating point number. For example, 1.23, 1548.567, and 7876554.344 are valid inputs.

    .+

This matches any character one or more times. For example, qwqewe, 12233, or f5^h_=!bg are all valid inputs:

    ^\w+\s+\w+$

This matches a word, followed by one or more whitespaces, followed by another word in an input. For example, hello word, John Smith, and United Kingdom will be matched using this regex.

Engine is a term often used for an underlying module that evaluates the provided regular expression and matches the input string.

Eager matching

At this point, it is important to understand one important behavior of regular expression engines, called eagerness. A regular expression engine performs a match operation from left to right in an input string. While matching a regex pattern against the input string, the regex engine moves from left to right and is always eager to complete a match, even though there are other alternative ways in the regular expression to complete the match. Once a substring is matched, it stops proceeding further and returns the match. Only when a character position fails to match all the possible permutations of the regular expression, then the regex engine moves character by character to attempt a match at the next position in the input string. While evaluating a regex pattern, the regex engine may move backwards (backtrack) one position at a time to attempt matching.

The effect of eager matching on regular expression alternation

This regular expression engine behavior may return unexpected matches in alternation if alternations are not ordered carefully in the regex pattern.

Take an example of this regex pattern, which matches the strings white or whitewash:

white|whitewash

While applying this regex against an input of whitewash, the regex engine finds that the first alternative white matches the white substring of the input string whitewash, hence, the regex engine stops proceeding further and returns the match as white.

Note that our regex pattern has a better second alternative as whitewash, but due to the regex engine's eagerness to complete and return the match, the first alternative is returned as a match and the second alternative is ignored.

However, consider swapping the positions of the third and fourth alternatives in our regex pattern to make it as follows:

whitewash|white

If we apply this against the same input, whitewash, then the regex engine correctly returns the match as whitewash.

We can also use anchors or boundary matchers in our regular expressions to make it match a complete word. Any of the following two patterns will match and return whitewash as a match:

^(white|whitewash)$

\b(white|whitewash)\b

Let's take a look at a more interesting example, which attempts to match a known literal string "cat & rat" or a complete word in the input, using the following pattern:

\b(\w+|cat & rat)\b

If the input string is story of cat & rat, and we apply our regex pattern repeatedly, then the following four matched substrings will be returned:

1. story
2. of
3. cat
4. rat

It is because the regex engine is eagerly using the first alternative pattern \w+ to match a complete word and is returning all the matched words. The engine never attempts a second alternative of the literal string, cat & rat, because a successful match is always found using the first alternative. However, let's change the regex pattern to the following:

\b(cat & rat|\w+)\b

If we apply this regex on the same sting, story of cat & rat, and we apply our regex pattern repeatedly, then the following three matched substrings will be returned:

1. story
2. of
3. cat & rat

This is because now cat & rat is the first alternative and when the regex engine moves to a position before the letter c in the input, it is able to match and return a successful match using the first alternative.