How .NET Regular Expressions Really Work

http://www.moserware.com/2009/03/how-net-regular-expressions-really-work.html

by moserware • 17 years ago

62 6 17 years ago

likpok• 17 years ago

I had always suspected that regular expressions were not, in fact, regular, and now it is obvious.

This is in fact why regexs are slow. The old Thompson NFA is orders of magnitude faster than current libraries. However, it can only recognize regular languages.

I wonder, are there any libraries for CFG's, that allow specifying the productions?

nuclear_eclipse2• 17 years ago

Flex and Bison come to mind, but they are tailored more for the point of generating new language parsers and compilers. You could, however, attempt to use them in another fashion, considering they are open source (BSDish and GPL respectively).

Although I have looked, I've been unable to find much more than a bunch of whitepapers and various incomplete projects.

defunkt• 17 years ago

it was refreshing to see that the .NET regular expression engine was written entirely in C#

Pretty awesome that he can do this sort of digging in his language of choice.

euroclydon• 17 years ago

This is a great article! Thanks for taking the time to write it.

dfj225• 17 years ago

If you do an investigation / code digging similar to this with Microsoft code (or any code that contains a similar license), could this create legal issues if later you decide to write open source code that operates similarly or performs a similar function?

This is just a random thought that I'm curious about. I'm not trying to troll the topic.

nuclear_eclipse2• 17 years ago

I believe that's the reason that the Mono project specifically disallows contributions from anyone who has laid eyes on any of the .Net source code, although it's still a somewhat gray area AFAIK.

How .NET Regular Expressions Really Work

Related Stories