3 ms·
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,
by jeffbr13 11y ago
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 for that.
More importantly, shouldn't SOMEBODY working on a text editor know and recognise this sort of thing? I'm all for the hacker mentality of shipping, reducing developer time instead of machine time, using what you know, but this is the sort of hacky fix that just pushes the problem further down the line.
Great write-up though, very enjoyable read!
- mediumdeviation 11y agoYou forgot your [1] URL
- jdmichal 11y agoI found this on the ground. Did you drop it? [1] https://en.wikipedia.org/wiki/Chomsky_hierarchy#The_hierarchy https://en.wikipedia.org/wiki/Chomsky_hierarchy#The_hierarch...
- revelation 11y agoI guess NFA is the classic regex, but most implementations are vastly more powerful through the introduction of backtracking and back references. In any case, a regex is hilariously unsuitable for the purpose here. It's obtuse, it has terrible corner case performance (as noticed here), it probably took vastly longer to write than a simple loop and apparently it isn't even correct.
- cyphar 11y ago> 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? Yes, but features like backtracking and backreferences (or recursive referencing) make regex implementations non-regular regular expressions. That comes with a whole heap of issues (pathologically exponential complexities in any circumstance where backtracking is inolved).