Как эта замена регулярного выражения меняет строку?

Это четвертая часть в серии учебных статей регулярных выражений. Он показывает, как комбинация вложенной ссылки (см. Как это регулярное выражение находит треугольные числа?) для "подсчета" внутри утверждений (см. Как мы можем сопоставить a ^ nb ^ n с регулярным выражением Java?) можно использовать для изменения строки. Программно сгенерированный шаблон использует абстракции мета-шаблона (см. Как это регулярное выражение Java обнаруживает палиндромы?). Впервые в серии эти методы используются вместо замены целых строк.

Предоставляются полные рабочие реализации Java и С#. Вдохновенные цитаты включены.

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

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

С# (также на ideone.com)

using System;
using System.Text.RegularExpressions;

public class TwoDollarReversal {    
public static void Main() {
   string REVERSE = 
      @"(?sx) . grab$2"
         .Replace("grab$2",
            ForEachDotBehind(
               AssertSuffix(@"((.) \1?)")
            )
         );
   Console.WriteLine(
      Regex.Replace(
         @"nietsniE treblA --
         hguone llew ti dnatsrednu t'nod uoy ,ylpmis ti nialpxe t'nac uoy fI",

         REVERSE, "$2"
      )
   );
   // If you can't explain it simply, you don't understand it well enough
   // -- Albert Einstein
}      
// performs an assertion for each dot behind current position
static string ForEachDotBehind(string assertion) {
   return "(?<=(?:.assertion)*)".Replace("assertion", assertion);
}
// asserts that the suffix of the string matches a given pattern
static string AssertSuffix(string pattern) {
   return "(?=.*$(?<=pattern))".Replace("pattern", pattern);
}

}

Java (также на ideone.com)

class TwoDollarReversal {

public static void main(String[] args) {
   String REVERSE =
      "(?sx) . grab$2"
         .replace("grab$2",
            forEachDotBehind(
               assertSuffix("((.) \\1?)")
            )
         );

   System.out.println(
      "taerG eht rednaxelA --\nyrt lliw ohw mih ot elbissopmi gnihton si erehT"
         .replaceAll(REVERSE, "$2")
   );
   // There is nothing impossible to him who will try
   // -- Alexander the Great"
}

static String forEachDotBehind(String assertion) {
   return "(?<=^(?:.assertion)*?)".replace("assertion", assertion);
}
static String assertSuffix(String pattern) {
   return "(?<=(?=^.*?pattern$).*)".replace("pattern", pattern);
}

}

Обе версии С# и Java, похоже, используют один и тот же общий алгоритм с незначительными вариациями только в деталях реферируемой реализации.

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

Приложение: Cheat sheet!

Это краткое описание основных конструкций регулярных выражений:

  • (?sx) - встроенный флаг modifiers. s позволяет использовать режим "однострочный", позволяя dot соответствовать ЛЮБОМУ символу (включая символы новой строки). x позволяет режим свободного пробега, где игнорируются пробелы без пробелов (и # может использоваться для комментариев).
  • ^ и $ - это начало и конец строки anchors.
  • ? как спецификатор повторения обозначает optional (т.е. нуль или один из). В качестве квантификатора повторения, например, .*? это означает, что повторение * (т.е. ноль или более) неохотно/non-greedy.
  • (…) используются для grouping. (?:…) - не захватывающая группа. Группа захвата сохраняет строку, в которой она соответствует; он позволяет использовать обратные/пересылаемые/вложенные ссылки (например, \1), замещение замещения (например, $2) и т.д.
  • (?=…) является положительным lookahead; он имеет право утверждать, что существует совпадение данного шаблона. (?<=…) - положительный lookbehind; он смотрит влево.

Ссылки на язык/дополнительные ресурсы

Ответы

Ответ 1

Обзор

На высоком уровне шаблон соответствует любому символу ., но дополнительно выполняет действие grab$2, которое фиксирует "помощник" разворота символа, который был сопоставлен с группой 2. Этот захват выполняется путем построения суффикс входной строки, длина которой соответствует длине префикса до текущей позиции. Мы делаем это, применяя assertSuffix к шаблону, который увеличивает суффикс на один символ, повторяя этот раз forEachDotBehind. Группа 1 фиксирует этот суффикс. Первый символ этого суффикса, записанный в группе 2, - это "мат" для символа, который был сопоставлен.

Таким образом, замена каждого совпадающего символа на его "мат" имеет эффект изменения строки.

Как это работает: более простой пример

Чтобы лучше понять, как работает шаблон регулярного выражения, сначала примените его на более простом входе. Кроме того, для нашего шаблона замены мы просто "выгрузим" все захваченные строки, чтобы мы лучше поняли, что происходит. Здесь версия Java:

System.out.println(
    "123456789"
        .replaceAll(REVERSE, "[$0; $1; $2]\n")
);

Вышеприведенные отпечатки (как видно на ideone.com):

[1; 9; 9]
[2; 89; 8]
[3; 789; 7]
[4; 6789; 6]
[5; 56789; 5]
[6; 456789; 4]
[7; 3456789; 3]
[8; 23456789; 2]
[9; 123456789; 1]

Таким образом, например, [3; 789; 7] означает, что точка соответствует 3 (зафиксирована в группе 0), соответствующий суффикс 789 (группа 1), чей первый символ 7 (группа 2). Обратите внимание, что 7 есть 3 "mate".

                   current position after
                      the dot matched 3
                              ↓        ________
                      1  2 [3] 4  5  6 (7) 8  9
                      \______/         \______/
                       3 dots        corresponding
                       behind      suffix of length 3

Обратите внимание, что символ "сопряжение" может быть справа или слева. Персонаж может даже быть его собственным "помощником".

Как создается суффикс: вложенная ссылка

Шаблон, отвечающий за сопоставление и создание растущего суффикса, следующий:

    ((.) \1?)
    |\_/    |
    | 2     |       "suffix := (.) + suffix
    |_______|                    or just (.) if there no suffix"
        1

Обратите внимание, что в определении группы 1 есть ссылка на себя (с \1), хотя она является необязательной (с ?). Необязательная часть предоставляет "базовый регистр", способ соответствия группы без ссылки на нее. Это необходимо, потому что попытка сопоставления ссылки на группу всегда терпит неудачу, когда группа еще ничего не зафиксировала.

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

Таким образом, этот шаблон пытается вырастить суффикс на одну точку. Повторение этого раз forEachDotBehind приведет к получению суффикса, длина которого точно равна длине префикса до нашей текущей позиции.

Как работают assertSuffix и forEachDotBehind: абстракции мета-шаблонов

Обратите внимание, что до сих пор мы рассматривали assertSuffix и forEachDotBehind как черные ящики. Фактически, оставление этого обсуждения в последний раз является преднамеренным действием: имена и краткая документация показывают, что они делают, и это было достаточно информации для нас, чтобы писать и читать наш шаблон REVERSE!

При ближайшем рассмотрении мы видим, что реализация этих абстракций Java и С# несколько отличается. Это связано с различиями между двумя двигателями регулярных выражений.

Механизм регулярных выражений .NET позволяет полностью регулярное выражение в lookbehind, поэтому эти мета-шаблоны выглядят намного более естественными в этом аромате.

  • AssertSuffix(pattern) := (?=.*$(?<=pattern)), то есть мы используем lookahead, чтобы пройти весь путь до конца строки, а затем использовать вложенный lookbehind для соответствия шаблону с суффиксом.
  • ForEachDotBehind(assertion) := (?<=(?:.assertion)*), т.е. мы просто сопоставляем .* в lookbehind, помечая это утверждение вместе с точкой внутри группы, не захваченной.

Так как Java официально не поддерживает бесконечную длину lookbehind (но она работает в любом случае при определенных обстоятельствах), ее аналог немного более неудобен:

  • assertSuffix(pattern) := (?<=(?=^.*?pattern$).*), т.е. мы используем lookbehind, чтобы пройти весь путь до начала строки, а затем использовать вложенный lookahead для соответствия всей строке, добавив шаблон суффикса с .*?, чтобы неохотно сопоставить какой-то нерелевантный префикс.
  • forEachDotBehind(assertion) := (?<=^(?:.assertion)*?), т.е. мы используем привязанный lookbehind с неохотным повторением, т.е. ^.*? (и аналогичным образом помещаем это утверждение вместе с точкой внутри группы, не захваченной).

Следует отметить, что, хотя реализация этих мета-шаблонов в С# не работает в Java, реализация Java работает в С# (видеть на ideone.com). Таким образом, нет фактической необходимости иметь разные реализации для С# и Java, но реализация С# сознательно использовала более мощную поддержку .NET regex engine lookbehind для более естественного выражения шаблонов.

Таким образом, мы показали преимущества использования абстракций мета-шаблона:

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

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

См. также

Закрытие мысли

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

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

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

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