BT

Facilitating the Spread of Knowledge and Innovation in Professional Software Development

Write for InfoQ

Topics

Choose your language

InfoQ Homepage News Jeff Moser's How .NET Regular Expressions Really Work

Jeff Moser's How .NET Regular Expressions Really Work

This item in japanese

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:

Index

Instruction

Op Code/Argument

String Table Reference

Description

0

Lazybranch

23

 

Lazily branch to the Stop instruction at offset 21.

1

 

21

 

2

Setmark

31

 

Push our current state onto a stack in case we need to backtrack later.

3

Multi

12

 

Perform a multi-character match of string table item 0 which is "http://".

4

 

0

"http://"

5

Setmark

31

 

Push our current state onto a stack in case we need to backtrack later.

6

Setrep

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

Setloop

5

 

Match the set [^\s/] in a loop at most Int32.MaxValue times.

10

 

1

"\x1\x2\x1\x2F\x30\x64"

11

 

2147483647

 

12

Capturemark

32

 

Capture into group #1, the string between the mark set by the last Setmark and the current position.

13

 

1

 

14

 

-1

 

15

Oneloop

3

 

Match Unicode character 47 (a '/') in a loop for a maximum of 1 time.

16

 

47

 

17

 

1

 

18

Capturemark

32

 

Capture into group #0, the contents between the first Setmark instruction and the current position.

19

 

0

 

20

 

-1

 

21

Stop

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

Rate this Article

Adoption
Style

BT