none
正则表达式在.NET中执行时,导致卡死,CPU一直占用100% RRS feed

  • 问题

  • 我有一段正则表达式,比如:

    public static MatchCollection RegexValidate(string words)
    {
          Regex regexForeignKey = new Regex(@"\s*AAA\s*", RegexOptions.IgnoreCase); // 这里的表达式只是为了说明
          MatchCollection matchColl = regexForeignKey.Matches(words);
          if (matchColl.Count == 0)
          {
            throw new ArgumentException("您输入的表达式错误!", "words");
          }
          return matchColl;
    }
    

     

    当运行时,有时侯会卡死,而且CPU一直占用100%。请问如何给这个方法设置一个过期时间,比如3秒。3秒后程序自动离开该方法,返回调用方法?
    或者直接在这个方法中抛出异常?

     

     


    2011年2月14日 9:28

答案

  • static void Main(string[] args)
    {
      string s = "AAA.{BBB},CCC.{DDD,EEE,FFF.{GGG}},HHH.{*},JJJ.{*,XXX.{YYY}},KKK.{LLL.{MMM},NNN,OOO},PPP.{QQQ,RRR.{SSS},TTT.{UUU,VVV},WWW}";
      List<MyData> result = new List<MyData>();
      Regex reg = new Regex(@"(?n)(?<name>[^{},]+)\{(?<data>((?<o>\{)|(?<-o>\})|[^{}]+)+(?(o)(?!)))\}", RegexOptions.Compiled);
      MatchCollection mc = reg.Matches(s);
      foreach (Match m in mc)
      {
        MyData t = new MyData(m.Groups["name"].Value, m.Groups["data"].Value);
        result.Add(t);
        foreach (Match m1 in reg.Matches(t.Code))
        {
          t.Inner.Add(new MyData(m1.Groups["name"].Value, m1.Groups["data"].Value));
        }
      }
      //输出
      foreach (MyData item in result)
      {
        Console.WriteLine(item.Name);
        Console.WriteLine("{");
        Console.WriteLine(Regex.Replace(item.Code, "(?<!{[^}]+),", "\r\n"));
        Console.WriteLine("}");
      }
      Console.ReadKey();
    }
    
    输出结果
    AAA.
    {
    BBB
    }
    CCC.
    {
    DDD
    EEE
    FFF.{GGG}
    }
    HHH.
    {
    *
    }
    JJJ.
    {
    *
    XXX.{YYY}
    }
    KKK.
    {
    LLL.{MMM}
    NNN
    OOO
    }
    PPP.
    {
    QQQ
    RRR.{SSS}
    TTT.{UUU,VVV}
    WWW
    }
    


    2011 c# mvp China
    • 已建议为答案 Flysha 2011年2月27日 1:03
    • 已标记为答案 陈书函 2011年2月27日 9:34
    • 取消答案标记 陈书函 2011年3月31日 9:47
    • 取消建议作为答案 陈书函 2011年3月31日 9:47
    • 已标记为答案 陈书函 2011年4月6日 3:50
    2011年2月26日 2:23

全部回复

  • 用线程异步 可以设置超时时间

    不过你这个cpu100% 估计是表达式问题,引起死循环了?

    先检查表达式吧。


    family as water
    2011年2月14日 11:03
  • 正则表达式引擎没有问题,问题在于你的表达式。正则表达式是对应文本规则的,你的*是贪婪模式,会可能造成回溯,因为前后都是*的贪婪模式,极端的情况下,可能会造成无限回溯导致假死,或是回溯过多看上去是效率不高的表现,尽量的选择非贪婪模式的*?,以及使用环视。

    既然你说你的表达式只是为了说明以下是,你实际的正则可能会比较有问题。正则问题不能一概而论,如果可以,你贴出文本和你实际正则给你分析一下。


    2011 c# mvp China
    2011年2月15日 0:54
  • 谢谢两位老师的回复!

    我上面那个正则表达式只是为了说明,真正我写的那个表达式有点复杂,是为了解析像JSON字符串那样的字符串,从而从中提取所有的对象。

    可我怕因为别的程序员不懂我这个表达式,而在调用我这个方法时,传入错误的参数,从而导致机器卡死。请问两位老师,有没有控制这个方法的调用时间,过期自动抛出异常或者

    离开这个方法?


    2011年2月16日 8:42
  • 建议你设断点,看看是否是停在你给出的正则语句上

    正则引擎效率是超级高的,不可能引起100%CPU,除非匹配结果过多,真有这种可能,建议加个线程,然后监视该线程

     

    我遇到过这个情况,通常是正则写的烂

    2011年2月16日 10:04
  • .net正则引擎无法避免大量回溯的问题,这是一个设计缺陷,很多的c++ regex引擎都具有防止大量回溯的功能,在.net下,大量回溯是导致正则引擎崩溃的主要原因。所以,实际使用中,表达式需要对应实际的文本,情况最糟糕的时候,是会有一个天文数字的回溯发生的。这个不可避免,无法中断,当然,你可以自己写一个线程独立运行,加入一个定时器,超时就强制结束线程,这样是可行的。

    避免回溯的方法很多,不能一概而论,比如使用原子组(?>exp),或是用更精确的描述表达式,避免范围过大,比如纯数字,你尽量用\d,而不是.,尽量选择吻合你情况的表达式,可以让表达式在错误的情况下更快的运行到失配结果,避免大量回溯。拼接字符串组合表达式要慎重。


    2011 c# mvp China
    2011年2月17日 0:48
  • 谢谢楼上的回答,我确定我的表达式没有错误,现在我真的不知道怎么办了?


    2011年2月18日 8:11
  • 我觉得George说得很有道理!  正则表达式的性能问题已经是老生常谈了。

    我觉得要继续研究您的问题,我们需要更具体的代码来重现这个问题。能否提供您使用的正则表达式?或许还有可以改进的地方。

    周末愉快!


    Michael Sun [MSFT]
    MSDN Community Support | Feedback to us
    Get or Request Code Sample from Microsoft
    Please remember to mark the replies as answers if they help and unmark them if they provide no help.

    2011年2月18日 13:39
  • 谢谢楼上老师的回答,明天我会贴出我的正则表达式和导致CPU 100% 的例子,希望老师们多多指教!
    2011年2月19日 12:18
  • 请老师们帮助优化一下我这个正则表达式,谢谢!

    using System;
    using System.Collections.Generic;
    using System.Text.RegularExpressions;
    
    namespace ConAppDemo
    {
      class Program
      {
        static void Main(string[] args)
        {
          MatchCollection matchColl = RegexValidate("AAA.{CCC},BBB.{DDD,EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE.{*}}"); //正确,打印:AAA  BBB
          // MatchCollection matchColl = RegexValidate("AAA.{CCC},BBB.{DDD,EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE.{}}"); //程序卡死,CPU 飙到 100% ,难道是我的电脑配置太低?
          List<Group> ltGroup = GetGroups(matchColl);
          foreach (Group groupItem in ltGroup)
          {
            Console.WriteLine(groupItem.Value);
          }
          Console.ReadKey();
        }
    
        private static readonly Regex regexForeignKey = new Regex(@"\s*(\w+|\*)\.\{\s*((\w+|\*|(\w+\.\{\s*((\w+|\*)\s*,?\s*)+\}))\s*,?\s*)+\s*\}\s*,?\s*", RegexOptions.IgnoreCase);
    
        /// <summary>
        /// 得到匹配结果
        /// </summary>
        /// <param name="words">表达式</param>
        /// <returns>匹配的结果集合</returns>
        public static MatchCollection RegexValidate(string words)
        {
          if (string.IsNullOrEmpty(words))
          {
            throw new ArgumentNullException("words", "参数不能为Null或Empty");
          }
          MatchCollection matchColl = regexForeignKey.Matches(words);
          if (matchColl.Count == 0)
          {
            throw new ArgumentException("您输入的表达式错误!", "words");
          }
          return matchColl;
        }
    
        /// <summary>
        /// 得到匹配结果
        /// </summary>
        /// <param name="matchColl"></param>
        /// <returns></returns>
        private static List<Group> GetGroups(MatchCollection matchColl)
        {
          if (matchColl == null)
          {
            throw new ArgumentNullException("matchColl", "参数不能为Null");
          }
          List<Group> groupColl = new List<Group>();
          if (matchColl.Count > 0)
          {
            foreach (Match matchItem in matchColl)
            {
              groupColl.Add(matchItem.Groups[1]);
            }
          }
          return groupColl;
        }
      }
    }
    
    

    2011年2月20日 7:47
  • \s*(\w+|\*)\.\{\s*((\w+|\*|(\w+\.\{\s*((\w+|\*)\s*,?\s*)+\}))\s*,?\s*)+\s*\}\s*,?\s*
    先看你这一段
    (\w+|\*|(\w+\.\{\s*((\w+|\*)\s*,?\s*)+\}))\s*,?\s*  
    是比较混乱,规则复杂。尝试开始优化,再拆开
    \w+|\*|(\w+\.\{\s*((\w+|\*)\s*,?\s*)+\})
    这里是三个并行的规则
    \w+
    \*
    \w+\.\{\s*((\w+|\*)\s*,?\s*)+\}
    这里,1和3之间,有相同的\w,那这样会在表达式3失配时候尝试回溯匹配表达式1,因为是并行的,也可能会表达式1匹配了尽可能多的\w字符,当表达式1失配后,引擎开始尝试使用并行的后面2个表达式匹配,\*可能可以,但也可能会失配,交给表达式3,此时没有\w了,因为已经被表达式1匹配完了,就会导致失配引起表达式3的匹配结果在
    abcd.{*,*}
    恒为假
    所以,你这里可以优化为
    (\w+(\.\{\s*((\w+|\*)\s*(?>,\s*)?)+\})?|\*)

    你整段的表达式
    \s*(\w+|\*)\.\{\s*((\w+|\*|(\w+\.\{\s*((\w+|\*)\s*,?\s*)+\}))\s*,?\s*)+\s*\}\s*,?\s*
    可以优化为
    \s*(\w+|\*)\.\{\s*(\w+(\.\{\s*((\w+|\*)\s*(?>,\s*)?)+\})?|\*)+\s*\}\s*,?\s*

    不过你表达式有点复杂,复杂的是你的想法有点偏,按你的思路重新整理了一下。用平衡组会效果好些。
    (?n)\w+\.\s*((?<o>\{)|(?<-o>\})|(\w+\.?|\*)\s*(,\s*)?)+(?(o)(?!))

    不知道我是否理解的正确。你试试吧。

    2011 c# mvp China
    2011年2月21日 1:22
  • @George.Wuyazhe

    您好,您给我的正则表达式不能解析我的表达式,会得到错误的结果。我要实现下面这样的功能,比如对于下面这个表达式:

    Text : 
    
    AAA.{BBB},CCC.{DDD,EEE,FFF.{GGG}},HHH.{*},JJJ.{*,XXX.{YYY}},KKK.{LLL.{MMM},NNN,OOO},PPP.{QQQ,RRR.{SSS},TTT.{UUU,VVV},WWW}
    
    
    展开后的效果图如下:
    
    AAA.
    {
    	BBB
    }
    ,
    CCC.
    {
    	DDD,
    	EEE,
    	FFF.{GGG}
    }
    ,
    HHH.
    {
    	*
    }
    ,
    JJJ.
    {
    	*,
    	XXX.{YYY}
    }
    ,
    KKK.
    {
    	LLL.{MMM},
    	NNN,
    	OOO
    }
    ,
    PPP.
    {
    	QQQ,
    	RRR.{SSS},
    	TTT.{UUU,VVV},
    	WWW
    }
    

    我想得到 AAA、CCC、HHH、JJJ、KKK、PPP  ,然后再 分别迭代它们。
    比如
    我得到 AAA 对象后, 然后再利用其他的正则表达式,得到 AAA的 子对象 BBB。
    我得到 CCC 对象后, 然后再利用其他的正则表达式,得到 AAA的 子对象 DDD、EEE、FFF{GGG}。然后再得到 FFF 的 子对象 GGG。说明:GGG 下面不能再有 子对象 了。


    请问老师们,我这个想法偏吗?


    2011年2月23日 8:25
  • 没,只要你需要,这个蛮容易的,你这么一说就明白了。

    [^{},]+\{((?<o>\{)|(?<-o>\})|[^{}]+)+(?(o)(?!))\}

    一会给你贴个代码。


    2011 c# mvp China
    2011年2月26日 1:42
  • static void Main(string[] args)
    {
      string s = "AAA.{BBB},CCC.{DDD,EEE,FFF.{GGG}},HHH.{*},JJJ.{*,XXX.{YYY}},KKK.{LLL.{MMM},NNN,OOO},PPP.{QQQ,RRR.{SSS},TTT.{UUU,VVV},WWW}";
      List<MyData> result = new List<MyData>();
      Regex reg = new Regex(@"(?n)(?<name>[^{},]+)\{(?<data>((?<o>\{)|(?<-o>\})|[^{}]+)+(?(o)(?!)))\}", RegexOptions.Compiled);
      MatchCollection mc = reg.Matches(s);
      foreach (Match m in mc)
      {
        MyData t = new MyData(m.Groups["name"].Value, m.Groups["data"].Value);
        result.Add(t);
        foreach (Match m1 in reg.Matches(t.Code))
        {
          t.Inner.Add(new MyData(m1.Groups["name"].Value, m1.Groups["data"].Value));
        }
      }
      //输出
      foreach (MyData item in result)
      {
        Console.WriteLine(item.Name);
        Console.WriteLine("{");
        Console.WriteLine(Regex.Replace(item.Code, "(?<!{[^}]+),", "\r\n"));
        Console.WriteLine("}");
      }
      Console.ReadKey();
    }
    
    输出结果
    AAA.
    {
    BBB
    }
    CCC.
    {
    DDD
    EEE
    FFF.{GGG}
    }
    HHH.
    {
    *
    }
    JJJ.
    {
    *
    XXX.{YYY}
    }
    KKK.
    {
    LLL.{MMM}
    NNN
    OOO
    }
    PPP.
    {
    QQQ
    RRR.{SSS}
    TTT.{UUU,VVV}
    WWW
    }
    


    2011 c# mvp China
    • 已建议为答案 Flysha 2011年2月27日 1:03
    • 已标记为答案 陈书函 2011年2月27日 9:34
    • 取消答案标记 陈书函 2011年3月31日 9:47
    • 取消建议作为答案 陈书函 2011年3月31日 9:47
    • 已标记为答案 陈书函 2011年4月6日 3:50
    2011年2月26日 2:23
  • @George.Wuyazhe

    老师,您太牛了,这个表达式猛的一看还看不懂,我试过了,可以,而且效率很快。非常感谢!<abbr class="affil" />


    2011年2月27日 9:34
  • Cool!
    Michael Sun [MSFT]
    MSDN Community Support | Feedback to us
    Get or Request Code Sample from Microsoft
    Please remember to mark the replies as answers if they help and unmark them if they provide no help.

    2011年2月27日 14:22
  • @George.Wuyazhe

    老师,又要再次麻烦您了。您能解释一下您提供的正则表达式吗?我展开了后得到:

    (?n)
    (?<name>[^{},]+)
    \{
    (?<data>
    	(
    		(
    			?<o>
    			\{
    		)
    		|
    		(
    			?<-o>
    			\}
    		)
    		|
    		[^{}]+
    	)+
    	(  
    		?(o)(?!)
    	)
    )
    \}
    

     

    有几个不明白的:

    1> 为什么要加 (?n) ,好像我测试时,不加也可以,它是什么意思啊?
    2> ?(o)(?!) 是什么意思啊?
    3> ?<o> 与 ?<-o> 是否是为了获取里面的值啊?
    4> (?<!{[^}]+), 的意思我大概知道,我有如下问题:

    Regex : (?<!{[^}]+),


    Source: QQQ,RRR.{SSS},TTT.{UUU,VVV},WWW


    结果:匹配了QQQ后面的逗号,SSS} 后面的逗号,VVV} 后面的逗号。


    我的问题:为什么没有匹配UUU后面的逗号呢?


    5> 对于

    string s = "AAA.{BBB},CCC.{DDD,EEE,FFF.{GGG}},HHH.{*},JJJ.{*,XXX.{YYY}},KKK.{LLL.{MMM},NNN,OOO},PPP.{QQQ,RRR.{SSS},TTT.{UUU,VVV},WWW}";

    我想得到父级下面的直接子类,且这些子类不能再有子类。比如我得到PPP对象后,我想得到 QQQ 和 WWW 这两个对象,并用逗号将它连接起来,在 MyData 类中新建一个属性来
    保存这个字符串“QQQ,WWW”。其中正则表达式怎么写呢?

     


    2011年3月31日 9:49
  • 我测试时的代码如下:

    using System;
    using System.Collections.Generic;
    using System.Text.RegularExpressions;
    
    namespace ConAppRegex
    {
      class Program
      {
        static void Main(string[] args)
        {
          string s = "AAA.{BBB},CCC.{DDD,EEE,FFF.{GGG}},HHH.{*},JJJ.{*,XXX.{YYY}},KKK.{LLL.{MMM},NNN,OOO},PPP.{QQQ,RRR.{SSS},TTT.{UUU,VVV},WWW}";
          // 展开后,得到如下效果:
          /*string s = @"
          AAA.
          {
            BBB
          },
          CCC.
          {
            DDD,
            EEE,
            FFF.{GGG}
          },
          HHH.
          {
            *
          },
          JJJ.
          {
            *,
            XXX.{YYY}
          },
          KKK.
          {
            LLL.{MMM},
            NNN,
            OOO
          },
          PPP.
          {
            QQQ,
            RRR.{SSS},
            TTT.{UUU,VVV},
            WWW
          }";
          */
          List<MyData> result = new List<MyData>();
          Regex reg = new Regex(@"(?n)(?<name>[^{},]+)\{(?<data>((?<o>\{)|(?<-o>\})|[^{}]+)+(?(o)(?!)))\}", RegexOptions.Compiled);
          MatchCollection mc = reg.Matches(s);
          foreach (Match m in mc)
          {
            MyData t = new MyData(m.Groups["name"].Value, m.Groups["data"].Value);
            result.Add(t);
            foreach (Match m1 in reg.Matches(t.Code))
            {
              t.Inner.Add(new MyData(m1.Groups["name"].Value, m1.Groups["data"].Value));
            }
          }
          //输出
          foreach (MyData item in result)
          {
            Console.WriteLine(item.Name);
            Console.WriteLine("{");
            Console.WriteLine(Regex.Replace(item.Code, "(?<!{[^}]+),", "\r\n"));
    
            //对于 KKK 对象,我想到 NNN 和 OOO 对象,并用逗号连接起来。
            //对于 PPP 对象,我想得到 QQQ 和 WWW 对象,并用逗号连接起来。正则表达式该怎么写呢?
    
            //foreach (MyData innerItem in item.Inner)
            //{
            //  Console.WriteLine(innerItem.Name);
            //  Console.WriteLine("{");
            //  Console.WriteLine(innerItem.Code);
            //  Console.WriteLine("}");
            //}
    
            Console.WriteLine("}");
          }
          Console.ReadKey();
        }
      }
    
      public class MyData
      {
        public MyData(string name, string code)
        {
          this.Name = name;
          this.Code = code;
        }
        public string Name { get; set; }
        public string Code { get; set; }
        public List<MyData> Inner = new List<MyData>();
      }
    }
    
    

    谢谢!


    2011年3月31日 9:59
  • 1.(?n) 的意思是取消未命名分组,目的是增加匹配速度,减少不必要的分组。

    2.?(o)(?!) 不是这样写的,这个是条件匹配,(?(o)(?!)),意思是当o分组匹配成功,这执行(?!),否则执行后面表达式,后面表达式省略,这不做任何匹配,(?!)的完整形式是逆序环视,(?!exp)当exp省略时,此表达式恒为假。这个是.net正则表达式中平衡组的关键,(?<o>)创建分组,押栈,(?<-o>)出栈,当最终,所有入栈的元素都出栈了,这(?(o))表达式失配,这不执行任何效果的匹配,给出最终结果,反之,如果有入栈,没出栈,这执行(?!),导致整个表达式失配。相关内容可以详细看看平衡组内容。

    3.上面说明了

    4.这个自己仔细看一下吧。一步一步分析,没什么好说的。仔细就行。

    5.忙,回头给你看。

     

    另外,不要取消标记正确答案,有问题再发令一个帖子。一个帖子弄太长多个问题不利于日后搜索做答案。


    2011 c# mvp China. *George读起来像不像“饺子”?我爱吃饺子,我叫George。
    2011年4月1日 1:45
  • @George.Wuyazhe

    1. 明白了。

    2. 大概有一点印象了,还需要在MSDN上面学习。

    3. 还需要学习。

    4. 完全明白了,突然想到 (?<!) 的匹配结果和 (?<=) 的匹配结果正好相反。但你的这个表达式不能适用于有N个子级的情况,也就没有入栈和出栈的概念了,您可以再想想,相信您本来就写得出来,只是偷一下懒,O(∩_∩)O

    5. 我差不多已经解决了,把已经匹配的表达式替换成 string.Empty 就行了。

    PS:我取消正确答案是想要您看到,怕系统认为这个问题解决了,就不会发邮件给您了。对于您的帮助,不胜感激,希望自己不断的努力,能达到您的水平。


    2011年4月4日 1:18
  • 这个是不能一条语句实现的,平衡组得到最外层的,如果多层,最好递归调用,当match对象的successed为false时止。平衡组本来就是最终分组会清空,所以无法匹配出内部有多少分组。不过可以试试嵌套分组,一层用于平衡组出入栈,一层用作结果捕获。但这个是无法和内容关联一起的。还是递归的匹配好点。
    2011 c# mvp China. *George读起来像不像“饺子”?我爱吃饺子,我叫George。
    2011年4月6日 5:01
  • 如果实在规则复杂,可以考虑自己用状态机实现分析,或是如果文本规则,可以当做xml文件分析,先把{替换为<,>替换为}。用xml方式。
    2011 c# mvp China. *George读起来像不像“饺子”?我爱吃饺子,我叫George。
    2011年4月6日 5:02
  • @George.Wuyazhe

    无过要匹配N级,确实要用递归,呵呵,不过我这个最大只能有3层,所以就不用递归了。

    谢谢您的帮助!


    2011年4月8日 9:45