Course contentsShow
← Computer Science
Lesson 1774 of 2,87240. Theory of Computation: Regular LanguagesFree lesson

Precedence and Parentheses in Regular Expressions

Understand operator precedence rules (star, concatenation, union) and use parentheses to control grouping.

Precedence and Parentheses in Regular Expressions

You'll learn how operator precedence controls the structure of regular expressions and how parentheses override default grouping.

Operator Precedence Rules

In regular expressions, operators follow a strict precedence hierarchy—just like how multiplication happens before addition in arithmetic. From highest to lowest precedence:

  1. Star (Kleene star) * – binds tightest to the immediately preceding element
  2. Concatenation – implicit joining of adjacent elements
  3. Union | – has the lowest precedence, splits broadly

This means ab*|c is parsed as (a(b*)) | c, not a(b*(|c)) or other interpretations.

Why Precedence Matters

Without understanding precedence, you might misread a pattern. Consider ab*:

  • Correct interpretation: the character a followed by zero or more bs (matches: a, ab, abb, etc.)
  • Common mistake: thinking it means zero or more repetitions of ab

Using Parentheses for Grouping

Parentheses override default precedence and explicitly group subexpressions:

  • (ab)* – now the star applies to the entire sequence ab, matching ε, ab, abab, ababab, etc.
  • a(b|c)d – matches abd or acd (union applies only to b and c)
  • Without parens, ab|cd means "ab OR cd" (the union splits the entire expression)

Think of parentheses as packaging: they bundle elements together so an operator treats them as one unit.

Practical Example

To match strings starting with a followed by one or more b or c characters:

  • Wrong: ab|c+ → means "ab OR one-or-more cs"
  • Right: a(b|c)+ → groups the union, then applies plus to the group

Key Takeaway: Star binds tightest, then concatenation, then union. Use parentheses to override precedence and explicitly control which elements operators apply to.