在正则表达式中创建第 n 层嵌套模式的算法

正如中所解释的可以使用正则表达式来匹配嵌套模式吗？，不可能创建正则表达式来匹配任意嵌套模式。但是是否有可能创建一个算法来生成第 n 级“嵌套”的正则表达式？

基本上，我想更换trim(whatever) with rtrim(ltrim(whatever))

我设法手动创建了 3 个级别（javascript 语法）：

level[1] = /\(([^()]*)\)/g
level[2] = /\(((?:[^()]*\([^()]*\))*[^()]*)\)/g
level[3] = /\(((?:(?:(?:[^()]*\([^()]*\))*[^()]*)*\((?:(?:[^()]*\([^()]*\))*[^()]*)*\))*[^()]*)\)/g

以下是一些测试数据：

1st(ddd) + 1st(ddd)
2nd(dd(d))
3rd(a(b) + (cd(h) + d(dfas) + zzz))
4th(a(b(c(d))))
8th(a(b(c(d(e(f(g()))))))

我知道在各个层面[^()]*需要替换为可以包含括号的非捕获组，但我不知道如何推广第 n 层的算法...

你可以从理论上更深入地思考：括号嵌套的匹配ndeep 只是匹配项周围的括号n-1或更深（至少有一个完全n-1 deep).

我们可以给出正则表达式的递归定义。让X[n]是精确嵌套的正则表达式n水平，以及Y[n]是包含任意级别嵌套的括号的字符串的正则表达式n水平，所以：

X[n] = \( (Y[n-2] X[n-1])+ Y[n-2] \)

Y[n] = [^()]* ( \( Y[n-1] \) [^()]* )*

with Y[0] = X[0] = [^()]*（无嵌套）和X[1] = \([^()]*\)。 （我还没有关心非捕获组等的细节，并且空格只是为了可读性。）

基于此编写算法应该很容易。

这些新的（相互递归性较低）定义中的正则表达式变得更长且更慢（它们是多项式而不是指数）。

Let l[n]的长度是X[n], and L[n]的长度是Y[n]，那么（常数项只是每项中的硬编码字符）：

L[n] = 19 + L[n-1] = 19*n + L[0] = 19*n + 6

l[n] = 3 + L[n-2] + l[n-1] + 2 + L[n-2] + 2
     = 7 + 2 * L[n-2] + l[n-1]
     = -57 + 38 * n + l[n-1]

具有适当的初始条件l[0] and l[1]。这种形式的递推关系有二次解，所以这只是O(n^2)。好多了。

（对于其他人，我之前有一个定义Y[n] was Y[n] = Y[n-1] | X[n];这个额外的递归意味着X正则表达式是O(2.41^n)，这很糟糕。）

（新定义Y是一个诱人的暗示，甚至可能有一种写作方式X是线性的n。我不知道，但我感觉有额外的限制X精确的长度意味着这是不可能的。）

下面是一些计算上述正则表达式的 Python 代码，您可以将其转换为 JavaScript，而不需要太麻烦。

# abbreviation for the No Parenthesis regex
np = "[^()]*"

# compute Y[n] from Y[n-1]
def next_y(y_n1):
    return np + "(?:\(" + y_n1 + "\)" + np + ")*"

# compute X[n] from X[n-1] and Y[n-2]
def next_x(x_n1, y_n2):
    return "\((?:" + y_n2 + x_n1 + ")+" + y_n2 + "\)"

# compute [X[n], Y[n], Y[n-1]]
# (to allow us to make just one recursive call at each step)
def XY(n):
    if n == 0:
        return [np, # X[0]
                np, # Y[0]
                ""] # unused
    elif n == 1:
        return ["\([^()]*\)", # X[1]
                next_y(np),   # Y[1]
                np]           # Y[0]

    x_n1, y_n1, y_n2 = XY(n-1) # X[n-1], Y[n-1], Y[n-2]

    return [next_x(x_n1, y_n2), # X[n]
            next_y(y_n1),       # Y[n]
            y_n1]               # Y[n-1]

# wrapper around XY to compute just X[n]
def X(n):
    return XY(n)[0]

# wrapper around XY to compute just Y[n]
def Y(n):
    return XY(n)[1]