Узнайте, где регулярное выражение удовлетворяет предложению

У меня есть предложение и регулярное выражение. Можно ли узнать, где в регулярном выражении удовлетворяет мое предложение. Например, рассмотрите мое предложение как MMMV и регулярное выражение как M+V?T*Z+. Теперь регулярное выражение до тех пор, пока M+V? не удовлетворит предложения, а оставшаяся часть регулярного выражения - это T*Z+, который должен быть моим выводом.

Мой подход прямо сейчас состоит в том, чтобы разбить регулярное выражение на отдельные части и сохранить их в списке, а затем сопоставить, объединяя первые n частей до совпадения предложений. Например, если мое регулярное выражение - M+V?T*Z+, то мой список - ['M+', 'V?', 'T*', 'Z+']. Затем я сопоставляю свою строку в цикле сначала с помощью M+, затем с помощью M+V? и так далее, пока не будет найдено полное совпадение, а затем беру оставшийся список в качестве вывода. Ниже приведен код

            re_exp = ['M+', 'V?', 'T*', 'Z+']
            for n in range(len(re_exp)):
                re_expression = ''.join(re_exp[:n+1])
                if re.match(r'{0}$'.format(re_expression), sentence_language):
                    return re_exp[n+1:]

Есть ли лучший подход для достижения этого, используя некоторую библиотеку синтаксического анализа и т. д.

Насколько сложным может быть регулярное выражение? Может ли он иметь группы, группы символов, обратные ссылки, опережающие просмотры и т. д.?

tobias_k 26.10.2018 10:56

Если регулярное выражение очень простое, как в вашем примере, вы мог бы даже сможете написать очень простой пользовательский парсер / сопоставитель регулярных выражений. В частности, если последовательные части регулярного выражения обрабатывают разные символы (например, нет V?V+), тогда это должно даже работать жадно, без какого-либо возврата.

tobias_k 26.10.2018 11:00

Регулярное выражение было бы простым. Но мое единственное соображение при написании пользовательской функции - это разница в скорости и обработка конечных случаев по мере увеличения размера регулярного выражения. Было бы полезно, если бы я мог настроить сам re, чтобы получить результат, или использовать другую библиотеку синтаксического анализа.

Paras 26.10.2018 11:30

Возможно, вместо объединения частей регулярного выражения и последующего сопоставления всей строки вы могли бы просто сопоставить одну часть, а затем сопоставить следующую часть с оставшейся частью строки, то есть вырезать префикс, который соответствует первому «члену» регулярного выражения. .

tobias_k 26.10.2018 11:52

Если строка соответствует M+V?, то она также соответствует M+V?T*, поскольку T* может соответствовать нулевым символам. Так что трудно понять, как гипотетический прибор частичного совпадения когда-либо сообщит о M+V? как о частичном совпадении.

rici 26.10.2018 16:54

@tobias_k, это действительно лучший подход.

Paras 27.10.2018 18:51

@rici, поэтому я сразу сопоставляю строку с частями регулярного выражения вместо полного регулярного выражения. В этом случае строка должна соответствовать только первым частям регулярного выражения до тех пор, пока не будет удовлетворена. Всякий раз, когда есть совпадение, я должен иметь возможность вернуть оставшуюся часть регулярного выражения. В вашем примере строка сначала будет соответствовать M+V?, а T* будет возвращен в качестве вывода. Теперь я должен переставить вывод и генерировать предложения.

Paras 27.10.2018 19:04

Но разрешенные последующие варианты для MMMV и MMMVT идентичны; за обоими могут следовать либо T, либо Z. Таким образом, можно было бы ожидать, что механизм регулярных выражений с частичным соответствием вернет одно и то же в обоих случаях.

rici 27.10.2018 20:35

Да, но в моем случае этого не потребуется. Мне потребуется только следующее регулярное выражение. Так что вывод для MMMV и MMMVT может быть разным.

Paras 27.10.2018 22:24
4
9
125
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Вы можете использовать () для включения групп в регулярное выражение. Например: M+V?(T*Z+), требуемый вывод сохраняется в первой группе регулярного выражения.

Я знаю, что вопрос говорит о python, но здесь вы можете увидеть регулярное выражение в действии:

const regex = /M+V?(T*Z+)/;
const str = `MMMVTZ`;
let m = regex.exec(str);

console.log(m[1]);

Проблема с этим подходом в том, что я не знаю заранее, где появится (). Подумайте об этом так: мне нужно сказать пользователю, что должно произойти после того, как он / она напечатает какое-то предложение. Предложение может быть MMM, MMMV и т. д. Таким образом, вывод различается в каждом случае.

Paras 26.10.2018 09:09
Ответ принят как подходящий

Предполагая, что ваше регулярное выражение довольно простое, без групп, обратных ссылок, опережающих просмотров и т. д., Например. как и в вашем случае, следуя шаблону \w[+*?]?, вы можете сначала разделить его на части, как вы это уже делаете. Но тогда вместо того, чтобы итеративно соединять части и сопоставлять их со всей цепочкой, вы можете тестировать каждую часть индивидуально, отрезая уже сопоставленные части.

def match(pattern, string):
    res = pat = ""
    for p in re.findall(r"\w[+*?]?", pattern):
        m = re.match(p, string)
        if m:
            g = m.group()
            string = string[len(g):]
            res, pat = res + g, pat + p
        else:
            break
    return pat, res

Пример:

>>> for s in "MMMV", "MMVVTTZ", "MTTZZZ", "MVZZZ", "MVTZX":
>>>     print(*match("M+V?T*Z+", s))
...
M+V?T* MMMV
M+V?T* MMV
M+V?T*Z+ MTTZZZ
M+V?T*Z+ MVZZZ
M+V?T*Z+ MVTZ

Однако обратите внимание, что в худшем случае наличия строки длиной n и шаблона из частей n, каждая из которых соответствует только одному символу, это все равно будет иметь O (n²) для многократного разрезания строки.

Кроме того, это может потерпеть неудачу, если две последовательные части имеют примерно один и тот же символ, например a?a+b (который должен эквивалентен a+b) не будет соответствовать ab, а будет соответствовать только aab, поскольку отдельный a уже "потреблен" a?.

Вы можете снизить сложность до O (n), написав свой собственный очень простой сопоставитель регулярных выражений для этого очень сокращенного вида регулярных выражений, но в среднем случае это того не стоит или даже медленнее.

Другие вопросы по теме