13
$\begingroup$

Mathematica's RegularExpression is based on Perl's PCRE library, which supports recursive regular expressions using (?R) (or, equivalently, (?0)).

This expression should match all palindromes:

DictionaryLookup[RegularExpression["(.)((?R)|.?)\\1"]]

However, it only finds three-letter palindromes. (It also matches two-letter palindromes, but there are none in the dictionary.) There's no error, so Mathematica seems to parse but discard the recursive pattern, leaving just (.).?\\1.

Does Mathematica disable some features of PCRE?

$\endgroup$
14
$\begingroup$

This response is really just an extended comment in support of the hypothesis that Mathematica is anchoring the pattern to the beginning and end of the string. In addition to the compelling behavioural observations reported in @2012rcampion's response, I submit the evidence of the following expressions:

ClearSystemCache[]
Trace[StringMatchQ["a", a_], TraceInternal->True]

trace output

We can see near the beginning of the trace output that the pattern is being anchored to StartOfString and EndOfString:

StringPattern`PatternConvert[StartOfString ~~ a_ ~~ EndOfString, None, 2]

Further down, we see the regular expression (?ms)\A(.)\z, again anchored to the string boundaries.

Unfortunately, this particular spelunking technique will not reveal the inner workings of RegularExpression[...] conversion. But it stands to reason that such conversions will follow the apparent anchoring policy exhibited in the simpler example.

We can see the lack of anchoring in contexts that would demand its absence, e.g.

StringCases["123AABCBAA123", RegularExpression["(.)((?R)|.?)\\1"]]
(* {"AABCBAA"} *)

StringReplace["123AABCBAA123", RegularExpression["(.)((?R)|.?)\\1"] -> "!!!"]
(* "123!!!123" *)

But even that last example is fragile. Consider what happens when we attempt to name the matched expression:

StringReplace["123AABCBAA123", r:RegularExpression["(.)((?R)|.?)\\1"] :> "("~~r~~")"]
(* "123AABCBAA123" *)

Mathematica has quietly introduced a capturing group that precedes ours, so \\1 is no longer referring to what we expect. This is readily confirmed by changing \\1 to \\2:

StringReplace["123AABCBAA123", r:RegularExpression["(.)((?R)|.?)\\2"] :> "("~~r~~")"]
(* "123(AABCBAA)123" *)

So, there is a moral to this story: assume that Mathematica is going to add elements to the regular expression. Thus, (?R) is not fully reliable since it matches the whole pattern, and the "whole pattern" is out of our control. We must content ourselves with using explicitly referenced subpatterns (e.g. (?1), (?2) etc). And even then, we must be wary of any implicit capturing groups or PCRE callbacks that Mathematica might add.

UPDATE - Named Patterns

As @2012rcampion points out in a comment, it is probably safest to use named patterns instead of numbered patterns to avoid conflicting with implicit capturing groups. PCRE in Mathematica appears to be configured so that only (?P) syntax is supported:

  • (?P<n>...) defines the pattern named n which matches ...
  • (?P=n) is a back-reference to the latest match for the pattern named n
  • (?P>n) is a reference to the pattern named n itself (e.g. for recursion)

If we adjust the pattern from the question to use named subpatterns, we get this:

DictionaryLookup[RegularExpression["(?P<a>(?P<b>.)((?P>a)|.?)(?P=b))"]]
(*
   {"aha", "aka", "bib", "bob", "boob", "bub", "CFC", "civic", "dad", "deed",
    "deified", "did", "dud", "DVD", "eke", "ere", "eve", "ewe", "eye", "gag",
    "gig", "huh", "kayak", "kook", "level", "ma'am", "madam", "mam", "MGM",
    "minim", "mom", "mum", "nan", "non", "noon", "nun", "oho", "pap", "peep",
    "pep", "pip", "poop", "pop", "pup", "radar", "redder", "refer", "repaper",
    "reviver", "rotor", "sagas", "sees", "seres", "sexes", "shahs", "sis",
    "solos", "SOS", "stats", "stets", "tat", "tenet", "TNT", "toot", "tot",
    "tut", "wow", "WWW"}
*)

This pattern:

  1. names the entire pattern a
  2. captures a character and calls it b
  3. either recurses into the entire pattern a or matches 0..1 character
  4. matches the character captured as b

This dodges the implicit string anchoring, and is relatively robust with respect to implicit captures.

UPDATE 2 - Expanded backreference syntax in v10.1+

As Alexey Popkov notes in a comment, later versions of Mathematica support new styles of backreference and subroutine reference. From version 10.1 onward, we can write our expression in Python, Perl or Oniguruma styles:

{ "(?P<a>(?P<b>.)((?P>a)|.?)(?P=b))"   (* Python, as above *)
, "(?<a>(?<b>.)((?&a)|.?)(\\k<b>))"    (* Perl *)
, "(?'a'(?'b'.)((?&a)|.?)(\\k'b'))"    (* Perl *)
, "(?<a>(?<b>.)((\\g<a>)|.?)(\\g{b}))" (* Oniguruma *)
, "(?<a>(?<b>.)((\\g'a')|.?)(\\g{b}))" (* Oniguruma *)
} // Map[DictionaryLookup @* RegularExpression] // SameQ

(* True *)
$\endgroup$
  • $\begingroup$ Nice "comment" -- +1. $\endgroup$ – Mr.Wizard Jan 29 '15 at 6:36
  • $\begingroup$ Seems the only truly safe way to handle regexes is to use named groups instead of numbered ones. $\endgroup$ – 2012rcampion Jan 29 '15 at 18:57
  • $\begingroup$ @2012rcampion Yes, good idea. I have updated my answer to give an example. I suppose this post has outgrown its original billing as just an extended comment... :) $\endgroup$ – WReach Jan 29 '15 at 21:27
  • $\begingroup$ As @Stitch notes in this post, "the (?<n>)/(?&n) syntax works as well as (?P<n>)/(?P>n)." $\endgroup$ – Alexey Popkov May 1 '17 at 5:50
  • $\begingroup$ @AlexeyPopkov It looks like the additional syntax forms were added in v10.1. I have updated my post. Thanks. $\endgroup$ – WReach May 1 '17 at 15:33
4
$\begingroup$

I realized I should probably double-check that the regular expression was correct... it worked on regex101, but I wanted to test it on my computer, just in case. Running the command:

grep -P '(.)((?R)|.?)\1' /usr/share/dict/words

resulted in matching every word that contained a palindrome inside it (e.g. Abbott -> bb). Of course, simply adding ^$ to match the beginning and end would't work, since the recursive match would also need to match the beginning and end (which never occurs), so we would end up with something equivalent to ^(.).?\1$ (seem familiar yet?). Also, it seems like you can't use -w with -P.

This, however, works fine:

grep -P '^((.)((?1)|.?)\2)$' /usr/share/dict/words

By changing the recursive part (now (?1)) to only recurse on the (new) first capturing group, we avoid trying to re-match the beginning and end (while \1 has been demoted to \2).

Then I went back to Mathematica and tried this:

DictionaryLookup[RegularExpression["((.)((?1)|.?)\\2)"]]

and it worked perfectly. So it seems to me that Mathematica prepends and appends ^ and $ to a regular expression used in a string pattern.

$\endgroup$
  • 1
    $\begingroup$ I believe we can see what Mathematica does with the pattern with this: StringPattern`PatternConvert[RegularExpression["((.)((?1)|.?)\\2)"]] output: {"(?ms)(?:((.)((?1)|.?)\\2))", {}, {}, Hold[None]}. Does the first part of that agree with what you're observing? $\endgroup$ – Mr.Wizard Jan 29 '15 at 4:06
2
$\begingroup$

Still looking at it, but (just in case) I think you don't need that pattern to detect palindromes:

DictionaryLookup[RegularExpression["^(?:(.)(?=.*(\\1(?(2)\\2|))$))*.?\\2?$"]]
(*
{"a", "aha", "aka", "bib", "bob", "boob", "bub", "CFC", "civic", \
"dad", "deed", "deified", "did", "dud", "DVD", "eke", "ere", "eve", \
"ewe", "eye", "gag", "gig", "huh", "I", "kayak", "kook", "level", \
"ma'am", "madam", "mam", "MGM", "minim", "mom", "mum", "nan", "non", \
"noon", "nun", "oho", "pap", "peep", "pep", "pip", "poop", "pop", \
"pup", "radar", "redder", "refer", "repaper", "reviver", "rotor", \
"sagas", "sees", "seres", "sexes", "shahs", "sis", "solos", "SOS", \
"stats", "stets", "tat", "tenet", "TNT", "toot", "tot", "tut", "wow", \
"WWW"}
*)
$\endgroup$
  • $\begingroup$ Doesn't quite answer the question (can you use (?R)?), but quite neat! Can you explain how this one works? I'm stuck on the nested reference... $\endgroup$ – 2012rcampion Jan 29 '15 at 3:31
  • $\begingroup$ @2012rcampion Googling for "PCRE palindrome" you'll find a lot of equivalent regexes. Some of them do work in Mathematica and others don't. I guess that depends on the PCRE version $\endgroup$ – Dr. belisarius Jan 29 '15 at 4:28
  • 1
    $\begingroup$ Explanation on StackOverflow, for those who are curious. $\endgroup$ – 2012rcampion Jan 29 '15 at 18:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.