Regular Expressions Machinery

The Illustrated Guide

by Staffan Nöteberg

To effectively use regular expressions, you need to understand how the machinery works under the hood. It’s about taking control of the search process, controlling how the pattern is matched, and thus getting both faster and more accurate results.

In this illustrated guide, you gain precisely that understanding.

You can even get started without any prior knowledge of regular expressions. Before you know it, advanced tools like reluctant, lookbehind and nondeterministic finite automata will be at your fingertips as you write efficient and elegant regexes with ease.

This work was written and produced entirely by the author. We are proud to be distributing it.

This book is written for those who want to deeply understand regular expressions. Maybe you’ve come across them in programming languages or tools, but never really understood how they work under the hood. The book presents complex concepts in a simple and visual way, with clear examples and practical applications. Whether you are a programmer, data analyst, or just want to get better at text processing, this book will take your knowledge to the next level.

The goal of the book is to give you a deep understanding of regular expressions so that you can use them with confidence and efficiency in your work. We begin by looking at the theoretical basis of regular expressions: finite automata. Then, we go through the only two operations and the only function needed to create regular expressions. We also thoroughly explore all basic and advanced features of modern regular expressions, and some of the most common pitfalls. Finally, we examine the concept of test-driven development (TDD) and how you can leverage it to write regexes that are correct and easy to maintain in your production code.

• Errata, typos, suggestions

Releases:

• P1.0 2025/01/23

Introduction excerpt

PART I: The Automaton

• Transition Diagram
• Alphabet
• States and Transitions
• Transitions Table
• Nondeterministic Finite Automaton
• Greedy and Reluctant
• NFA to DFA
• Pushdown Automata

PART II: Two Operations and One Function excerpt

• History of Regular Expressions
• Match One Character
• Four More Rules
• Operation №1: Concatenation
• Operation №2: Alternation
• The Function: Kleene Star
• Precedence
• Some Examples With *, |, and ×
• Regular Expressions Are Finite Automata
• Traits
• Architecture
• Functions

PART III: Syntactic Sugar, Abstractions, and Extensions excerpt

• Quantifiers
• Quantifier Equations
• Reluctant Quantifiers
• Possessive Quantifier
• Literal vs. Metacharacters
• Character Code Points
• Character Aliases
• The Period Symbol
• Shrthnd
• Unicode Categories, Scripts, and Blocks
• Generic Character Class
• Generic Character Class Negated and Tweaked
• Generic Character Class Escape
• Posix Character Class
• Grouping
• Capture and Back Reference
• Named groups
• Atomic Groups
• Anchors
• Lookarounds

Part IV: Test-Driven Regex Development

• Wishful Thinking and Test-Driven Development excerpt
• TDD and Regression Testing
• TDD and Legacy Code

Afterword

Appendix A: Precedence