Regular Expression
A pattern language for matching text, compiled internally into a finite state machine that runs over the input.
Regular Expression describes a pattern over text — literal characters, wildcards, repetition, alternation — that a matching engine compiles into a Finite State Machine and runs over the input one character at a time. \d{3}-\d{4} compiles to a machine with states for "seen 0 digits," "seen 1 digit," and so on, transitioning on each input character and accepting if it lands in a final state at the pattern's end — the pattern is notation, the FSM is the actual mechanism doing the matching.
This compiled-FSM origin is also the source of a regex's fundamental limit: a true regular expression, in the formal-language-theory sense, can only recognize what a finite state machine can, which provably excludes anything requiring unbounded memory to check — matching balanced parentheses or nested tags needs to count nesting depth, which has no bound a finite number of states can hold. This is the real content behind "you can't parse HTML with regex" — not a stylistic objection, a theorem.
What most programming languages call "regex" (PCRE and its descendants: Perl's, Python's re, JavaScript's) isn't a true regular expression anymore — backreferences (\1, referring back to an earlier captured group) match languages no finite automaton can recognize, and engines implement them — along with lookahead/lookbehind assertions, which keep the language regular but are handled the same way — via backtracking, which, on an adversarial input, can take exponential time to fail to match — the ReDoS (regex denial of service) vulnerability class, where a pattern that looks innocuous hangs a server on a crafted string of a few dozen characters. RE2 (Google's library) and Rust's regex crate deliberately give up backreferences to guarantee linear-time matching, trading expressive power for a hard performance ceiling that can't be blown by any input.
See also6
Pattern Matching
Testing a value against a shape and binding its parts to names in one step, instead of inspecting it field by field.
Computation & Algorithms7 connections
Trie
A tree that stores strings by shared prefix, so each node represents a prefix all its descendants extend.
Computation & Algorithms12 connections
Determinism
The property that identical inputs produce identical outputs, and the foundation of caching and verification.
Systems & Tooling61 connections
Phone Number
The international numbering scheme for telephones, E.164, and the many ways phone numbers break software that treats them as simple integers or as stable proofs of identity.
Data & Content7 connections
Lexical Analysis
The first stage of reading a program, which groups a stream of characters into tokens such as names, numbers, operators and keywords, usually using regular expressions compiled into a finite automaton, so the parser can work with words rather than letters.
Computation & Algorithms9 connections
Form Validation
Checking what people type into a web form before accepting it, done in the browser for fast feedback and on the server for safety, and harder than it looks because real names, addresses, and numbers break simple rules.
Web Platform11 connections
Linked from7
- BacktrackingComputation & Algorithms
Searching for a solution by making choices one at a time and undoing the latest choice when it leads nowhere, the method behind puzzle solvers, regex engines, and dependency resolvers.
- CSVData & Content
The plain-text table format of rows separated by line breaks and fields separated by commas, universal and simple until quoting, encoding, and spreadsheets get involved.
- Denial-of-Service AttackNetworks & Distribution
Making a service unavailable by overwhelming it with traffic or expensive requests, usually from many machines at once, and the layered defenses that absorb or filter the flood.
- Finite State MachineComputation & Algorithms
A model with a fixed set of states, one active at a time, and defined transitions between them on each input.
- Form ValidationWeb Platform
Checking what people type into a web form before accepting it, done in the browser for fast feedback and on the server for safety, and harder than it looks because real names, addresses, and numbers break simple rules.
- Lexical AnalysisComputation & Algorithms
The first stage of reading a program, which groups a stream of characters into tokens such as names, numbers, operators and keywords, usually using regular expressions compiled into a finite automaton, so the parser can work with words rather than letters.
- Phone NumberData & Content
The international numbering scheme for telephones, E.164, and the many ways phone numbers break software that treats them as simple integers or as stable proofs of identity.