我应该如何重构这个regex反转算法以允许重复字符类？

Question

我编写这种算法是为了生成一个正则表达式将匹配的字符串。工作非常好，但它仍然缺少一些功能。

例如，当反转\d{3}时，它首先选择一个数字，然后重复这个数字3次。我想选择三个不同的号码。

我认为解决这个问题的最简单的方法是将\d推到令牌列表中，并在量词之后而不是之前对其进行评估。

这一切都很好，但是解析像(a(b)){2}|(c)\3这样的东西怎么样？假设我遵循“评估稍后”策略，这将被标记为"(a(b))，(a(b))或(c)，\3“。这实际上导致了一些问题。我不能仅仅把(a(b))作为一个整体来处理并重复它，实际上，我必须在\3之前对它进行评估，以便计算编号的引用(ab是\1，b是\2，c是\3)。

另一个问题是，如果我真的重复这样的字符串，(a(b))，(a(b))两次.然后，当我对它进行编号时，它将被加倍计数，因为我丢失了量词信息。除非我没有保存一个字符串列表，而是一个更复杂的结构来表示它是否被计数。或者我马上把它塞到后面的参考名单里.但是如果我把它放在未评估的地方，它将需要被评估两次，这是行不通的，所以我必须在把它放到后面的参考列表之前对它进行评估……

但是如果我有类似(a|b){2}\1的东西呢？I https://stackoverflow.com/questions/4381762/how-do-repeated-disjuncts-with-back-references-work \1指的是最后一次捕获。因此，我不能立即评估(a|b)，然后将结果放到后引用列表中，因为它可能是量化的.我也许可以在量化后立即评估它。

我在想不同的结构会帮我做这一切。但我还是不知道如何考虑量词.当找到量化词时，我打算立即复制节点，但我不确定这是否是最好的方法。如果我把重复-min，重复-max变量添加到节点上，可能会怎么样？

Answer 1

我认为您处于正则表达式所能做的极限。我认为您需要做的是经典的解析，从您的输入字符串生成一个解析树，然后在树分析步骤中执行您在文章中谈到的分析类型。