How should I refactor this regex-reversal algorithm to allow repeating character classes?

I wrote this algorithm to generate a 开发者_StackOverflow社区string that a regex will match. Works really well, but it's still missing a couple features.

For example, when reversing \d{3} it first chooses a number, and then repeats that same number 3 times. I'd like to choose 3 different numbers.

I think the easiest way to solve this problem would be to push the \d onto the token list and evaluate it after the quantifier, rather than before.

That's all fine and dandy, but how about parsing things like (a(b)){2}|(c)\3. Assuming I'm following the "evaluate later" strategy, this would be tokenized into "(a(b)),(a(b)) or (c),\3". Which actually leads to a few problems. I can't just treat (a(b)) as a whole chunk and repeat it, I actually have to evaluate it sometime before \3 so that I can count the numbered references (ab is \1, b is \2, and c is \3).

The other problem is that if I actually repeat the strings like that, (a(b)),(a(b)) twice... then when I go to number it, it will be double-counted since I've lost the quantifier information. Unless I don't keep a list of strings, but rather a more complicated structure that indicates if its been counted or not. That, or I stuff it into the back-reference list immediately... but if I put it in unevaluated, it will need to be evaluated twice, which won't work, so I'd have to evaluate it before putting it into the back-reference list...

But then if I have something like (a|b){2}\1? I think the \1 refers to the last capture. So I can't evaluate (a|b) immediately and then throw the result in the back-reference list because it might be quantified... I can perhaps evaluate it immediately after quantifying.

I was thinking a different structure would help me with all this. But I still don't know how to factor in the quantifiers... I was just going to duplicate the nodes immediately when a quantifier is found, but I'm not sure if that's the best approach. Maybe if I add repeat-min, repeat-max variables onto the node?

I think you are at the limit of what a regular expression can do. I think what you need to do is classic parsing, generate a parse tree from your input string and then in a tree analysis step do the type of analyses you talk about in your post.