Regular Expressions and Their Types
On this page
Regular Expressions and Their Types
Recall first
Write a pattern for a four-digit number and a pattern that finds words ending in ing. Which regex feature lets a pattern repeat, and which anchors it to a boundary?
First principles
A regular expression (regex) describes a set of strings. Classical operators include literal/character class ([A-Z]), concatenation (ab), alternation (a|b), repetition (*, +, ?, {m,n}), grouping ((...)), and anchors (^, $). A regex engine searches for matches unless the pattern is explicitly anchored or matched against the whole string.
The formal view is important: classical regular expressions describe regular languages, recognizable by finite automata. This explains their bounded-memory strength and limitation: they handle local patterns such as dates or suffixes, but not arbitrary balanced nesting such as perfectly matched parentheses. Practical engines add conveniences—capturing groups, backreferences, lookaround, Unicode properties, and lazy/greedy modes. Backreferences can exceed regular-language power, so “regex” in software is broader than the formal term.
Worked trace. Pattern \b[A-Za-z]+ing\b on Birds are singing. checks a word boundary, consumes letters, requires the suffix ing, then checks a boundary; it matches singing, not the ing inside a longer word. Pattern ^(19|20)\d\d$ accepts a four-digit year beginning with 19 or 20. Parentheses group alternatives; the anchors prevent a substring match.
Types useful in NLP
- Character-level regex: identify scripts, punctuation, digits, URLs, or affixes.
- Token-level patterns: sequences such as
DET ADJ* NOUN, often implemented after tagging. - Search vs full-match patterns: search locates a substring; full match validates the entire input.
- Capturing vs non-capturing groups: capture text for extraction;
(?:...)groups without storing it. - Greedy vs lazy quantifiers: greedy consumes as much as possible; lazy as little as possible. Neither understands syntax.
Regex is excellent for deterministic cleanup and extraction, but overuse can silently delete language information. Apply it after deciding the task’s boundary and Unicode policy; test false positives, false negatives, and adversarial inputs.
Exercise — reveal after answering
Why does .* often produce a bad sentence-level pattern?
Answer: It is unconstrained and greedy: it may span punctuation or multiple fields and hide the intended boundary. Use explicit character classes, anchors, or a parser when structure is required.
Exam lens
Define regex, list operators, connect regex ↔ finite automaton, and state the limitation on nested structure. Mention that backreferences/lookaround are implementation extensions.
Rapid revision checklist
- Explain concatenation, alternation, repetition, class, anchor.
- Distinguish search from full match.
- State regular-language limits.
- Give one NLP extraction example.
Key takeaways
- Regex is a compact local-pattern language, not a grammar for all natural language.
- Anchors and Unicode-aware classes prevent common matching errors.
- Practical regex engines may be more powerful than formal regular expressions.