Recursive Regexes

…have been troubling me for days now.

The Regex engine maintains a stack, so regular expressions in Perl can be constructed recursively. For instance,

$paren = qr/ \( ( [^()]+ # Not parens | (??{$paren}) # Another balanced group )* \) /x;

matches a string if parentheses in the string are paired correctly. (Taken from Regexp Power.)

That funny (??{}) (apparently) keeps qr/ / from interpolating the variable in the funny brackets when the expression is compiled- saving the interpolation for when the matching is carried out, which sends it recursing deeper.

So here’s the question:

A palindrome is a nested set of palindromes. That is, a [ palindrome – {first character, last character} ] is a palindrome again, and so forth until there is (i) nothing, or (ii) one character left. Cases (i) and (ii) are palindromes by definition. So how do you write a regex that matches any palindrome?

The best I could do was:

$palin = qr/ (.)? #Any character or no character, captured (??{$palin})? #A palindrome, not interpolated yet \1 #Character captured in line 1 /x;

But this doesn’t work. Any ideas?

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s