Regular Expression Matching Can Be Simple And Fast

Re:Regular Expression Matching Can Be Simple And Fast by jimrandomh on Wednesday February 04, 2009 @11:32PM (#467096)

Textbook regex algorithms assume that you're trying to determine whether a string matches an expression using a standard set of operators. Perl regular expressions have to match text to subexpressions, rather than just return a yes/no answer, and have a greatly expanded set of operators, some of which are completely incompatible with the usual NFA and DFA algorithms. It even lets you drop arbitrary perl code into the middle of a regex. You can easily write a perl regex that is NP-complete to match. You can't do that with the simplified regex language that textbooks talk about.

[ Parent | on HN ]

Re:Regular Expression Matching Can Be Simple And Fast by tl on Thursday February 05, 2009 @12:08AM (#467126)

The article offers a simple solution here: if the regex fits the model (no backtracking, no arbitrary code, etc..._), use the linear-scaling algorithm described. Else, use the slow, exponential one. Perl (according to the article) is not doing this.

[ Parent | on HN ]

Re:Regular Expression Matching Can Be Simple And Fast by light3 on Thursday February 05, 2009 @12:21AM (#467139)

I have to say the reason I spent so much time using perl is because of its ease in handling text and such strength in regular expressions, which are fascinating. I now use regular expressions when ever I can, and I think in most cases it saves you a lot of time.

I still remember when I was young and starting to work with Perl, I found this zip file with the whole bible represented as (I think) 1 html file, with chapter / verse tags. So I posed this question to an online friend who was then studying in Germany, he had built many cgi sites (he made our clan page for Earth2025 if anybody still remembers that game) with perl and was very good at it. About a day later he icq'ed me this 1 page perl script, which created file index positions for all the chapters and verses. This was such an ingenious solution which made seeking a particular chapter/ verse range extremely fast, and all done with text files and perl.

[ Parent | on HN ]

Re:Regular Expression Matching Can Be Simple And Fast by jacobscott on Wednesday February 04, 2009 @11:52PM (#467112)

Sounds about right. Wikipedia has more information on regular languages, which computer scientists know a lot about, and of which Perl regex is a superset:

http://en.wikipedia.org/wiki/Regular_language

[ Parent | on HN ]

Re:Regular Expression Matching Can Be Simple And Fast by alexk on Thursday February 05, 2009 @01:21AM (#467203)

"some of which are completely incompatible with the usual NFA and DFA algorithms" - It would be nice if you pointed to some article/resource giving more info on this.

[ Parent | on HN ]

Re:Regular Expression Matching Can Be Simple And Fast by tome on Thursday February 05, 2009 @06:05AM (#467561)

Well here's a starter for you. Using enhanced regex syntax you can match a language containing strings of prime length. On the other hand (using the pumping lemma[1]) you can prove that that set is not regular, hence not detectable by a standard regex.

[1] http://books.google.com/books?id=MDQ_K7-z2AMC&pg=PA47...

[ Parent | on HN ]

Re:Regular Expression Matching Can Be Simple And Fast by llimllib on Thursday February 05, 2009 @09:40AM (#467846)

Sipser's book is great for understanding this stuff, IMHO: http://books.google.com/books?id=eRYFAAAACAAJ&dq=sipser+...

[ Parent | on HN ]