3 ms·

Another problem with regular expressions is using them inappropriately. If you have elaborate, convoluted regular expressions, it's usually a sign that you shou

Another problem with regular expressions is using them inappropriately. If you have elaborate, convoluted regular expressions, it's usually a sign that you should try using a parser as well. Regular expressions cannot maintain context (though some extensions have ad hoc extensions for doing this inefficiently and in a limited fashion; apparently the problem is NP-complete), so doing things like balancing parenthesis or HTML tags in a recursive expression is impossible. Using regular expressions to break the input text into tokens ("tokenizing" or "lexing") and then matching the sequence of tokens according to a grammar ("parsing") is usually much simpler. The two-phase approach often factors out some complexity - only the lexer needs to care about things like whitespace, for example. While most compiler textbooks cover lexing and parsing, I particularly recommend Andrew Appel's _Modern Compiler Implementation in ML_ and Niklaus Wirth's _Compiler Construction_ (free online, http://www-old.oberon.ethz.ch/WirthPubl/CBEAll.pdf http://www-old.oberon.ethz.ch/WirthPubl/CBEAll.pdf). More recommendations on learning parsing here: http://news.ycombinator.com/item?id=1820858 http://news.ycombinator.com/item?id=1820858

amalcon 16y ago
There are exactly two reasons that regular expression parsing "needs" to be slow. First, we have the "ad hoc extensions for doing this inefficiently and in a limited fashion", and second, we have subexpression capture. Backreferences (the former) are generally only useful in situations where you really ought to be using some other construct. The backreferences are the part that's NP-complete. Subexpression capture is great, and at least that can be done in (low-order) polynomial time with a nondeterministic automaton approach. So really, the only problem is the backreferences.

amalcon 16y ago

There are exactly two reasons that regular expression parsing "needs" to be slow. First, we have the "ad hoc extensions for doing this inefficiently and in a limited fashion", and second, we have subexpression capture. Backreferences (the former) are generally only useful in situations where you really ought to be using some other construct. The backreferences are the part that's NP-complete. Subexpression capture is great, and at least that can be done in (low-order) polynomial time with a nondeterministic automaton approach. So really, the only problem is the backreferences.