logo标签列表

使用正则表达式时出现的灾难性回溯问题

javascriptregex
4

我在使用正则表达式方面还比较新手，目前遇到了一个问题。

我正在尝试构建一个正则表达式来匹配以下格式的字符串：

OptionalStaticText{OptionalStaticText %(Placholder) OptionalStaticText {OptionalSubSection} OptionalStaticText} OptionalStaticText

每个 Section 或 Subsection 由 {...} 表示。每个 Placeholder 由 %(...) 表示。每个 Section 或 Subsection 可以具有 OptionalStaticText、%(Placholder) 和 OptionalSubSection 的任意排列组合。

为此，我创建了一个正则表达式，如下所示（也可以在这里查看）。

/^(?:(?:(?:[\s\w])*(?:({(?:(?:[\s\w])*[%\(\w\)]+(?:[\s\w])*)+(?:{(?:(?:[\s\w])*[%\(\w\)]+(?:[\s\w])*)+})*})+)(?:[\s\w])*)+)$/g

这个表达式完美匹配有效的字符串（例如：abc {st1 %(ph1) st11} int {st2 %(ph2) st22}{st3 %(ph3) st33 {st31 %(ph4) st332}} cd，可以在给定的链接中测试）。
然而，当输入字符串无效时（例如：abc {st1 %(ph1) st11} int {st2 %(ph2) st22}{st3 %(ph3) st33 {st31 %(ph4) st332}} c-d，- 不是 [\s\w] 字符组中的有效字符），它会导致超时。
这种无效的字符串通过“灾难性回溯”导致超时，可以在上面的链接中进行测试。
我一定犯了一些新手错误，但不确定是什么。是否有任何更改可以避免这种情况？
谢谢。
1
我认为仅凭正则表达式是不适合这项工作的。即使你能够完成，最终的正则表达式对于大多数人来说都是完全无法阅读的，因此你将面临严重的维护问题。你可以尝试编写一个解析器来代替。 - abl
开始删除无用的组。 - Casimir et Hippolyte
3个回答
1
如果您遇到超时问题，可能是由于此类字符[%\(\w\)]+包含在您正在查找的表单中。
请改用表单本身。

^(?:(?:[\s\w]*(?:({(?:[\s\w]*%\(\w*\)[\s\w]*)+(?:{(?:[\s\w]*%\(\w*\)[\s\w]*)+})*})+)[\s\w]*)+)$

已格式化并测试过：

 ^ 
 (?:
      (?:
           [\s\w]* 
           (?:
                (                             # (1 start)
                     {
                     (?:
                          [\s\w]* 
                          % \( \w* \) 
                          [\s\w]* 
                     )+
                     (?:
                          {
                          (?:
                               [\s\w]* 
                               % \( \w* \) 
                               [\s\w]* 
                          )+
                          }
                     )*
                     }
                )+                            # (1 end)
           )
           [\s\w]* 
      )+
 )
 $
这个正则表达式匹配到字符串的结尾，但在多个测试用例中无法工作，请参见（此链接）[https://regex101.com/r/wT7jV3/1]。它还有一个不必要的括号层级（第一个括号）。 - Giuseppe Ricupero
@GsusRecovery - 是的，它确实有一个不必要的嵌套群集组。没什么大不了的，我不试图教育别人风格问题。我只是拿了他的正则表达式并解决了他的回溯问题。我不知道你怎么知道_他_的测试用例是什么，但那真的是问题吗？而且请向我展示一下单个嵌套群集组比没有使用时慢了一毫秒的证据。 - user557597
你可以在 regex101 上进行测试（如果我正确格式化了上面的链接）：没有外部组，正则表达式引擎会跳过 71 步，但这不是重点。我从问题中提取了测试用例的字符串描述：OptionalStaticText{OptionalStaticText %(Placholder) OptionalStaticText {OptionalSubSection} OptionalStaticText} OptionalStaticText。 - Giuseppe Ricupero
跳过71个步骤。我试图将每个“步骤”的微秒数相加以获得总数，但我无法做到。引擎存在于编译世界中，而不是步进世界中。至于在线测试工具，它们都是无用的垃圾，充满了噪音。 - user557597
我指出了你的答案中存在的问题（主要是在括号和外部括号方面，这只是你可以忽略的一个附加项），只是为了促使你修复它们，如果你能做到，请。我真的很好奇是否存在一个纯粹的正则表达式解决方案（主要是在JavaScript中）。 - Giuseppe Ricupero
显示剩余2条评论
1

尝试使用所有这些嵌套重复运算符(*或+)从开头的^到结尾的$精确匹配该行会导致灾难性回溯。

删除结尾锚点$，只需检查输入字符串的长度与匹配的长度是否相同。

我已重新编写了正则表达式，在去除可选部分的情况下也能起作用：

^(?:[\w \t]*(?:{(?:[\w \t]*|%\(\w+\)|{(?:[\w \t]*|%\(\w+\))+})+})?)+

在线演示

Legenda

^                              # Start of the line
(?:                            # OPEN NGM1 - Non matching group 1
  [\w \t]*                     # regex word char or space or tab (zero or more)
  (?:                          # OPEN NMG2
    {                          # A literal '{'
    (?:                        # OPEN NMG3 with alternation between:
      [\w \t]*|                # 1. regex word or space or tab (zero or more)
      %\(\w+\)|                # 2. A literal '%(' follower by regex word and literal ')'
      {(?:[\w \t]*|%\(\w+\))+} # 3. 
    )+                         # CLOSE NMG3 - Repeat one or more time
    }                          # A literal '}'
  )?                           # CLOSE NMG2 - Repeat zero or one time
)+                             # CLOSE NMG1 - Repeat one or more time

正则表达式模式

Regular expression visualization

Js演示

var re = /^(?:[\w \t]*(?:{(?:[\w \t]*|%\(\w+\)|{(?:[\w \t]*|%\(\w+\))+})+})?)+/;

var tests = ['OptionalStaticText{OptionalStaticText %(Placeholder) OptionalStaticText {OptionalSubSection} OptionalStaticText} OptionalStaticText', '{%(Placeholder) OptionalStaticText {OptionalSubSection}}', 'OptionalStaticText{%(Placeholder)} OptionalStaticText', 'abc {st1 %(ph1) st11} int {st2 %(ph2) st22}{st3 %(ph3) st33 {st31 %(ph4) st332}} cd', 'abc {st1 %(ph1) st11} int {st2 %(ph2) st22}{st3 %(!ph3!) st33 {st31 %([ph4]) st332}} cd', 'abc {st1 %(ph1) st11} int {st2 %(ph2) st22}{st3 %(ph3) st33 {st31 %(ph4) st332}} c-d',  'abc {st1 %(ph1) st11} int {st2 %(ph2) st22}{st3 %(ph3) st33 {st31 %(ph4) st332}} cd'];
var m;

while(t = tests.pop()) {
    document.getElementById("r").innerHTML += '"' + t + "'<br/>";
    document.getElementById("r").innerHTML += 'Valid string? ' + ( (t.match(re)[0].length == t.length) ? '<font color="green">YES</font>' : '<font color="red">NO</font>') + '<br/><br/>';
}
    
<div id="r"/>

只是提醒一下。尝试使用所有这些嵌套重复运算符（*或+）从开头^到结尾$精确匹配行会导致灾难性的回溯 - 这本身并不会导致回溯问题。像这样^(?:a(?:b(?:(?:c(?:d+)+)*)*)+)$就不会。 - user557597
0
你可以编写解析器来解析这种结构化字符串，解析器本身可以让你检查字符串的有效性。例如（不完整）：
var sample = "OptionalStaticText{OptionalStaticText %(Placholder) OptionalStaticText {OptionalSubSection} OptionalStaticText} OptionalStaticText";

function parse(str){

  return parseSection(str);

  function parseSection(str) {
    var section = new Section();
    var pointer = 0;

    while(!endOfSection()){

      if (placeHolderAhead()){
        section.push(parsePlaceHolder());
      } else if (sectionAhead()){
        section.push(parseInnerSection());
      } else {
        section.push(parseText());
      }
    }

    return section;

    function eat(token){
      if(str.substr(pointer, token.length) === token) {
        pointer += token.length;
        section.textLength += token.length;
      } else {
        throw ("Error: expected " + chr + " but found " + str.charAt(pointer));
      }
    }

    function parseInnerSection(){
      eat("{");
      var innerSection = parseSection(str.substr(pointer));
      pointer += innerSection.textLength;
      eat("}");
      return innerSection;
    }

    function endOfSection(){
      return (pointer >= str.length)
            || (str.charAt(pointer) === "}");
    }

    function placeHolderAhead(){
      return str.substr(pointer, 2) === "%(";
    }

    function sectionAhead(){
      return str.charAt(pointer) === "{";
    }

    function parsePlaceHolder(){
      var phText = "";
      eat("%(");
      while(str.charAt(pointer) !== ")") {
        phText += str.charAt(pointer);
        pointer++;
      }
      eat(")");
      return new PlaceHolder(phText);
    }

    function parseText(){
      var text = "";

      while(!endOfSection() && !placeHolderAhead() && !sectionAhead()){
        text += str.charAt(pointer);
        pointer++;
      }
      return text;
    }
  }
}

function Section(){
  this.isSection = true;
  this.contents = [];
  this.textLength = 0;

  this.push = function(elem){
    this.contents.push(elem);
    if(typeof elem === "string"){
      this.textLength += elem.length;
    } else if(elem.isSection || elem.isPlaceHolder) {
      this.textLength += elem.textLength;
    }
  }

  this.toString = function(indent){
    indent = indent || 0;
    var result = "";
    this.contents.forEach(function(elem){
      if(elem.isSection){
        result += elem.toString(indent+1);
      } else {
        result += Array((indent*8)+1).join(" ") + elem + "\n";
      }
    });
    return result;
  }
}

function PlaceHolder(text){
  this.isPlaceHolder = true;
  this.text = text;
  this.textLength = text.length;

  this.toString = function(){
    return "PlaceHolder: \"" + this.text + "\"";
  }
}


console.log(parse(sample).toString());

/* Prints:
OptionalStaticText
        OptionalStaticText 
        PlaceHolder: "Placholder"
         OptionalStaticText 
                OptionalSubSection
         OptionalStaticText
 OptionalStaticText
*/
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接