> But when programmers talk about “regular expressions” they aren’t talking about formal grammars. They are talking about the regular expression derivative which their language implements. And those regex implementations are only very slightly related to the original notion of regularity.
That's why we call those derivatives "Franken-xpressions". They can take exponential time in the worst case. See "Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...)" (http://swtch.com/~rsc/regexp/regexp1.html).
The additional power of Franken-xpressions comes at a cost.
For general purpose parsing, I suggest using a parser combinator library.
That's why we call those derivatives "Franken-xpressions". They can take exponential time in the worst case. See "Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...)" (http://swtch.com/~rsc/regexp/regexp1.html).
The additional power of Franken-xpressions comes at a cost.
For general purpose parsing, I suggest using a parser combinator library.