js에서 정규식 역추적을 올바르게 이해하는 방법-JS 튜토리얼-php.cn

이번에는 js에서 정규식역추적을 올바르게 이해하는 방법을 알려드리겠습니다. js에서 정규식 역추적을 올바르게 사용하기 위한 주의사항은 무엇인지 살펴보겠습니다.

정규식 구현에서 역추적은 일치 프로세스의 기본 부분이며 정규식이 그토록 유용하고 강력한 이유입니다. 그러나 역추적은 계산 비용이 많이 들고 설계가 잘못된 경우 제어력 상실로 이어질 수 있습니다. 역추적은 전체 성능에 영향을 미치는 유일한 요소로, 어떻게 동작하는지 이해하고, 사용빈도를 줄이는 것이 효율적인 정규식 작성의 핵심이 될 수 있습니다

정규식은 대상 문자열을 왼쪽부터 하나씩 스캔할 때 오른쪽으로 정규식의 구성 요소를 검사하여 각 위치에서 일치하는 항목을 찾을 수 있는지 테스트합니다. 각 수량자와 분기에 대해 진행 방법을 결정해야 합니다. 수량자(예: *, +? 또는 {2,})인 경우 정규식은 분기를 발견하면(| 연산자를 통해) 언제 더 많은 문자를 일치시키려고 할지 결정해야 합니다. 다음 중에서 시작하세요. 시도해 볼 옵션 중 하나를 선택하세요.

정규식이 이와 같은 결정을 내릴 때 필요한 경우 나중에 사용할 수 있도록 다른 옵션을 기억합니다. 선택한 구성표가 성공적으로 일치하면 정규식은 계속해서 정규식 템플릿을 검색하고, 나머지 일치도 성공하면 일치가 종료됩니다. 그러나 선택한 옵션이 일치 항목을 찾지 못하거나 후속 일치 항목이 실패하는 경우 정규식은 마지막 결정 지점으로 돌아가 나머지 옵션 중 하나를 선택합니다. 일치하는 항목이 발견되거나 수량자 및 분기 옵션의 가능한 모든 순열이 시도될 때까지 이 과정을 계속한 다음 프로세스를 중단하고 프로세스 시작 부분에서 다음 문자로 이동하고 프로세스를 반복합니다.

예를 들어 아래 코드는 이 프로세스가 역추적을 통해 분기를 처리하는 방법을 보여줍니다.

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

로그인 후 복사

위의 정규 표현식 줄은 "hello hippo”或“happy hippo"과 일치하는 데 사용됩니다. 테스트 초반에 우리는 h를 찾고 있었는데, 우연히 대상 문자열의 첫 글자가 h였는데, 바로 찾았습니다. 다음으로 하위 표현식(ello|appy)은 두 가지 처리 옵션을 제공합니다. 정규식은 가장 왼쪽 옵션을 선택하고(분기 선택은 항상 왼쪽에서 오른쪽으로 진행됨) ello가 문자열의 다음 문자와 일치하는지 확인한 후 정규식은 다음 공백과 일치합니다.

그러나 hippo의 h는 문자열의 다음 문자 t와 일치할 수 없기 때문에 정규 표현식은 다음 일치에서 "막다른 골목에 도달합니다". 정규식은 아직 모든 옵션을 시도하지 않았기 때문에 이 시점에서 포기할 수 없으므로 마지막 체크포인트(초기 h와 일치한 후)로 역추적하여 두 번째 분기 옵션과 일치하려고 시도합니다. 하지만 일치에 실패하고 더 이상 옵션이 없기 때문에 정규식은 문자열의 첫 번째 문자부터 시작하는 일치는 성공하지 못할 것이라고 판단하여 두 번째 문자부터 다시 검색을 시작했습니다. 정규식은 h를 찾지 못했기 때문에 행복한 h와 일치하는 14번째 문자를 찾을 때까지 계속해서 거꾸로 검색했습니다. 그런 다음 정규식이 다시 분기되고 이번에는 ello가 일치에 실패하지만 역추적 후 두 번째 분기에서는 전체 문자열 "happy hippo"와 일치하고 일치가 성공합니다.

또 다른 예인 다음 코드는 반복 수량자를 사용한 역추적을 보여줍니다.

var str = "<p>Para 1.</p>" +"<img src=&#39;smiley.jpg&#39;>" +"<p>Para 2.</p>" +"<p>p.</p>";
/<p>.*<\/p>/i.test(str);

로그인 후 복사

정규식은 먼저 문자열 시작 부분의 세 글자

를 일치시킨 다음 .*를 찾습니다. 점은 개행 문자를 제외한 모든 문자와 일치한다는 의미이며, "탐욕스러운" 수량자인 별표는 가능한 한 많이 일치시키기 위해 0회 이상 반복한다는 의미입니다. 대상 문자열에 개행 문자가 없기 때문에 정규식은 나머지 문자열 전체와 일치합니다! 그러나 정규식 템플릿에는 일치시킬 콘텐츠가 더 많기 때문에 정규식은 <와 일치하려고 시도합니다. 문자열 끝의 일치가 실패하므로 한 번에 한 문자씩 역추적하고 정규식이

태그의 < 위치로 돌아올 때까지 < 다음으로 성공적으로 일치하는 /(백슬래시 이스케이프 처리)를 시도하고 p를 시도하지만 일치하지 않습니다. 정규 표현식은 두 번째 단락의 끝에서

와 일치할 때까지 계속 역추적하고 이 프로세스를 반복합니다. 성공적인 일치 항목을 반환하려면 첫 번째 단락의 시작부터 마지막 단락의 끝까지 스캔해야 하는데, 이는 우리가 원하는 결과가 아닐 수 있습니다.

단일 단락과 일치하도록 정규 표현식의 "탐욕스러운" 수량자 *를 "게으른"(일명 "욕심 없음") 수량자 *로 변경하시겠습니까? "게으른" 수량자에 대한 역추적은 반대 방식으로 작동합니다. 정규식 /

.*?

/가 .*?로 발전하면 먼저 모두 건너뛰려고 시도한 다음

와 계속 일치합니다.

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

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

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

/<html>[\s\S]*?<head>[\s\S]*?<title>[\s\S]*?<\/title>[\s\S]*?<\/head>
[\s\S]*?<body>[\s\S]*?<\/body>[\s\S]*?<\/html>/

로그인 후 복사

此正则表达式匹配在正常HTML 字符串时工作良好，但当目标字符串缺少一个或多个标签时，就会变得十分糟糕。例如标签缺失，最后一个[\s\S]*?将扩展到字符串的末尾，因为在那里没有发现标签，然后正则表达式将查看此前的[\s\S]*?队列记录的回溯位置，使它们进一步扩大。正则表达式尝试扩展倒数第二个[\s\S]*?—用它匹配标签，就是此前匹配过正则表达式模板<\/body>的那个标签，然后继续查找第二个标签，直到字符串的末尾。当所有这些步骤都失败时，倒数第三个[\s\S]*?将被扩展，直至字符串的末尾，依此类推。

此类问题的解决办法在于尽可能具体地指出分隔符之间的字符匹配形式，如模板“.*?”用于匹配双引号包围的一个字符串。用更具体的[^"\rn]*取代过于宽泛的.*?就去除了回溯时可能发生的几种情况，如尝试用点号匹配引号，或者扩展搜索超出预期范围。

在HTML 的例子中解决办法不是那么简单。不能使用否定字符类型，如用[^<]替代[\s\S]，因为在搜索过程中可能会遇到其他类型的标签。但是，可以通过重复一个非捕获组来达到同样效果，它包含一个回溯（阻塞下一个所需的标签）和[\s\S]（任意字符）元序列。这样可以确保中间位置上查找的每个标签都会失败。然后，更重要的是，[\s\S]模板在回溯过程中阻塞的标签在被发现之前不能被扩展。应用此方法后对正则表达式的最终修改如下：

/<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>/

로그인 후 복사

虽然这样做消除了潜在的回溯失控，并允许正则表达式在匹配不完整HTML字符串失败时的使用时间与文本长度呈线性关系，但是正则表达式的效率并没有提高。像这样为每个匹配字符进行多次前瞻，缺乏效率，而且成功匹配过程也相当慢。匹配较短字符串时使用此方法相当不错，而匹配一个HTML 文件可能需要前瞻并测试上千次。

相信看了本文案例你已经掌握了方法，更多精彩请关注php中文网其它相关文章！