Introduced in the RegexEngine topic, NFA engines use backtracking. Backtracking is the action of returning back in the input text and trying another alternative of the regular expression.

Alternatives in a regular expression arise from Alternation and Quantifiers. In an alternation, the engine has to try each possible alternatives provided. With a quantifier, it has to decide whether to try a match or yet another match.

Backtracking rules

NFA engines applies the following rules when backtracking:

• Always backtrack to the last saved option. Backtracking works like LIFO stacks.
• For alternation, try each alternative in given order
• For greedy quantifier, when choosing between try another match or skip it, try another match first.
• For lazy quantifier, when choosing between try another match or skip it, try to skip it first.
• Do not save backtracking option for an atomic grouping or a possesive quantifier. These are always backtracked as whole.

To helps you better understand these concepts, look at these Examples.