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

99

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

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

L = { an bn: n > 0 }

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

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

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

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

Ссылки

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

полигенные смазочные материалы
источник
4
Эта серия была начата с разрешения некоторых участников сообщества ( meta.stackexchange.com/questions/62695/… ). Если прием хороший, я планирую продолжить рассмотрение других более сложных, а также более простых функций регулярного выражения.
polygenelubricants
Часть 3: stackoverflow.com/questions/3664881/…
polygenelubricants
Вау, я никогда не знал, что регулярные выражения Java не ограничиваются регулярными выражениями. Думаю, это объясняет, почему я всегда думал, что они не будут полностью реализованы. Я имею в виду, что в Java Regexs нет встроенных операторов дополнений, различий или продуктов, но это имеет смысл, поскольку они не ограничиваются обычными языками.
Lan
Этот вопрос был добавлен в FAQ по регулярным выражениям при переполнении стека в разделе «Advanced Regex-Fu».
aliteralmind

Ответы:

139

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

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

Язык, используемый для разработки решения, будет 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 n
  • Если их недостаточно 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 n b n .

Вот окончательный шаблон с дополнительными тестовыми примерами, в том числе одним из 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, и в 5000 б 5000 . Запуск на 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 n b n , это здорово, на практике это не всегда «лучшее» решение. Гораздо лучшее решение - просто сопоставить ^(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 n b n c n !!

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

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

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

полигенные смазочные материалы
источник
Несомненно, в этом длинном ответе могут быть ошибки / опечатки, поэтому, пожалуйста, оставляйте отзывы в качестве комментариев, чтобы я мог их исправить самостоятельно.
polygenelubricants
Прекрасная работа. Мне понадобится время, чтобы перечитать, но самую последнюю строчку прочитать практически невозможно; это такой мелкий шрифт. ------ Ой, подождите. Это feature? .... Не уверен, хорошая ли это идея. Я знаю, что это за последний символ, но его нельзя прочитать (кроме копирования и вставки).
Питер Айтай,
6
@Peter: Выделите небольшой текст, скопируйте и вставьте что-нибудь еще. Его специально усложнили для чтения: это спойлер, решение бонусной головоломки.
polygenelubricants
8
+1: Фантастическое объяснение, эти «Дополнительные статьи» - блестящие идеи.
Каллум Роджерс
1
@LarsH PHP preg_match()- это пример PCRE . Регулярные выражения Java, похоже, основаны на более старой версии регулярных выражений Perl . Это означает, что регулярные выражения PHP более мощные, чем версия на Java. По состоянию на 2013-02-21 , pcre.txt утверждает , что примерно соответствует Perl 5.12 . В то время как Perl в настоящее время находится на уровне 5.16, а 5.18 - через несколько месяцев. (На самом деле, к регулярным выражениям в то время особо не добавлялось)
Брэд Гилберт,
20

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

/^(a(?1)?b)$/
Jaytea
источник
+1 вау, я не знал, что PCRE поддерживает рекурсивный паттерн (я все еще учусь! Каждый день!). Я отредактировал статью, чтобы учесть эту информацию. Однако я не думаю, что рекурсивный шаблон может совпадать a^n b^n c^n.
polygenelubricants
Следует отметить, что этот вариант проще, но не так хорош, как опубликованный ответ - рекурсия переполняется на длинных строках.
Коби
@Kobi Это зависит от вашего определения «хорошо». Например, рекурсивное решение примерно на порядок быстрее, чем другое ( codepad.viper-7.com/CWgy7c ). И понять это намного проще. Рекурсивное решение - это в значительной степени прямое преобразование грамматики в регулярное выражение (на самом деле вы могли бы просто написать его в грамматической форме, это сработает).
NikiC
1
@polygeniclubricants, вы можете сопоставить этот шаблон с двумя рекурсивными шаблонами, один для потребления as и bs без захвата (и проверяет, есть ли одинаковое количество с рекурсией), за которым следует захватывающее регулярное выражение, которое жадно потребляет все a, а затем применяет рекурсивный шаблон для потребления и проверки того, что существует одинаковое количество bs и cs. Регулярное выражение: /^(?=(a(?-1)?b)c)a+(b(?-1)?c)$/x. Предоставлено
Джош Рибак,
11

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

^
  (?<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

Kennytm
источник
1
@poly: Спасибо :). На самом деле я не знаком с шаблонами .NET, но для такого рода шаблонов оказывается очень просто с балансировкой групп, поэтому я дополняю этот ответ.
kennytm 06
вы можете сделать это с помощью рекурсивного шаблона? Потому что, если вы не можете, это интересный поворот: балансирующая группа может делать то, чего не может делать рекурсивный паттерн. (И да, я очень ценю это дополнение).
polygenelubricants
кстати, я пропустил решение .NET по той причине, что у меня есть планы на тему «Как мы можем сопоставить a^n b^nс регулярным выражением .NET?» статья в будущем, но вы можете написать ее, если хотите. Я пишу эти статьи не только для себя; Я действительно хочу побудить других делать то же самое, чтобы на сайте был хороший контент.
polygenelubricants
Обновите, если вы нашли способ сделать это с помощью рекурсивных шаблонов. Я поигрался с уравновешивающими группами, чтобы захватить слова, длина которых составляет ряд Фибоначчи, и не мог заставить его работать. Возможно, это удастся осмотреться, аналогично тому, что я сделал.
Коби
1
Я просто хотел бы отметить, что версия этого шаблона для PCRE немного ошибочна, поскольку соответствует, если следующий фрагмент символов длиннее предыдущего. Смотрите здесь: regex101.com/r/sdlRTm/1 Вам нужно добавить (?!b), (?!c)и т.д. после того, как группы захвата , как так: regex101.com/r/sdlRTm/2
jaytea