Добавление одного символа в мой .NET RegEx приводит к его зависанию - PullRequest
Новая
       9

Добавление одного символа в мой .NET RegEx приводит к его зависанию

5 голосов
/ 04 июня 2010

Вот входные данные: 

                                *** INVOICE ***                                

                              THE BIKE SHOP                              
                      1 NEW ROAD, TOWNVILLE,                       
                          SOMEWHERE, UK, AB1 2CD                          
                        TEL 01234-567890  

 To: COUNTER SALE                                   No:  243529 Page: 1

                                                    Date: 04/06/10 12:00

                                                    Ref:    Aiden   

 Cust No: 010000

Вот регулярное выражение, которое работает (Опции: singleline, ignorewhitespace, compiled) - оно совпадает немедленно и группы заполнены правильно: 

\W+INVOICE\W+
(?<shopAddr>.*?)\W+
To:\W+(?<custAddr>.*?)\W+
No:\W+(?<invNo>\d+).*?
Date:\W+(?<invDate>[0-9/ :]+)\W+
Ref:\W+(?<ref>[\w ]*?)\W+
Cust

Как только я добавляю 'N' из Cust No в рекс, анализ ввода зависает навсегда: 

\W+INVOICE\W+
(?<shopAddr>.*?)\W+
To:\W+(?<custAddr>.*?)\W+
No:\W+(?<invNo>\d+).*?
Date:\W+(?<invDate>[0-9/ :]+)\W+
Ref:\W+(?<ref>[\w ]*?)\W+
Cust N

Если я добавлю что-то вроде «любой персонаж»: 

\W+INVOICE\W+
(?<shopAddr>.*?)\W+
To:\W+(?<custAddr>.*?)\W+
No:\W+(?<invNo>\d+).*?
Date:\W+(?<invDate>[0-9/ :]+)\W+
Ref:\W+(?<ref>[\w ]*?)\W+
Cust .

Работает, но как только я добавляю фиксированный символ, рекс снова зависает: 

\W+INVOICE\W+
(?<shopAddr>.*?)\W+
To:\W+(?<custAddr>.*?)\W+
No:\W+(?<invNo>\d+).*?
Date:\W+(?<invDate>[0-9/ :]+)\W+
Ref:\W+(?<ref>[\w ]*?)\W+
Cust ..:

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

Ответы [ 3 ]

8 голосов
/ 04 июня 2010

С RegexOptions.IgnorePatternWhitespace вы говорите движку игнорировать пробелы в вашем шаблоне. Таким образом, когда вы пишете Cust No в шаблоне, это действительно означает CustNo, что не соответствует вводу. Это является причиной проблемы.

С документация :

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

Параметр RegexOptions.IgnorePatternWhitespace или встроенный параметр x изменяет это поведение по умолчанию следующим образом:

  • Неэкранированные пробелы в шаблоне регулярного выражения игнорируются. Чтобы быть частью шаблона регулярного выражения, необходимо экранировать символы пробела (например, как \s или "\ ").

Таким образом, вместо Cust No, в режиме IgnorePatternWhitespace вы должны написать Cust\ No, потому что в противном случае он интерпретируется как CustNo.

2 голосов
/ 04 июня 2010

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

E. г. в To:\W+(?<custAddr>.*?)\W+ .*? с удовольствием совпадет с теми же символами, что и \W, и, поскольку вы используете Singleline, .*? также перейдет в часть No:... входного текста и далее и в дальнейшем. В вашем примере я протестировал в RegexBuddy, что произойдет, если вы добавите «N» после «Cust» - механизм регулярных выражений прерывается после 1 000 000 шагов.

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

(?>\W+INVOICE\W+)
(?>(?<shopAddr>.*?)\W+To:)
(?>\W+(?<custAddr>.*?)\W+No:)
(?>\W+(?<invNo>\d+).*?Date:)
(?>\W+(?<invDate>[0-9/\ :]+)\W+Ref:)
(?>\W+(?<ref>[\w\ ]*?)\W+Cust)

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

0 голосов
/ 07 марта 2011

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

Например, если вы должны соответствовать выражению [abc] + c в «abc», это будет успешным. [Abc] + сначала будет соответствовать всем трем символам, затем последний c потерпит неудачу, потому что он достиг конца строки. Это приведет к возврату и совпадению только с «ab», что оставляет c для успешного совпадения.

Где, если вы попытаетесь сопоставить выражение [abc] ++ c в «abc», произойдет сбой. [Abc] ++ сначала будет соответствовать всем трем символам, затем завершится с ошибкой, потому что он достиг конца строки. Однако на этот раз возврата не будет из-за существующего квантификатора (дополнительный знак плюс +), и выражение не будет соответствовать.

Тим Пицкер указал альтернативу использованию пассивного квантификатора. Атомная группа может удерживать регулярное выражение от катастрофического возврата. Таким образом, для всех практических целей притяжательное выражение [abc] ++ c и атомарное выражение (?> [Abc] +) c эквивалентны.

Вы сэкономили мне много времени. Спасибо.

...