A regular expression is a formal notation for describing sets of strings using a concise pattern language built from literals, character classes, quantifiers, and grouping. Regular expressions describe exactly the class of regular languages and are typically implemented by compiling the pattern into a finite-state machine for efficient matching. They are a foundational tool for searching, validating, and transforming text.
Overview
- Regular expressions originate from the theory of regular languages and are equivalent in expressive power to deterministic and nondeterministic finite automata.
- Practical regex engines extend the pure formalism with features such as backreferences and lookaround, some of which exceed the regular-language class.
- Matching can be performed by simulating an automaton (linear time) or by backtracking (potentially exponential time on adversarial inputs).
Mechanisms
- The pattern is compiled into a nondeterministic finite automaton, optionally converted to a deterministic one.
- Quantifiers, character classes, anchors, and groups define how the pattern consumes input.
- Greedy and lazy matching control how much input a quantifier consumes.
- Captured groups extract substrings for downstream processing or substitution.
Applications
- Input validation for fields such as email addresses, identifiers, and structured codes.
- Lexical analysis in compilers and interpreters.
- Search-and-replace operations in editors, log processing, and data cleaning pipelines.