2

有一个简单的任务来获取 XPath 表达式并返回与（可能）选择的节点的父节点匹配的前缀。

例子：

/aaa/bbb       =>   /aaa
/aaa/bbb/ccc   =>   /aaa/bbb
/aaa/bbb/ccc[@x='1' and @y="/aaa[name='z']"] => /aaa/bbb

因为方括号内的模式可能包含引号内的括号，所以我决定尝试使用正则表达式来实现这一点。这是一个代码片段：

string input =
    "/aaa/bbb/ccc[@x='1' and @y=\"/aaa[name='z'] \"]";
                                            //  ^-- remove space for no loop
string pattern = @"/[a-zA-Z0-9]+(\[([^]]*(]"")?)+])?$";

System.Text.RegularExpressions.Regex re =
    new System.Text.RegularExpressions.Regex(pattern);
bool ismatch = re.IsMatch(input); // <== Infinite loop in here
// some code based on the match

因为模式相当规则，所以我查找了 '/' 后跟标识符，后跟一个匹配字符串末尾的可选组 (....)?$

代码似乎可以工作，但是使用不同的输入字符串值，我发现通过简单地插入一个空格（在注释中显示的位置），.NET IsMatch 函数进入一个无限循环，占用它获得的所有 CPU .

现在，不管这个正则表达式模式是否是最好的模式（我有更复杂但简化它以显示问题），这似乎表明使用 RegEx 与任何不平凡的事情可能是非常冒险的。

我错过了什么吗？有没有办法防止正则表达式匹配中的无限循环？

4

4 回答 4

7

好的，让我们分解一下：

Input: /aaa/bbb/ccc[@x='1' and @y="/aaa[name='z'] "]
Pattern: /[a-zA-Z0-9]+(\[([^]]*(]")?)+])?$

（我假设你的意思是 \" 在你的 C# 转义字符串中，而不是 ""... 从 VB.NET 翻译？）

首先，/[a-zA-Z0-9]+将吞噬第一个方括号，留下：

Input: [@x='1' and @y="/aaa[name='z'] "]

如果在 EOL 之前有 0 或 1 个实例，则 (\[([^]]*(]"")?)+])?$" 的外部组应该匹配。所以让我们打破内部，看看它是否匹配任何东西。

"[" 立即被吞噬，给我们留下：

Input: @x='1' and @y="/aaa[name='z'] "]
Pattern: ([^]]*(]")?)+]

分解模式：匹配 0 个或多个非]字符，然后匹配"] 0 或 1 次，一直这样做直到你不能。然后尝试找到并吞下一个]。

模式匹配基于[^]]*直到它到达]。

由于]和"之间有一个空格，因此它不能吞噬这两个字符中的任何一个，但是(]")之后的?仍然允许它返回 true。

现在我们已经成功匹配([^]]*(]")?)一次，但是+表示我们应该尝试尽可能多次匹配它。

这给我们留下了：

Input: ] "]

这里的问题是这个输入可以匹配([^]]*(]")?)无限次而不会被吞噬，而“+”将迫使它继续尝试。

您实际上是在匹配“1 个或多个”情况，您可以匹配“0 或 1”的某事物，然后是“0 或 1”的其他事物。由于两个子模式都不存在于剩余的输入中，因此它会在无限循环中保持匹配[^]]\*的 0 和(]")?的 0。

输入永远不会被吞噬，“+”之后的其余模式永远不会被评估。

（希望我在上面得到了 SO-escape-of-regex-escape。）

于 2009-07-29T21:37:57.823 回答
4

要回答最初的问题（即如何避免使用正则表达式的无限循环），这在 .Net 4.5 中变得很容易，因为您可以简单地将时间传递给正则表达式方法。有一个内部计时器将在超时到期时停止正则表达式循环并引发 RegexMatchTimeoutException

例如，您将执行以下操作

string input = "/aaa/bbb/ccc[@x='1' and @y=\"/aaa[name='z'] \"]";
string pattern = @"/[a-zA-Z0-9]+(\[([^]]*(]"")?)+])?$";
bool ismatch = Regex.IsMatch(input, pattern, RegexOptions.None, TimeSpan.FromSeconds(5));

您可以查看MSDN了解更多详细信息

于 2014-10-16T20:11:29.543 回答
2

这里的问题是这个输入可以匹配 ([^]]*(]")?) 无限次而不会被吞噬，而“+”将迫使它继续尝试。

这是 .NET 的 RegEx 实现中的一大错误。正则表达式不能那样工作。当你把它们变成自动机时，你会自动得到这样一个事实，一个空字符串的无限重复仍然是一个空字符串。

换句话说，任何没有错误的正则表达式引擎都会立即执行这个无限循环并继续执行其余的正则表达式。

如果您愿意，正则表达式是一种有限的语言，可以（并且很容易）检测和避免这种无限循环。

于 2016-10-25T09:42:50.157 回答
1

它表明，使用任何不重要的代码都是有风险的。您创建了可能导致无限循环的代码，RegEx 编译器必须这样做。自从前 20 个 IF X=0 THEN GOTO 10 以来，没有什么新的事情没有完成。

如果您在特定的边缘情况下担心这一点，您可以为 RegEx 生成一个线程，然后在一段合理的执行时间后将其终止。

于 2009-07-29T14:32:42.017 回答