Как мы можем сопоставить ^ nb ^ n с регулярным выражением Java?

_{Это вторая часть серии образовательных статей о регулярных выражениях. Он показывает , как lookaheads и вложенные ссылки могут быть использованы , чтобы соответствовать нерегулярного languge а ^п б ^п . Вложенные ссылки впервые представлены в: Как это регулярное выражение находит треугольные числа?}

Один из архетипических нерегулярных языков :

L = { aⁿ bⁿ: n > 0 }

Это язык всех непустых строк, состоящих из некоторого количества aсимволов, за которыми следует равное количество bсимволов. Примеры строк в этом языке являются ab, aabb, aaabbb.

Нерегулярность этого языка можно показать с помощью леммы о накачке . Фактически это архетипический контекстно-свободный язык , который может быть создан с помощью контекстно-свободной грамматики S → aSb | ab .

Тем не менее, современные реализации регулярных выражений явно распознают не только обычные языки. То есть они не являются «регулярными» по определению теории формального языка. PCRE и Perl поддерживают рекурсивное регулярное выражение, а .NET поддерживает определение балансирующих групп. Еще менее «причудливые» функции, например сопоставление обратных ссылок, означают, что регулярное выражение не является регулярным.

Но насколько мощны эти «базовые» функции? Можем ли мы, например, распознать Lс помощью регулярного выражения Java? Можем ли мы , возможно , объединить lookarounds и вложенные ссылки и иметь рисунок , который работает с , например , String.matchesчтобы соответствовать строки , как ab, aabb, aaabbbи т.д.?

Ссылки

• perlfaq6: Могу ли я использовать регулярные выражения Perl для сопоставления сбалансированного текста?
• MSDN - Элементы языка регулярных выражений - Балансировка определений групп
• pcre.org - справочная страница PCRE
• regular-expressions.info - Lookarounds и группирование и обратные ссылки
• java.util.regex.Pattern

Связанные вопросы

• Влияет ли поиск на то, какие языки могут соответствовать регулярным выражениям?
• Балансирующие группы .NET Regex и рекурсивные шаблоны PCRE

Ответ, разумеется, ДА! Вы, безусловно, можете написать шаблон регулярного выражения Java, соответствующий a ⁿ b ⁿ . Он использует положительный просмотр вперед для утверждения и одну вложенную ссылку для «подсчета».

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

Язык, используемый для разработки решения, будет PHP из-за его краткости. Заключительный тест после того, как шаблон будет завершен, будет выполнен на Java.

Шаг 1. Посмотрите вперед для утверждения

Начнем с более простой проблемы: мы хотим найти соответствие a+в начале строки, но только если за ней сразу следует b+. Мы можем использовать ^для привязки нашего совпадения, а так как мы хотим сопоставить только a+без символаb+ , мы можем использовать утверждение опережающего просмотра(?=…) .

Вот наш образец с простой тестовой обвязкой:

function testAll($r, $tests) {
   foreach ($tests as $test) {
      $isMatch = preg_match($r, $test, $groups);
      $groupsJoined = join('|', $groups);
      print("$test $isMatch $groupsJoined\n");
   }
}
 
$tests = array('aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb');
 
$r1 = '/^a+(?=b+)/';
#          └────┘
#         lookahead

testAll($r1, $tests);

Результат ( как показано на ideone.com ):

aaa 0
aaab 1 aaa
aaaxb 0
xaaab 0
b 0
abbb 1 a

Это именно тот результат, который нам нужен: мы сопоставляем a+, только если он находится в начале строки и только если за ним сразу следует b+.

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

Шаг 2. Захват в упреждающем (и в режиме свободного интервала)

Теперь предположим, что даже если мы не хотим, b+чтобы это было частью совпадения, мы все равно хотим захватить его в группу 1. Кроме того, поскольку мы ожидаем более сложного шаблона, давайте использовать xмодификатор для свободного интервала, чтобы мы может сделать наше регулярное выражение более читабельным.

Основываясь на нашем предыдущем фрагменте PHP, теперь у нас есть следующий шаблон:

$r2 = '/ ^ a+ (?= (b+) ) /x';
#             │   └──┘ │
#             │     1  │
#             └────────┘
#              lookahead
 
testAll($r2, $tests);

Теперь вывод ( как видно на ideone.com ):

aaa 0
aaab 1 aaa|b
aaaxb 0
xaaab 0
b 0
abbb 1 a|bbb

Обратите внимание, что например, aaa|bэто результат того, joinчто каждая группа захватила '|'. В этом случае захватывается группа 0 (т. Е. То, что соответствует шаблону) aaa, и захватывается группа 1 b.

Урок : вы можете делать снимки внутри обзора. Вы можете использовать свободный интервал, чтобы улучшить читаемость.

Шаг 3. Реорганизация опережающего просмотра в «цикл»

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

Давайте пока не будем беспокоиться о механизме подсчета и просто проведем рефакторинг следующим образом:

• Первый рефакторинг a+до (?: a )+(обратите внимание, что (?:…)это группа без захвата)
• Затем переместите просмотр вперед внутри этой группы без захвата.
  • Обратите внимание, что теперь мы должны «пропустить», a*прежде чем мы сможем «увидеть» b+, поэтому измените шаблон соответствующим образом.

Итак, теперь у нас есть следующее:

$r3 = '/ ^ (?: a (?= a* (b+) ) )+ /x';
#          │     │      └──┘ │ │
#          │     │        1  │ │
#          │     └───────────┘ │
#          │       lookahead   │
#          └───────────────────┘
#           non-capturing group

Результат такой же, как и раньше ( как показано на ideone.com ), поэтому в этом отношении нет никаких изменений. Важно то, что теперь мы делаем утверждение на каждой итерации в +«петле». С нашим текущим шаблоном в этом нет необходимости, но теперь мы сделаем группу 1 «подсчитываемой» для нас, используя саморегуляцию.

Урок : вы можете снимать внутри группы без захвата. Поисковые запросы можно повторять.

Шаг 4: Это шаг, с которого мы начинаем считать

Вот что мы собираемся сделать: мы перепишем группу 1 так, чтобы:

• В конце первой итерации +, когда первая aсоответствует, она должна захватитьb
• В конце второй итерации, когда aсопоставляется другой , он должен захватыватьbb
• В конце третьей итерации он должен захватить bbb
• ...
• В конце n -й итерации группа 1 должна захватить b ⁿ
• Если их недостаточно bдля захвата в группу 1, утверждение просто не выполняется.

Так что группу 1, которая сейчас существует (b+), придется переписать во что-то вроде (\1 b). То есть мы пытаемся «добавить» bк тому, что группа 1 захватила в предыдущей итерации.

Здесь есть небольшая проблема в том, что в этом шаблоне отсутствует «базовый случай», то есть случай, когда он может соответствовать без ссылки на себя. Базовый вариант необходим, потому что группа 1 запускается как «неинициализированная»; он еще ничего не захватил (даже пустую строку), поэтому попытка ссылки на себя всегда будет неудачной.

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

$tests = array(
  'aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb', 'aabb', 'aaabbbbb', 'aaaaabbb'
);
 
$r4 = '/ ^ (?: a (?= a* (\1? b) ) )+ /x';
#          │     │      └─────┘ | │
#          │     │         1    | │
#          │     └──────────────┘ │
#          │         lookahead    │
#          └──────────────────────┘
#             non-capturing group

Теперь вывод ( как видно на ideone.com ):

aaa 0
aaab 1 aaa|b        # (*gasp!*)
aaaxb 0
xaaab 0
b 0
abbb 1 a|b          # yes!
aabb 1 aa|bb        # YES!!
aaabbbbb 1 aaa|bbb  # YESS!!!
aaaaabbb 1 aaaaa|bb # NOOOOOoooooo....

Ага! Похоже, мы действительно близки к решению! Нам удалось «подсчитать» группу 1, используя саморегуляцию! Но подождите ... что-то не так со вторым и последним тестами !! Не хватает bs, и как-то неправильно посчитали! Мы выясним, почему это произошло на следующем шаге.

Урок : Один из способов «инициализировать» группу со ссылками на себя - сделать сопоставление со ссылками на себя необязательным.

Шаг 4½: понять, что пошло не так

Проблема в том, что, поскольку мы сделали сопоставление ссылок на себя необязательным, «счетчик» может «сбросить» обратно на 0, когда их недостаточно b. Давайте внимательно посмотрим, что происходит на каждой итерации нашего шаблона с aaaaabbbвходными данными.

 a a a a a b b b
↑
# Initial state: Group 1 is "uninitialized".
           _
 a a a a a b b b
  ↑
  # 1st iteration: Group 1 couldn't match \1 since it was "uninitialized",
  #                  so it matched and captured just b
           ___
 a a a a a b b b
    ↑
    # 2nd iteration: Group 1 matched \1b and captured bb
           _____
 a a a a a b b b
      ↑
      # 3rd iteration: Group 1 matched \1b and captured bbb
           _
 a a a a a b b b
        ↑
        # 4th iteration: Group 1 could still match \1, but not \1b,
        #  (!!!)           so it matched and captured just b
           ___
 a a a a a b b b
          ↑
          # 5th iteration: Group 1 matched \1b and captured bb
          #
          # No more a, + "loop" terminates

Ага! На нашей 4-й итерации мы все еще могли совпадать \1, но не могли \1b! Поскольку мы допускаем, чтобы сопоставление ссылок на себя было необязательным \1?, движок откатывается назад и выбирает вариант «Нет, спасибо», который затем позволяет нам сопоставить и захватить просто b!

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

Урок : остерегайтесь возврата. Механизм регулярных выражений будет выполнять столько откатов, сколько вы позволите, пока заданный шаблон не совпадет. Это может повлиять на производительность (например, катастрофический возврат ) и / или правильность.

Шаг 5: На помощь приходит самообладание!

«Исправление» теперь должно быть очевидным: объединить необязательное повторение с притяжательным квантификатором. То есть вместо простого ?использования ?+(помните, что повторение, которое количественно определяется как притяжательное, не приводит к возврату, даже если такое «сотрудничество» может привести к совпадению с общим шаблоном).

В очень Неформально, это то , что ?+, ?и ??говорит:

?+

• (необязательно) «Этого не должно быть»,
  • (притяжательное) "но если он есть, вы должны взять его и не отпускать!"

?

• (необязательно) «Этого не должно быть»,
  • (жадно) "но если это так, ты можешь взять это сейчас",
    • (возврат) "но вас могут попросить отпустить это позже!"

??

• (необязательно) «Этого не должно быть»,
  • (неохотно) "и даже если это так, вам пока не нужно принимать это",
    • (возврат) "но вас могут попросить принять это позже!"

В нашей настройке \1он не будет там в первый раз, но он всегда будет там в любое время после этого, и мы всегда хотим сопоставить его тогда. Таким образом, \1?+достигнем именно того, что мы хотим.

$r5 = '/ ^ (?: a (?= a* (\1?+ b) ) )+ /x';
#          │     │      └──────┘ │ │
#          │     │          1    │ │
#          │     └───────────────┘ │
#          │         lookahead     │
#          └───────────────────────┘
#             non-capturing group

Теперь вывод ( как показано на ideone.com ):

aaa 0
aaab 1 a|b          # Yay! Fixed!
aaaxb 0
xaaab 0
b 0
abbb 1 a|b
aabb 1 aa|bb
aaabbbbb 1 aaa|bbb
aaaaabbb 1 aaa|bbb  # Hurrahh!!!

Вуаля !!! Задача решена!!! Теперь мы считаем правильно, именно так, как мы этого хотим!

Урок : узнайте разницу между жадным, упорным и притяжательным повторением. Необязательное-притяжательное может быть мощной комбинацией.

Шаг 6: Последние штрихи

Итак, то, что у нас есть прямо сейчас, - это шаблон, который aповторяется многократно, и для каждого совпадения aесть соответствующий bзахваченный в группе 1. Шаблон +завершается, когда их больше нет a, или если утверждение не удалось, потому что нет соответствующего bдля ан a.

Чтобы завершить работу, нам просто нужно добавить к нашему шаблону \1 $. Теперь это обратная ссылка на то, что соответствует группе 1, за которой следует конец привязки строки. Якорь гарантирует, что bв строке нет лишних символов; другими словами, что на самом деле у нас есть a ⁿ b ⁿ .

Вот окончательный шаблон с дополнительными тестовыми примерами, в том числе одним из 10 000 символов:

$tests = array(
  'aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb', 'aabb', 'aaabbbbb', 'aaaaabbb',
  '', 'ab', 'abb', 'aab', 'aaaabb', 'aaabbb', 'bbbaaa', 'ababab', 'abc',
  str_repeat('a', 5000).str_repeat('b', 5000)
);
 
$r6 = '/ ^ (?: a (?= a* (\1?+ b) ) )+ \1 $ /x';
#          │     │      └──────┘ │ │
#          │     │          1    │ │
#          │     └───────────────┘ │
#          │         lookahead     │
#          └───────────────────────┘
#             non-capturing group

Он находит 4 матча: ab, aabb, aaabbb, и в ⁵⁰⁰⁰ б ⁵⁰⁰⁰ . Запуск на ideone.com занимает всего 0,06 секунды .

Шаг 7. Тест Java

Итак, шаблон работает в PHP, но конечная цель - написать шаблон, который работает на Java.

public static void main(String[] args) {
 
        String aNbN = "(?x) (?:  a  (?= a* (\\1?+ b))  )+ \\1";
        String[] tests = {
                "",      // false
                "ab",    // true
                "abb",   // false
                "aab",   // false
                "aabb",  // true
                "abab",  // false
                "abc",   // false
                repeat('a', 5000) + repeat('b', 4999), // false
                repeat('a', 5000) + repeat('b', 5000), // true
                repeat('a', 5000) + repeat('b', 5001), // false
        };
        for (String test : tests) {
                System.out.printf("[%s]%n  %s%n%n", test, test.matches(aNbN));
        }
 
}
 
static String repeat(char ch, int n) {
        return new String(new char[n]).replace('\0', ch);
}

Шаблон работает должным образом ( как показано на ideone.com ).

А теперь подходим к выводу ...

Надо сказать, что и a*в предварительном просмотре, и в «основном +цикле» разрешен возврат с возвратом. Читателям предлагается подтвердить, почему это не проблема с точки зрения правильности, и почему в то же время использование обоих притяжательных элементов также будет работать (хотя, возможно, смешивание обязательного и необязательного притяжательного квантора в одном и том же шаблоне может привести к неправильному восприятию).

Следует также сказать, что хотя наличие шаблона регулярного выражения, который будет соответствовать a ⁿ b ⁿ , это здорово, на практике это не всегда «лучшее» решение. Гораздо лучшее решение - просто сопоставить ^(a+)(b+)$, а затем сравнить длину строк, захваченных группами 1 и 2 на языке программирования хостинга.

В PHP это может выглядеть примерно так ( как показано на ideone.com ):

function is_anbn($s) {
   return (preg_match('/^(a+)(b+)$/', $s, $groups)) &&
      (strlen($groups[1]) == strlen($groups[2]));
}

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

Как упоминалось выше, хотя эта статья обязательно помечена [regex]для stackoverflow, возможно, она о большем. Хотя, безусловно, есть ценность в изучении утверждений, вложенных ссылок, притяжательного квантификатора и т. Д., Возможно, более важным уроком здесь является творческий процесс, с помощью которого можно попытаться решить проблемы, решимость и тяжелая работа, которые часто требуются, когда вы сталкиваетесь с различные ограничения, систематический состав из различных частей для построения рабочего раствора и т. д.

Бонусный материал! Рекурсивный шаблон PCRE!

Поскольку мы действительно подняли PHP, необходимо сказать, что PCRE поддерживает рекурсивные шаблоны и подпрограммы. Таким образом, следующий шаблон работает для preg_match( как показано на ideone.com ):

$rRecursive = '/ ^ (a (?1)? b) $ /x';

В настоящее время регулярное выражение Java не поддерживает рекурсивный шаблон.

Еще больше бонусного материала! Соответствие a ⁿ b ⁿ c ⁿ !!

Итак , мы видели , как в соответствии с ^п б ^п , которая не является регулярным, но по- прежнему контекстно-свободной, но мы можем также соответствовать с ^п б ^п С ^п , которая не является даже контекстно-свободной?

Конечно, ДА! Читателям предлагается попытаться решить эту проблему самостоятельно, но решение представлено ниже (с реализацией на Java на ideone.com ).

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

Учитывая, что не упоминалось о поддержке рекурсивных шаблонов PCRE, я просто хотел бы указать на простейший и наиболее эффективный пример PCRE, который описывает рассматриваемый язык:

/^(a(?1)?b)$/

Как упоминалось в вопросе - с группой балансировки .NET шаблоны типа a ⁿ b ⁿ c ⁿ d ⁿ … z ⁿ могут быть легко сопоставлены как

^
  (?<A>a)+
  (?<B-A>b)+  (?(A)(?!))
  (?<C-B>c)+  (?(B)(?!))
  ...
  (?<Z-Y>z)+  (?(Y)(?!))
$

Например: http://www.ideone.com/usuOE

Редактировать:

Существует также шаблон PCRE для обобщенного языка с рекурсивным шаблоном, но необходим просмотр вперед. Я не думаю, что это прямой перевод вышесказанного.

^
  (?=(a(?-1)?b))  a+
  (?=(b(?-1)?c))  b+
  ...
  (?=(x(?-1)?y))  x+
     (y(?-1)?z)
$

Например: http://www.ideone.com/9gUwF