0

到目前为止,在我对正则表达式的研究中,我得出的结论是,无论何时发生回溯,当前“在回溯点”的标记要么尝试扩展(假设它后面跟着一个惰性量词;比如 x*?最初抓取的“x”将尝试抓取另一个 x 以变成“xx”)或缩小(只要它后面跟着一个贪婪的量词;最初抓取“xxx”的 x* 将尝试释放一个 x 以保持“ xx”)。我的理解是,这些动作是严格由记号后面的量词类型决定的。

但这在某种程度上与正则表达式教程的这一部分中提供的信息相矛盾:http ://www.regular-expressions.info/catastrophic.html 。
那里的作者给出了一个正在搜索的字符串的例子 -

"1,2,3,4,5,6,7,8,9,10,11,12,13" and regex - "^([^,\r\n]*,){11}P".

他进一步指出:“如果找不到 P,引擎仍然会回溯。但它只会回溯 11 次,并且每次[^,\r\n]无法扩展超出逗号,迫使正则表达式引擎到 11 中的前一个立即迭代,无需尝试其他选项”。

“扩大”这个词让我很困惑。当它回溯时,令牌是否会在此时尝试扩展?正则表达式是否应该写成这样:"^([^,\r\n]*?,){11}P",不会出现任何问题,但现在我想知道我是否正确理解了回溯的概念
。?

有人可以对此有所了解吗?

4

1 回答 1

1

他所说的是[^,\r\n]*永远不会使用逗号以外的字符,这是分隔符。

如果字符集不包含逗号,那么回溯的数量将灾难性地增加,因为它是一个重复的子模式。

于 2012-08-04T23:13:37.583 回答