一、正则表达式中的贪婪匹配与懒惰匹配
1.1 贪婪匹配（Greedy Matching）
定义：
贪婪匹配是指正则表达式中的量词在匹配时，尽可能多地匹配字符，直到后续的模式无法匹配为止。
贪婪匹配的默认性：
如果没有明确指定懒惰匹配，正则表达式量词默认都是贪婪的。例如 *, +, {m,n} 等量词在没有其他修饰时，都是贪婪的。
示例：
let str = "abc123def456";
let regex = /\d+/; // \d+ 表示匹配一个或多个数字
console.log(str.match(regex)); // 输出 ["123"]
在这个示例中，\d+ 表示匹配一个或多个数字。由于 + 是贪婪匹配，正则引擎会尽可能多地匹配连续的数字，因此匹配结果为 123。
1.2 懒惰匹配（Lazy Matching）
定义：
懒惰匹配是指正则表达式中的量词尽可能少地匹配字符，也就是说它会在满足最小匹配条件时立即停下，而不是继续匹配更多的字符。
如何实现懒惰匹配：
在贪婪量词后面添加 ?，可以将贪婪匹配转为懒惰匹配。例如，*?, +?, {m,n}? 等。
示例：
let str = "abc123def456";
let regex = /\d+?/; // \d+? 表示懒惰匹配一个或多个数字
console.log(str.match(regex)); // 输出 ["1"]
在这个例子中，\d+? 是懒惰匹配，它会尽可能少地匹配数字字符。结果只会匹配到第一个数字 1，因为懒惰匹配会在最小的匹配条件下立即停下。
1.3 贪婪与懒惰的对比总结
- 贪婪匹配会尽可能多地匹配字符。
- 懒惰匹配会尽可能少地匹配字符。
| 类型 | 行为 | 示例 | 匹配结果 |
|---|---|---|---|
| 贪婪匹配 | 尽可能多地匹配 | \d+ | 123 |
| 懒惰匹配 | 尽可能少地匹配 | \d+? | 1 |
二、贪婪匹配中的回溯机制
回溯是贪婪匹配的核心原理。当贪婪匹配尽可能多地匹配字符后，可能会导致后续的模式无法匹配。这时，正则表达式引擎会通过回溯，逐步减少已匹配的字符，以便找到匹配的结果。
2.1 回溯的原理
贪婪匹配是逐步尝试最多的匹配字符：
- 正则引擎先尽量多地匹配字符。
- 如果后面的模式匹配失败，正则引擎会回溯，减少已匹配的字符数，看看是否能使整个表达式匹配成功。
2.2 回溯的例子
let str = "abc123def456";
let regex = /\d+def/; // 尝试匹配一个或多个数字后跟 "def"
console.log(str.match(regex)); // 输出 ["123def"]
匹配步骤：
- 正则引擎首先用
\d+贪婪匹配尽可能多的数字，因此匹配到123。 - 接下来，正则引擎尝试匹配
def，正好在123后找到def，因此匹配成功。
2.3 回溯的深入分析
如果贪婪匹配失败，引擎会尝试逐步减少匹配字符并回溯。对于较复杂的表达式和字符串，回溯可能会非常频繁，影响性能。例如：
let str = "aaaaaaaaaaaaaaaaaaaaaab";
let regex = /a+b/;
console.log(str.match(regex)); // 输出 ["aaaaaaaaaaaaaaaaaaaaaab"]
在这个例子中，正则 a+b 贪婪地匹配尽可能多的 a，然后匹配最后的 b。贪婪匹配首先匹配了所有的 a，但由于正则后面跟有 b，最后才能匹配成功。如果匹配失败（例如字符串没有 b），则引擎会回溯。
三、懒惰匹配中的回溯
懒惰匹配的回溯与贪婪匹配相反，它会首先匹配最少字符，然后如果后面的模式匹配失败，引擎会尝试匹配更多的字符。这种回溯过程通常比贪婪匹配更加简单，因为它总是从最少匹配开始。
3.1 懒惰匹配的回溯示例
let str = "abc123def456";
let regex = /\d+?def/; // 尝试懒惰匹配一个或多个数字后跟 "def"
console.log(str.match(regex)); // 输出 ["123def"]
步骤：
\d+?懒惰匹配，起初只匹配最少的数字（即1）。- 然后它会尝试匹配
def，但发现1后没有def，于是回溯并增加匹配的数字数量。 - 最终它匹配了
123后跟的def，匹配成功。
3.2 回溯深度分析
懒惰匹配虽然一开始匹配较少字符，但它依然可能需要回溯。当字符串较长且模式较复杂时，懒惰匹配的回溯频率也可能增高。例如：
let str = "aaaaaabbbbb";
let regex = /a+?b+/;
console.log(str.match(regex)); // 输出 ["aaaaaabbbbb"]
在这个例子中：
a+?懒惰匹配最少的a，即一个a。- 然后尝试匹配
b+，但后续发现无法完成匹配，因此回溯并增加a的匹配数量。 - 最终匹配到了
aaaaaabbbbb。
四、量词的贪婪与懒惰模式总结
4.1 贪婪量词
常见的贪婪量词：
*：匹配 0 次或多次，尽可能多匹配。+：匹配 1 次或多次，尽可能多匹配。?：匹配 0 次或 1 次，尽可能多匹配。{m,n}：匹配 m 到 n 次，尽可能多匹配。
4.2 懒惰量词
将贪婪量词变成懒惰量词的方式是添加 ?：
*?：匹配 0 次或多次，尽可能少匹配。+?：匹配 1 次或多次，尽可能少匹配。??：匹配 0 次或 1 次，尽可能少匹配。{m,n}?：匹配 m 到 n 次，尽可能少匹配。
4.3 性能问题
在复杂的正则表达式中，贪婪匹配和懒惰匹配可能都会导致大量的回溯，从而引发性能问题。尤其是当模式匹配失败时，频繁的回溯会让正则引擎进行大量计算。因此在实际使用中，需要根据具体场景合理选择贪婪或懒惰匹配，并注意避免过度复杂的匹配模式。
五、总结
通过重新梳理贪婪匹配和懒惰匹配的概念及其回溯机制，我们可以更好地理解正则表达式的工作原理。贪婪匹配尝试匹配尽可能多的字符，但可能带来频繁的回溯，而懒惰匹配则会尽量减少匹配字符，但在需要更长匹配时也可能回溯。选择合适的匹配模式，能够提高正则表达式的效率并减少性能开销。