Catastrophic regex tracking problem

Question

I am new to regex and am currently facing a problem in this regard.

I am trying to create a regular expression that matches a string in the following format:

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

Each Sectionor is Subsectionindicated by a symbol {...}. Each is Placeholderindicated by a symbol %(...). Each Sectionor Subsectionmay have an arbitrary permutation OptionalStaticText, %(Placholder)and OptionalSubSection.

To do this, I created a regular expression, which is given below (also can be seen here ).

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

This expression matches perfectly valid strings (for example: abc {st1 %(ph1) st11} int {st2 %(ph2) st22}{st3 %(ph3) st33 {st31 %(ph4) st332}} cdthat can be checked in the specified link).

However, it calls a timeout whenever the input string is invalid (for example:, abc {st1 %(ph1) st11} int {st2 %(ph2) st22}{st3 %(ph3) st33 {st31 %(ph4) st332}} c-dis -not a valid character according to a character group [\s\w]).

Such an invalid string causes a timeout using Catastrophic backtracking, which can also be tested in the link above.

I must have made a rookie mistake, but I don't know what. Is there any change I have to make to avoid this?

Thanks.

Answer 1

If you have a timeout problem, it is probably because of this [%\(\w\)]+
which is a character class contained in the form you are looking for.

Use only form.

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

Formatted and tested:

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

Answer 2

^ $ (* +) .

$ .

regex alse , :

^(?:[\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

Js Demo

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"/>

Hide result

Answer 3

, . ( ):

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