How I fixed a bug in Atom

Post by mwcampbell » Fri, Jan 29, 2016, 9:50 PM UTC

pcwalton wrote: post #154

cyphar wrote: post #10

First of all, this is why people should stop adding stupid features to regular expressions. A sane regular expression implementation has no pathological cases. DFA generation can be done in O(n^2) from memory (in the absolute worst case O(n) is average), and matching can't be worse than O(m) or similar (n is the size of the regex and m the size of the string). When you add features like back references and recursive…

You don't need to throw out your favorite regex features—backreferences aren't stupid, they're useful and usually harmless! Rather, a good regex engine should start with recursive backtracking (ideally JIT'd) and fall back to the Thompson NFA if the regex supports it and the recursive backtracking approach is taking too long. Think of it like the adaptive sorting algorithms that switch between insertion sort and quic…

Post by paulddraper » Fri, Jan 29, 2016, 10:35 PM UTC

rspeer wrote: post #135

jerf wrote: post #98

Earlier quoted context omitted.

"I don't always want to spend insane amounts of time writing full AST parsers." This is an effect of the language, not the problem space. Backtracking REs make it very easy to write bad code, and then most languages make writing the parsing code hard. If you're in a language that makes parsing code easier, like Haskell, then the tradeoff isn't anywhere near so bad. I don't mention Haskell just because it's the trendy…

Haskell is, in fact, a really good way to write parser code. That's the main thing I use Haskell for. But how are you suggesting that Haskell could solve the problem of letting CoffeeScript plugins express which text they should apply to in a CoffeeScript text editor?

Post by cyphar » Sat, Jan 30, 2016, 3:04 AM UTC

wfunction wrote: post #20

cyphar wrote: post #10

First of all, this is why people should stop adding stupid features to regular expressions. A sane regular expression implementation has no pathological cases. DFA generation can be done in O(n^2) from memory (in the absolute worst case O(n) is average), and matching can't be worse than O(m) or similar (n is the size of the regex and m the size of the string). When you add features like back references and recursive…

> The conversion from DFA to NFA [...] I believe you mean NFA to DFA. > [...] would require O(n^2) in that case I believe you mean O(2^n). https://en.wikipedia.org/wiki/Powerset_construction#Complexi...

Post by cyphar » Sat, Jan 30, 2016, 5:41 AM UTC

jeffbr13 wrote: post #71

Isn't arbitrarily-long nesting or matching any sort of palindrome, where you count up and down, the classic case of something you should never do with a regex, because they're finite automata? People don't build parsers because of masochism, but because regular expressions are provably insufficient to capture things like nesting. You need to go at least one level up on the Chomsky hierarchy[1] to pushdown automata fo…

Post by jerguismi » Sat, Jan 30, 2016, 1:40 PM UTC

jandrese wrote: post #128

pilif wrote: post #110

In general, when you are working on a problem and you think "let me use a regex for that" and then you come up with ^\s*[^\s()}]+(? [^()]*\((?:\g |[^()]*)\)[^()]*)*[^()]*\)[,]?$ to solve your problem, then you have IMHO come across a problem which you should not be solving using regular expressions. Case in point is counting and balancing parentheses which is very easily done using a single loop over the string in qu…

The worst part is that as soon as he mentioned regular expressions I knew exactly what the problem was. Regexes are powerful and useful but also dangerous. People who don't thoroughly understand them and try to get fancy often run into problems like this. In general you shouldn't be using them to parse a computer language anyway, it is something you should be using a tokenizer/parser for.