Соответствие a ^ n b ^ n c ^ n при n> 0 с помощью PCRE

Ответ 1

трюк Qtax

(Мощная группа самоназывающих захватов)

^(?:a(?=a*(\1?+b)b*(\2?+c)))+\1\2$

Это решение также называется "трюк Qtax", потому что он использует ту же технику, что и от "vertical" регулярное выражение в ASCII-изображении "Qtax.

Проблема, о которой идет речь, сжигает необходимость утверждать, что три группы сопоставляются с одинаковой длиной. В качестве упрощенной версии, чтобы соответствовать:

xyz

Где x, y и z на самом деле просто подшаблоны с переменной с длиной согласования n от a, b и c. С выражением, которое использует lookaheads с группами привязки для самореференции, указываемый вами символ добавляется к каждому повторению представления, которое может эффективно использоваться для "подсчета":

aaabbbccc
 ^  ^  ^

Это достигается следующим образом:

• (?:a…)+ Соответствует символ подшаблона a. С помощью (?=a* мы переходим непосредственно к "счетчику".
• (\1?+b) Группа захвата (\1) эффективно потребляет то, что ранее было сопоставлено, если оно есть, и использует притяжательное соответствие, которое не позволяет выполнить обратное отслеживание, и совпадение не выполняется, если счетчик выходит из строя. То есть было больше подшаблонов b, чем подшаблон a. На первой итерации это отсутствует, и ничего не сопоставляется. Затем сопоставляется символ подшаблона b. Он добавляется в группу захвата, эффективно "подсчитывая" одну из b в группе. С b* мы переходим непосредственно к следующему "счетчику".
• (\2?+c) Группа захвата (\2) эффективно потребляет то, что ранее было сопоставлено, как указано выше. Поскольку этот дополнительный захват символов работает так же, как и предыдущая группа, символам разрешено синхронизировать длину в пределах этих групп символов. Предполагая непрерывные последовательности a..b..c..:

_{(Извините мое искусство.)}

Первая итерация:

| The first 'a' is matched by the 'a' in '^(?:a…)'.
| The pointer is stuck after it as we begin the lookahead.
v,- Matcher pointer
aaaa...bbbbbbbb...cccc...
 ^^^   |^^^       ^
skipped| skipped  Matched by c in (\2?+c);
by a*  | by b*         \2 was "nothing",
       |               now it is "c".
       Matched by b
       in (\1?+b).
     \1 was "nothing", now it is "b".

Вторая итерация:

 | The second 'a' is matched by the 'a' in '^(?:a…)'.
 | The pointer is stuck after it as we begin the lookahead.
 v,- Matcher pointer
aaaa...bbbbbbbb...cccc...
       /|^^^      |^
eaten by| skipped |Matched by c in (\2?+c);
\1?+    | by b*   |     '\2' was "nothing",
  ^^    |      \2?+     now it is "cc".
 skipped|
 by a*  \ Matched by b
          in (\1?+b).
          '\1' was "nothing", now it is "bb".

Поскольку три группы, рассмотренные выше, "потребляют" один из каждого из a, b, c соответственно, они сопоставляются в круговом стиле и "подсчитываются" с помощью (?:a…)+, (\1?+b) и (\2?+c) соответственно. С дополнительным привязкой и фиксацией того, что мы начали, мы можем утверждать, что мы сопоставляем xyz (представляя каждую группу выше), где x, y и z равны an, bn и cn соответственно.

В качестве бонуса, чтобы "подсчитать" больше, можно сделать следующее:

Pattern: ^(?:a(?=a*(\1?+b)b*(\2?+c)))+\1{3}\2$
Matches: abbbc
aabbbbbbcc
aaabbbbbbbbbccc

Pattern: ^(?:a(?=a*(\1?+bbb)b*(\2?+c)))+\1\2$
Matches: abbbc
aabbbbbbcc
aaabbbbbbbbbccc

Ответ 2

Сначала объясните шаблон, который у вас есть:

^               # Assert begin of line
    (           # Capturing group 1
        a       # Match a
        (?1)?   # Recurse group 1 optionally
        b       # Match b
    )           # End of group 1
$               # Assert end of line

Со следующими модификаторами:

g: global, match all
m: multiline, match start and end of line with ^ and $ respectively
x: extended, indentation are ignored with the ability to add comments with #

Рекурсивная часть является необязательной, чтобы в конечном итоге выйти из "бесконечной" рекурсии.

Мы могли бы использовать приведенный выше шаблон для решения проблемы. Нам нужно добавить некоторое регулярное выражение для соответствия части c. Проблема в том, что когда aabb сопоставляется в aabbcc, он уже потребляется, что означает, что мы не могли отследить назад.

Решение? Использование lookaheads! Lookaheads имеют нулевую ширину, что означает, что он не будет потреблять и двигаться вперед. Проверьте это:

^                    # Assert begin of line
    (?=              # First zero-with lookahead
        (            # Capturing group 1
            a        # Match a
            (?1)?    # Recurse group 1 optionally
            b        # Match b
        )            # End of group 1
        c+           # Match c one or more times
    )                # End of the first lookahead

    (?=              # Second zero-with lookahead
        a+           # Match a one or more times
        (            # Capturing group 2
            b        # Match b
            (?2)?    # Recurse group 2 optionally
            c        # Match c
        )            # End of group 2
    )                # End of the second lookahead
a+b+c+               # Match each of a,b and c one or more times
$                    # Assert end of line

Онлайн-демонстрация

В основном мы сначала утверждаем, что a ^ n b ^ n, а затем мы утверждаем b ^ n c ^ n, что привело бы к a n n b ^ n c ^ n.