[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
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.
