Jessica Brown

Understanding how a regex engine processes patterns can significantly improve your ability to write efficient and accurate regular expressions. By learning the internal mechanics, you’ll be better equipped to troubleshoot and refine your regex patterns, reducing frustration and guesswork when tackling complex tasks.

Types of Regex Engines

There are two primary types of regex engines:

1. Text-Directed Engines (also known as DFA - Deterministic Finite Automaton)

2. Regex-Directed Engines (also known as NFA - Non-Deterministic Finite Automaton)

All the regex flavors discussed in this tutorial utilize regex-directed engines. This type is more popular because it supports features like lazy quantifiers and backreferences, which are not possible in text-directed engines.

Examples of Text-Directed Engines:

• awk

• egrep

• flex

• lex

• MySQL

• Procmail

Note: Some versions of awk and egrep use regex-directed engines.

How to Identify the Engine Type

To determine whether a regex engine is text-directed or regex-directed, you can apply a simple test using the pattern:

regex|regex not

Apply this pattern to the string "regex not":

• If the result is "regex", the engine is regex-directed.

• If the result is "regex not", the engine is text-directed.

The difference lies in how eager the engine is to find matches. A regex-directed engine is eager and will report the leftmost match, even if a better match exists later in the string.

The Regex-Directed Engine Always Returns the Leftmost Match

A crucial concept to grasp is that a regex-directed engine will always return the leftmost match. This behavior is essential to understand because it affects how the engine processes patterns and determines matches.

How It Works

When applying a regex to a string, the engine starts at the first character of the string and tries every possible permutation of the regex at that position. If all possibilities fail, the engine moves to the next character and repeats the process.

For example, consider applying the pattern «cat» to the string:

"He captured a catfish for his cat."

Here’s a step-by-step breakdown:

1. The engine starts at the first character "H" and tries to match "c" from the pattern. This fails.

2. The engine moves to "e", then space, and so on, failing each time until it reaches the fourth character "c".

3. At "c", it tries to match the next character "a" from the pattern with the fifth character of the string, which is "a". This succeeds.

4. The engine then tries to match "t" with the sixth character, "p", but this fails.

5. The engine backtracks and resumes at the next character "a", continuing the process.

6. Finally, at the 15th character in the string, it matches "c", then "a", and finally "t", successfully finding a match for "cat".

Key Point

The engine reports the first valid match it finds, even if a better match could be found later in the string. In this case, it matches the first three letters of "catfish" rather than the standalone "cat" at the end of the string.

Why?

At first glance, the behavior of the regex-directed engine may seem similar to a basic text search routine. However, as we introduce more complex regex tokens, you’ll see how the internal workings of the engine have a profound impact on the matches it returns.

Understanding this behavior will help you avoid surprises and leverage the full power of regex for more effective and efficient text processing.

A regular expression engine is a software component that processes regex patterns, attempting to match them against a given string. Typically, you won’t interact directly with the engine. Instead, it operates behind the scenes within applications and programming languages, which invoke the engine as needed to apply the appropriate regex patterns to your data or files.

Variations Across Regex Engines

As is often the case in software development, not all regex engines are created equal. Different engines support different regex syntaxes, often referred to as regex flavors. This tutorial focuses on the Perl 5 regex flavor, widely considered the most popular and influential. Many modern engines, including the open-source PCRE (Perl-Compatible Regular Expressions) engine, closely mimic Perl 5’s syntax but may introduce slight variations. Other notable engines include:

• .NET Regular Expression Library

• Java’s Regular Expression Package (included from JDK 1.4 onwards)

Whenever significant differences arise between flavors, this guide will highlight them, ensuring you understand which features are specific to Perl-derived engines.

Getting Hands-On with Regex

You can start experimenting with regular expressions in any text editor that supports regex functionality. One recommended option is EditPad Pro, which offers a robust regex engine in its evaluation version.

To try it out:

1. Copy and paste the text from this page into EditPad Pro.

2. From the menu, select Search > Show Search Panel to open the search pane at the bottom.

3. In the Search Text box, type «regex».

4. Check the Regular expression option.

5. Click Find First to locate the first match. Use Find Next to jump to subsequent matches. When there are no more matches, the Find Next button will briefly flash.

A More Advanced Example

Let’s take it a step further. Try searching for the following regex pattern:

«reg(ular expressions?|ex(p|es)?)»

This pattern matches all variations of the term "regex" used on this page, whether singular or plural. Without regex, you’d need to perform five separate searches to achieve the same result. With regex, one pattern does the job, saving you significant time and effort.

For instance, in EditPad Pro, select Search > Count Matches to see how many times the regex matches the text. This feature showcases the power of regex for efficient text processing.

Why Use Regex in Programming?

For programmers, regexes offer both performance and productivity benefits:

• Efficiency: Even a basic regex engine can outperform state-of-the-art plain text search algorithms by applying a pattern once instead of running multiple searches.

• Reduced Development Time: Checking if a user’s input resembles a valid email address can be accomplished with a single line of code in languages like Perl, PHP, Java, or .NET, or with just a few lines when using libraries like PCRE in C.

By incorporating regex into your workflows and applications, you can achieve faster, more efficient text processing and validation tasks.

Character classes, also known as character sets, allow you to define a set of characters that a regex engine should match at a specific position in the text. To create a character class, place the desired characters between square brackets. For instance, to match either an a or an e, use the pattern [ae]. This can be particularly useful when dealing with variations in spelling, such as in the regex gr[ae]y, which will match both "gray" and "grey."

Key Points About Character Classes:

• A character class matches only a single character.

• The order of characters inside a character class does not affect the outcome.

For example, gr[ae]y will not match "graay" or "graey," as the class only matches one character from the set at a time.

Using Ranges in Character Classes

You can specify a range of characters within a character class by using a hyphen (-). For example:

• [0-9] matches any digit from 0 to 9.

• [a-fA-F] matches any letter from a to f, regardless of case.

You can also combine multiple ranges and individual characters within a character class:

• [0-9a-fxA-FX] matches any hexadecimal digit or the letter X.

Again, the order of characters inside the class does not matter.

Useful Applications of Character Classes

Here are some practical use cases for character classes:

• sep[ae]r[ae]te: Matches "separate" or "seperate" (common spelling errors).

• li[cs]en[cs]e: Matches "license" or "licence."

• [A-Za-z_][A-Za-z_0-9]*: Matches identifiers in programming languages.

• 0[xX][A-Fa-f0-9]+: Matches C-style hexadecimal numbers.

Negated Character Classes

By adding a caret (^) immediately after the opening square bracket, you create a negated character class. This instructs the regex engine to match any character not in the specified set.

For example:

• q[^u]: Matches a q followed by any character except u.

However, it’s essential to remember that a negated character class still requires a character to follow the initial match. For instance, q[^u] will match the q and the space in "Iraq is a country," but it will not match the q in "Iraq" by itself.

To ensure that the q is not followed by a u, use negative lookahead: q(?!u). We will cover lookaheads later in this tutorial.

Metacharacters Inside Character Classes

Inside character classes, most metacharacters lose their special meaning. However, a few characters retain their special roles:

• Closing bracket (])

• Backslash (\)

• Caret (^) (only if it appears immediately after the opening bracket)

• Hyphen (-) (only if placed between characters to specify a range)

To include these characters as literals:

• Backslash (\) must be escaped as [\].

• Caret (^) can appear anywhere except right after the opening bracket.

• Closing bracket (]) can be placed right after the opening bracket or caret.

• Hyphen (-) can be placed at the start or end of the class.

Examples:

• [x^] matches x or ^.

• []x] matches ] or x.

• [^]x] matches any character that is not ] or x.

• [-x] matches x or -.

Shorthand Character Classes

Shorthand character classes are predefined character sets that simplify your regex patterns. Here are the most common shorthand classes:

Details:

• \d matches digits from 0 to 9.

• \w includes letters, digits, and underscores.

• \s matches spaces, tabs, and line breaks. In some flavors, it may also include form feeds and vertical tabs.

The characters included in these shorthand classes may vary depending on the regex flavor. For example:

• JavaScript treats \d and \w as ASCII-only but includes Unicode characters for \s.

• XML handles \d and \w as Unicode but limits \s to ASCII characters.

• Python allows you to control what the shorthand classes match using specific flags.

Shorthand character classes can be used both inside and outside of square brackets:

• \s\d matches a whitespace character followed by a digit.

• [\s\d] matches a single character that is either whitespace or a digit.

For instance, when applied to the string "1 + 2 = 3":

• \s\d matches the space and the digit 2.

• [\s\d] matches the digit 1.

The shorthand [\da-fA-F] matches a hexadecimal digit and is equivalent to [0-9a-fA-F].

Negated Shorthand Character Classes

The primary shorthand classes also have negated versions:

• \D: Matches any character that is not a digit. Equivalent to [^\d].

• \W: Matches any character that is not a word character. Equivalent to [^\w].

• \S: Matches any character that is not whitespace. Equivalent to [^\s].

Be careful when using negated shorthand inside square brackets. For example:

• [\D\S] is not the same as [^\d\s].

  • [\D\S] will match any character, including digits and whitespace, because a digit is not whitespace and whitespace is not a digit.

  • [^\d\s] will match any character that is neither a digit nor whitespace.

Repeating Character Classes

You can repeat a character class using quantifiers like ?, *, or +:

• [0-9]+: Matches one or more digits and can match "837" as well as "222".

If you want to repeat the matched character instead of the entire class, you need to use backreferences:

• ([0-9])\1+: Matches repeated digits, like "222," but not "837."

  • Applied to the string "833337," this regex matches "3333."

If you want more control over repeated matches, consider using lookahead and lookbehind assertions, which we will explore later in the tutorial.

Looking Inside the Regex Engine

As previously discussed, the order of characters inside a character class does not matter. For instance, gr[ae]y can match both "gray" and "grey."

Let’s see how the regex engine processes gr[ae]y step by step:

Given the string:

"Is his hair grey or gray?"

1. The engine starts at the first character and fails to match g until it reaches the 13th character.

2. At the 13th character, g matches.

3. The next token r matches the following character.

4. The character class [ae] gives the engine two options:

   • First, it tries a, which fails.

   • Then, it tries e, which matches.

5. The final token y matches the next character, completing the match.

The engine returns "grey" as the match result and stops searching, even though "gray" also exists in the string. This is because the regex engine is eager to report the first valid match it finds.

Understanding how the regex engine processes character classes helps you write more efficient patterns and predict match results more accurately.

Previously, we explored how character classes allow you to match a single character out of several possible options. Alternation, on the other hand, enables you to match one of several possible regular expressions.

The vertical bar or pipe symbol (|) is used for alternation. It acts as an OR operator within a regex.

Basic Syntax

To search for either "cat" or "dog," use the pattern:

cat|dog

You can add more options as needed:

cat|dog|mouse|fish

The regex engine will match any of these options. For example:

Precedence and Grouping

The alternation operator has the lowest precedence among all regex operators. This means the regex engine will try to match everything to the left or right of the vertical bar. If you need to control the scope of the alternation, use round brackets (()) to group expressions.

Example:

Without grouping:

\bcat|dog\b

This regex will match:

• A word boundary followed by "cat"

• "dog" followed by a word boundary

With grouping:

\b(cat|dog)\b

This regex will match:

• A word boundary, then either "cat" or "dog," followed by another word boundary.

Understanding Regex Engine Behavior

The regex engine is eager, meaning it stops searching as soon as it finds a valid match. The order of alternatives matters.

Consider the pattern:

Get|GetValue|Set|SetValue

When applied to the string "SetValue," the engine will:

1. Try to match Get, but fail.

2. Try GetValue, but fail.

3. Match Set and stop.

The result is that the engine matches "Set," but not "SetValue." This happens because the engine found a valid match early and stopped.

Solutions to Eagerness

There are several ways to address this behavior:

1. Change the Order of Options

By changing the order of options, you can ensure longer matches are attempted first:

GetValue|Get|SetValue|Set

This way, "SetValue" will be matched before "Set."

2. Use Optional Groups

You can combine related options and use ? to make parts of them optional:

Get(Value)?|Set(Value)?

This pattern ensures "GetValue" is matched before "Get," and "SetValue" before "Set."

3. Use Word Boundaries

To ensure you match whole words only, use word boundaries:

\b(Get|GetValue|Set|SetValue)\b

Alternatively, use:

\b(Get(Value)?|Set(Value)?)\b

Or even better:

\b(Get|Set)(Value)?\b

This pattern is more efficient and concise.

POSIX Regex Behavior

Unlike most regex engines, POSIX-compliant regex engines always return the longest possible match, regardless of the order of alternatives. In a POSIX engine, applying Get|GetValue|Set|SetValue to "SetValue" will return "SetValue," not "Set." This behavior is due to the POSIX standard, which prioritizes the longest match.

Summary

Alternation is a powerful feature in regex that allows you to match one of several possible patterns. However, due to the eager behavior of most regex engines, it’s essential to order your alternatives carefully and use grouping to ensure accurate matches. By understanding how the engine processes alternation, you can write more effective and optimized regex patterns.

Regular expressions can quickly become complex and difficult to understand, especially when dealing with long patterns. To make them easier to read and maintain, many modern regex engines allow you to add comments directly into your regex patterns. This makes it possible to explain what each part of the expression does, reducing confusion and improving readability.

How to Add Comments in Regular Expressions

The syntax for adding a comment inside a regex is:

(?#comment)

• The text inside the parentheses after ?# is treated as a comment.

• The regex engine ignores everything inside the comment until it encounters a closing parenthesis ).

• The comment can be anything you want, as long as it does not include a closing parenthesis.

For example, here’s a regex to match a valid date in the format yyyy-mm-dd, with comments to explain each part:

(?#year)(19|20)\d\d[- /.](?#month)(0[1-9]|1[012])[- /.](?#day)(0[1-9]|[12][0-9]|3[01])

This regex is much more understandable with comments:

• (?#year): Marks the section that matches the year.

• (?#month): Marks the section that matches the month.

• (?#day): Marks the section that matches the day.

Without these comments, the regex would be difficult to decipher at a glance.

Benefits of Using Comments in Regular Expressions

Adding comments to your regex patterns offers several benefits:

1. Improves readability: Comments clarify the purpose of each section of your regex, making it easier to understand.

2. Simplifies maintenance: If you need to update a regex later, comments make it easier to remember what each part of the pattern does.

3. Helps collaboration: When sharing regex patterns with others, comments make it easier for them to follow your logic.

Using Free-Spacing Mode for Better Formatting

In addition to inline comments, many regex engines also support free-spacing mode, which allows you to add spaces and line breaks to your regex without affecting the match.

Free-spacing mode makes your regex more structured and readable by allowing you to organize it into logical sections. To enable free-spacing mode:

• In Perl, PCRE, Python, and Ruby, use the /x modifier to activate free-spacing mode.

• In .NET, use the RegexOptions.IgnorePatternWhitespace option.

• In Java, use the Pattern.COMMENTS flag.

Here’s an example of how free-spacing mode can improve the readability of a regex:

Without Free-Spacing Mode:

(19|20)\d\d[- /.](0[1-9]|1[012])[- /.](0[1-9]|[12][0-9]|3[01])

With Free-Spacing Mode and Comments:

(?#year) (19|20) \d\d        # Match years 1900 to 2099
[- /.]                       # Separator (dash, slash, or dot)
(?#month) (0[1-9] | 1[012])  # Match months 01 to 12
[- /.]                       # Separator
(?#day) (0[1-9] | [12][0-9] | 3[01])  # Match days 01 to 31

The second version is far easier to read and maintain.

Which Regex Engines Support Comments?

Most modern regex engines support the (?#comment) syntax for adding comments, including:

Example: Using Comments to Document a Complex Regex

Here’s an example of a more complex regex that extracts email addresses from a text file. Without comments, the regex looks like this:

\b[A-Za-z0-9._%+-]+@[A-Za-z0-9.-]+\.[A-Za-z]{2,}\b

Adding comments and using free-spacing mode makes it much more understandable:

\b                      # Word boundary to ensure we're at the start of a word
[A-Za-z0-9._%+-]+       # Local part of the email (before @)
@                       # At symbol
[A-Za-z0-9.-]+          # Domain name
\.                      # Dot before the top-level domain
[A-Za-z]{2,}            # Top-level domain (e.g., com, net, org)
\b                      # Word boundary to ensure we're at the end of a word

Key Points to Remember

• Comments in regex are added using the (?#comment) syntax.

• Free-spacing mode makes regex patterns more readable by allowing spaces and line breaks.

• Supported engines include JGsoft, .NET, Perl, PCRE, Python, and Ruby.

• Java supports free-spacing mode but does not support inline comments.

When to Use Comments and Free-Spacing Mode

Use comments and free-spacing mode when:

1. Your regex pattern is complex and hard to read.

2. You’re working on a team and need to make your patterns understandable to others.

3. You need to revisit your regex after some time and want to avoid deciphering cryptic patterns.

Adding comments and using free-spacing mode can greatly enhance the readability and maintainability of your regular expressions. Complex patterns become easier to understand, update, and share with others. When working with modern regex engines, take advantage of these features to write cleaner, more maintainable regex patterns.

By making your regex more human-readable, you’ll save time and reduce frustration when dealing with intricate text-processing tasks.