Swift 和正则表达式，cpu 对某些字符串失控

Question

我想用正则表达式匹配本地化行。一切正常，除非尝试匹配此字符串。您可以将代码放在 playground 中以查看它不会停止，或者将代码放在空白项目中以查看 cpu 100% 并停留在 'let match' 行。现在有趣的是，如果你删除最后一个词它会起作用。我不知道是否适用于中文或其他奇怪的字符，这是希腊语。

let lineContent = "\"key\" = \" Χρήση παλιάς συνόμευση\";"
if let r = try? NSRegularExpression(pattern: "\"(.*)+\"(^|[ ]*)=(^|[ ]*)\"(.*)+\";", options: NSRegularExpressionOptions()) {
   let match = r.matchesInString(lineContent, options: NSMatchingOptions(), range: NSMakeRange(0, lineContent.characters.count))
   match.count
}

稍后编辑：实际上字符类型并不重要，而是字数。这个放在右边的字符串也不起作用：'jhg jhgjklkhjkh hhhhh hhh'

Answer 1

正如评论中已经提到的那样，.*+ 导致了灾难性的回溯，导致 CPU 的高使用率（通常无法匹配）。

而不是使用像

这样的模式

\"(.*)+\"

因为您要匹配双引号之间的所有内容，请使用否定字符集：

\"([^\"]+)\"

Answer 2

根据上面的评论 - 用惰性版本替换嵌套的 (.*)+ - (.*?).

Answer 3

您在 (.*)+ 中嵌套了量词，这将导致 catastrophic backtracking（我建议阅读那篇文章）。问题是当子表达式失败时，正则表达式引擎回溯以测试另一个替代方案。嵌套量词意味着主题字符串中每个字符的尝试次数将呈指数级增长：它将测试 (.*)+ 的所有重复，并且对于每个字符，还将测试 .*.[=23 的所有重复=]

为避免这种情况，请使用尽可能具体定义的模式：

"\"([^\"]+)\"[ ]*=[ ]*\"([^\"]*)\";"

\"([^\"]+)\" 匹配
- 开场"
- [^\"]+ 除引号外的任意数量的字符。将 + 更改为 * 以允许空字符串。
- 收盘"

代码

let lineContent = "\"key\" = \" Χρήση παλιάς συνόμευση\";"
if let r = try? NSRegularExpression(pattern: "\"([^\"]+)\"[ ]*=[ ]*\"([^\"]*)\";", options: NSRegularExpressionOptions()) {
    let match = r.matchesInString(
        lineContent,
        options: NSMatchingOptions(), 
        range: NSMakeRange(0, lineContent.characters.count)
    )

    for index in 1..<match[0].numberOfRanges {
        print((lineContent as NSString).substringWithRange(match[0].rangeAtIndex(index)))
    }
}

SwiftStub demo

Swift 和正则表达式，cpu 对某些字符串失控

Swift and regex, cpu goes haywire for some strings

regex

swift

nsregularexpression