Регулярное выражение, соответствующее xa? B? C?но не один х - PullRequest
11 голосов
/ 12 ноября 2010

Я пытаюсь написать регулярное выражение, которое соответствует xa? B? C?но не х.На самом деле «x», «a», «b» и «c» не являются одиночными символами, они представляют собой умеренно сложные подвыражения, поэтому я стараюсь избегать чего-то вроде x (abc | ab | ac | bc| | б | в).Есть ли простой способ сопоставить «хотя бы одно из a, b и c в указанном порядке» в регулярном выражении, или мне не повезло?

Ответы [ 7 ]

11 голосов
/ 13 ноября 2010

Вот самая короткая версия:

(a)?(b)?(c)?(?(1)|(?(2)|(?(3)|(*FAIL))))

Если вам нужно провести матч в отдельной группе, напишите:

((a)?(b)?(c)?)(?(2)|(?(3)|(?(4)|(*FAIL))))

Но это не очень надежно, если a, b или c содержат группы захвата. Поэтому вместо этого напишите:

(?<A>a)?(?<B>b)?(?<C>c)?(?(<A>)|(?(<B>)|(?(<C>)|(*FAIL))))

А если вам нужна группа для всего матча, напишите это:

(?<M>(?<A>a)?(?<B>b)?(?<C>c)?(?(<A>)|(?(<B>)|(?(<C>)|(*FAIL)))))

И если вы, как и я, предпочитаете многобуквенные идентификаторы, а также считаете, что подобные вещи безумны, не находясь в режиме /x, напишите:

(?x)
(?<Whole_Match>
    (?<Group_A> a) ?
    (?<Group_B> b) ?  
    (?<Group_C> c) ?

    (?(<Group_A>)           # Succeed 
      | (?(<Group_B>)       # Succeed
          | (?(<Group_C>)   # Succeed
              |             (*FAIL)
            )
        )
    )
 )

И вот полная программа тестирования, чтобы доказать, что все это работает:

#!/usr/bin/perl
use 5.010_000;

my @pats = (
    qr/(a)?(b)?(c)?(?(1)|(?(2)|(?(3)|(*FAIL))))/,
    qr/((a)?(b)?(c)?)(?(2)|(?(3)|(?(4)|(*FAIL))))/,
    qr/(?<A>a)?(?<B>b)?(?<C>c)?(?(<A>)|(?(<B>)|(?(<C>)|(*FAIL))))/,
    qr/(?<M>(?<A>a)?(?<B>b)?(?<C>c)?(?(<A>)|(?(<B>)|(?(<C>)|(*FAIL)))))/,
    qr{
        (?<Whole_Match>

            (?<Group_A> a) ?
            (?<Group_B> b) ?
            (?<Group_C> c) ?

            (?(<Group_A>)               # Succeed
              | (?(<Group_B>)           # Succeed
                  | (?(<Group_C>)       # Succeed
                      |                 (*FAIL)
                    )
                )
            )

        )
    }x,
);

for my $pat (@pats) {
    say "\nTESTING $pat";
    $_ = "i can match bad crabcatchers from 34 bc and call a cab";
    while (/$pat/g) {
        say "$`<$&>$'";
    }
}

Все пять версий выдают этот вывод:

i <c>an match bad crabcatchers from 34 bc and call a cab
i c<a>n match bad crabcatchers from 34 bc and call a cab
i can m<a>tch bad crabcatchers from 34 bc and call a cab
i can mat<c>h bad crabcatchers from 34 bc and call a cab
i can match <b>ad crabcatchers from 34 bc and call a cab
i can match b<a>d crabcatchers from 34 bc and call a cab
i can match bad <c>rabcatchers from 34 bc and call a cab
i can match bad cr<abc>atchers from 34 bc and call a cab
i can match bad crabc<a>tchers from 34 bc and call a cab
i can match bad crabcat<c>hers from 34 bc and call a cab
i can match bad crabcatchers from 34 <bc> and call a cab
i can match bad crabcatchers from 34 bc <a>nd call a cab
i can match bad crabcatchers from 34 bc and <c>all a cab
i can match bad crabcatchers from 34 bc and c<a>ll a cab
i can match bad crabcatchers from 34 bc and call <a> cab
i can match bad crabcatchers from 34 bc and call a <c>ab
i can match bad crabcatchers from 34 bc and call a c<ab>

Сладкий, а?

РЕДАКТИРОВАТЬ: Для x в начальной части, просто поместите все, что вы хотите x в начале матча, перед самой первой необязательной группой захвата для части a, вот так:

x(a)?(b)?(c)?(?(1)|(?(2)|(?(3)|(*FAIL))))

или как это

(?x)                        # enable non-insane mode

(?<Whole_Match>
    x                       # first match some leader string

    # now match a, b, and c, in that order, and each optional
    (?<Group_A> a ) ?
    (?<Group_B> b ) ?  
    (?<Group_C> c ) ?

    # now make sure we got at least one of a, b, or c
    (?(<Group_A>)           # SUCCEED!
      | (?(<Group_B>)       # SUCCEED!
          | (?(<Group_C>)   # SUCCEED!
              |             (*FAIL)
            )
        )
    )
)

Тестовое предложение было построено без части x, поэтому оно не сработает, но я думаю, что я показал, как я собираюсь пойти на это. Обратите внимание, что все x, a, b и c могут быть произвольно сложными шаблонами (да, даже рекурсивными), а не просто отдельными буквами, и не имеет значения, используют ли они пронумерованные группы захвата их даже.

Если вы хотите пойти на это с предвкушением, вы можете сделать это:

(?x)

(?(DEFINE)
       (?<Group_A> a)
       (?<Group_B> b)
       (?<Group_C> c)
)

x

(?= (?&Group_A)
  | (?&Group_B)
  | (?&Group_C)
)

(?&Group_A) ?
(?&Group_B) ?
(?&Group_C) ?

А вот что добавить в массив @pats в тестовой программе, чтобы показать, что этот подход также работает:

qr{
    (?(DEFINE)
        (?<Group_A> a)
        (?<Group_B> b)
        (?<Group_C> c)
    )

    (?= (?&Group_A)
      | (?&Group_B)
      | (?&Group_C)
    )

    (?&Group_A) ?
    (?&Group_B) ?
    (?&Group_C) ?
}x

Вы заметите, пожалуйста, что мне все еще удается никогда не повторять ни одного из a, b или c, даже с техникой прогнозирования.

Я выиграю? ☺

5 голосов
/ 12 ноября 2010

Как насчет этого:

x(?:a())?(?:b())?(?:c())?(\1|\2|\3)

Пустые группы захвата после a, b и c всегда будут совпадать (пустая строка), если a, b или c match, в таком порядке.

Партия (\1|\2|\3) будет соответствовать, только если в матче участвовала хотя бы одна из предыдущих групп.Поэтому, если у вас просто есть x, регулярное выражение не выполняется.

Каждая часть регулярного выражения будет оцениваться только один раз.

Конечно, если x, a, b и c являются более сложными подвыражениями, которые содержат сами группы захвата, поэтому вы должны соответствующим образом скорректировать номера обратных ссылок *.

Поскольку это регулярное выражение выглядит немного странно, вот подробная версия:

x          # Match x
(?:a())?   # Try to match a. If this succeeds, \1 will contain an empty string.
(?:b())?   # Same with b and \2.
(?:c())?   # Same with c and \3.
(\1|\2|\3) # Now try to match the content of one of the backreferences. 
           # This works if one of the empty parentheses participated in the match.
           # If so, the backref contains an empty string which always matches. 
           # Bingo!

Возможно, вам понадобится окружить это якорями (^ и $), если вы не возражаете против совпадения xb в строке cxba и т. Д.

Например,в Python:

>>> r=re.compile(r"x(?:a())?(?:b())?(?:c())?(\1|\2|\3)$")
>>> for test in ("x", "xa", "xabc", "xba"):
...     m = r.match(test)
...     if m:
...         print("{} --> {}".format(test, m.group(0)))
...     else:
...         print("{} --> no match".format(test))
...
x --> no match
xa --> xa
xabc --> xabc
xba --> no match

* или, если ваш регулярный выражение знает именованные группы захвата, вы можете использовать их, например,

x(?:a(?P<a>))?(?:b(?P<b>))?(?:c(?P<c>))?((?P=a)|(?P=b)|(?P=c))

в Python / PCRE.В .NET (и, возможно, других разновидностях) даже законно иметь несколько групп захвата, использующих одно и то же имя, что делает возможным еще одно упрощение:

x(?:a(?<m>))?(?:b(?<m>))?(?:c(?<m>))?\k<m>
5 голосов
/ 12 ноября 2010

Нетривиально, если у вас нет взгляда вперед.

x(ab?c?|bc?|c)
3 голосов
/ 12 ноября 2010

Как насчет чего-то вроде

x(?=[abc])a?b?c?
2 голосов
/ 18 ноября 2010

Если вы абсолютно должны не повторять a, b или c, то это самое короткое и простое регулярное выражение - при условии, что x представляет выражение фиксированной длины , или чтоиспользуемая вами реализация поддерживает переменную длину.Он использует отрицательный взгляд назад, и Perl, например, умрет при просмотре переменной длины.

По сути, это то, что вы говорите, перефразируя:

/(x)a?b?c?(?<!x)/;

Вот что он говорит: я хочу соответствовать xa? B? C?но когда я рассматриваю это, я не хочу, чтобы последнее выражение было x .

Кроме того, он не будет работать, если совпадение для a, b или c заканчивается на x.(кончик шляпы: tchrist)

1 голос
/ 12 ноября 2010

Вот самое короткое, что я мог придумать:

x(ab?c?|bc?|c)

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

Эта версия повторяется c три раза. Вы можете адаптировать его так, чтобы a или b повторялось чаще всего, поэтому вы можете выбрать самый короткий из a, b и c, который будет повторяться три раза.

0 голосов
/ 12 ноября 2010

Если вам не нужно находить максимальное (жадное) совпадение, вы можете отбросить «в таком порядке», потому что если вы соответствуете x(a|b|c) и игнорируете любой следующий текст, который вы уже сопоставили, хотя бы один из , б и в, в этом порядке ". Другими словами, если все, что вам нужно, это верный / ложный ответ (соответствует он или нет), тогда достаточно x(a|b|c). (Другое предположение: вы пытаетесь определить, содержит ли входная строка совпадение , а не соответствует ли вся строка регулярному выражению. Т.е. см. Вопрос @Alan Moore.)

Однако, если вы хотите определить максимальное совпадение или сопоставить всю входную строку, вы можете использовать lookahead: x(?=(a|b|c))a?b?c?

Там есть некоторая избыточность, но намного меньше, чем комбинаторный подход, которого вы пытались избежать.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...