[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
- Subject: Re: Safe user-facing pattern matching.
- From: Martin <eden_martin_fuhrspam@...>
- Date: Fri, 28 Apr 2017 23:44:54 -0700
On 04/24/2017 12:12 PM, Gé Weijers wrote:
> Here's another problem:
>
> "^a*(%bab)(%bbc)c*$"
>
> This won't match if the number of b's is larger than the sum of the
> numbers of a's and c's. And "%bab" matches "a-+abb", for instance,
> whereas "a*" won't match any letters except 'a'.
I didn't catch problem, could you provide sample strings that matched
and not matched by pattern?
> So of course there's an ad-hoc linear time algorithm to match this, but
> the point is: can we come up with a matching algorithm that writes that
> ad-hoc algorithm automatically, i.e. can we solve the general case?
I think the more common questions besides this are
* does current regexps language is powerful enough to match all
possible strings that can be matched in linear time?
(probably not)
* does such language exists?
* could this language be constructed?
This recalls me Goedel's statement that on any complex enough
axioms basis may be assertions whose trueness or falseness
cannot be proved anyhow.
-- Martin