Правила приоритета для сопоставления групп с регулярным выражением - PullRequest
1 голос
/ 01 февраля 2012

Рассмотрим следующее регулярное выражение .NET:

^(REF)?(.{1,10})-(\d{12})-(\d+)$

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

Теперь рассмотрим входную строку для этого регулярного выражения:

REFmisc03-123456789012-213

Можно сопоставить это так:

(REF)(misc03)-(123456789012)-(213)

И это также можно сопоставить так:

()(REFmisc03)-(123456789012)-(213)

Задокументировано, какой путь предпочтет механизм регулярных выражений, или это случайный случай?

1 Ответ

2 голосов
/ 03 февраля 2012

Это не случайно.Это сводится к тому, как квантификаторы интерпретируются механизмом регулярных выражений и потенциальным возвратом.Под квантификатором я имею в виду ? в (REF)?. Согласно MSDN :

Обычно квантификаторы являются жадными;они заставляют механизм регулярных выражений сопоставлять как можно больше вхождений определенных шаблонов.Добавление?характер к квантификатору делает его ленивым;это заставляет механизм регулярных выражений сопоставлять как можно меньше вхождений.

Другими словами, ? является жадным, а ?? - ленивым.Оба сопоставляют ноль или один раз, но они будут влиять на то, как выполняется сопоставление.

Что касается возврата, MSDN упоминает :

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

Еще один полезный ресурс, чтобы узнать больше об обратном отслеживании, можно найти здесь: Притяжательные квантификаторы .

Чтобы ответить на ваш вопрос напрямую, мы можем сравнить оба подхода.

Жадный подход

Исходный ввод: REFmisc03-123456789012-213

Использованиеиз (REF)? будет соответствовать вашему тексту с 4 группами (исключая первую группу со всем соответствием), и все группы будут успешно сопоставлены:

  1. REF
  2. misc03
  3. 123456789012
  4. 213

Соответствует вашему первому возможному сценарию сопоставления (в общих чертах):

(REF) (misc03) - (123456789012)- (213)

До тех пор, пока длина "misc..." составляет 1-10 символов, совпадение будет одинаковым, все 1-10 символов будут отображаться во второй группе.Часть REF всегда будет совпадать в первой группе.

Новый вход: REF-123456789012-213

Часть "misc..." отсутствует.Поскольку (REF)? является необязательным, а (.{1,10}) - необязательным, механизм регулярных выражений будет использовать ввод "REF" для удовлетворения последней (обязательной) части шаблона и игнорирования предыдущей (необязательной) части.Это приведет к следующим групповым значениям:

  1. "" (пустая строка, Success property = false)
  2. REF
  3. 123456789012
  4. 213

Ленивый подход

Исходный ввод: REFmisc03-123456789012-213

При использовании (REF)?? и сохранении остальныхваш шаблон тот же, квантификатор становится ленивым, и это возвращает 4 группы со следующими значениями:

  1. "" (пустая строка, Success property = false)
  2. REFmisc03
  3. 123456789012
  4. 213

Это соответствует вашему второму возможному сценарию совпадения:

() (REFmisc03) - (123456789012) -(213)

Так как первая группа является необязательной с ленивым квантификатором, механизм регулярных выражений может игнорировать ее.Поскольку "REFmisc03" имеет длину 9 символов, двигатель переходит к объединению "REF" с "misc03", поскольку они вписываются в группу (.{1,10}).

Новый ввод: REF-123456789012-213

Это ведет себя подобно жадному шаблону, и применяются те же рассуждения.

Еще один новый ввод: REFmisc0345-123456789012-213

В этом примере "misc0345" часть длиной 8 символов.Хотя в шаблоне используется ленивый квантификатор, он не может вписаться "REFmisc0345" во вторую группу, поскольку он превышает ограничение в 10 символов.Движок регулярных выражений будет возвращаться и совпадать с "REF" в первой группе и "misc0345" во второй группе:

  1. REF
  2. misc0345
  3. 123456789012
  4. 213
...