From: janis_papanagnou+ng@hotmail.com   
      
   On 05.07.2024 05:58, Lawrence D'Oliveiro wrote:   
   > On Fri, 5 Jul 2024 04:00:01 +0200, Janis Papanagnou wrote:   
   >>   
   >> [...] First, there's differences on the functional level; Perl   
   >> supports with their regexp library functions that are not part of the   
   >> Regular Expression grammar class, they exceed that class. The   
   >> consequence is that for that subset there's no O(N) (linear) complexity   
   >> guaranteed any more.   
   >   
   > Precisely. Many users of REs seem to feel it is useful to at least   
   > have the option of such extensions, and they are willing to pay that   
   > price.   
      
   There's two problems; one related to the Perl user, and one related   
   to the Perl implementor - if they're not aware about the line drawn   
   between regular and non-regular grammars. - The Perl user should be   
   informed about the complexities they buy with certain constructs   
   so that they are really "willing to pay" and not "pay a price that   
   they just did not expect". The implementor shall be aware that the   
   mechanism implemented should well differentiate between the two   
   domains of complexity for the respective functions, otherwise (as   
   happened in the past!) a common mechanism is implemented that even   
   for ordinary O(N) Regular Expressions non-linear complexities have   
   to be payed (unintentionally!) in certain, even simple, cases.   
      
   Note that this caveat is not Perl-specific; all pattern matchers   
   that support such functions, like e.g. back-references, should be   
   aware of that.   
      
   Janis   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)