js之正则表达式回溯的示例分析_程序开发

js之正则表达式回溯的示例分析

创始人

2024-11-26 19:21:53

0次

当一个正则表达式扫描目标字符串时，从左到右逐个扫描正则表达式的组成部分，在每个位置上测试能不能找到一个匹配。对于每一个量词和分支，都必须确定如何继续进行。如果是一个量词（如*、+?或者{2,}），那么正则表达式必须确定何时尝试匹配更多的字符；如果遇到分支（通过|操作符），那么正则表达式必须从这些选项中选择一个进行尝试。

当正则表达式做出这样的决定时，如果有必要，它会记住另一个选项，以备返回后使用。如果所选方案匹配成功，正则表达式将继续扫描正则表达式模板，如果其余部分匹配也成功了，那么匹配就结束了。但是，如果所选择的方案未能发现相应匹配，或者后来的匹配也失败了，正则表达式将回溯到最后一个决策点，然后在剩余的选项中选择一个。继续这样，直到找到一个匹配，或者量词和分支选项的所有可能的排列组合都尝试失败后放弃这一过程，然后移动到此过程开始位置的下一个字符上，重复此过程。

例如，下面的代码演示了这一过程是如何通过回溯处理分支的。

/h(ello|appy) hippo/.test("hello there, happy hippo");

上面一行正则表达式用于匹配“hello hippo”或“happy hippo”。测试一开始要查找一个h，目标字符串的第一个字母恰好就是h，立刻就找到了。接下来，子表达式（ello|appy）提供了两个处理选项。正则表达式选择最左边的选项（分支选择总是从左到右进行），检查ello 是否匹配字符串的下一个字符，确实匹配，然后正则表达式又匹配了后面的空格。

然而，在接下来的匹配中正则表达式“走进了死胡同”，因为hippo 中的h 不能匹配字符串中的下一个字母t。此时正则表达式还不能放弃，因为它还没有尝试过所有的选择，随后它回溯到最后一个检查点（在匹配了首字母h 之后的那个位置上）并尝试匹配第二个分支选项。但由于匹配没有成功，而且也没有更多的选项了，正则表达式认为从字符串的第一个字符开始匹配是不能成功的，因此它从第二个字符开始重新进行查找。正则表达式没有找到h，继续向后找，直到第14 个字母才找到，它匹配happy 的那个h。随后正则表达式再次进入分支过程，这次ello 未能匹配，但在回溯之后的第二次分支中，它匹配了整个字符串“happy hippo”，匹配成功了。

再如，下面代码演示了带重复量词的回溯。

var str = "Para 1.
" +"" +"Para 2.
" +"Div.";
/.*<\/p>/i.test(str);

正则表达式先匹配了字符串开始的3个字母

，然后是.*。点号表示匹配除换行符以外的任意字符，星号这个“贪婪”量词表示重复零次或多次，匹配尽量多的次数。因为目标字符串中没有换行符，正则表达式将匹配剩下的全部字符串！不过由于正则表达式模板中还有更多内容需要匹配，所以正则表达式尝试匹配<。由于在字符串末尾匹配不成功，因此每次回溯一个字符，继续尝试匹配<，直到正则表达式回到

标签的<位置。接下来尝试匹配\/（转义反斜杠），匹配成功，然后匹配p，匹配不成功。正则表达式继续回溯，重复此过程，直到第二段末尾时终于匹配了

。匹配返回成功需要从第一段头部一直扫描到最后一个的末尾，这可能不是我们想要的结果。

将正则表达式中的“贪婪”量词*改为“懒惰”（又名“非贪婪”）量词*?，以匹配单个段落。“懒惰”量词的回溯工作以相反方式进行。当正则表达式/

.*?<\/p>/推进到.*?时，首先尝试全部跳过，然后继续匹配<\/p>。

这样做是因为*?匹配零次或多次，尽可能少重复，尽可能少意味着可以重复零次。但是，当随后的<在字符串的这一点上匹配失败时，正则表达式回溯并尝试下一个最小的字符数：1个。正则表达式继续像这样向前回溯到第一段的末尾，在那里量词后面的<\/p>得到完全匹配。

如果目标字符串只有一个段落，那么此正则表达式的“贪婪”版本和“懒惰”版本是等价的，但尝试匹配的过程不同。

当一个正则表达式占用浏览器几秒甚至更长时间时，问题原因很可能是回溯失控。为说明此问题，给出下面的正则表达式，它的目标是匹配整个HTML文件。此表达式被拆分成多行是为了适合页面显示。与其他正则表达式不同，JavaScript在没有选项时可使点号匹配任意字符，包括换行符，所以此例中以[\s\S]匹配任意字符。

/[\s\S]*?[\s\S]*?[\s\S]*?<\/title>[\s\S]*?<\/head>
[\s\S]*?<body>[\s\S]*?<\/body>[\s\S]*?<\/html>/</pre><p>此正则表达式匹配在正常HTML 字符串时工作良好，但当目标字符串缺少一个或多个标签时，就会变得十分糟糕。例如</html>标签缺失，最后一个[\s\S]*?将扩展到字符串的末尾，因为在那里没有发现</html>标签，然后正则表达式将查看此前的[\s\S]*?队列记录的回溯位置，使它们进一步扩大。正则表达式尝试扩展倒数第二个[\s\S]*?—用它匹配</body>标签，就是此前匹配过正则表达式模板<\/body>的那个标签，然后继续查找第二个</body>标签，直到字符串的末尾。当所有这些步骤都失败时，倒数第三个[\s\S]*?将被扩展，直至字符串的末尾，依此类推。</p><p>此类问题的解决办法在于尽可能具体地指出分隔符之间的字符匹配形式，如模板“.*?”用于匹配双引号包围的一个字符串。用更具体的[^"\rn]*取代过于宽泛的.*?就去除了回溯时可能发生的几种情况，如尝试用点号匹配引号，或者扩展搜索超出预期范围。</p><p>在HTML 的例子中解决办法不是那么简单。不能使用否定字符类型，如用[^<]替代[\s\S]，因为在搜索过程中可能会遇到其他类型的标签。但是，可以通过重复一个非捕获组来达到同样效果，它包含一个回溯（阻塞下一个所需的标签）和[\s\S]（任意字符）元序列。这样可以确保中间位置上查找的每个标签都会失败。然后，更重要的是，[\s\S]模板在回溯过程中阻塞的标签在被发现之前不能被扩展。应用此方法后对正则表达式的最终修改如下：</p><pre class="brush:js;">/<html>(?:(?!<head>)[\s\S])*<head>(?:(?!<title>)[\s\S])*<title>

(?:(?!<\/title>)[\s\S])*<\/title>(?:(?!<\/head>)[\s\S])*<\/head>

(?:(?!<body>)[\s\S])*<body>(?:(?!<\/body>)[\s\S])*<\/body>
(?:(?!<\/html>)[\s\S])*<\/html>/</pre><p>虽然这样做消除了潜在的回溯失控，并允许正则表达式在匹配不完整HTML字符串失败时的使用时间与文本长度呈线性关系，但是正则表达式的效率并没有提高。像这样为每个匹配字符进行多次前瞻，缺乏效率，而且成功匹配过程也相当慢。匹配较短字符串时使用此方法相当不错，而匹配一个HTML 文件可能需要前瞻并测试上千次。</p>                <!--end::Text-->
            </div>
            <!--end::Description-->
            <div class="mt-5">
                <!--关键词搜索-->
                            </div>
            <div class="mt-5">
                <p class="fc-show-prev-next">
                    <strong>上一篇：</strong><a href="/kaifa/show-13780762.html">正则表达式中{n,m}量词怎么用</a><br>
                </p>
                <p class="fc-show-prev-next">
                    <strong>下一篇：</strong><a href="/kaifa/show-13780768.html">js中Abba逆向前瞻正则匹配的示例分析</a>                </p>
            </div>
            <!--begin::Block-->
            <div class="d-flex flex-stack mb-2 mt-10">
                <!--begin::Title-->
                <h3 class="text-dark fs-5 fw-bold text-gray-800">相关内容</h3>
                <!--end::Title-->
            </div>
            <div class="separator separator-dashed mb-9"></div>
            <!--end::Block-->
            <div class="row g-10">
                

            </div>


        </div>
        <!--end::Table widget 14-->
    </div>
    <!--end::Col-->

    <!--begin::Col-->
    <div class="col-xl-4 mt-0">
        <!--begin::Chart Widget 35-->
        <div class="card card-flush h-md-100">
            <!--begin::Header-->
            <div class="card-header pt-5 ">
                <!--begin::Title-->
                <h3 class="card-title align-items-start flex-column">
                    <!--begin::Statistics-->
                    <div class="d-flex align-items-center mb-2">
                        <!--begin::Currency-->
                        <span class="fs-5 fw-bold text-gray-800 ">热门资讯</span>
                        <!--end::Currency-->
                    </div>
                    <!--end::Statistics-->
                </h3>
                <!--end::Title-->
            </div>
            <!--end::Header-->
            <!--begin::Body-->
            <div class="card-body pt-3">

                                <!--begin::Item-->
                <div class="d-flex flex-stack mb-7">
                    <!--begin::Symbol-->
                    <div class="symbol symbol-60px symbol-2by3 me-4">
                        <div class="symbol-label" style="background-image: url('/uploadfile/[db:缩略图]')"></div>
                    </div>
                    <!--end::Symbol-->
                    <!--begin::Title-->
                    <div class="m-0">
                        <a href="/weixiu/show-14537931.html" class="text-dark fw-bold text-hover-primary fs-6">空调连续工作多久需要停机休息</a>
                        <span class="text-gray-600 fw-semibold d-block pt-1 fs-7">空调连续工作的时间取决于多个因素，包括空调的型号、功率、使用环境和维护情况等。一般来说，空调可以连续...</span>
                    </div>
                    <!--end::Title-->
                </div>
                                <!--begin::Item-->
                <div class="d-flex flex-stack mb-7">
                    <!--begin::Symbol-->
                    <div class="symbol symbol-60px symbol-2by3 me-4">
                        <div class="symbol-label" style="background-image: url('/uploadfile/[db:缩略图]')"></div>
                    </div>
                    <!--end::Symbol-->
                    <!--begin::Title-->
                    <div class="m-0">
                        <a href="/weixiu/show-14537930.html" class="text-dark fw-bold text-hover-primary fs-6">空调哪个符号是除湿的</a>
                        <span class="text-gray-600 fw-semibold d-block pt-1 fs-7">空调除湿功能通常用一个水滴形状的符号表示。不同品牌和型号的空调遥控器可能会有所差异，但一般来说，除湿...</span>
                    </div>
                    <!--end::Title-->
                </div>
                                <!--begin::Item-->
                <div class="d-flex flex-stack mb-7">
                    <!--begin::Symbol-->
                    <div class="symbol symbol-60px symbol-2by3 me-4">
                        <div class="symbol-label" style="background-image: url('/uploadfile/[db:缩略图]')"></div>
                    </div>
                    <!--end::Symbol-->
                    <!--begin::Title-->
                    <div class="m-0">
                        <a href="/weixiu/show-14537929.html" class="text-dark fw-bold text-hover-primary fs-6">格力空调多长时间加一次氟利昂</a>
                        <span class="text-gray-600 fw-semibold d-block pt-1 fs-7">1、一般情况下，空调对氟利昂的使用量是非常小的，所以在空调使用了四年左右的时候再考虑加也没问题。2、...</span>
                    </div>
                    <!--end::Title-->
                </div>
                                <!--begin::Item-->
                <div class="d-flex flex-stack mb-7">
                    <!--begin::Symbol-->
                    <div class="symbol symbol-60px symbol-2by3 me-4">
                        <div class="symbol-label" style="background-image: url('/uploadfile/[db:缩略图]')"></div>
                    </div>
                    <!--end::Symbol-->
                    <!--begin::Title-->
                    <div class="m-0">
                        <a href="/weixiu/show-14537928.html" class="text-dark fw-bold text-hover-primary fs-6">空调用多长时间需要加氟一次</a>
                        <span class="text-gray-600 fw-semibold d-block pt-1 fs-7">一般情况下是五年。当出现以下这几种情况时，空调才需要加氟。1、空调的室内机和室外机各有两个接口，当接...</span>
                    </div>
                    <!--end::Title-->
                </div>
                                <!--begin::Item-->
                <div class="d-flex flex-stack mb-7">
                    <!--begin::Symbol-->
                    <div class="symbol symbol-60px symbol-2by3 me-4">
                        <div class="symbol-label" style="background-image: url('/uploadfile/202609/83c0c0800a58e3b.jpg')"></div>
                    </div>
                    <!--end::Symbol-->
                    <!--begin::Title-->
                    <div class="m-0">
                        <a href="/news/show-14537927.html" class="text-dark fw-bold text-hover-primary fs-6">格调生活·C标思享荟：卡萨帝在...</a>
                        <span class="text-gray-600 fw-semibold d-block pt-1 fs-7">9月12日的郑州龙湖金融岛，夜风轻拂，灯光璀璨。“C标时刻共传奇——卡萨帝思享荟暨20周年品牌盛典郑...</span>
                    </div>
                    <!--end::Title-->
                </div>
                                <!--begin::Item-->
                <div class="d-flex flex-stack mb-7">
                    <!--begin::Symbol-->
                    <div class="symbol symbol-60px symbol-2by3 me-4">
                        <div class="symbol-label" style="background-image: url('/uploadfile/202609/bd5bdfc6ba7da8c.jpg')"></div>
                    </div>
                    <!--end::Symbol-->
                    <!--begin::Title-->
                    <div class="m-0">
                        <a href="/news/show-14537926.html" class="text-dark fw-bold text-hover-primary fs-6">品牌价值破千亿、高端份额持续领...</a>
                        <span class="text-gray-600 fw-semibold d-block pt-1 fs-7">9月12日，“C标时刻共传奇——卡萨帝思享荟暨20周年品牌盛典郑州站”在郑州龙湖金融岛举办。2026...</span>
                    </div>
                    <!--end::Title-->
                </div>
                                <!--begin::Item-->
                <div class="d-flex flex-stack mb-7">
                    <!--begin::Symbol-->
                    <div class="symbol symbol-60px symbol-2by3 me-4">
                        <div class="symbol-label" style="background-image: url('/uploadfile/[db:缩略图]')"></div>
                    </div>
                    <!--end::Symbol-->
                    <!--begin::Title-->
                    <div class="m-0">
                        <a href="/weixiu/show-14537925.html" class="text-dark fw-bold text-hover-primary fs-6">空调主板坏了修800还是换新的</a>
                        <span class="text-gray-600 fw-semibold d-block pt-1 fs-7">空调主板坏了是修还是换新，需要考虑多个因素，以下是一些建议：1. 维修成本：如果维修费用较低，比如 ...</span>
                    </div>
                    <!--end::Title-->
                </div>
                                <!--begin::Item-->
                <div class="d-flex flex-stack mb-7">
                    <!--begin::Symbol-->
                    <div class="symbol symbol-60px symbol-2by3 me-4">
                        <div class="symbol-label" style="background-image: url('/uploadfile/[db:缩略图]')"></div>
                    </div>
                    <!--end::Symbol-->
                    <!--begin::Title-->
                    <div class="m-0">
                        <a href="/weixiu/show-14537924.html" class="text-dark fw-bold text-hover-primary fs-6">空调开多久需要休息多长时间</a>
                        <span class="text-gray-600 fw-semibold d-block pt-1 fs-7">问题：空调开多久需要休息多长时间回答：1、在使用空调的过程中，一般空调开7~8个小时左右需要休息2~...</span>
                    </div>
                    <!--end::Title-->
                </div>
                                <!--begin::Item-->
                <div class="d-flex flex-stack mb-7">
                    <!--begin::Symbol-->
                    <div class="symbol symbol-60px symbol-2by3 me-4">
                        <div class="symbol-label" style="background-image: url('/uploadfile/[db:缩略图]')"></div>
                    </div>
                    <!--end::Symbol-->
                    <!--begin::Title-->
                    <div class="m-0">
                        <a href="/weixiu/show-14537923.html" class="text-dark fw-bold text-hover-primary fs-6">中央空调多长时间清洗一次</a>
                        <span class="text-gray-600 fw-semibold d-block pt-1 fs-7">1、一般空调开机前清洗一次即可，空调开机中间时段再清洗一次，空调关机时清洗一次，这样比较合理。2、空...</span>
                    </div>
                    <!--end::Title-->
                </div>
                                <!--begin::Item-->
                <div class="d-flex flex-stack mb-7">
                    <!--begin::Symbol-->
                    <div class="symbol symbol-60px symbol-2by3 me-4">
                        <div class="symbol-label" style="background-image: url('/uploadfile/[db:缩略图]')"></div>
                    </div>
                    <!--end::Symbol-->
                    <!--begin::Title-->
                    <div class="m-0">
                        <a href="/weixiu/show-14537922.html" class="text-dark fw-bold text-hover-primary fs-6">中央空调氟利昂多久加一次</a>
                        <span class="text-gray-600 fw-semibold d-block pt-1 fs-7">看空调制热和制冷程度，很多人的观点认为氟利昂必须一年放一次，其实这个观点是错误的，理解上面有点偏差，...</span>
                    </div>
                    <!--end::Title-->
                </div>
                
            </div>
            <!--end::Body-->
        </div>
        <!--end::Chart Widget 35-->
    </div>
    <!--end::Col-->
</div>



</div>
<!--end::Content container-->
</div>
<!--end::Content-->
</div>
<!--end::Content wrapper-->
<!--begin::Footer-->
<div id="kt_app_footer" class="app-footer">
    <!--begin::Footer container-->
    <div class="app-container container-xxl d-flex flex-column flex-md-row flex-center flex-md-stack py-3">
        <!--begin::Copyright-->
        <div class="text-dark order-2 order-md-1">
            <span class="text-muted fw-semibold me-1">2026 ©</span>
            太卓网<a href="http://www.yexian114.com/">叶县生活网</a> <a href="https://www.wxx86.cn/">编程知识网</a>  <a href="http://www.kcwzh.com/">开创游戏网</a> <a href="https://www.caiding5.net">菜丁网</a><a href="http://cn.office369.com">奥飞商务网</a>  <a href="http://www.zlnznjj.com/">众乐知识网</a><a href="http://www.lhjia.com/">乐活家</a><a href="http://www.nengyuan100.com/">能源100网</a> <a href="http://it.tdroid.net/">泰达科技</a><a href="http://cn.tdroid.net/">太卓开发网</a><a href="http://cn.yuansudz.com/">元素科技网</a><a href="http://www.80hlw.com/">八零商务网</a><a href="http://game.tdroid.net/">土豆游戏网</a>        </div>
        <!--end::Copyright-->
        <!--begin::Menu-->
        <ul class="menu menu-gray-600 menu-hover-primary fw-semibold order-1">
                        <li class="menu-item">
                <a href="/news" target="_blank" class="menu-link px-2">科技资讯</a>
            </li>
                        <li class="menu-item">
                <a href="/jishu" target="_blank" class="menu-link px-2">技术分享</a>
            </li>
                        <li class="menu-item">
                <a href="/kaifa" target="_blank" class="menu-link px-2">程序开发</a>
            </li>
                        <li class="menu-item">
                <a href="/weixiu" target="_blank" class="menu-link px-2">设备维修</a>
            </li>
                    </ul>
        <!--end::Menu-->
    </div>
    <!--end::Footer container-->
</div>
<!--end::Footer-->
</div>
<!--end:::Main-->
</div>
<!--end::Wrapper-->
</div>
<!--end::Page-->
</div>
<!--end::App-->
<div id="kt_scrolltop" class="scrolltop" data-kt-scrolltop="true">
    <!--begin::Svg Icon | path: icons/duotune/arrows/arr066.svg-->
    <span class="svg-icon">
        <svg width="24" height="24" viewBox="0 0 24 24" fill="none" xmlns="http://www.w3.org/2000/svg">
            <rect opacity="0.5" x="13" y="6" width="13" height="2" rx="1" transform="rotate(90 13 6)" fill="currentColor"></rect>
            <path d="M12.5657 8.56569L16.75 12.75C17.1642 13.1642 17.8358 13.1642 18.25 12.75C18.6642 12.3358 18.6642 11.6642 18.25 11.25L12.7071 5.70711C12.3166 5.31658 11.6834 5.31658 11.2929 5.70711L5.75 11.25C5.33579 11.6642 5.33579 12.3358 5.75 12.75C6.16421 13.1642 6.83579 13.1642 7.25 12.75L11.4343 8.56569C11.7467 8.25327 12.2533 8.25327 12.5657 8.56569Z" fill="currentColor"></path>
        </svg>
    </span>
    <!--end::Svg Icon-->
</div>
<!--begin::Javascript-->
<script>var hostUrl = "/static/default/pc/";</script>
<!--begin::Global Javascript Bundle(mandatory for all pages)-->
<script src="/static/default/pc/plugins/global/plugins.bundle.js"></script>
<script src="/static/default/pc/js/scripts.bundle.js"></script>
<!--end::Global Javascript Bundle-->

<!--end::Javascript-->
</body>
<!--end::Body-->
</html>