Regular Expressions
A compact pattern language for matching and transforming text, grounded in the theory of finite automata.
A regular expression is a compact notation for describing a set of strings. Expressions combine literal characters with metacharacters that express repetition, choice, and position, which makes them the standard tool for searching, validating, and transforming text in almost every programming language and editor.
The core syntax is small:
| Syntax | Meaning | |
|---|---|---|
| . | any single character | |
| [abc] | one of the listed characters | |
| [a-z] | one character in the range | |
| \d \w \s | digit, word character, whitespace | |
| * | zero or more of the previous element | |
| + | one or more | |
| ? | zero or one | |
| {2,4} | between two and four | |
| ^ $ | start and end of the string/line | |
| ( ... ) | capture group | |
| a\ | b | alternation: a or b |
| \b | word boundary |
Theory gives the notation a precise meaning. A regular expression denotes a regular language, and by Kleene's theorem every regular language is accepted by some finite automaton. That equivalence is the basis of tools such as grep, lexer generators, and the pattern matchers inside programming-language runtimes.
Implementation matters in practice. Backtracking engines, used by Perl, PCRE, Python, and JavaScript, are expressive and familiar but can take exponential time on adversarial patterns — the source of "catastrophic backtracking" and ReDoS vulnerabilities. Automaton-based engines such as RE2 and grep's engine run in linear time and are preferred for untrusted input.
Typical uses include validating email addresses and phone numbers, extracting fields from logs, search-and-replace in editors, and tokenizing source code. Regular expressions are not, however, general parsers: nested structures such as balanced parentheses or HTML elements cannot be matched by a finite automaton and require a context-free grammar.