Tri's external memory

Regex Lesson 2 - Engine Execution & Backtracking

3 min read

Goal

Understand how a regex engine actually executes a pattern.

Learn:

  • Consuming characters

  • Greedy matching

  • Backtracking

  • Lazy matching

  • How to mentally trace regex execution

Mental Model

A regex engine behaves like a tiny program.

Given:

cat

and:

dog cat bird

The engine tries:

position 0 -> fail
position 1 -> fail
position 2 -> fail
...
position 4 -> success

The engine scans through the text looking for a match.

Consuming Characters

When a pattern matches, it consumes characters.

Example:

abc

Text:

abcdef

Execution:

a -> matches
b -> matches
c -> matches

Consumed:

abc

Greedy Matching

Most quantifiers are greedy.

Greedy means:

Take as much as possible.

Example:

a.*

Text:

abcdef

Execution:

a -> matches
.* -> consumes bcdef

Match:

abcdef

Greedy Quantifiers

These are greedy by default:

*
+
{n,m}

Examples:

.*
.+
\d+
[a-z]{3,10}

All try to consume as much text as possible.

Backtracking

When a greedy match causes a later failure, the engine goes backwards.

Example:

a.*d

Text:

abcdef

First attempt:

a -> a
.* -> bcdef
d -> fail

Backtrack:

.* -> bcde
d -> fail

Backtrack:

.* -> bcd
d -> matches

Success.

Match:

abcd

Visual Model

Greedy matching:

Take everything
      ↓
Later part fails
      ↓
Give back characters
      ↓
Try again

This “give back” step is backtracking.

Common Interview Trace

Regex:

a.*b

Text:

axxbxxbxx

Execution:

a -> matches
 
.* -> xxbxxbxx
 
b -> fail

Backtrack:

.* -> xxbxxbx
b -> fail

Backtrack:

.* -> xxbxxb
b -> fail

Backtrack:

.* -> xxbxx
b -> matches

Result:

axxbxxb

Why .* Causes Problems

Example:

<a>one</a><a>two</a>

Regex:

<a>.*</a>

Execution:

<a> matches first tag
.* consumes everything
</a> matches last closing tag

Result:

<a>one</a><a>two</a>

Often not what we intended.

Lazy Matching

Add a ’?’ after a quantifier.

Examples:

*?
+?
{n,m}?

Meaning:

Take as little as possible.

Example

Regex:

a.*?b

Text:

axxbxxbxx

Execution:

a -> matches
 
.*? -> empty
b -> fail
 
.*? -> x
b -> fail
 
.*? -> xx
b -> matches

Result:

axxb

Greedy vs Lazy

Greedy:

a.*b

Result:

axxbxxb

Lazy:

a.*?b

Result:

axxb

Important Distinction

Question mark has two meanings.

As a Quantifier

a?

Means:

zero or one a

As a Lazy Modifier

a+?

Means:

one or more a
but as few as possible

The meaning depends on context.

Example

Regex:

a+?

Text:

aaaaab

Execution:

Take one a
If rest fails, expand

Result:

aaaaa

only because the remaining pattern forces expansion.

Anchors Revisited

Regex:

abc

Matches:

123abc456

Regex:

^abc$

Matches only:

abc

because:

^

requires start of string

and:

$

requires end of string

Debugging Checklist

When a regex behaves unexpectedly, ask:

  1. Where does matching begin?

  2. Which part consumes characters?

  3. Is a quantifier greedy?

  4. Can the engine backtrack?

  5. Would a lazy quantifier help?

Key Lessons

  • Regex engines consume text from left to right.

  • *, +, {n,m} are greedy by default.

  • Greedy quantifiers take as much as possible.

  • Backtracking occurs when later matching fails.

  • Lazy quantifiers (*?, +?, {n,m}?) take as little as possible.

  • Most regex bugs involve unexpected greediness.

  • Think like the engine, not like the final result.

Mental Shortcut

Greedy:

Grab everything first.
Then backtrack.

Lazy:

Grab nothing first.
Then expand.

This simple model explains most regex behavior.

Graph View

Backlinks