skip to content

Which three operators does every regular pattern reduce to, and how do they bind relative to one another?

level: middleimportance: must knowfreq 58%

answer

  1. three operations, then a binding order
  2. sequence, choice, repetition
  3. the choice operator binds loosest
  4. repetition binds tighter than sequencing
  5. same shape as exponent, product, sum

basics

~10 s

Concatenation, alternation and the Kleene star. Repetition binds tightest, then concatenation, then alternation, so ab*|c reads as (a(b*))|c. Parentheses exist only to override that order.

solid answer

~40 s

Three operators generate the whole formalism: **concatenation** (this, then that), **alternation** (`|`, this or that) and the **Kleene star** (zero or more copies). Precedence runs star tightest, concatenation next, alternation loosest — the same shape as exponent, product and sum in arithmetic. So `ab*|c` parses as `(a(b*))|c`, not as `a(b*|c)` or `(ab)*|c`. Parentheses are forced in exactly two situations: when a repetition must apply to a sequence rather than to one symbol, as in `(ab)*`; and when an alternation must sit inside a sequence, as in `a(b|c)d`. Everything else in a pattern language — classes, the optional mark, bounded repeats — is sugar over these three.

go deeper

for a junior

Memorise the three operations and the binding order, tightest first: repetition, then sequencing, then choice. Practise reading one small pattern aloud as a fully parenthesised form.

for a middle

Explain the ordering with a pattern whose two readings differ, and state the two places parentheses are genuinely required: repeating a sequence, and placing a choice inside a sequence.

for a senior

Bring a case where a mis-parsed rule shipped — a route or filter whose bar split more of the pattern than the author meant — and say how review or a test would have caught the wrong reading.

for a principal

Treat pattern notation as a language your team reads under incident pressure: decide whether house style writes redundant parentheses for clarity, and make that decision once rather than per author.

## The three operators A regular pattern is built from literal symbols plus exactly three operations. Everything a pattern language offers beyond them is notation. 1. **Concatenation** — write `R` then `S` to mean text matched by `R` immediately followed by text matched by `S`. It has no written symbol, which is precisely why its precedence is easy to get wrong. 2. **Alternation** — `R|S` matches text matched by `R` or text matched by `S`. As an operation on sets of texts it is union: associative and commutative, so the grouping of a chain of alternatives does not change which texts match. 3. **Kleene star** — `R*` matches zero or more copies of `R` joined end to end. A fourth ingredient is not an operator but is worth naming: the **empty text**, which the star relies on for its zero-copy case. ## Precedence, tightest to loosest | Tier | Operator | Binds to | Example | Reads as | |---|---|---|---|---| | 1 (tightest) | repetition `*` | the one unit before it | `ab*` | `a(b*)` | | 2 | concatenation | adjacent units | `ab\|c` | `(ab)\|c` | | 3 (loosest) | alternation `\|` | whole sequences | `ab\|cd` | `(ab)\|(cd)` | The arithmetic parallel is exact enough to be useful: repetition behaves like an exponent, concatenation like a product and alternation like a sum. `ab*|c` is read the way you read `a·b² + c`. Two misreadings account for most mistakes: - Reading `ab*` as *the sequence ab, repeated*. The star sits at tier 1 and cannot reach back over the `a`. - Reading `ab|c` as *a, then b or c*. Alternation is the loosest operator, so the bar splits the largest sequences around it, giving `ab` or `c`. ## Where parentheses are forced Parentheses do one job: make a sub-pattern into a single unit so a tighter operator can apply to it. That is needed in exactly two shapes. - **Repeating a sequence.** `(ab)*` matches the empty text, `ab`, `abab`, and so on. Without the parentheses you get `ab*`, which is a different language entirely. - **Putting a choice inside a sequence.** `a(b|c)d` matches `abd` and `acd`. Without the parentheses, `ab|cd` matches `ab` and `cd`, which shares no text at all with the intended set. They are **not** needed to concatenate two sequences, and **not** needed to choose between two whole sequences — precedence already does both. Parentheses that only restate the default order are noise; in a configuration file read under pressure, noise is a cost. ## A route rule taken apart Take an edge proxy rule written `/(api|static)/v[0-9]+/.*` and remove the sugar and the defaults: - `/` then the group `(api|static)` — the parentheses are load-bearing, because without them the alternation would split the entire rule into *everything up to `api`* or *`static` and everything after*. - `/v` then `[0-9]+`, which is sugar: one digit alternative followed by a star over the same alternation. - `/` then `.*` — a star over the any-symbol class, that is, an arbitrarily long tail, including an empty one. What is left when the sugar is gone is a sequence of concatenations, one alternation and two stars. That is the whole vocabulary. ## Why three is the right number The three operators are not an arbitrary choice: they are exactly the operations under which the class of languages accepted by finite automata is closed and which suffice to generate that class from single symbols. Adding notation — classes, optional marks, bounded repeats — makes patterns shorter but does not enlarge the class. Adding a feature that is not built from these three, such as one demanding that a later span reproduce text captured earlier, does leave the class; that is a different operator altogether, not a shorthand. ## What an interviewer is listening for Name the three, order them by precedence, and show the ordering with a pattern whose two readings differ. Then say where parentheses are genuinely required. A candidate who can look at `ab*|c` and read out `(a(b*))|c` without hesitating has internalised the grammar of the notation rather than pattern-matching on examples.

  • Where does a bounded repeat such as `{2,4}` sit in the precedence order?
    In the same tier as the star. All repetition notations are postfix and bind to the single unit immediately before them, so `ab{2,4}` repeats only `b`. To repeat a sequence you need parentheses, exactly as with the star.
  • Does the grouping of a chain of alternatives change which texts match?
    No. Alternation is union over sets of texts, so it is associative and commutative: `(A|B)|C` and `A|(B|C)` describe the same set. Grouping can affect the order in which an engine tries alternatives, which is a matching-order question rather than a question about which texts the pattern describes.
  • Why does concatenation have no written symbol, and does that cost anything?
    It is the most frequent operation, so the notation leaves it implicit for brevity. The cost is real: an invisible operator makes its precedence easy to overlook, which is why `ab|c` is misread far more often than an explicitly written operator would be.

Read a pattern the way you read arithmetic: repetition is the exponent, concatenation the product, alternation the sum. Parentheses are needed in exactly the places they are needed in arithmetic — to lift a sum into a product.

saying these in an interview costs you the question

  • Reads ab* as the sequence ab repeated.
  • Thinks alternation binds tighter than concatenation.
  • Believes character classes are a fourth primitive operator.
  • Adds parentheses around every sequence out of superstition.
  • Says parentheses are required to concatenate two sequences.
  • Claims alternation ordering changes which texts match.