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

[Coda Highland <chighland@...>]

On Fri, Feb 24, 2017 at 9:18 AM, Roberto Ierusalimschy
<roberto@inf.puc-rio.br> wrote:
>> In layman's terms, this means that there are languages that LPeg can
>> parse that PCRE cannot. (For example, PCRE cannot parse the balanced
>> parentheses language without calling out to Perl code.)
>
> PCRE (and the Perl engine) can parse the balanced parentheses
> language. Check for "(?R)".
>
> -- Roberto

Oh. Huh. I actually went and tried to research it before I posted
that, and I hadn't found a solution using that technique. TIL, I
guess! Though that's only supported by Perl, Ruby, and libpcre, not by
other PCRE-style implementations like Javascript and Python.

I don't know if there's a concrete answer to whether a regular
language with recursion is as powerful as a nondeterministic pushdown
automaton. My intuition says that they're equivalent to deterministic
PDAs, which are known to be strictly weaker than NPDAs, but in terms
of real-world parsing tasks I'm not certain if that ends up mattering.

/s/ Adam