3 ms·
Textbook regex algorithms assume that you're trying to determine whether a string matches an expression using a standard set of operators. Perl regular expressi
by jimrandomh 18y ago
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.
- jacobscott 18y agoSounds 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 http://en.wikipedia.org/wiki/Regular_language
- tl 18y agoThe 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.
- light3 18y agoI 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.
- alexk 18y ago"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.
- tome 18y agoWell 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&lpg=PA47&dq=finite+automaton+prime&source=bl&ots=0wWTv5AeBd&sig=6sOwOf6PNdQmcvI6QhWVMKLvKKA&hl=en&sa=X&oi=book_result&resnum=3&ct=result http://books.google.com/books?id=MDQ_K7-z2AMC&pg=PA47...
- llimllib 18y agoSipser's book is great for understanding this stuff, IMHO: http://books.google.com/books?id=eRYFAAAACAAJ&dq=sipser+theory&ei=SvqKSfnBHZb0ygS22KG6BQ http://books.google.com/books?id=eRYFAAAACAAJ&dq=sipser+...