Поиск с возвратом в регулярных выраженияхBacktracking in Regular Expressions

Поиск с возвратом происходит, если шаблон регулярного выражения содержит переменные квантификаторы или конструкции изменения, и обработчик регулярных выражений возвращается в предыдущее сохраненное состояние, чтобы продолжить поиск совпадения.Backtracking occurs when a regular expression pattern contains optional quantifiers or alternation constructs, and the regular expression engine returns to a previous saved state to continue its search for a match. В поиске с возвратом заключена сила регулярных выражений. Благодаря ему выражения могут быть мощными и гибкими, а также совпадать со сложными шаблонами.Backtracking is central to the power of regular expressions; it makes it possible for expressions to be powerful and flexible, and to match very complex patterns. С другой стороны, эти возможности дорого обходятся.At the same time, this power comes at a cost. Часто именно поиск с возвратом существенно снижает производительность обработчика регулярных выражений.Backtracking is often the single most important factor that affects the performance of the regular expression engine. К счастью, разработчик может управлять работой обработчика регулярных выражений и тем, как он использует поиск с возвратом.Fortunately, the developer has control over the behavior of the regular expression engine and how it uses backtracking. В этом разделе описано, как функционирует поиск с возвратом, и как им можно управлять.This topic explains how backtracking works and how it can be controlled.

Примечание

В целом при использовании NFA-машины (недетерминированного конечного автомата), такой как обработчик регулярных выражений .NET, ответственность за создание эффективных и быстро выполняемых регулярных выражений лежит на разработчике.In general, a Nondeterministic Finite Automaton (NFA) engine like .NET regular expression engine places the responsibility for crafting efficient, fast regular expressions on the developer.

В этом разделе содержатся следующие подразделы.This topic contains the following sections:

Линейное сравнение без поиска с возвратомLinear Comparison Without Backtracking

Если шаблон регулярного выражения не содержит переменных квантификаторов или конструкций изменения, обработчик регулярных выражений работает за линейное время.If a regular expression pattern has no optional quantifiers or alternation constructs, the regular expression engine executes in linear time. Это значит, что когда обработчик регулярных выражений находит совпадение с первым языковым элементом шаблона в тексте входной строки, он сопоставляет следующий языковой элемент шаблона со следующим символом или группой символов входной строки.That is, after the regular expression engine matches the first language element in the pattern with text in the input string, it tries to match the next language element in the pattern with the next character or group of characters in the input string. Так продолжается, пока поиск совпадения не заканчивается успешно или неуспешно.This continues until the match either succeeds or fails. В обоих случаях обработчик регулярных выражений продвигается вперед, обрабатывая по одному символу входной строки.In either case, the regular expression engine advances by one character at a time in the input string.

Ниже приведен пример.The following example provides an illustration. Регулярное выражение e{2}\w\b ищет следующую строку: два вхождения буквы «e», затем символ слова, затем граница слова.The regular expression e{2}\w\b looks for two occurrences of the letter "e" followed by any word character followed by a word boundary.

using System;
using System.Text.RegularExpressions;

public class Example
{
   public static void Main()
   {
      string input = "needing a reed";
      string pattern = @"e{2}\w\b";
      foreach (Match match in Regex.Matches(input, pattern))
         Console.WriteLine("{0} found at position {1}", 
                           match.Value, match.Index);
   }
}
// The example displays the following output:
//       eed found at position 11
Imports System.Text.RegularExpressions

Module Example
   Public Sub Main()
      Dim input As String = "needing a reed"
      Dim pattern As String = "e{2}\w\b"
      For Each match As Match In Regex.Matches(input, pattern)
         Console.WriteLine("{0} found at position {1}", _
                           match.Value, match.Index)
      Next   
   End Sub
End Module
' The example displays the following output:
'       eed found at position 11

Несмотря на то что это регулярное выражение содержит квантификатор {2}, оно обрабатывается линейным образом.Although this regular expression includes the quantifier {2}, it is evaluated in a linear manner. Обработчик регулярных выражений не выполняет поиск с возвратом, поскольку квантификатор {2} не является переменным квантификатором; он указывает конкретное, а не переменное число вхождений предшествующей части выражения.The regular expression engine does not backtrack because {2} is not an optional quantifier; it specifies an exact number and not a variable number of times that the previous subexpression must match. В результате обработчик регулярных выражений ищет совпадение с шаблоном во входной строке, как показано в следующей таблице.As a result, the regular expression engine tries to match the regular expression pattern with the input string as shown in the following table.

ОперацияOperation Положение в шаблонеPosition in pattern Положение в строкеPosition in string РезультатResult
11 йe "needing a reed" (позиция 0)"needing a reed" (index 0) Нет совпадения.No match.
22 йe "eeding a reed" (позиция 1)"eeding a reed" (index 1) Возможное совпадение.Possible match.
33 e{2}e{2} "eding a reed" (позиция 2)"eding a reed" (index 2) Возможное совпадение.Possible match.
44 \w\w "ding a reed" (позиция 3)"ding a reed" (index 3) Возможное совпадение.Possible match.
55 \b\b "ing a reed" (позиция 4)"ing a reed" (index 4) Совпадение не подтвердилось.Possible match fails.
66 йe "eding a reed" (позиция 2)"eding a reed" (index 2) Возможное совпадение.Possible match.
77 e{2}e{2} "ding a reed" (позиция 3)"ding a reed" (index 3) Совпадение не подтвердилось.Possible match fails.
88 йe "ding a reed" (позиция 3)"ding a reed" (index 3) Совпадение отсутствует.Match fails.
99 йe "ing a reed" (позиция 4)"ing a reed" (index 4) Нет совпадения.No match.
1010 йe "ng a reed" (позиция 5)"ng a reed" (index 5) Нет совпадения.No match.
1111 йe "g a reed" (позиция 6)"g a reed" (index 6) Нет совпадения.No match.
1212 йe " a reed" (позиция 7)" a reed" (index 7) Нет совпадения.No match.
1313 йe a reed (позиция 8)"a reed" (index 8) Нет совпадения.No match.
1414 йe " reed" (позиция 9)" reed" (index 9) Нет совпадения.No match.
1515 йe reed (позиция 10)"reed" (index 10) Нет совпадения.No match
1616 йe "eed" (позиция 11)"eed" (index 11) Возможное совпадение.Possible match.
1717 e{2}e{2} "ed" (позиция 12)"ed" (index 12) Возможное совпадение.Possible match.
1818 \w\w "d" (позиция 13)"d" (index 13) Возможное совпадение.Possible match.
1919 \b\b "" (позиция 14)"" (index 14) Совпадение.Match.

Если в шаблоне регулярного выражения нет переменных квантификаторов или конструкций изменения, максимальное число сравнений, необходимое для поиска во входной строке совпадения с шаблоном регулярного выражения, примерно равно числу символов во входной строке.If a regular expression pattern includes no optional quantifiers or alternation constructs, the maximum number of comparisons required to match the regular expression pattern with the input string is roughly equivalent to the number of characters in the input string. В этом случае обработчик регулярных выражений использует 19 сравнений, чтобы определить возможные совпадения в этой 13-значной строке.In this case, the regular expression engine uses 19 comparisons to identify possible matches in this 13-character string. Другими словами, обработчик регулярных выражений работает почти за линейное время, если отсутствуют переменные квантификаторы или конструкции изменения.In other words, the regular expression engine runs in near-linear time if it contains no optional quantifiers or alternation constructs.

К началуBack to top

Поиск с возвратом с переменными квантификаторами и конструкциями измененияBacktracking with Optional Quantifiers or Alternation Constructs

Если регулярное выражение содержит переменные квантификаторы или конструкции изменения, оценка входной строки уже не может быть линейной.When a regular expression includes optional quantifiers or alternation constructs, the evaluation of the input string is no longer linear. При использовании NFA-машины сопоставление шаблонов определяется языковыми элементами регулярного выражения, а не символами входной строки.Pattern matching with an NFA engine is driven by the language elements in the regular expression and not by the characters to be matched in the input string. Поэтому обработчик регулярных выражений пытается найти полное совпадение для переменных подвыражений или подвыражений выбора.Therefore, the regular expression engine tries to fully match optional or alternative subexpressions. При переходе к следующему языковому элементу подвыражения и нарушении совпадения обработчик регулярных выражений отбрасывает совпавшую часть и возвращается к ранее сохраненному состоянию; ему снова требуется найти во входной строке совпадение с регулярным выражением целиком.When it advances to the next language element in the subexpression and the match is unsuccessful, the regular expression engine can abandon a portion of its successful match and return to an earlier saved state in the interest of matching the regular expression as a whole with the input string. Процесс возвращения к ранее сохраненному состоянию для поиска совпадения называется "поиск с возвратом".This process of returning to a previous saved state to find a match is known as backtracking.

Например, рассмотрим шаблон регулярного выражения .*(es), совпадающий с символами "es" и любыми предшествующими символам.For example, consider the regular expression pattern .*(es), which matches the characters "es" and all the characters that precede it. Как показано в следующем примере, если взять входную строку "Essential services are provided by regular expressions.", совпадать с шаблоном будет вся строка до букв "es" в слове "expressions" включительно.As the following example shows, if the input string is "Essential services are provided by regular expressions.", the pattern matches the whole string up to and including the "es" in "expressions".

using System;
using System.Text.RegularExpressions;

public class Example
{
   public static void Main()
   {
      string input = "Essential services are provided by regular expressions.";
      string pattern = ".*(es)"; 
      Match m = Regex.Match(input, pattern, RegexOptions.IgnoreCase);
      if (m.Success) {
         Console.WriteLine("'{0}' found at position {1}", 
                           m.Value, m.Index);
         Console.WriteLine("'es' found at position {0}", 
                           m.Groups[1].Index);      
      } 
   }
}
//    'Essential services are provided by regular expres' found at position 0
//    'es' found at position 47
Imports System.Text.RegularExpressions

Module Example
   Public Sub Main()
      Dim input As String = "Essential services are provided by regular expressions."
      Dim pattern As String = ".*(es)" 
      Dim m As Match = Regex.Match(input, pattern, RegexOptions.IgnoreCase)
      If m.Success Then
         Console.WriteLine("'{0}' found at position {1}", _
                           m.Value, m.Index)
         Console.WriteLine("'es' found at position {0}", _
                           m.Groups(1).Index)                  
      End If     
   End Sub
End Module
'    'Essential services are provided by regular expres' found at position 0
'    'es' found at position 47

В этом случае обработчик регулярных выражений использует поиск с возвратом следующим образом.To do this, the regular expression engine uses backtracking as follows:

  • Обработчик обнаруживает совпадение части выражения .* (что соответствует любому числу любых символов) со всей входной строкой.It matches the .* (which matches zero, one, or more occurrences of any character) with the whole input string.

  • Затем обработчик ищет совпадение для символа "e" шаблона регулярного выражения.It attempts to match "e" in the regular expression pattern. Однако во входной строке нет больше символов для поиска совпадения.However, the input string has no remaining characters available to match.

  • Обработчик возвращается к месту последнего успешного совпадения, "Essential services are provided by regular expressions", и сравнивает символ "e" с точкой в конце предложения.It backtracks to its last successful match, "Essential services are provided by regular expressions", and attempts to match "e" with the period at the end of the sentence. Совпадение отсутствует.The match fails.

  • Обработчик продолжает возвращаться к предыдущим успешным совпадениям, отступая по одному символу, пока предположительно подходящей подстрокой не становится подстрока "Essential services are provided by regular expr".It continues to backtrack to a previous successful match one character at a time until the tentatively matched substring is "Essential services are provided by regular expr". Затем обработчик сравнивает символ "e" шаблона со второй буквой "e" в слове "expressions" и обнаруживает совпадение.It then compares the "e" in the pattern to the second "e" in "expressions" and finds a match.

  • Затем он сравнивает символ "s" шаблона с символом "s" после символа "e" в строке (первая буква "s" в слове "expressions").It compares "s" in the pattern to the "s" that follows the matched "e" character (the first "s" in "expressions"). Совпадение успешно.The match is successful.

При использовании поиска с возвратом поиск совпадения шаблона регулярного выражения со входной строкой длиной 55 символов требует 67 операций сравнения.When you use backtracking, matching the regular expression pattern with the input string, which is 55 characters long, requires 67 comparison operations. Как правило, если в шаблоне регулярного выражения есть один переменный квантификатор или одна конструкция изменения, число сравнений, необходимых для поиска во входной строке совпадения с шаблоном регулярного выражения, более чем вдвое превышает число символов во входной строке.Generally, if a regular expression pattern has a single alternation construct or a single optional quantifier, the number of comparison operations required to match the pattern is more than twice the number of characters in the input string.

К началуBack to top

Поиск с возвратом со вложенными переменными квантификаторамиBacktracking with Nested Optional Quantifiers

Количество сравнений, необходимое для поиска во входной строке совпадения с шаблоном регулярного выражения, может увеличиваться экспоненциально, если шаблон включает большое количество конструкций изменения или вложенные конструкции изменения, или, что случается чаще, вложенные переменные квантификаторы.The number of comparison operations required to match a regular expression pattern can increase exponentially if the pattern includes a large number of alternation constructs, if it includes nested alternation constructs, or, most commonly, if it includes nested optional quantifiers. Например, шаблон регулярного выражения ^(a+)+$ должен совпадать со строкой, состоящей из одного и более символов "a".For example, the regular expression pattern ^(a+)+$ is designed to match a complete string that contains one or more "a" characters. В примере показаны две входные строки одинаковой длины, только одна из которых совпадает с шаблоном.The example provides two input strings of identical length, but only the first string matches the pattern. Класс System.Diagnostics.Stopwatch используется для определения времени выполнения операции поиска совпадения.The System.Diagnostics.Stopwatch class is used to determine how long the match operation takes.

using System;
using System.Diagnostics;
using System.Text.RegularExpressions;

public class Example
{
   public static void Main()
   {
      string pattern = "^(a+)+$";
      string[] inputs = { "aaaaaa", "aaaaa!" };
      Regex rgx = new Regex(pattern);
      Stopwatch sw;
      
      foreach (string input in inputs) {
         sw = Stopwatch.StartNew();   
         Match match = rgx.Match(input);
         sw.Stop();
         if (match.Success)
            Console.WriteLine("Matched {0} in {1}", match.Value, sw.Elapsed);
         else
            Console.WriteLine("No match found in {0}", sw.Elapsed);
      }
   }
}
Imports System.Diagnostics
Imports System.Text.RegularExpressions

Module Example
   Public Sub Main()
      Dim pattern As String = "^(a+)+$"
      Dim inputs() As String = { "aaaaaa", "aaaaa!" }
      Dim rgx As New Regex(pattern)
      Dim sw As Stopwatch
      
      For Each input As String In inputs
         sw = Stopwatch.StartNew()   
         Dim match As Match = rgx.Match(input)
         sw.Stop()
         If match.Success Then
            Console.WriteLine("Matched {0} in {1}", match.Value, sw.Elapsed)
         Else
            Console.WriteLine("No match found in {0}", sw.Elapsed)
         End If      
      Next
   End Sub
End Module

Как показывают выходные данные примера, у обработчика регулярных выражений установление отсутствия совпадения с шаблоном занимает в два раза больше времени, чем нахождение совпадения.As the output from the example shows, the regular expression engine took about twice as long to find that an input string did not match the pattern as it did to identify a matching string. Неуспешное совпадение — худший сценарий.This is because an unsuccessful match always represents a worst-case scenario. Обработчик регулярных выражений должен использовать регулярное выражение для проверки всех возможных путей в данных, чтобы заключить, что совпадения нет, а вложенные скобки сильно увеличивают количество таких путей.The regular expression engine must use the regular expression to follow all possible paths through the data before it can conclude that the match is unsuccessful, and the nested parentheses create many additional paths through the data. Чтобы установить, что вторая строка не совпадает с шаблоном, обработчику регулярных выражений нужно выполнить следующие действия:The regular expression engine concludes that the second string did not match the pattern by doing the following:

  • Он проверяет, что находится в начале строки, после чего проверяет первые пять символов строки на совпадение с шаблоном a+.It checks that it was at the beginning of the string, and then matches the first five characters in the string with the pattern a+. Затем проверяет, что в строке нет других групп символов "a".It then determines that there are no additional groups of "a" characters in the string. Затем выполняется проверка до конца строки.Finally, it tests for the end of the string. Поскольку в строке содержится один дополнительный символ, проверка оказывается неудачной.Because one additional character remains in the string, the match fails. Этот отрицательный результат требует 9 сравнений.This failed match requires 9 comparisons. Обработчик регулярных выражений также сохраняет информацию о состоянии при совпадениях "a" (совпадение 1), "aa" (совпадение 2), "aaa" (совпадение 3) и "aaaa" (совпадение 4).The regular expression engine also saves state information from its matches of "a" (which we will call match 1), "aa" (match 2), "aaa" (match 3), and "aaaa" (match 4).

  • Затем он возвращается к предварительно сохраненному совпадению 4.It returns to the previously saved match 4. Далее устанавливается наличие дополнительного символа "a", который назначается дополнительной захваченной группе.It determines that there is one additional "a" character to assign to an additional captured group. Затем выполняется проверка до конца строки.Finally, it tests for the end of the string. Поскольку в строке содержится один дополнительный символ, проверка оказывается неудачной.Because one additional character remains in the string, the match fails. Этот отрицательный результат требует 4 сравнений.This failed match requires 4 comparisons. Таким образом, всего выполнено 13 сравнений.So far, a total of 13 comparisons have been performed.

  • Затем он возвращается к предварительно сохраненному совпадению 3.It returns to the previously saved match 3. Он устанавливает наличие двух дополнительных символов "a", которые назначаются дополнительной захваченной группе.It determines that there are two additional "a" characters to assign to an additional captured group. Однако проверка на наличие окончания строки не проходит.However, the end-of-string test fails. Обработчик возвращается к совпадению 3 и пытается сопоставить два дополнительных символа "a" с двумя дополнительными захваченными группами.It then returns to match3 and tries to match the two additional "a" characters in two additional captured groups. Проверка на наличие окончания строки не проходит.The end-of-string test still fails. Для получения этих неуспешных совпадений потребовалось 12 сравнений.These failed matches require 12 comparisons. Таким образом, всего выполнено 25 сравнений.So far, a total of 25 comparisons have been performed.

Сравнение входной строки с регулярным выражением продолжается таким же образом, пока обработчик регулярных выражений не переберет все возможные комбинации совпадений, заключив, что совпадений нет.Comparison of the input string with the regular expression continues in this way until the regular expression engine has tried all possible combinations of matches, and then concludes that there is no match. Из-за наличия вложенных квантификаторов это сравнение представляет собой операцию экспоненциальной сложности O(2n), где n — количество символов входной строки.Because of the nested quantifiers, this comparison is an O(2n) or an exponential operation, where n is the number of characters in the input string. Это значит, что в худшем случае входная строка, состоящая из 30 символов, требует по примерным подсчетам 1 073 741 824 сравнений, а входная строка длиной 40 символов — 1 099 511 627 776 сравнений.This means that in the worst case, an input string of 30 characters requires approximately 1,073,741,824 comparisons, and an input string of 40 characters requires approximately 1,099,511,627,776 comparisons. При использовании строк такого или большего размера методы, выполняющие регулярные выражения, могут выполняться очень долго, прежде чем будет установлено, что входная строка не совпадает с шаблоном регулярного выражения.If you use strings of these or even greater lengths, regular expression methods can take an extremely long time to complete when they process input that does not match the regular expression pattern.

К началуBack to top

Управление поиском с возвратомControlling Backtracking

Поиск с возвратом позволяет создавать мощные и гибкие регулярные выражения.Backtracking lets you create powerful, flexible regular expressions. Однако, как было показано в предыдущем разделе, эти преимущества могут сопровождаться неприемлемо низкой производительностью.However, as the previous section showed, these benefits may be coupled with unacceptably poor performance. Чтобы предотвратить излишнее использование поиска с возвратом, необходимо указать интервал времени ожидания при создании экземпляра объекта Regex или вызвать соответствующий метод статического регулярного выражения.To prevent excessive backtracking, you should define a time-out interval when you instantiate a Regex object or call a static regular expression matching method. Этот метод будет рассмотрен в следующем разделе.This is discussed in the next section. Кроме того, в .NET Core поддерживаются три элемента языка регулярных выражений, ограничивающих или подавляющих поиск с возвратом, что позволяет выполнять сложные регулярные выражения, не теряя или почти не теряя в производительности: невозвращающиеся части выражения, утверждения просмотра назад и утверждения просмотра вперед.In addition, .NET supports three regular expression language elements that limit or suppress backtracking and that support complex regular expressions with little or no performance penalty: nonbacktracking subexpressions, lookbehind assertions, and lookahead assertions. Дополнительные сведения об этих элементах языка см. в разделе Grouping Constructs.For more information about each language element, see Grouping Constructs.

Определение интервала времени ожиданияDefining a Time-out Interval

Начиная с .NET Framework 4.5 можно задавать значение времени ожидания, которое равняется значению самого длинного интервала, необходимого обработчику регулярных выражений для выполнения поиска до первого совпадения, пока он не приостановит попытки найти соответствие и не вызовет исключение RegexMatchTimeoutException.Starting with the .NET Framework 4.5, you can set a time-out value that represents the longest interval the regular expression engine will search for a single match before it abandons the attempt and throws a RegexMatchTimeoutException exception. Чтобы задать интервал ожидания, укажите значение TimeSpan в конструкторе Regex.Regex(String, RegexOptions, TimeSpan) регулярных выражений экземпляра.You specify the time-out interval by supplying a TimeSpan value to the Regex.Regex(String, RegexOptions, TimeSpan) constructor for instance regular expressions. Кроме того, каждый статический метод сравнения с шаблоном имеет перегруженную версию с параметром TimeSpan , который позволяет указать значение времени ожидания.In addition, each static pattern matching method has an overload with a TimeSpan parameter that allows you to specify a time-out value. По умолчанию интервал времени ожидания задается в Regex.InfiniteMatchTimeout и время ожидания обработчика регулярных выражений не истекает.By default, the time-out interval is set to Regex.InfiniteMatchTimeout and the regular expression engine does not time out.

Важно!

Рекомендуется всегда устанавливать интервал времени ожидания, если регулярное выражение использует поиск с возвратом.We recommend that you always set a time-out interval if your regular expression relies on backtracking.

Выражение RegexMatchTimeoutException указывает на то, что обработчику регулярных выражений не удалось найти совпадение в пределах заданного интервала времени ожидания, но не указывает причину создания исключения.A RegexMatchTimeoutException exception indicates that the regular expression engine was unable to find a match within the specified time-out interval but does not indicate why the exception was thrown. Причина может быть как в излишнем поиске с возвратом, так и в недостаточном значении интервала времени ожидания для текущей загруженности системы на момент создания исключения.The reason might be excessive backtracking, but it is also possible that the time-out interval was set too low given the system load at the time the exception was thrown. При обработке исключения можно прервать дальнейший поиск совпадений входной строки или увеличить интервал времени ожидания и повторно выполнить операцию поиска.When you handle the exception, you can choose to abandon further matches with the input string or increase the time-out interval and retry the matching operation.

Например, следующий код вызывает конструктор Regex.Regex(String, RegexOptions, TimeSpan) для создания экземпляра объекта Regex со значением времени ожидания, равным одной секунде.For example, the following code calls the Regex.Regex(String, RegexOptions, TimeSpan) constructor to instantiate a Regex object with a time-out value of one second. Шаблон регулярного выражения (a+)+$, который сопоставляется с последовательностью из одного или нескольких символов "a" в конце строки, относится к шаблонам с чрезмерным использованием поиска с возвратом.The regular expression pattern (a+)+$, which matches one or more sequences of one or more "a" characters at the end of a line, is subject to excessive backtracking. Если создается исключение RegexMatchTimeoutException , то интервал времени ожидания в данном примере увеличивается до максимального значения, равного трем секундам.If a RegexMatchTimeoutException is thrown, the example increases the time-out value up to a maximum interval of three seconds. После этого попытки найти соответствие шаблону будут прерваны.After that, it abandons the attempt to match the pattern.

using System;
using System.ComponentModel;
using System.Diagnostics;
using System.Security;
using System.Text.RegularExpressions;
using System.Threading; 

public class Example
{
   const int MaxTimeoutInSeconds = 3;

   public static void Main()
   {
      string pattern = @"(a+)+$";    // DO NOT REUSE THIS PATTERN.
      Regex rgx = new Regex(pattern, RegexOptions.IgnoreCase, TimeSpan.FromSeconds(1));       
      Stopwatch sw = null;
      
      string[] inputs= { "aa", "aaaa>", 
                         "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
                         "aaaaaaaaaaaaaaaaaaaaaa>",
                         "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>" };
                                 
      foreach (var inputValue in inputs) {
         Console.WriteLine("Processing {0}", inputValue);
         bool timedOut = false;
         do { 
            try {
               sw = Stopwatch.StartNew();
               // Display the result.
               if (rgx.IsMatch(inputValue)) {
                  sw.Stop();
                  Console.WriteLine(@"Valid: '{0}' ({1:ss\.fffffff} seconds)", 
                                    inputValue, sw.Elapsed); 
               }
               else {
                  sw.Stop();
                  Console.WriteLine(@"'{0}' is not a valid string. ({1:ss\.fffff} seconds)", 
                                    inputValue, sw.Elapsed);
               }
            }
            catch (RegexMatchTimeoutException e) {   
               sw.Stop();
               // Display the elapsed time until the exception.
               Console.WriteLine(@"Timeout with '{0}' after {1:ss\.fffff}", 
                                 inputValue, sw.Elapsed);
               Thread.Sleep(1500);       // Pause for 1.5 seconds.

               // Increase the timeout interval and retry.
               TimeSpan timeout = e.MatchTimeout.Add(TimeSpan.FromSeconds(1));
               if (timeout.TotalSeconds > MaxTimeoutInSeconds) {
                  Console.WriteLine("Maximum timeout interval of {0} seconds exceeded.",
                                    MaxTimeoutInSeconds);
                  timedOut = false;
               }
               else {               
                  Console.WriteLine("Changing the timeout interval to {0}", 
                                    timeout); 
                  rgx = new Regex(pattern, RegexOptions.IgnoreCase, timeout);
                  timedOut = true;
               }
            }
         } while (timedOut);
         Console.WriteLine();
      }   
   }
}
// The example displays output like the following :
//    Processing aa
//    Valid: 'aa' (00.0000779 seconds)
//    
//    Processing aaaa>
//    'aaaa>' is not a valid string. (00.00005 seconds)
//    
//    Processing aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
//    Valid: 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa' (00.0000043 seconds)
//    
//    Processing aaaaaaaaaaaaaaaaaaaaaa>
//    Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 01.00469
//    Changing the timeout interval to 00:00:02
//    Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 02.01202
//    Changing the timeout interval to 00:00:03
//    Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 03.01043
//    Maximum timeout interval of 3 seconds exceeded.
//    
//    Processing aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>
//    Timeout with 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>' after 03.01018
//    Maximum timeout interval of 3 seconds exceeded.
Imports System.ComponentModel
Imports System.Diagnostics
Imports System.Security
Imports System.Text.RegularExpressions
Imports System.Threading 

Module Example
   Const MaxTimeoutInSeconds As Integer = 3
   
   Public Sub Main()
      Dim pattern As String = "(a+)+$"    ' DO NOT REUSE THIS PATTERN.
      Dim rgx As New Regex(pattern, RegexOptions.IgnoreCase, TimeSpan.FromSeconds(1))       
      Dim sw As Stopwatch = Nothing
      
      Dim inputs() As String = { "aa", "aaaa>", 
                                 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
                                 "aaaaaaaaaaaaaaaaaaaaaa>",
                                 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>" }
                                 
      For Each inputValue In inputs
         Console.WriteLine("Processing {0}", inputValue)
         Dim timedOut As Boolean = False
         Do 
            Try
               sw = Stopwatch.StartNew()
               ' Display the result.
               If rgx.IsMatch(inputValue) Then
                  sw.Stop()
                  Console.WriteLine("Valid: '{0}' ({1:ss\.fffffff} seconds)", 
                                    inputValue, sw.Elapsed) 
               Else
                  sw.Stop()
                  Console.WriteLine("'{0}' is not a valid string. ({1:ss\.fffff} seconds)", 
                                    inputValue, sw.Elapsed)
               End If
            Catch e As RegexMatchTimeoutException   
               sw.Stop()
               ' Display the elapsed time until the exception.
               Console.WriteLine("Timeout with '{0}' after {1:ss\.fffff}", 
                                 inputValue, sw.Elapsed)
               Thread.Sleep(1500)       ' Pause for 1.5 seconds.

               ' Increase the timeout interval and retry.
               Dim timeout As TimeSpan = e.MatchTimeout.Add(TimeSpan.FromSeconds(1))
               If timeout.TotalSeconds > MaxTimeoutInSeconds Then
                  Console.WriteLine("Maximum timeout interval of {0} seconds exceeded.",
                                    MaxTimeoutInSeconds)
                  timedOut = False
               Else                
                  Console.WriteLine("Changing the timeout interval to {0}", 
                                    timeout) 
                  rgx = New Regex(pattern, RegexOptions.IgnoreCase, timeout)
                  timedOut = True
               End If
            End Try
         Loop While timedOut
         Console.WriteLine()
      Next   
   End Sub 
End Module
' The example displays output like the following:
'    Processing aa
'    Valid: 'aa' (00.0000779 seconds)
'    
'    Processing aaaa>
'    'aaaa>' is not a valid string. (00.00005 seconds)
'    
'    Processing aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
'    Valid: 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa' (00.0000043 seconds)
'    
'    Processing aaaaaaaaaaaaaaaaaaaaaa>
'    Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 01.00469
'    Changing the timeout interval to 00:00:02
'    Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 02.01202
'    Changing the timeout interval to 00:00:03
'    Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 03.01043
'    Maximum timeout interval of 3 seconds exceeded.
'    
'    Processing aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>
'    Timeout with 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>' after 03.01018
'    Maximum timeout interval of 3 seconds exceeded.

Невозвращающиеся подвыраженияNonbacktracking Subexpression

Элемент языка (?> subexpression) подавляет поиск с возвратом в подвыражении.The (?> subexpression) language element suppresses backtracking in a subexpression. Это полезно для предотвращения проблем с производительностью, связанных с неуспешным совпадением.It is useful for preventing the performance problems associated with failed matches.

В следующем примере показано, как подавление поиска с возвратом улучшает производительность при использовании вложенных квантификаторов.The following example illustrates how suppressing backtracking improves performance when using nested quantifiers. В нем измеряется время, которое требуется обработчику регулярных выражений, чтобы определить, что входная строка не совпадает с двумя регулярными выражениями.It measures the time required for the regular expression engine to determine that an input string does not match two regular expressions. В первом регулярном выражении поиск с возвратом используется для поиска строки, содержащей последовательно одну и более шестнадцатеричных цифр, двоеточие, одну и более шестнадцатеричных цифр и два двоеточия.The first regular expression uses backtracking to attempt to match a string that contains one or more occurrences of one or more hexadecimal digits, followed by a colon, followed by one or more hexadecimal digits, followed by two colons. Второе регулярное выражение аналогично первому, но в нем отключен поиск с возвратом.The second regular expression is identical to the first, except that it disables backtracking. Как показывают выходные данные примера, отключение поиска с возвратом приводит к существенному росту производительности.As the output from the example shows, the performance improvement from disabling backtracking is significant.

using System;
using System.Diagnostics;
using System.Text.RegularExpressions;

public class Example
{
   public static void Main()
   {
      string input = "b51:4:1DB:9EE1:5:27d60:f44:D4:cd:E:5:0A5:4a:D24:41Ad:";
      bool matched;
      Stopwatch sw;
      
      Console.WriteLine("With backtracking:");
      string backPattern = "^(([0-9a-fA-F]{1,4}:)*([0-9a-fA-F]{1,4}))*(::)$";
      sw = Stopwatch.StartNew();
      matched = Regex.IsMatch(input, backPattern);
      sw.Stop();
      Console.WriteLine("Match: {0} in {1}", Regex.IsMatch(input, backPattern), sw.Elapsed);
      Console.WriteLine();
      
      Console.WriteLine("Without backtracking:");
      string noBackPattern = "^((?>[0-9a-fA-F]{1,4}:)*(?>[0-9a-fA-F]{1,4}))*(::)$";
      sw = Stopwatch.StartNew();
      matched = Regex.IsMatch(input, noBackPattern);
      sw.Stop();
      Console.WriteLine("Match: {0} in {1}", Regex.IsMatch(input, noBackPattern), sw.Elapsed);
   }
}
// The example displays output like the following:
//       With backtracking:
//       Match: False in 00:00:27.4282019
//       
//       Without backtracking:
//       Match: False in 00:00:00.0001391
Imports System.Diagnostics
Imports System.Text.RegularExpressions

Module Example
   Public Sub Main()
      Dim input As String = "b51:4:1DB:9EE1:5:27d60:f44:D4:cd:E:5:0A5:4a:D24:41Ad:"
      Dim matched As Boolean
      Dim sw As Stopwatch
      
      Console.WriteLine("With backtracking:")
      Dim backPattern As String = "^(([0-9a-fA-F]{1,4}:)*([0-9a-fA-F]{1,4}))*(::)$"
      sw = Stopwatch.StartNew()
      matched = Regex.IsMatch(input, backPattern)
      sw.Stop()
      Console.WriteLine("Match: {0} in {1}", Regex.IsMatch(input, backPattern), sw.Elapsed)
      Console.WriteLine()
      
      Console.WriteLine("Without backtracking:")
      Dim noBackPattern As String = "^((?>[0-9a-fA-F]{1,4}:)*(?>[0-9a-fA-F]{1,4}))*(::)$"
      sw = Stopwatch.StartNew()
      matched = Regex.IsMatch(input, noBackPattern)
      sw.Stop()
      Console.WriteLine("Match: {0} in {1}", Regex.IsMatch(input, noBackPattern), sw.Elapsed)
   End Sub
End Module
' The example displays the following output:
'       With backtracking:
'       Match: False in 00:00:27.4282019
'       
'       Without backtracking:
'       Match: False in 00:00:00.0001391

утверждения просмотра назадLookbehind Assertions

В платформу .NET входят два элемента языка, (?<=часть_выражения) и (?<!часть_выражения), которые сопоставляются с одним или несколькими предшествующими символами во входной строке..NET includes two language elements, (?<=subexpression) and (?<!subexpression), that match the previous character or characters in the input string. Оба элемента языка являются утверждениями нулевой ширины; они определяют, должны ли символы, непосредственно предшествующие текущему, соответствовать subexpression. Смещения или поиска с возвратом не происходит.Both language elements are zero-width assertions; that is, they determine whether the character or characters that immediately precede the current character can be matched by subexpression, without advancing or backtracking.

(?<= subexpression ) — это утверждение положительного просмотра назад; символы, непосредственно предшествующие текущему, должны соответствовать subexpression.(?<= subexpression ) is a positive lookbehind assertion; that is, the character or characters before the current position must match subexpression. (?<!subexpression) — это утверждение отрицательного просмотра назад; символы, непосредственно предшествующие текущему, не должны соответствовать subexpression.(?<!subexpression) is a negative lookbehind assertion; that is, the character or characters before the current position must not match subexpression. Утверждения положительного и отрицательного просмотра назад наиболее полезны, если subexpression является подмножеством предыдущего подвыражения.Both positive and negative lookbehind assertions are most useful when subexpression is a subset of the previous subexpression.

В следующем примере используются два равнозначных шаблона регулярных выражений, которые проверяют имя пользователя в адресе электронной почты.The following example uses two equivalent regular expression patterns that validate the user name in an email address. Первый шаблон демонстрирует низкую производительность из-за неоправданного использования поиска с возвратом.The first pattern is subject to poor performance because of excessive backtracking. Во втором шаблоне то же самое регулярное выражение изменено. Вложенный квантификатор заменен на утверждение положительного просмотра назад.The second pattern modifies the first regular expression by replacing a nested quantifier with a positive lookbehind assertion. Выходные данные примера демонстрируют время выполнения метода Regex.IsMatch .The output from the example displays the execution time of the Regex.IsMatch method.

using System;
using System.Diagnostics;
using System.Text.RegularExpressions;

public class Example
{
   public static void Main()
   {
      Stopwatch sw;
      string input = "test@contoso.com";
      bool result;
      
      string pattern = @"^[0-9A-Z]([-.\w]*[0-9A-Z])?@";
      sw = Stopwatch.StartNew();
      result = Regex.IsMatch(input, pattern, RegexOptions.IgnoreCase);
      sw.Stop();
      Console.WriteLine("Match: {0} in {1}", result, sw.Elapsed);
      
      string behindPattern = @"^[0-9A-Z][-.\w]*(?<=[0-9A-Z])@";
      sw = Stopwatch.StartNew();
      result = Regex.IsMatch(input, behindPattern, RegexOptions.IgnoreCase);
      sw.Stop();
      Console.WriteLine("Match with Lookbehind: {0} in {1}", result, sw.Elapsed);
   }
}
// The example displays output similar to the following:
//       Match: True in 00:00:00.0017549
//       Match with Lookbehind: True in 00:00:00.0000659
Module Example
   Public Sub Main()
      Dim sw As Stopwatch
      Dim input As String = "test@contoso.com"
      Dim result As Boolean
      
      Dim pattern As String = "^[0-9A-Z]([-.\w]*[0-9A-Z])?@"
      sw = Stopwatch.StartNew()
      result = Regex.IsMatch(input, pattern, RegexOptions.IgnoreCase)
      sw.Stop()
      Console.WriteLine("Match: {0} in {1}", result, sw.Elapsed)
      
      Dim behindPattern As String = "^[0-9A-Z][-.\w]*(?<=[0-9A-Z])@"
      sw = Stopwatch.StartNew()
      result = Regex.IsMatch(input, behindPattern, RegexOptions.IgnoreCase)
      sw.Stop()
      Console.WriteLine("Match with Lookbehind: {0} in {1}", result, sw.Elapsed)
   End Sub
End Module
' The example displays output similar to the following:
'       Match: True in 00:00:00.0017549
'       Match with Lookbehind: True in 00:00:00.0000659

Первый шаблон регулярного выражения ^[0-9A-Z]([-.\w]*[0-9A-Z])*@определяется, как показано в следующей таблице.The first regular expression pattern, ^[0-9A-Z]([-.\w]*[0-9A-Z])*@, is defined as shown in the following table.

ШаблонPattern ОПИСАНИЕDescription
^ Совпадение с началом строки.Start the match at the beginning of the string.
[0-9A-Z] Совпадение с алфавитно-цифровым символом.Match an alphanumeric character. Поскольку метод Regex.IsMatch вызывается с параметром RegexOptions.IgnoreCase , сравнение не зависит от регистра символов.This comparison is case-insensitive, because the Regex.IsMatch method is called with the RegexOptions.IgnoreCase option.
[-.\w]* Нуль и более совпадений с дефисом, точкой или символом слова.Match zero, one, or more occurrences of a hyphen, period, or word character.
[0-9A-Z] Совпадение с алфавитно-цифровым символом.Match an alphanumeric character.
([-.\w]*[0-9A-Z])* Ноль и более совпадений с комбинацией нуля и более дефисов, точек и символов слова, за которыми следует алфавитно-цифровой символ.Match zero or more occurrences of the combination of zero or more hyphens, periods, or word characters, followed by an alphanumeric character. Это первая группа записи.This is the first capturing group.
@ Совпадение со знаком "коммерческое эт" (@).Match an at sign ("@").

Второй шаблон регулярного выражения ^[0-9A-Z][-.\w]*(?<=[0-9A-Z])@использует утверждение положительного просмотра назад.The second regular expression pattern, ^[0-9A-Z][-.\w]*(?<=[0-9A-Z])@, uses a positive lookbehind assertion. Определяется, как показано в следующей таблице.It is defined as shown in the following table.

ШаблонPattern ОПИСАНИЕDescription
^ Совпадение с началом строки.Start the match at the beginning of the string.
[0-9A-Z] Совпадение с алфавитно-цифровым символом.Match an alphanumeric character. Поскольку метод Regex.IsMatch вызывается с параметром RegexOptions.IgnoreCase , сравнение не зависит от регистра символов.This comparison is case-insensitive, because the Regex.IsMatch method is called with the RegexOptions.IgnoreCase option.
[-.\w]* Нуль и более совпадений с дефисом, точкой или символом слова.Match zero or more occurrences of a hyphen, period, or word character.
(?<=[0-9A-Z]) Выполняется просмотр назад последнего совпавшего символа; поиск совпадения продолжается, если этот символ является алфавитно-цифровым.Look back at the last matched character and continue the match if it is alphanumeric. Обратите внимание, что алфавитно-цифровой символ является подмножеством набора, образованного точкой, дефисом и всеми символами слова.Note that alphanumeric characters are a subset of the set that consists of periods, hyphens, and all word characters.
@ Совпадение со знаком "коммерческое эт" (@).Match an at sign ("@").

утверждения просмотра впередLookahead Assertions

В платформу .NET входят два элемента языка, (?=часть_выражения) и (?!часть_выражения), которые сопоставляются с одним или несколькими следующими символами во входной строке..NET includes two language elements, (?=subexpression) and (?!subexpression), that match the next character or characters in the input string. Оба элемента языка являются утверждениями нулевой ширины; они определяют, должны ли символы, непосредственно следующие за текущим, соответствовать subexpression. Смещения или поиска с возвратом не происходит.Both language elements are zero-width assertions; that is, they determine whether the character or characters that immediately follow the current character can be matched by subexpression, without advancing or backtracking.

(?= subexpression ) — это утверждение положительного просмотра вперед; символы, непосредственно следующие за текущим, должны соответствовать subexpression.(?= subexpression ) is a positive lookahead assertion; that is, the character or characters after the current position must match subexpression. (?!subexpression) — это утверждение отрицательного просмотра вперед; символы, непосредственно следующие за текущим, не должны соответствовать subexpression.(?!subexpression) is a negative lookahead assertion; that is, the character or characters after the current position must not match subexpression. Утверждения положительного и отрицательного просмотра вперед наиболее полезны, если subexpression является подмножеством следующего подвыражения.Both positive and negative lookahead assertions are most useful when subexpression is a subset of the next subexpression.

В следующем примере используются два одинаковых шаблона регулярного выражения, проверяющих полное имя типа.The following example uses two equivalent regular expression patterns that validate a fully qualified type name. Первый шаблон демонстрирует низкую производительность из-за неоправданного использования поиска с возвратом.The first pattern is subject to poor performance because of excessive backtracking. Во втором шаблоне то же самое регулярное выражение изменено. Вложенный квантификатор заменен на утверждение положительного просмотра вперед.The second modifies the first regular expression by replacing a nested quantifier with a positive lookahead assertion. Выходные данные примера демонстрируют время выполнения метода Regex.IsMatch .The output from the example displays the execution time of the Regex.IsMatch method.

using System;
using System.Diagnostics;
using System.Text.RegularExpressions;

public class Example
{
   public static void Main()
   {
      string input = "aaaaaaaaaaaaaaaaaaaaaa.";
      bool result;
      Stopwatch sw;
      
      string pattern = @"^(([A-Z]\w*)+\.)*[A-Z]\w*$";
      sw = Stopwatch.StartNew();
      result = Regex.IsMatch(input, pattern, RegexOptions.IgnoreCase);
      sw.Stop();
      Console.WriteLine("{0} in {1}", result, sw.Elapsed);

      string aheadPattern = @"^((?=[A-Z])\w+\.)*[A-Z]\w*$";
      sw = Stopwatch.StartNew();
      result = Regex.IsMatch(input, aheadPattern, RegexOptions.IgnoreCase);
      sw.Stop();
      Console.WriteLine("{0} in {1}", result, sw.Elapsed);
   }
}
// The example displays the following output:
//       False in 00:00:03.8003793
//       False in 00:00:00.0000866
Imports System.Diagnostics
Imports System.Text.RegularExpressions

Module Example
   Public Sub Main()
      Dim input As String = "aaaaaaaaaaaaaaaaaaaaaa."
      Dim result As Boolean
      Dim sw As Stopwatch
      
      Dim pattern As String = "^(([A-Z]\w*)+\.)*[A-Z]\w*$"
      sw = Stopwatch.StartNew()
      result = Regex.IsMatch(input, pattern, RegexOptions.IgnoreCase)
      sw.Stop()
      Console.WriteLine("{0} in {1}", result, sw.Elapsed)

      Dim aheadPattern As String = "^((?=[A-Z])\w+\.)*[A-Z]\w*$"
      sw = Stopwatch.StartNew()
      result = Regex.IsMatch(input, aheadPattern, RegexOptions.IgnoreCase)
      sw.Stop()
      Console.WriteLine("{0} in {1}", result, sw.Elapsed)
   End Sub
End Module
' The example displays the following output:
'       False in 00:00:03.8003793
'       False in 00:00:00.0000866

Первый шаблон регулярного выражения ^(([A-Z]\w*)+\.)*[A-Z]\w*$определяется, как показано в следующей таблице.The first regular expression pattern, ^(([A-Z]\w*)+\.)*[A-Z]\w*$, is defined as shown in the following table.

ШаблонPattern ОПИСАНИЕDescription
^ Совпадение с началом строки.Start the match at the beginning of the string.
([A-Z]\w*)+\. Совпадение с алфавитным символом (A-Z), за которым следует ноль и более символов слова, повторенных ноль и более раз, за которыми следует точка.Match an alphabetical character (A-Z) followed by zero or more word characters one or more times, followed by a period. Поскольку метод Regex.IsMatch вызывается с параметром RegexOptions.IgnoreCase , сравнение не зависит от регистра символов.This comparison is case-insensitive, because the Regex.IsMatch method is called with the RegexOptions.IgnoreCase option.
(([A-Z]\w*)+\.)* Совпадение с предыдущим шаблоном ноль и более раз.Match the previous pattern zero or more times.
[A-Z]\w* Совпадение с алфавитно-цифровым символом, за которым следует ноль и более символов слова.Match an alphabetical character followed by zero or more word characters.
$ Совпадение должно заканчиваться в конце входной строки.End the match at the end of the input string.

Второй шаблон регулярного выражения ^((?=[A-Z])\w+\.)*[A-Z]\w*$использует утверждение положительного просмотра вперед.The second regular expression pattern, ^((?=[A-Z])\w+\.)*[A-Z]\w*$, uses a positive lookahead assertion. Определяется, как показано в следующей таблице.It is defined as shown in the following table.

ШаблонPattern ОПИСАНИЕDescription
^ Совпадение с началом строки.Start the match at the beginning of the string.
(?=[A-Z]) Выполняется просмотр вперед к следующему символу; если он является алфавитным (A-Z), продолжается поиск совпадения.Look ahead to the first character and continue the match if it is alphabetical (A-Z). Поскольку метод Regex.IsMatch вызывается с параметром RegexOptions.IgnoreCase , сравнение не зависит от регистра символов.This comparison is case-insensitive, because the Regex.IsMatch method is called with the RegexOptions.IgnoreCase option.
\w+\. Совпадение с одним или несколькими символами слова, за которыми следует точка.Match one or more word characters followed by a period.
((?=[A-Z])\w+\.)* Совпадение с одним или несколькими символами слова, за которым следует ноль и более точек.Match the pattern of one or more word characters followed by a period zero or more times. Первый символ слова должен быть алфавитным.The initial word character must be alphabetical.
[A-Z]\w* Совпадение с алфавитно-цифровым символом, за которым следует ноль и более символов слова.Match an alphabetical character followed by zero or more word characters.
$ Совпадение должно заканчиваться в конце входной строки.End the match at the end of the input string.

К началуBack to top

См. такжеSee also