在RegEx中创建第n级嵌套模式的算法

Question

正如可以使用正则表达式来匹配嵌套模式？,无法创建正则表达式来匹配任意嵌套模式.但是有可能创建一个能够生成n级"nesteness"正则表达式的算法吗？

基本上,我想,以取代trim(whatever)与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级 ......

Answer 1

您可以在理论上更多地考虑它:嵌套n深度的括号匹配只是围绕匹配n-1或不太深(至少一个n-1深度)的括号.

我们可以给出正则表达式的递归定义.让我们X[n]成为嵌套精确n级别Y[n]的正则表达式,并且是包含括号的字符串的正则表达式,其中任何级别的嵌套都达到n级别,因此:

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

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

有Y[0] = X[0] = [^()]*(无嵌套)和X[1] = \([^()]*\).(我还没有打扰非捕获组等细节,这些空间只是为了便于阅读.)

基于此编写算法应该非常简单.

来自这些新的(不太相互递归的)定义的正则表达得更慢得多(它们是多项式而不是指数).

让l[n]是的长度X[n],并且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]和l[1].这种形式的递归关系有二次解,所以这只是O(n^2).好多了.

(对于其他人,我有一个先前的定义Y[n]是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]