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.

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.

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

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.

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

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:

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.

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.

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.

In this chapter, you were introduced to regular expressions with a bit of history and their flavors. You learnt some use cases where regex are needed. Finally, we covered the basic rules and building blocks of writing regex, with a few examples. You also learnt the eager-matching behavior of the regex engine and how it may impact matching in alternations.

In the next chapter, we will go a level deeper and cover the core concepts of regex in detail, such as quantifiers, lazy vs greedy matching, anchors, negated character classes, Unicode and predefined character classes, special escape sequences, and the rules of escaping inside a character class.