Date: Tue, 16 Jul 2013 10:00:53 -0400 From: Rich Felker <dalias@...ifal.cx> To: musl@...ts.openwall.com Subject: Re: embedded newbies site. On Tue, Jul 16, 2013 at 07:50:29AM -0400, LM wrote: > design. For instance, there are some negative mentions about the PCRE > library, but when I tried to track down the cons for using it, I only found > dated performance comparisons showing how poorly it worked if you don't use > the newer JIT implementation. What might be a positive for a system that's The whole concept of regular expressions is that they're regular, meaning they're matchable in O(n) time with O(1) space. PCRE (the implementation) uses backtracking for everything, giving it exponentially-bad performance (JIT cannot fix this), and PCRE (the language) has a lot of features that are fundamentally not regular and thus can't be implemented efficiently. Also, the behavior of some of the features (e.g. greedy vs non-greedy matching) were not designed intentionally but just arose out of the backtracking implementation, and thus don't make a lot of sense unless you think from the standpoint of such an implementation. Aside from performance, PCRE is harmful to CS education because it undermines the whole definition of "regular" when students learn a sense of "regular expression" that's not actually regular. Of course this can be worked around if the instructor teaches this issue well when teaching PCRE, but I think normally PCRE is just taught as a tool without any theoretical background. Rich
Powered by blists - more mailing lists
Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.