Путаница с атомарной группировкой - чем она отличается от группирования регулярным выражением Ruby?

Я только что просмотрел документы по атомной группировке и rubyinfo, и у меня возникли следующие вопросы:

  1. Почему название пришло как "Атомная группировка"? Какую "атомарность" имеет эта общая группировка, которой нет.
  2. Чем атомная группировка отличается от общей?
  3. Почему атомные группы называются не захватывающими группами?

Я попробовал приведенный ниже код, чтобы понять, но у меня была путаница с выводом и как по-разному они работают на одной и той же строке?

irb(main):001:0> /a(?>bc|b)c/ =~ "abbcdabcc"
=> 5
irb(main):004:0> $~
=> #<MatchData "abcc">
irb(main):005:0> /a(bc|b)c/ =~ "abcdabcc"
=> 0
irb(main):006:0> $~
=> #<MatchData "abc" 1:"b">
Источник

3 ответа

Решение

() имеет некоторые свойства (включая такие, как (?!pattern), (?=pattern)и т. д. и равнина (pattern)), но общим свойством для всех них является группировка, которая делает произвольный шаблон единым целым (единица - моя собственная терминология), что полезно при повторении.

Нормальный захват (pattern) обладает свойством захвата и группировки. Захват означает, что текст, соответствующий шаблону внутри, будет захвачен, чтобы вы могли использовать его с обратной ссылкой, при сопоставлении или замене. Группа без захвата (?:pattern) не имеет свойства захвата, поэтому он сэкономит немного места и немного ускорит по сравнению с (pattern) так как он не хранит начальный и конечный индекс строки, соответствующей шаблону внутри.

Атомная группировка (?>pattern) также имеет свойство non-capturing, поэтому положение текста, соответствующего внутри, не будет зафиксировано.

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

Группа без атомарности позволит вернуться назад - она ​​все равно найдет первую последовательность, затем, если не удается выполнить сопоставление вперед, она вернется и найдет следующую последовательность, пока не будет найдено соответствие всему выражению регулярного выражения или пока не исчерпаны все возможности.

пример

Строка ввода: bbabbbabbbbc
Шаблон: /(?>.*)c/

Первый матч .* является bbabbbabbbbc из-за жадного квантификатора *, Он продержится в этом матче, запретив c от сопоставления. Сопоставитель повторяет попытку в следующей позиции до конца строки, и происходит то же самое. Так что ничто не соответствует регулярному выражению вообще.

Строка ввода: bbabbbabbbbc
Шаблон: /((?>.*)|b*)[ac]/, для тестирования /(((?>.*))|(b*))[ac]/

Есть 3 совпадения с этим регулярным выражением, которые bba, bbba, bbbbc, Если вы используете второе регулярное выражение, то же самое, но с добавлением групп захвата для отладки, вы можете увидеть, что все совпадения являются результатом сопоставления b* внутри.

Вы можете увидеть поведение возврата назад здесь.

  • Без атомной группировки /(.*|b*)[ac]/, строка будет иметь одно совпадение, которое является целой строкой, из-за обратного отслеживания в конце совпадения [ac], Обратите внимание, что двигатель вернется к .* вернуться на 1 символ, поскольку у него все еще есть другие возможности.

    Pattern: /(.*|b*)[ac]/
bbabbbabbbbc
^             -- Start matching. Look at first item in alternation: .*
bbabbbabbbbc
            ^ -- First match of .*, due to greedy quantifier
bbabbbabbbbc
            X -- [ac] cannot match
              -- Backtrack to ()      
bbabbbabbbbc
           ^  -- Continue explore other possibility with .*
              -- Step back 1 character
bbabbbabbbbc
            ^ -- [ac] matches, end of regex, a match is found

  • С атомной группировкой все возможности .* отрезан и ограничен первым матчем. Таким образом, после того, как жадно съел всю строку и не соответствует, двигатель должен пойти на b* шаблон, где он успешно находит соответствие регулярному выражению.

    Pattern: /((?>.*)|b*)[ac]/
bbabbbabbbbc
^             -- Start matching. Look at first item in alternation: (?>.*)
bbabbbabbbbc
            ^ -- First match of .*, due to greedy quantifier
              -- The atomic grouping will disallow .* to be backtracked and rematched
bbabbbabbbbc
            X -- [ac] cannot match
              -- Backtrack to ()
              -- (?>.*) is atomic, check the next possibility by alternation: b*
bbabbbabbbbc
^             -- Starting to rematch with b*
bbabbbabbbbc
  ^           -- First match with b*, due to greedy quantifier
bbabbbabbbbc
   ^          -- [ac] matches, end of regex, a match is found

    Последующие матчи продолжатся отсюда.

Источник

Недавно мне пришлось объяснять атомные группы кому-то еще, и я решил подправить и поделиться этим примером здесь.

Рассматривать the (big|small|biggest) (cat|dog|bird),

Совпадения, выделенные жирным шрифтом

  • большая собака
  • маленькая птичка
  • самая большая собака
  • маленький кот

Для первой строки, двигатель регулярного выражения найдет the, Затем перейдем к нашим прилагательным (big, small, biggest), он находит big, Сопрягая "большой", он продолжается и находит место. Потом смотрит на наших питомцев (cat, dog, bird) и находит cat пропускает и находит dog,

Для второй строки наше регулярное выражение найдет the, Было бы продолжить и посмотреть на big пропустите, посмотрите и найдите small, Затем он находит " ". Он смотрит на "кошку", пропускает ее, смотрит на "собаку", пропускает ее и находит "птицу".

Для третьей строки наше регулярное выражение найдет the, Продолжается и найти big который соответствует немедленному требованию, и продолжается. Он не может найти пространство, поэтому он возвращается (перематывает позицию к последнему выбранному варианту). Пропускает big, смотрит на small и пропускает это. Он находит самый большой, который также соответствует немедленному требованию. Затем он находит " ". Это смотрит на cat и пропускает, и совпадает dog,

Для четвертой строки наше регулярное выражение найдет the, Было бы продолжать смотреть на big пропустите, посмотрите и найдите small, Затем он находит " ". Это выглядит и соответствует cat,

Теперь рассмотрим the (?>big|small|biggest) (cat|dog|bird) Обратите внимание ?> атомная группа на прилагательных.

Совпадения, выделенные жирным шрифтом

  • большая собака
  • маленькая птичка
  • самая большая собака
  • маленький кот

Для первой, второй и четвертой строк наш двигатель работает одинаково.

Для третьей строки наше регулярное выражение найдет the, Он продолжает и находит "большой", который соответствует немедленному требованию, и продолжается. Он не может найти пространство, но атомная группа, являющаяся последним выбором, сделанным двигателем, не позволит пересмотреть этот выбор (запрещает возврат). Поскольку он не может сделать новый выбор, совпадение должно завершиться неудачей, поскольку у нашего простого выражения нет другого выбора.

Это только базовое резюме. Двигателю не нужно было бы смотреть на все cat знать, что это не соответствует dog достаточно просто посмотреть на c. При попытке сопоставить птицу, c в cat и d У собаки достаточно сказать двигателю, чтобы изучить другие варианты.

Однако если бы вы имели... ((cat|snake)|dog|bird) Двигателю также, конечно, нужно будет проверить змею, прежде чем она упадет в предыдущую группу и изучит собаку и птицу.

Есть также множество вариантов, которые двигатель не может решить, не пройдя мимо того, что может показаться не похожим на матч. Если у вас есть ((red)?cat|dog|bird) , Двигатель будет смотреть на "г", назад, обратите внимание на ? квантификатор, игнорировать подгруппу (red) и искать совпадение.

Источник

"Атомная группа" - это группа, в которой регулярное выражение никогда не будет возвращаться назад. Итак, в вашем первом примере /a(?>bc|b)c/ если bc чередование в групповых матчах, то он никогда не отступит и попробует b Чередование. Если вы немного измените свой первый пример, чтобы соответствовать "abcdabcc" тогда вы увидите, что он по-прежнему соответствует "abcc" в конце строки вместо "abc" в начале. Если вы не используете атомную группу, то она может вернуться назад bc и попробуйте b чередование и в конечном итоге соответствия "abc" в начале.

Что касается второго вопроса, как он отличается, то это просто перефразировка вашего первого вопроса.

И, наконец, атомные группы не называются "не захватывающими" группами. Это не альтернативное имя для них. Неподхваченные группы - это группы, которые не фиксируют свое содержимое. Обычно, когда вы сопоставляете регулярное выражение со строкой, вы можете извлечь все сопоставленные группы, а если вы используете подстановку, вы можете использовать обратные ссылки в подстановке, например \1 вставить туда захваченные группы. Но группа без захвата не обеспечивает этого. Классическая группа без захвата (?:pattern), Атомная группа также обладает свойством не захватывать, поэтому она называется группой без захвата.

Источник
Другие вопросы по тегам