11–20 of 39 posts
I sometimes think regular expressions being greedy is a bad default.
a="xxx" b="yyy"
I sometimes think regular expressions being greedy is a bad default.
I sometimes think regular expressions being greedy is a bad default.
Yeah, almost never what I want. Like if I have some "unstructured" data like a="xxx" b="yyy" And I do a regex like /a="(.*)"/ I'd like it to match xxx, not until the end " after yyy. Always have to do weird tricks like /a="([^"]*)"/
Why Perl version of regexps returns near-instantly for same regexp ? I tested few other on regex101.com and none of them ran longer than a millisecond or two
>On my laptop it takes about 20ms to do the search above with 16 characters - but by doubling the input string size to 32 characters, it takes over 12 minutes to finish. Exponential running time really does suck.
I checked with 32 characters on regex101, and it says "Match 1 halted after 119986 step(s)" when you click the debug icon (click the message above the regex input box).
I sometimes think regular expressions being greedy is a bad default.
Yeah, almost never what I want. Like if I have some "unstructured" data like a="xxx" b="yyy" And I do a regex like /a="(.*)"/ I'd like it to match xxx, not until the end " after yyy. Always have to do weird tricks like /a="([^"]*)"/
The article starts with the famous quote by Jamie Zawinski: Some people, when confronted with a problem, think ‘I know, I’ll use regular expressions.’ Now they have two problems. It then goes on to discuss the perils of regular expressions, when they encounter unanticipated data and run into catastrophic backtracking because of greedy expressions. The article is short and to the point.
More on that quote: https://blog.codinghorror.com/regular-expressions-now-you-ha... >... there's a bit more to the story than that, as evidenced by Jeffrey Friedl's exhaustive research on the Zawinski quote. Zawinski himself commented on it. Analyzing the full text of Jamie's posts in the original 1997 thread, we find the following: >Perl's nature encourages the use of regular expressions almost to the exclusion of a…
I like Perl, but that is true. Despite the pretty rich set of built-ins, for example, there's not a top-level string replace function. You have to roll your own with index and substr.
Earlier quoted context omitted.
Yeah, almost never what I want. Like if I have some "unstructured" data like a="xxx" b="yyy" And I do a regex like /a="(.*)"/ I'd like it to match xxx, not until the end " after yyy. Always have to do weird tricks like /a="([^"]*)"/
Ah, the /"([^"]*)"/ trick. It was one of those small, obvious in retrospect but not that easy to invent on your own, useful things I was taught at my first job among others such as "if in a unit test you need a future date, use year 3001".
For another real-world example, see "Details of the Cloudflare outage on July 2, 2019" [1] Python `re` module now supports possessive quantifiers and atomic grouping (I wrote a blog post here [2]). So, for example, `(a+|\w+)*+:` instead of `(a+|\w+)*:` will avoid such catastrophic behavior. [1] https://blog.cloudflare.com/details-of-the-cloudflare-outage... [2] https://learnbyexample.github.io/python-regex-possessive…
https://vtechworks.lib.vt.edu/bitstream/handle/10919/98593/D...
For another real-world example, see "Details of the Cloudflare outage on July 2, 2019" [1] Python `re` module now supports possessive quantifiers and atomic grouping (I wrote a blog post here [2]). So, for example, `(a+|\w+)*+:` instead of `(a+|\w+)*:` will avoid such catastrophic behavior. [1] https://blog.cloudflare.com/details-of-the-cloudflare-outage... [2] https://learnbyexample.github.io/python-regex-possessive…
(disclosure: I work for Doyensec)