261–270 of 335 posts
"This regular expression has been replaced with a substring function." This should be the title of a book on software engineering.
This regular expression has been replaced with a substring function. God I wish all my bugs were this easy to fix and deploy
> 20,000+19,999+19,998+…+3+2+1 = 199,990,000Earlier quoted context omitted.
The key quote here is: "Regular expressions are one of computer science's shining examples of how using good theory leads to good programs ..." "Today, regular expressions have also become a shining example of how ignoring good theory leads to bad programs. The regular expression implementations used by today's popular tools are significantly slower than the ones used in many of those thirty-year-old Unix tools." The…
It's a little unfair to complain that they're slower than 30 year old regex engines when the old regex engines were so feature limited that they were nearly useless.
I wondered about this for some time. Simple regex (as in formal language theory) are matched in O(n) time by finite automaton. Extended regex like PCRE are more powerful, but most of the time are implemented by backtracking engines, where really bad regex pattern might go exponential, but even simple pattern as in postmortem can go O(n^2). Do implementations optimize simple regex patterns to O(n) matching? Even I wro…
Earlier quoted context omitted.
Sadly not much Thompson's libraries are implemented. I have tried to find one for F# but are just toy projects.
It doesn't actually take that many lines of code to implement a linear time NFA engine. Most of the code is actually in the regex compiler. That is, there are only a few actual "instructions" or node types in a regex engine (alternation, concatenation, etc.). The rest is just compiling the bizarre syntax to a those nodes/instructions. (And dealing with Unicode if you need that.) The whole awk implementation is 958 li…
Earlier quoted context omitted.
Is there a difference between greedy and non-greedy atoms?
In the order of searching and hence the match you can get, yes. In performance in the case of a non-match, no.
I remember the day I learned that Python's "re" module uses backtracking for non-extended regexes. My tests covered lots of corner cases in the regex logic, but were too short for me to notice the performance penalty. Luckily I only caused a partial outage in production. I actually got to talk to Raymond Hettinger (Python core team) about why re uses a potentially exponential-time algorithm for regexes when there is…
Earlier quoted context omitted.
Also implemented in the go stdlib https://golang.org/pkg/regexp
And it doesn't have any problems with this particular regex: https://play.golang.org/p/7UFkG3qrpS
This is what I saw on my Kindle 3 Keyboard:
This page contains the following errors:
error on line 2 at column 36: Extra content at the end of the document
Below is a rendering of the page up to the first error.
var __pbpa = true;