Jeff Moser's has done an in-depth study of how regular expressions work in .NET. His article covers the core operating principals of Microsoft’s implementation such as the machine code used by compiled regular expressions.
The first thing he reveals is that the last 15 regular expressions are cached. For those little utility applications that only use one or two expressions, this means explicitly creating a RegEx object is probably not necessary.
When compiling a regular expression, the first step consists of a scanner than emits a RegexTree. Looking at just the leaf node, this resembles the source code to a fair extend. Next this is translated into the machine code of the regular expression engine.
The bulk of the work is done by the 250 line switch statement that makes up the EmitFragment function. This function breaks up RegexTree "fragments" and converts them to a simpler RegexCode.
[…]
The reward for all this work is an integer array that describes the RegexCode "op codes" and their arguments. You can see that some instructions like "Setrep" take a string argument. These arguments point to offsets in a string table. This is why it was critical to pack everything about a set into the obscure string we saw earlier. It was the only way to pass that information to the instruction.
Decoding the code array, we see:
|
Instruction |
Op Code/Argument |
String Table Reference |
Description |
|
0 |
23 |
Lazily branch to the Stop instruction at offset 21. |
||
|
1 |
21 |
|||
|
2 |
31 |
Push our current state onto a stack in case we need to backtrack later. |
||
|
3 |
12 |
Perform a multi-character match of string table item 0 which is "http://". |
||
|
4 |
0 |
"http://" |
||
|
5 |
31 |
Push our current state onto a stack in case we need to backtrack later. |
||
|
6 |
2 |
Perform a set repetition match of length 1 on the set stored at string table position 1, which represents [^\s/]. |
||
|
7 |
1 |
"\x1\x2\x1\x2F\x30\x64" |
||
|
8 |
1 |
|||
|
9 |
5 |
Match the set [^\s/] in a loop at most Int32.MaxValue times. |
||
|
10 |
1 |
"\x1\x2\x1\x2F\x30\x64" |
||
|
11 |
2147483647 |
|||
|
12 |
32 |
Capture into group #1, the string between the mark set by the last Setmark and the current position. |
||
|
13 |
1 |
|||
|
14 |
-1 |
|||
|
15 |
3 |
Match Unicode character 47 (a '/') in a loop for a maximum of 1 time. |
||
|
16 |
47 |
|||
|
17 |
1 |
|||
|
18 |
32 |
Capture into group #0, the contents between the first Setmark instruction and the current position. |
||
|
19 |
0 |
|||
|
20 |
-1 |
|||
|
21 |
40 |
Stop the regex. |
We can now see that our regex has turned into a simple "program" that will be executed later.
You can read more about this process on Jeff Moser's blog. His article also covers
- Prefix Optimizations
- The Interpreter
- Backtracking
- Know Bugs