Упрощение регулярного выражения ab|a|b

(Как) можно упростить следующее регулярное выражение:

ab|a|b

?

Я ищу менее избыточный, то есть только с одним a и одним b. Является ли это возможным?

Некоторые попытки:

a?b?       # matches empty string while shouldn't
ab?|b      # still two b

Обратите внимание, что реальное регулярное выражение имеет более сложные части a и b, то есть, скажем, не один символ, а внутренние подрегулярные выражения.


person sp00m    schedule 25.04.2013    source источник
comment
моя интуиция подсказывает мне, что это не может быть упрощено   -  person Sam I am says Reinstate Monica    schedule 25.04.2013
comment
Есть ли причина, по которой вам нужно упростить это регулярное выражение? Несмотря на некоторую избыточность, он по-прежнему очень прост и легко читается.   -  person Jeff    schedule 25.04.2013
comment
@leppie: это соответствует aa и bb, которые оба недействительны   -  person Jeff    schedule 25.04.2013
comment
@Jeff: Хороший вопрос, я думаю, это нельзя упростить.   -  person leppie    schedule 25.04.2013
comment
@Jeff Пример вполне читаем, как вы сказали, но регулярное выражение real имеет более сложные части a и b.   -  person sp00m    schedule 25.04.2013
comment
@ sp00m: Тогда подумайте о том, чтобы разбить его на три регулярных выражения. Если вы просто разделите его на '|' символов, у вас остается три более простых регулярных выражения, каждое из которых проще в сопровождении, чем исходное, и их можно тестировать по отдельности.   -  person Jeff    schedule 25.04.2013
comment
Как насчет: (ab?)|(a?b) ? Не кажется проще, и анализ DFA, вероятно, построит такое же дерево синтаксического анализа.   -  person leppie    schedule 25.04.2013
comment
@ sp00m это (как и многие другие вопросы о регулярных выражениях) в некоторой степени зависит от вашего вкуса регулярных выражений. так на каком языке или в какой среде вы это используете?   -  person Martin Ender    schedule 25.04.2013
comment
@m.buettner Допустим, Java, но это скорее общий вопрос о регулярных выражениях, т. е. давайте рассмотрим разновидность, которая поддерживает все предложения регулярных выражений (например, не такие, как в JavaScript).   -  person sp00m    schedule 25.04.2013
comment
@sp00m sp00m, тогда вы не можете сделать ничего лучше этого, за исключением решения Джеффа или конкатенации строк.   -  person Martin Ender    schedule 25.04.2013
comment
С поиском: (?=.)a?b? или а?б?(?‹=.)   -  person Casimir et Hippolyte    schedule 25.04.2013


Ответы (1)


Если вы используете Perl или какой-либо механизм PCRE (например, функции PHP preg_), вы можете ссылаться на предыдущие группы в шаблоне, например:

/(a)(b)|(?1)|(?2)/

Основная цель этой функции — поддержка рекурсии, но ее также можно использовать для повторного использования шаблонов.

Обратите внимание, что в этом случае вы не можете обойти захват a и b в первом чередовании, что влечет за собой некоторые (возможно) ненужные накладные расходы. Чтобы избежать этого, вы можете определить группы внутри условного оператора, который никогда не выполняется. Канонический способ сделать это - использовать группу (?(DEFINE)...) (которая проверяет, соответствует ли именованная группа DEFINE чему-либо, но, конечно, эта группа не существует):

/(?(DEFINE)(a)(b))(?1)(?2)|(?1)|(?2)/

Если ваш движок не поддерживает это (EDIT: поскольку вы используете Java, эта функция не поддерживается), лучшее, что вы можете получить в одном шаблоне, действительно

ab?|b

В качестве альтернативы вы можете создать версию ab|a|b вручную путем объединения/форматирования строк, например:

String a = "a";
String b = "b";
String pattern = a + b + "|" + a + "|" + b;

Это также позволяет избежать дублирования. Или вы можете использовать 3 отдельных шаблона ab, a и b для строки темы (где первый снова является конкатенацией двух последних).

person Martin Ender    schedule 25.04.2013
comment
@leppie Я думаю, что это субъективно, и если вы это сделаете, вы должны использовать (?:ab?) - в противном случае скобки несут ненужные накладные расходы из-за захвата ab (возможно, мне следует добавить это к первому решению) - person Martin Ender; 25.04.2013
comment
+1 Регулярное выражение: вы узнаете что-то новое каждый день, даже 40 лет спустя; p - person leppie; 25.04.2013