Regular expressions backtracking and quantifiers greediness

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.