Example
A NFA (Nondeterministic Finite Automaton) engine is driven by the pattern.
Principle
The regex pattern is parsed into a tree.
The current position pointer is set to the start of the input string, and a match is attempted at this position. If the match fais, the position is incremented to the next character in the string and another match is attempted from this position. This process is repeated until a match is found or the end of the input string is reached.
For each match attempt
The algorithm works by performing a traversal of the pattern tree for a given starting position. As it progresses through the tree, it updates the current input position by consuming matching characters.
If the algorithm encounters a tree node which does not match the input string at the current position, it will have to backtrack. This is performed by going back to the parent node in the tree, resetting the current input position to the value it had upon entering the parent node, and trying the next alternative branch.
If the algorithm manages to exit the tree, it reports a successful match. Otherwise, when all possibilities have been tried, the match fails.
Optimizations
Regex engines usually apply some optimizations for better performance. For instance, if they determine that a match must start with a given character, they will attempt a match only at those positions in the input string where that character appears.
Example
Match a(b|c)a against the input string abeacab:
The pattern tree could looks something like:
CONCATENATION
EXACT: a
ALTERNATION
EXACT: b
EXACT: c
EXACT: a
The match processes as follows:
a(b|c)a abeacab
^ ^
a is found in the input string, consume it and proceed to the next item in the pattern tree: the alternation. Try the first possibility: an exact b.
a(b|c)a abeacab
^ ^
b is found, so the alternation succeeds, consume it and proceed to the next item in the concatenation: an exact a:
a(b|c)a abeacab
^ ^
a is not found at the expected position. Backtrack to the alternation, reset the input position to the value it had upon entering the alternation for the first time, and try the second alternative:
a(b|c)a abeacab
^ ^
c is not found at this position. Backtrack to the concatenation. There are no other possibilities to try at this point, so there is no match at the start of the string.
Attempt a second match at the next input position:
a(b|c)a abeacab
^ ^
a does not match there. Attempt another match at the next position:
a(b|c)a abeacab
^ ^
No luck either. Advance to the next position.
a(b|c)a abeacab
^ ^
a matches, so consume it and enter the alternation:
a(b|c)a abeacab
^ ^
b does not match. Attempt the second alternative:
a(b|c)a abeacab
^ ^
c matches, so consume it and advance to the next item in the concatenation:
a(b|c)a abeacab
^ ^
a matches, and the end of the tree has been reached. Report a successful match:
a(b|c)a abeacab
\_/
