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

Question

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

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

L = { a ^N b ^N : n > 0 }

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

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

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

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

Рекомендации

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

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

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

Answer 1

Ответ, разумеется, ДА! Вы наверняка можете написать шаблон регулярных выражений 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 "счет", используя самоссылку.

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

---

Шаг 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 "подсчитать", используя самоссылку! Но подождите... что-то не так со вторым и последним тестами! Не хватает b с, и как-то это считается неправильно! Мы рассмотрим, почему это произошло на следующем этапе.

Урок. Один из способов "инициализации" группы, ссылающейся на себя, состоит в том, чтобы сделать сопоставление с собственной ссылкой необязательным.

---

Шаг 4½: Понимание того, что пошло не так

Проблема в том, что, поскольку мы сделали сопоставление с собственной ссылкой необязательным, "счетчик" может "сбросить" обратно до 0, когда не хватает b "S. Давайте внимательно рассмотрим, что происходит на каждой итерации нашего шаблона с 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 в строке; другими словами, что на самом деле у нас есть ⁿ b ⁿ.

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

$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* в предвкушении, и действительно + loop ", оба разрешают возврат. Читателям предлагается подтвердить, почему это не является проблемой с точки зрения корректности, и почему одновременно может работать и притяжательный метод (хотя, возможно, смешивание обязательного и необязательного притяжательного квантификатора в одном и том же шаблоне может привести к неправильному восприятию).

Следует также сказать, что, хотя очень хорошо, что существует шаблон регулярного выражения, который будет соответствовать 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] для stackru это, возможно, о чем-то большем. Хотя, безусловно, полезно узнать об утверждениях, вложенных ссылках, собственнических квантификаторах и т. Д., Пожалуй, самый большой урок здесь - это творческий процесс, с помощью которого можно попытаться решить проблемы, решительность и тяжелая работа, которые часто требуются, когда вы подвергаетесь различные ограничения, систематический состав из разных частей для построения рабочего решения и т. д.

---

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

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

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

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

---

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

Итак, мы увидели, как сопоставить a ⁿ b ^n, который является нерегулярным, но все же не зависящим от контекста, но можем ли мы также сопоставить a ⁿ b ⁿ c ⁿ, который даже не является контекстно-свободным?

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

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

Answer 2

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

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

Answer 3

Как уже упоминалось в вопросе - с балансировочной группой.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