Reading — step 1 of 5
Read
~1 min readQuantifiers & Anchors
Alternation and Groups
| Construct | Meaning |
|---|---|
(abc) | grouping (apply quantifier to a sub-pattern) |
| `a | b` |
(?:abc) | non-capturing group (no backreference cost) |
\1 | backreference: match the same text as group 1 captured |
Alternation has the LOWEST precedence: ab|cd is (ab)|(cd), not a(b|c)d.
Examples:
cat|dog— matches "cat" or "dog"(cat|dog)s?— matches "cat", "cats", "dog", "dogs"(\d+)x\1— matches "5x5" or "42x42" but not "5x6" (backref)https?://— matches "http://" or "https://"(yes|no|maybe)— capture group: query later which alternative matched
Implementation gets harder. The straightforward approach:
- Parse the regex into an AST: literal | group | alternation | quantifier.
- Compile to NFA states (Thompson's construction — next lesson).
- Simulate the NFA over the input.
Backreferences (\1) BREAK regular language semantics — they require
backtracking. RE2 (Go's stdlib, used by Google) refuses to support them
to maintain its O(n*m) guarantee.
For this lesson we focus on alternation + non-capturing groups; capture + backref come in the production-features chapter.
Discussion
Ask a question, share an insight, or help someone who’s stuck.
Sign in to post a comment or reply.
Loading…