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

Algorithm to create n-th level of nested patterns in RegEx

本文关键字：嵌套 模式 算法 正则表达式 创建      更新时间：2023-09-26

如正则表达式可用于匹配嵌套模式？中所述，无法创建正则表达式来匹配任意嵌套模式。但是，是否有可能创建一种算法来生成第 n 级"嵌套性"的正则表达式？

基本上，我想用rtrim(ltrim(whatever))替换trim(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 级的算法......

你可以

从理论上考虑一下：嵌套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的新定义是一个诱人的暗示，甚至可能有一种n线性的X书写方式。我不知道，我有一种感觉，对确切长度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]
相关文章：