http://www.perlmonks.org?node_id=806255


in reply to Re: Recursive substitution
in thread Recursive substitution

When you replied, my first thought—and rightly so, I think—was “Oh no, I've under-specified the problem again”, and I'm sorry for that.

However, I'd like now to offer a less panicked reply. You are certainly correct that I can do what I want with a loop, but we know that recursion can do whatever iteration can; and, in a sense, I'm trying to make that abstract understanding concrete in this particular sense. Sure, I could just say

sub f; sub f { $_[0] =~ s/^(a{1,3})(?=b)/$1a/ ? goto &f : return $_[0]; }
to get something that only a functional programmer could love; but I'm wondering if I can make the regex perform (or ‘simulate’, of whatever) the recursion for me, without explicit function calls.

‘Regular’ regexes don't have this power, but Perl regexes are, of course, not regular; and so I could have phrased my question vaguely as: is there any way for back-references and other assorted Perl tricks to let us get around this limitations of ‘regular’ regexes?

In order to avoid under-specifying again, let me give the real question that I am trying to answer, because of moritz's post: Are Perl regexes Turing complete without (?{}) and (??{})? If not, can I get by with some minimal amount of embedded code (like (?{pos = 0}), as you suggested)?

This started off as a reply to the parent, but, while I was (slowly) composing it, you posted another node. This is my response to that node, too. :-)