Regex для извлечения вложенных шаблонов

Возможный дубликат:
Сопоставление вложенных структур с регулярными выражениями в Python

Я не могу обернуть голову вокруг этой проблемы. У меня есть строка, подобная следующей:

Lorem ipsum dolor sit amet [@a xxx yyy [@b xxx yyy [@c xxx yyy]]] lorem ipsum sit amet

Моя задача - извлечь команды (они всегда начинаются с [@ и заканчиваются ]) и их подкоманды. Результат как

[
    [@a xxx yyy [@b xxx yyy [@c xxx yyy]]], # the most outer
    [@b xxx yyy [@c xxx yyy]],              # the middle one
    [@c xxx yyy]                            # the inner most
]

будет высоко ценится. Проблема заключается в том, что такого рода команды могут встречаться в очень длинных текстовых сообщениях, поэтому было бы неплохо "быстродействующее" решение.

Я играл с некоторыми шаблонами регулярных выражений, в большинстве случаев

(\[@.*?\]\s) # for the outer one

но я не видел света в соответствии среднего и внутреннего. Чтобы сделать это более сложным, количество вложенных команд является переменным... Может быть, какое-то специальное регулярное выражение может быть решением? Я читал о lookaheads и lookbehinds, но не знаю, как использовать их в этом особом случае.

Спасибо большое!

ОБНОВИТЬ

@Cyborgx37 указал мне на другой пост, который использует пакет pyparsing. Было бы неплохо иметь решение без внешнего пакета или библиотеки. Но pyparsing определенно решает эту проблему!

Источник

3 ответа

Решение

C# имеет рекурсивный / вложенный RegEx, я не верю, что Python делает. Вы можете повторно запустить поиск RegEx по предыдущим результатам, но это, вероятно, менее эффективно (издержки RegEx для такого простого поиска), чем просто создание собственного анализатора. Текст, который вы ищете "[@" и "]", не очень сложен.

Вот пользовательский анализатор (в JavaScript), который сделает эту работу.

var txt = "Lorem ipsum dolor sit amet [@a xxx yyy [@b xxx yyy [@c xxx yyy]]] lorem ipsum sit amet";
function parse(s) {
    var stack = [];
    var result = [];
    for(var x=0; x<s.length; x++) {
        var c = s.charAt(x);
        if(c == '[' && x+1 < s.length-1 && s.charAt(x+1) == '@') {
            for(var y=0; y<stack.length; y++)
                stack[y] += "[@";
            stack.push("[@");
            x++;
        } else if(c == ']' && stack.length > 0) {
            for(var y=0; y<stack.length; y++)
                stack[y] += "]";
            result.push(stack.pop());
        } else {
            for(var y=0; y<stack.length; y++)
                stack[y] += c;
        }
    }
    return result;
}
parse(txt);

Он быстро перебирает все символы текста (только один раз) и использует стек и условие if... if else... else, чтобы выдвинуть, вытолкнуть и изменить значения в этом стеке соответственно.

Источник

Исходя из aC# background, я не уверен, что это поможет, но я представляю, что, поскольку вы все равно должны анализировать внутренние команды, почему бы просто не сохранить содержимое команды, а затем снова запустить функцию regex на внутренние данные? Я знаю, что, наверное, чего-то не хватает, но поэтому я бы попробовал хотя бы.

Источник

Не удивительно, что вы не можете обернуть голову вокруг проблемы. Существует теория формального языка относительно формальных языков. Ноам Хомский описал четыре категории языков - известные как иерархия Хомского. Регулярные выражения способны описать легкую категорию языков - регулярные языки. Однако языки с вложенными парными структурами находятся за пределами обычных языков, и они не могут быть описаны / приняты регулярными выражениями.

Один из видов синтаксических анализаторов, которые легче всего реализовать, это те, которые основаны на рекурсивном вызове функций, которые анализируют элементы языка.

Источник
Другие вопросы по тегам