灾难性回溯
考虑用正则表达式 (x+x+)+y 匹配字符串 xxxxxxxxxxy (10 个 x). 显然正则可以改写为 xx+y 或者 x{2,}y, 但先不管这点, 该例旨在展示匹配机制.
- 第一个
x+匹配 10 个 x, 第二个x+没匹配上; 于是第一个x+回溯 到匹配 9 个 x, 第二个x+匹配一个 x. 至此 group 1x+x+完成了一次匹配. - Group 1 尝试重复, 但失败了, 于是
(x+x+)+完成了一次匹配. 接下来匹配 y, 完成匹配.
删除字符串结尾的 y 使得正则匹配失败会导致 灾难性回溯 (catastrophic backtracking).
