Dodawanie pojedynczego znaku do mojego .NET RegEx powoduje powiesić

Question

Oto dane wejściowe:

       *** INVOICE ***         

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

To: COUNTER SALE         No: 243529 Page: 1 

                Date: 04/06/10 12:00 

                Ref: Aiden 

Cust No: 010000     

Tutaj jest regex, który działa (opcje: SingleLine, ignoreWhitespace, skompilowany) - pasuje natychmiast i grupy są prawidłowo wypełniane:

\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 

jak tylko dodam „n” z Cust Nie do rex, parsowania wejściowych wisi na zawsze:

\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 

Jeśli dodać coś jak „charakteru”:

\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 . 

To działa, ale jak tylko dodam stały charakter, Rex zawiesza się ponownie:

\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 ..: 

Może ktoś doradzić dlaczego dodając coś tak trywialny spowodowałby upadek? Czy mogę włączyć śledzenie, aby zobaczyć pasujące działanie, aby zobaczyć, czy utknie ono w katastroficznym backtracku?

Answer 1

Dzięki RegexOptions.IgnorePatternWhitespace, chcesz, aby silnik ignorował białe znaki we wzorcu. Tak więc, podczas pisania Cust No we wzorze, to naprawdę oznacza CustNo, który nie pasuje do wejścia. To jest przyczyną problemu.

Od the documentation:

Domyślnie białe miejsca w regularny wzór ekspresji jest znacząca; zmusza mechanizm wyrażeń regularnych do dopasowania znaku białej spacji w łańcuchu wejściowym. [...]

Opcja RegexOptions.IgnorePatternWhitespace lub opcja x inline zmienia to zachowanie domyślne, co następuje:

• Unescaped spacje w regularny wzór ekspresji jest ignorowany. Aby być częścią wzorca wyrażeń regularnych, znaki białe spacji muszą być znakowane (np. Jako \s lub "\ ").

Więc zamiast Cust No w trybie IgnorePatternWhitespace, należy napisać Cust\ No, bo inaczej to interpretować jako CustNo.

Answer 2

Polygenelubricants już wyjaśnił, dlaczego Twój regex nie powiodło się. Powodem, dla którego zawiesza się jest to, że używasz catastrophic backtracking. Twój regex ma wiele części, które mogą dopasować ten sam tekst na wiele różnych sposobów. Jeśli ogólne dopasowanie się nie powiedzie, silnik wyrażeń wypróbuje wszystkie możliwe permutacje, dopóki nie wyczerpie ich wszystkich lub przerwie przepełnienie stosu.

E. g. w wersji To:\W+(?<custAddr>.*?)\W+ z łatwością będzie pasować te same znaki co \W, a ponieważ używasz Singleline, .*? przejdzie również do części wejściowej tekstu i dalej i dalej.W twoim przykładzie testowałem w RegexBuddy, co się stanie, jeśli dodasz "N" po "Cust" - silnik regex przerywa po 1 000 000 kroków.

Aby tego uniknąć, trzeba wykonać regex bardziej szczegółowe, albo (to może być lepszym rozwiązaniem w tym przypadku) utrzymać silnik regex z wycofywania przez zamknięcie części, które zostały już dopasowane w „atomic groups”:

(?>\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) 

Pozwala to na wykonanie regexu znacznie szybciej, jeśli dane wejściowe i wyrażenie regularne nie pasują do siebie.

Answer 3

Tim Pietzcker jest naprawdę na coś tutaj, gdy stara się uniknąć katastroficznego wycofywania. .NET ma brakującą funkcję zwaną "kwantyzatorami dzierżawczymi". Zasadniczo oznacza to, że wyrażenie regularne będzie tak chciwe, jak to możliwe, i nie da nic, gdy cofa się.

Na przykład, jeśli miałbyś dopasować wyrażenie [abc] + c na "abc", to się uda. [Abc] + najpierw dopasuje wszystkie trzy znaki, a następnie c zakończy się niepowodzeniem, ponieważ dotarł do końca linii. To spowoduje, że backtrack i mecz po prostu "ab", który pozostawia c do udanego meczu.

Gdzie jeśli spróbujesz dopasować wyrażenie [abc] ++ c na "abc", to się nie powiedzie. [Abc] ++ najpierw dopasuje wszystkie trzy znaki, a następnie c zakończy się niepowodzeniem, ponieważ dotarł do końca linii. Jednak tym razem nie będzie backtrack ze względu na kwantyfikator o charakterze dodatnim (dodatkowy znak plus +), a wyrażenie nie będzie pasować.

Tim Pietzcker wskazał alternatywę dla użycia kwantyfikatora o charakterze kwantowym. Grupa atomowa może zachować regularną ekspresję od katastroficznego wstecznego śledzenia. Tak więc dla wszystkich praktycznych celów, wyrażenie dzierżawcze [abc] ++ c oraz wyrażenie atomowe (?> [Abc] +) c są równoważne.

Zaoszczędziłeś mi dużo czasu. Dziękuję Ci.