Catastrophic or exponential backtracking

Regular expression engines can be broadly categorized into two types:

  1. The Non-deterministic Finite Automation (NFA) engine
  2. The Deterministic Finite Automation (DFA) engine

The DFA engines do not evaluate each character more than once to find a match. On the other hand, the NFA engines support backtracking, which means that each character in the input can be evaluated multiple times by the regex engine. The Java regular expression engine is an NFA engine.

Regex engines backtrack or give back one position at a time to make various attempts to match a given pattern when using the greedy quantifier or trying alternations. Similarly, when using lazy quantifiers, the regex engine moves forward one position ...

Get Java 9 Regular Expressions now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.