liveBook · Manning

Regex engine

As explained in Secrets of the JavaScript Ninja, Third Edition

A regex engine is software that interprets regular-expression patterns and searches or matches text according to them.

A regex engine interprets a pattern by moving through text and changing states. With greedy quantifiers, it may save consumed characters as choices, then backtrack when a later part of the pattern fails. section 12.6.3

Greedy matching can backtrack

In `/[1-9][0-9]*\s+[a-z]+s/`, matching `27 dresses` first lets `[a-z]+` consume `dresses`. Since the final `s` cannot then match, the engine gives back the last character; the pattern succeeds with `dresse` followed by `s`. section 12.6.3

Listing 12.13 A regex with catastrophic backtracking
const rosterRegex = /^(?:\w+\s*)+$/; #A

console.assert( #B
  rosterRegex.test("Hattori Yoshi Fuma"), #B
  "A genuine roster is accepted instantly", #B
); #B

const attack = #C
  "I will erase your existence from this realm!"; #C
const start = performance.now(); #C
rosterRegex.test(attack); #C
const elapsed = performance.now() - start; #C
console.log(
  `Rejecting the attack string took ${elapsed.toFixed(0)}ms`,
);

A roster-matching regex and attack string illustrate how nested repetition can make rejection take seconds. section 12.6.3

How Secrets of the JavaScript Ninja, Third Edition covers it

How deep it goes
Traces greedy matching through saved choices and backtracking, then demonstrates a costly rejection case.
Examples
Uses `27 dresses` and a roster regex tested against an attack string.
What you can do after
Diagnose potential regex performance problems by tracing backtracking and testing costly rejection cases.
How it connects
Connects regular expressions with greedy quantifiers and backtracking.

Also explained in

Compare how 2 books explain regex engine →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Secrets of the JavaScript Ninja, Third Edition. The section links point to the parts of the book it draws on.