Рекурсивный шаблон в регулярном выражении

Question

Это очень сильно связано с регулярным выражением для соответствия внешним скобкам, однако, я специально хочу знать, как или возможно ли сделать рекурсивный шаблон этого регулярного выражения? Я еще не нашел пример на python, использующий эту стратегию, поэтому думаю, что это должен быть полезный вопрос!

Я видел некоторые утверждения, что рекурсивные шаблоны могут использоваться для соответствия сбалансированным круглым скобкам, но нет примеров использования пакета регулярных выражений python (Примечание: re не поддерживает рекурсивный шаблон, вам нужно использовать регулярное выражение).

Одним из утверждений является то, что синтаксис b(?:m|(?R))*e где:

b это то, что начинает конструкцию, m это то, что может произойти в середине конструкции, и e это то, что может произойти в конце конструкции

---

Я хочу извлечь совпадения для внешних скобок в следующем:

"{1, {2, 3}} {4, 5}"
["1, {2, 3}", "4, 5"]  # desired

Обратите внимание, что это легко сделать то же самое для внутренних скобок:

re.findall(r"{([^{}]*)}", "{1, {2, 3}} {4, 5}")
['2, 3', '4, 5']

(В моем примере я использовал finditer (более подходящих объектов), см. Здесь.)

Поэтому я надеялся, что следующее или какое-то изменение подойдет:

regex.findall(r"{(:[^{}]*|?R)}", "{1, {2, 3}} {4, 5}")
regex.findall(r"({(:[^{}]*|?R)})", "{1, {2, 3}} {4, 5}")
regex.findall(r"({(:.*|(?R))*})", "{1, {2, 3}} {4, 5}")
regex.findall(r"({(:.*)|(?R)*})", "{1, {2, 3}} {4, 5}")
regex.findall(r"({(:[^{}])|(?R)})", "{1, {2, 3}} {4, 5}")

но меня смутило либо [], либо error: too much backtracking,

Можно ли извлечь объекты соответствия для внешних скобок с помощью рекурсии regex?

---

Очевидно, я рискую быть застреленным с:

• не анализировать HTML с регулярным выражением
• сделать это с pyparse
• написать правильный лексер и парсер, например, используя ply

Я хочу подчеркнуть, что речь идет о том, как использовать рекурсивный шаблон (который, если мое понимание правильное, выводит нас за пределы обычного синтаксического анализа, так что может быть на самом деле возможно!). Если это можно сделать, это должно быть более чистым решением.

Answer 1

Шаблон является:

{((?>[^{}]+|(?R))*)}

Вы можете увидеть это работает для вашего примера:

regex.findall("{((?>[^{}]+|(?R))*)}", "{1, {2, 3}} {4, 5}")
# ['1, {2, 3}', '4, 5']

Объяснение:

Часть m должна исключать скобки. Использование атомарной группы необходимо, если вы хотите одновременно разрешить квантификатор для [^{}] и повторить группу без катастрофических проблем с возвратом. Для большей ясности, если отсутствует последняя закрывающая фигурная скобка, этот механизм регулярных выражений будет возвращать атомную группу по атомной группе, а не по буквам. Чтобы добраться до этой точки, вы можете сделать квантификатор притяжательным так: {((?>[^{}]+|(?R))*+)} (или же {((?:[^{}]+|(?R))*+)} так как атомная группа больше не полезна).

Атомная группа (?>....) и собственнический квантификатор ?+, *+, ++ две стороны одной и той же функции. Эта функция запрещает движку регулярных выражений возвращаться в группу символов, которая становится "атомом" (то, что нельзя разделить на более мелкие части).

Основными примерами являются следующие два шаблона, которые всегда терпят неудачу для строки aaaaaaaaaab:

(?>a+)ab
a++ab

то есть:

regex.match("a++ab", "aaaaaaaaaab")
regex.match("(?>a+)ab", "aaaaaaaaaab")

Когда вы используете (?:a+) или же a+ движок регулярных выражений (по умолчанию) записывает (в предвидении) все позиции возврата для всех символов. Но когда вы используете атомную группу или притяжательный квантификатор, эти позиции для возврата больше не записываются (за исключением начала группы). Поэтому, когда происходит механизм возврата, последний символ "а" не может быть возвращен. Только вся группа может быть возвращена.

[РЕДАКТИРОВАТЬ]: шаблон может быть написан более эффективным способом, если вы используете "развернутый" подшаблон для описания содержимого в скобках:

{([^{}]*+(?:(?R)[^{}]*)*+)}

Answer 2

Я был в состоянии сделать это без проблем с b(?:m|(?R))*e синтаксис:

{((?:[^{}]|(?R))*)}

демонстрация

---

Я думаю, что ключ от того, что вы пытались сделать, состоит в том, что повторение не продолжается m, но весь (?:m|(?R)) группа. Это то, что позволяет рекурсию с (?R) ссылка.