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

[Coda Highland <chighland@...>]

On Fri, Feb 24, 2017 at 1:29 AM, Martin <eden_martin_fuhrspam@gmx.de> wrote:
> Hello all!
>
> I'm seeking for simply formulated and easy-coding string matching
> task which is impossible to solve via currently existing regular
> expressions handlers.
>
> (Indeed I'm seeking for a complete definition of task classes that
> regexps can't handle in principle.)

To actually answer the question, though, the canonical example of "not
possible with regexps" is balanced braces. A regexp cannot verify that
every ( has a matching ) in the right place, but it's trivially easy
to implement in imperative code with a loop and a counter.

It's also trivial with a more powerful language processing tool, such as LPeg.

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.

/s/ Adam