Re: [mind game] Seeking for simple task impossible via regexps

[Roberto Ierusalimschy <roberto@...>]

> Basically, regular expressions are incapable of retaining
> relationships between specific entities in the input string across
> distance. Every step of evaluation can be done knowing only what part
> of the regular expression has been evaluated so far and where you're
> currently sitting in the input string. If any more information than
> that is necessary, a regexp can't do it.

This is true for real regular expressions, not for what Perl and other
languages call "regular expressions". For instance, back references
clearly violate what real regular expressions can do. In particular,
because of back references, Perl's regexs are NP-complete: you can code
any NP problem as a regex plus a subject string (in polynomial time) and
Perl will solve the problem (not in polynomial time :-).

    http://perl.plover.com/NPC/NPC-3SAT.html

-- Roberto