정규 표현식의 역추적 정의 및 사용 분석 [JS 및 Java 구현]

이 글은 정규 표현식에서 역추적의 정의와 사용법을 예제와 함께 분석합니다. 자세한 내용은 다음과 같으니 참고하시길 바라겠습니다.

제가 '백트래킹'을 처음 접한 거라 잘 모르겠습니다. 이제 나는 나중에 참고할 수 있도록 정신적 미덕으로 내가 이해한 것을 기록하겠습니다.

우리가 사용하는 정규식의 일치 기준은 대략적으로 다음과 같이 나뉩니다. 가장 왼쪽(가장 시작) 일치 결과에 우선 순위를 부여하는 것과 표준 일치 수량자(*, +, ? 및 {m, n}) 일치 항목은 다음과 같습니다. 상위.

"가장 왼쪽 일치 선호"는 이름에서 알 수 있듯이 문자열의 처음부터 일치의 끝까지 일치하는 것입니다. 이것이 "표준 일치 수량자"로 구분됩니다. 결정론적 유한 오토마타(NFA)" )"는 "표현 중심"이라고도 할 수 있으며, 다른 하나는 "텍스트 주도"라고도 할 수 있는 "결정론적 유한 오토마타(DFA)"입니다. 현재 JavaScript에서 사용하는 정규식은 "표현식 기반"입니다. 표현 우세와 텍스트 우세는 설명하기가 좀 까다롭습니다. 예를 먼저 보면 더 명확해질 수 있습니다.

// 使用正则表达式匹配文本
var reg = /to(nite|knight|night)/;
var str = 'doing tonight';
reg.test(str);

위의 예에서 첫 번째 요소 [t]는 대상 문자열 'until에서 't를 찾을 때까지 반복적으로 시도합니다. 그 후, 다음 문자가 [o]와 일치하는지 확인하고, 그렇다면 다음 요소(nite|knight|night)를 확인합니다. 실제 의미는 "nite", "knight" 또는 "night"입니다. 엔진은 이 세 가지 가능성을 차례로 시도합니다. [nite]를 시도하는 과정은 먼저 [n]을 시도하고, 그 다음 [i], 그 다음 [t], 마지막으로 [e]를 시도하는 것입니다. 이 시도가 실패하면 엔진은 일치가 성공하거나 실패가 보고될 때까지 다른 가능성을 시도합니다. 표현식의 제어는 서로 다른 요소 간에 전송되므로 "표현식 우위"라는 이름이 붙습니다.

위의 예와 마찬가지로 "text-led"는 문자열을 스캔할 때 현재 유효한 모든 일치 항목을 기록합니다. 엔진이 t로 이동하면 현재 처리된 일치 가능성에 잠재력이 추가됩니다.

다음에 스캔되는 각 문자는 현재 가능성 일치 순서를 업데이트합니다. 두 문자를 계속 스캔한 후 상황은 다음과 같습니다.

유효한 일치 항목이 2개가 됩니다(기사가 제거됨). g를 스캔하면 가능한 일치 항목이 하나만 남습니다. h와 t가 일치하면 엔진은 일치가 완료된 것을 확인하고 성공을 보고합니다. 검색하는 문자열의 모든 문자가 엔진을 제어하기 때문에 "텍스트 중심"입니다.

'표현 리더십'이 어떻게 작동하는지 이해하고 싶다면 오늘의 주제인 '역추적'을 살펴보세요. 역추적은 도로에서 갈림길을 택하는 것과 같습니다. 도로에서 갈림길을 만나면 먼저 각 교차로에 표시를 하십시오. 막다른 골목에 이르면 이전에 만들었던 표지판을 발견할 때까지 왔던 길로 되돌아가서 아직 시도하지 않은 도로를 표시할 수 있습니다. 그 길로 갈 수 없다면 계속해서 되돌아가서 다음 표시를 찾고, 나가는 길을 찾을 때까지 또는 시도하지 않은 길을 모두 완료할 때까지 반복할 수 있습니다.

많은 경우 정규식 엔진은 두 개 이상의 옵션 중에서 선택해야 합니다. /…x?…/를 만나면 엔진은 X와 일치하는지 여부를 확인해야 합니다. /의 경우... 첫 번째 X 일치 후 이 요구 사항이 충족되었으며 다음 X를 시도할지 여부를 결정해야 합니다. 계속 진행하기로 결정한 경우 세 번째 X, 네 번째 X 등을 일치시킬지 여부도 결정해야 합니다. 선택할 때마다 실제로 여기에 또 다른 가능한 선택이 있음을 상기시키기 위해 표시를 하며 이는 나중에 사용하도록 예약되어 있습니다. 역추적 프로세스 중에 고려해야 할 두 가지 중요한 사항이 있습니다. 어떤 분기를 먼저 선택해야 합니까? 역추적할 때 이전에 저장한 분기 중 어느 것이 사용됩니까?

첫 번째 질문은 다음 중요한 원칙에 따라 선택됩니다.

"시도 수행"과 "시도 통과" 중 하나를 선택해야 하는 경우 일치하는 우선순위 수량자에 대해 엔진은 "시도"가 기본적으로 선택되는 반면, 우선순위 수량자를 무시하려면 "통과 시도"가 선택됩니다.

두 번째 질문은 다음 원칙을 기반으로 합니다.

가장 최근에 저장된 옵션은 로컬 오류가 강제로 역추적될 때 반환되는 것입니다. 사용된 원리는 LIFO(후입선출)입니다.

먼저 도로 표시의 몇 가지 예를 살펴보겠습니다.

1. 역추적 없이 일치

"abc"를 일치시키려면 [ab?c]를 사용합니다. [a] 매칭 후 현재 매칭 상태는 다음과 같습니다.

现在轮到[b?]了，正则引擎需要决定：是需要尝试[b]呢，还是跳过？因为[？]是匹配优先的，它会尝试匹配。但是，为了确保在这个尝试最终失败之后能够恢复，引擎会把：

添加到备用状态序列中。也就是说，稍后引擎可能从下面的位置继续匹配：从正则表达式中的[b?]之后，字符串的c之前（也就是说当前的位置）匹配。这实际上就是跳过[b]的匹配，而问题容许这样做。引擎做好标记后，就会继续向前检查[b]。在示例中，它能够匹配，所以新的当前状态变为：

最终的[c]也能成功匹配，所以整个匹配完成。备用状态不再需要了，所以不再保存它们。

2、进行了回溯的匹配

下面要匹配的文本是“ac”，在尝试[b]之前，一切都与之前的过程相同。显然，这次[b]无法匹配。也就是说，对[……？]进行尝试的路走不通了。因为有一个备用状态，这个“局部匹配失败”产工会导致整体匹配失败。引擎会进行回溯，也就是说，把“当前状态”切换为最近保存的状态。

在[b]尝试之前保存的尚未尝试的选项。这时候，[c]可以匹配c，所以整个匹配宣告完成。

3、不成功的匹配

现在要匹配的文本是“abx”。在尝试[b]以前，因为存在问号，保存了这个备用状态：

[b]能够匹配，但这条路往下却走不通了，因为[c]无法匹配x。于是引擎会回溯到之前的状态，“交还”b给[c]来匹配。显然，这次测试也失败了。如果还有其他保存的状态，回溯会继续进行，但是此时不存在其他状态，在字符串中当前位置开始的整个匹配也就宣告失败。

例子1： 提取字符串 提取 da12bka3434bdca4343bdca234bm 提取包含在字符a和b之间的数字，但是这个a之前的字符不能是c,b后面的字符必须是d才能提取。

例如这里就只有3434这个数字满足要求。那么我们怎么提取呢？

首先我们写出提取这个字符串的表达式： (?

Java代码片段如下：

Pattern p = Pattern.compile( "(?<!c)a(//d+)bd " );
Matcher m = p.matcher( "da12bka3434bdca4343bdca234bm" );
 while (m.find()){
 System.out.println(m.group( 1 )); //我们只要捕获组1的数字即可。结果 3434
 System.out.println(m.group(0)); // 0组是整个表达式，看这里，并没有提炼出(?<!c)的字符 。结果 a3434bd
}

例子2： 将一些多位的小数截短到三位小数：\d+\.\d\d[1-9]?\d+

在这种条件下 6.625 能进行匹配，这样做没有必要，因为它本身就是三位小数。最后一个“5”本来是给 [1-9] 匹配的，但是后面还有一个 \d+ 所以，[1-9] 由于是“?”可以不匹配所以只能放弃当前的匹配，将这个“5”送给 \d+ 去匹配，如果改为：

\d+\.\d\d[1-9]?+\d+

的侵占形式，在“5”匹配到 [1-9] 时，由于是侵占式的，所以不会进行回溯，后面的 \d+ 就匹配不到任东西了，所以导致 6.625 匹配失败。

这种情况，在替换时就有效了，比如把数字截短到小数点后三位，如果正好是三位小数的，就可以不用替换了，可以提高效率，侵占量词基本上就是用来提高匹配效率的。

把 \d+\.\d\d[1-9]?+\d+ 改为 \d+\.\d\d(?>[1-9]?)\d+ 这样是一样的。

希望本文所述对大家JavaScript程序设计有所帮助。

更多정규 표현식의 역추적 정의 및 사용 분석 [JS 및 Java 구현]相关文章请关注PHP中文网！