c# - 为什么这个正则表达式模式会导致解析器在给定某些输入时挂起？

Question

我有一个解析 TNS 名称文件的正则表达式。但是它会卡在某些 TNSNames 文件上。问题已追踪到匹配的字符串在 HOST= 部分之后是否有空格。忽略模式的适当性，以及如何解决问题(已处理)我想知道的是为什么输入的更改会导致应用程序挂起，如 Regex.Match(invalid) 调用永远不会返回

string valid = "SOMENAME = (DESCRIPTION= " + 
                "(ADDRESS= (PROTOCOL=TCP) (HOST = localhost) (PORT=1521) ) " + 
                "(CONNECT_DATA= (SERVICE_NAME=ABC)))";

string invalid = "SOMENAME = (DESCRIPTION= " + 
                "(ADDRESS= (PROTOCOL=TCP) (HOST =localhost) (PORT=1521) ) " + 
                "(CONNECT_DATA= (SERVICE_NAME=ABC)))";
Regex regex = new Regex("SOMENAME" + @"[^=]*=(\s|[^H]*)*HOST\s*=\s(?<host>[^\)]*)\s*\)", RegexOptions.Multiline | RegexOptions.IgnoreCase);
//this line is fine
Match match = regex.Match(valid);  
//this line causes visual studio to hang
match = regex.Match(invalid);

Answer 1

这肯定是由 catastrophic backtracking 引起的，罪魁祸首是

(\s|[^H]*)*

因为 \s 和 [^H] 可以匹配相同的内容，并且因为您嵌套了两个无限量词。

[^H]* 单独匹配完全相同的内容并且不容易回溯，所以试试这个:

Regex regex = new Regex("SOMENAME" + @"[^=]*=([^H]*)HOST\s*=\s(?<host>[^\)]*)\s*\)", RegexOptions.Multiline | RegexOptions.IgnoreCase);