5

这是输入数据：

                                *** 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

这是一个有效的正则表达式（选项：单行，忽略空白，编译） - 它立即匹配并且组被正确填充：

\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

一旦我将 Cust No 中的“N”添加到 rex 中，解析输入就会永远挂起：

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

它可以工作，但只要我添加一个固定字符，rex 就会再次挂起：

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

谁能告诉我为什么添加如此微不足道的东西会导致它倒下？我可以启用某种跟踪来观察匹配的活动，看看它是否陷入了灾难性的回溯？

4

3 回答 3

8

使用RegexOptions.IgnorePatternWhitespace，您是在告诉引擎忽略模式中的空格。因此，当您Cust No在模式中写入时，它实际上意味着CustNo, 与输入不匹配。这就是问题的原因。

从文档中：

默认情况下，正则表达式模式中的空格很重要；它强制正则表达式引擎匹配输入字符串中的空白字符。[...]

该RegexOptions.IgnorePatternWhitespace选项或xinline 选项会更改此默认行为，如下所示：

  • 正则表达式模式中未转义的空格将被忽略。要成为正则表达式模式的一部分，必须对空白字符进行转义（例如 as\s或"\ "）。

因此Cust No，在IgnorePatternWhitespace模式下，您必须编写Cust\ No，而不是 ，否则它会被解释为CustNo。

于 2010-06-04T13:24:27.940 回答
2

polygenelubricants 已经解释了您的正则表达式失败的原因。它挂起的原因是您遇到了灾难性的回溯。您的正则表达式有很多部分可以以多种不同的方式匹配相同的文本。如果整体匹配失败，正则表达式引擎将尝试所有可能的排列，直到将它们全部耗尽或因堆栈溢出而中止。

例如。inTo:\W+(?<custAddr>.*?)\W+将.*?很乐意匹配与 , 相同的字符\W，并且由于您正在使用Singleline，因此.*?也将越过No:...输入文本的一部分，并且越来越远。在您的示例中，我在 RegexBuddy 中测试了如果您在“Cust”之后添加“N”会发生什么 - 正则表达式引擎在 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)

如果输入和正则表达式碰巧不适合在一起，这允许正则表达式更快地失败。

于 2010-06-04T16:39:24.337 回答
0

当试图避免灾难性的回溯时，蒂姆·皮茨克 (Tim Pietzcker) 真的很感兴趣。.NET 缺少一个称为“占有量词”的功能。这基本上意味着正则表达式将尽可能贪婪，并且在回溯时不会放弃任何东西。

例如，如果您要在“abc”上匹配表达式 [abc]+c，它将成功。[abc]+ 将首先匹配所有三个字符，然后最后的 c 将失败，因为它已到达行尾。这将导致回溯并仅匹配“ab”，从而使 c 成功匹配。

如果您尝试在“abc”上匹配表达式 [abc]++c，它将失败。[abc]++ 将首先匹配所有三个字符，然后最后的 c 将失败，因为它已到达行尾。但是，这次不会因为位姿量词（额外的加号+）而出现回溯，表达式匹配失败。

Tim Pietzcker 指出了使用姿势量词的替代方法。原子组可以防止正则表达式发生灾难性的回溯。因此，出于所有实际目的，所有格表达式 [abc]++c 和原子表达式 (?>[abc]+)c 是等价的。

你为我节省了很多时间。谢谢你。

于 2011-03-07T17:53:58.630 回答