Convert recursive RegularExpression to StringExpression?

Consider the following expression for matching balanced brackets:

StringPosition["[[hello][[hi]][hey]ahoy][]", RegularExpression@"(?P<0>\$([^\$$\$]|(?P>0))*\$$)"]

{{1, 24}, {2, 8}, {9, 14}, {10, 13}, {15, 19}, {25, 26}}


It uses features for recursive pattern matching. This answer by WReach explains the general structure using similar example. This comment by Leonid Shifrin states that recursive StringExpression is possible but its performance is worse than StringExpression's. And this question by Mr.Wizard shows that StringExpression can perform faster than RegularExpression.
So I'm eagerly interested if it's possible to build recursive StringExpressions, and if true, then how? What have I tried:

bb := "[" ~~ (Except@{"[", "]"} | bb) ... ~~ "]";
StringPosition["[[hello][[hi]][hey]ahoy][]", bb]

\$RecursionLimit::reclim: Recursion depth of 1024 exceeded. >>


Ok, that was wrong, I think I know why, but I do not see another approach. :|

2 Answers

TL;DR

Recursive expressions are possible using native string patterns in Mathematica, but can be difficult to write correctly, and might perform very poorly.

Difficult To Write?

As @Leonid's solution shows, it is possible to express recursive patterns without resorting to regular expressions. However, recursive string patterns can be more difficult to construct.

Consider the pattern bb from @Leonid's response:

bb = "[" ~~ ((Except["[" | "]"] ...) | (patt__ /; StringMatchQ[patt, bb])) ~~ "]";


This is not actually equivalent to the original regular expression as can be seen from the presence of the string position {1, 24} in the original answer, but its absence when using bb. Here is a smaller example that demonstrates the problem:

re = RegularExpression@"(?P<0>\$([^\$$\$]|(?P>0))*\$$)";

StringPosition["[[x][y]]", re]
(* {{1, 8}, {2, 4}, {5, 7}} *)

StringPosition["[[x][y]]", bb]
(* {{2, 4}, {5, 7}} *)


The outermost match is lost because bb does not allow multiple occurrences of the recursive pattern:

StringMatchQ["[[x][x]]", re]
(* True *)

StringMatchQ["[[x][x]]", bb]
(* False *)


That seems to be easy to fix...

bbb = "[" ~~ (Except["[" | "]"] | (patt__ /; StringMatchQ[patt, bbb])) ... ~~ "]";

StringMatchQ["[[x][x]]", bbb]
(* True *)


... but perhaps it is not so easy:

StringMatchQ["[[x][y]]", re]
(* True *)

StringMatchQ["[[x][y]]", bbb]
(* False *)

StringPosition["[[x][y]]", bbb]
(* {{2, 4}, {5, 7}} *)


Expressing Recursive Repetition is Hard

The problem is that once we name a subpattern patt, its repetition using ... requires that each submatch be the same. That is why [[x][x]] matches, but [[x][y]] does not.

In normal (non-string) pattern-matching, the work-around is simple. We would use a pattern test instead of a condition, like this: __?(StringMatchQ[#, bbb]&). This allows the match to remain anonymous, and each repetition to have a different value. Unfortunately, the documentation for string patterns tells us that pattern tests are applied to each matched character separately whereas we want to test the entire match. Consider:

StringMatchQ["a", __?(# === "a" &)]
(* True *)

StringMatchQ["abc", __?(# === "abc" &)]
(* False *)

StringMatchQ["aaaaaa", __?(# === "a"&)]
(* True *)


Thus the pattern-test solution is closed to us. It means that we must express independent repetition directly as recursion:

x1 = "[" ~~ (a___ /; StringMatchQ[a, x2]) ~~ "]";

x2 = Except["["|"]"]... ~~
("" | ((a:("["~~__) /; StringMatchQ[a, x1]) ~~ (b___ /; StringMatchQ[b, x2])));


This fixes the observed problems:

StringMatchQ["[[x][y]]", x1]
(* True *)

StringPosition["[[x][y]]", x1]
(* {{1, 8}, {2, 4}, {5, 7}} *)


BUT...

Say Goodbye to PCRE Optimization

These patterns are phenomenally slow to run. Consider the original question:

StringPosition["[[hello][[hi]][hey]ahoy][]", x1] // Timing
(* {99.435037, {{1, 24}, {2, 8}, {9, 14}, {10, 13}, {15, 19}, {25, 26}}} *)


99 seconds! Why is it so slow, even when we took great care to ensure that each matching path would consume at least one character?

Normally, PCRE compiles a regular expression into a highly efficient finite state machine that optimizes back-tracking. It identifies common back-tracking states and eliminates the need to constantly revisit the same potential matches over and over again. However, when we use conditions in string patterns, we force PCRE to call back into Mathematica to evaluate those conditions. The PCRE compiler has no information about the nature of those callback expressions, so it cannot determine whether a backtracking path can be abandoned. The net result is that all possible backtracking paths need to be explored, a process which can exhibit exponential time complexity. This is why our revised pattern is so slow. 100 seconds for a 26 character string -- imagine how long it would take to scan a text file!

Summary

To summarize...

It is possible to implement recursive patterns using native Mathematica string patterns, but such usage:

1. can be more difficult to express (an ironic statement given the "write only" nature of regular expressions), and
2. might block the PCRE optimization strategies, causing poor performance.
• Vey nice! +1 of course. Some bits and pieces of this were on the back of my mind too, but not in such coherent form. – Leonid Shifrin Feb 7 '15 at 12:48
• Thank you, WReach, I appreciate your time and effort! I've decided not to use recursive StringExpression in my program, since it's indeed inefficient in this case. – Dan Oak Feb 7 '15 at 21:18

NOTE

Apparently, the solution below isn't quite right, as demonstrated by WReach in his answer. It is, therefore, better to treat this one as a simple illustration of the idea, while the correct one is given by the answer of WReach.

In your approach, you need delayed evaluation of the inner pattern bb, to avoid infinite recursion. Here is one way:

bb = "[" ~~ ((Except["[" | "]"] ...) | (patt__ /; StringMatchQ[patt, bb])) ~~ "]";


So that

StringPosition["[[hello][[hi]][hey]ahoy][]", bb]

(* {{2, 8}, {9, 14}, {10, 13}, {15, 19}, {25, 26}} *)


In this case, delayed evaluation has been achieved by using Condition. Therefore, the internal pattern bb is only evaluated when the matching reaches that point. So, the evaluation of the inner pattern is delayed from the point when we define bb until the point when matching actually happens, and this does not therefore lead to infinite recursion.

• +1 btw I think patt__ would be enough because of the necessary "[" and "]"? – Silvia Feb 5 '15 at 10:13
• @Silvia Yes, you're right. It actually crossed my mind, but I was too lazy to correct. Since you noted this, will make a correction. Thanks for the upvote. – Leonid Shifrin Feb 5 '15 at 10:14
• Thank you, Leonid! :) – Dan Oak Feb 6 '15 at 12:55
• @DanyloDubinin Was glad to help. Thanks for the accept. – Leonid Shifrin Feb 6 '15 at 13:52
• @Leonid +1. I started to write a comment pointing out the absence of {1, 24} from the solution, along with a revised expression to correct it. The revision proved to be difficult to find (for me, at least). So I have posted a TL;DR response describing my woes. Perhaps you (or someone else) can spot the flaw in my reasoning and present a simple solution. – WReach Feb 7 '15 at 7:39