Вопрос по regex, algorithm, recursion, javascript – Алгоритм создания n-го уровня вложенных шаблонов в RegEx

3

Как объяснено вМожно ли использовать регулярные выражения для сопоставления с вложенными шаблонами?, невозможно создать регулярное выражение для сопоставления с произвольным вложенным шаблоном. Но возможно ли создать алгоритм, который бы генерировал регулярное выражение n-го уровня «нестабильности»?

в основном я хочу заменитьtrim(whatever) сrtrim(ltrim(whatever))

мне удалось создать 3 уровня вручную (синтаксис javascript):

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

Вот некоторые тестовые данные:

<code>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()))))))
</code>

я знаю это на каждом уровне[^()]* должна быть заменена группой без захвата, которая может содержать круглые скобки, но я не уверен, какgeneralize the algoritm for n-th level...

Ваш Ответ

1   ответ
6

совпадение для круглых скобок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]
@deathApril, я просто значительно улучшил ответ, изменив определениеY, Это уменьшает размер регулярного выражения дляn=10 от ~ 45000 до ~ 1500 (так даже для10 O () делает регулярное выражение огромным!). (Я понимаю, что вы не беспокоитесь о большихn, но я нахожу этот вопрос очень интересным (спасибо, что задали его!), поэтому я все равно делаю анализ.)
рад слышать, что это так интересно для вас - меньше работы для меня;)) с python все в порядке, я просто запустлю его и использую полученное регулярное выражение в макросе notepad ++ (или я создам для этого простое веб-приложение, если другие члены команды захотят использовать это) - я приму после того, как я проверю это немного больше;) Aprillion
@deathApril, и теперь есть некоторый код (хотя Python, а не Javascript).
спасибо, O () не проблема, я надеюсь, что никто не будет использовать более 10 вложенных скобок, я взгляну на это в выходные дни :) Aprillion

Похожие вопросы