Définition du backtracking et analyse de l'utilisation dans les expressions régulières [implémentation JS et Java]

Cet article analyse la définition et l'utilisation du backtracking dans les expressions régulières avec des exemples. J'aimerais le partager avec vous pour votre référence. Les détails sont les suivants :

C'est mon premier contact avec le « backtracking » et je n'y connais pas grand-chose. Je vais maintenant enregistrer ce que je comprends comme une vertu mentale pour référence future.

La base de correspondance des expressions régulières que nous utilisons est grossièrement divisée en : donner la priorité au résultat de correspondance le plus à gauche (le tout début) et les quantificateurs de correspondance standard (*, ,? et {m, n}) sont Les matchs sont prioritaires.

"Préférer la correspondance la plus à gauche", comme son nom l'indique, consiste à correspondre du début de la chaîne jusqu'à la fin de la correspondance. C'est la base du "quantificateur de correspondance standard" qui est divisé en "non-". les automates finis déterministes (NFA)" )" peuvent également être appelés "dirigés par l'expression" ; l'autre est "automate fini déterministe (DFA)" qui peut également être appelé "dirigé par le texte". Les expressions régulières que nous utilisons actuellement en JavaScript sont « basées sur les expressions ». La dominance d'expression et la dominance de texte sont un peu difficiles à expliquer. Cela peut être plus clair si nous regardons d'abord un exemple.

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

Dans l'exemple ci-dessus, le premier élément [t], il essaiera à plusieurs reprises jusqu'à ce que 't soit trouvé dans la chaîne cible' jusqu'à. Après cela, il vérifie si le caractère suivant peut correspondre à [o], et si c'est le cas, il vérifie l'élément suivant (nite|knight|night). Sa vraie signification est « nuit » ou « chevalier » ou « nuit ». Le moteur essaiera ces trois possibilités en séquence. Le processus pour essayer [nite] consiste à essayer [n] d'abord, puis [i], puis [t] et enfin [e]. Si cette tentative échoue, le moteur essaie une autre possibilité, et ainsi de suite, jusqu'à ce qu'une correspondance réussisse ou qu'un échec soit signalé. Le contrôle dans une expression est transféré entre différents éléments, d'où le nom de « dominance de l'expression ».

Comme dans l'exemple ci-dessus, "text-led" enregistrera toutes les correspondances actuellement valides lors de l'analyse de la chaîne. Lorsque le moteur passe à t, il ajoute un potentiel aux possibilités de correspondance actuellement traitées :

Chaque caractère scanné ensuite met à jour la séquence de correspondance de possibilités actuelle. Après avoir continué à scanner deux personnages, la situation est la suivante :

Les correspondances possibles valides deviennent deux (le chevalier est éliminé). Lorsque g est scanné, il ne reste qu’une seule correspondance possible. Lorsque h et t correspondent, le moteur constate que la correspondance est terminée et signale le succès. "Dominé par le texte" car chaque caractère de la chaîne analysée contrôle le moteur.

Si vous souhaitez comprendre comment fonctionne le « leadership d'expression », alors jetez un œil à notre sujet d'aujourd'hui « retour en arrière ». Faire marche arrière, c'est comme prendre une bifurcation sur la route. Lorsque vous rencontrez une bifurcation sur la route, faites d'abord une marque à chaque intersection. Si vous arrivez dans une impasse, vous pouvez revenir sur vos pas jusqu'à ce que vous tombiez sur un panneau que vous avez fait auparavant, marquant une route que vous n'avez pas encore essayée. Si vous ne pouvez pas marcher de cette façon, vous pouvez continuer à revenir en arrière, trouver la marque suivante et répéter jusqu'à ce que vous trouviez une issue ou jusqu'à ce que vous ayez parcouru toutes les routes non essayées.

Dans de nombreux cas, le moteur d'expression régulière doit choisir entre deux (ou plus) options. Lorsqu'il rencontre /…x?…/, le moteur doit essayer de faire correspondre X ou non. Dans le cas d /... Après les X premiers matchs, cette condition est remplie et une décision doit être prise quant à l’opportunité d’essayer le prochain X. Si vous décidez de continuer, vous devez également décider si vous souhaitez faire correspondre le troisième X, le quatrième X, etc. Chaque fois que vous faites un choix, vous faites en fait une marque pour vous rappeler qu'il existe ici un autre choix possible, qui est réservé pour une utilisation future. Il y a deux points importants à considérer lors du processus de retour en arrière : Quelle branche choisir en premier ? Quelles (ou lesquelles) branches précédemment enregistrées sont utilisées lors du retour en arrière ?

La première question est choisie selon le principe important suivant :

Si vous devez choisir entre "faire une tentative" et "passer par une tentative", pour le quantificateur de priorité correspondant, le moteur "Faire une tentative" est choisi de préférence, alors que pour ignorer le quantificateur de priorité, "tentative de passage" est choisi.

La deuxième question est basée sur le principe suivant :

L'option la plus récemment stockée est ce qui est renvoyé lorsqu'une défaillance locale force un backtrace. Le principe utilisé est LIFO (last in first out).

Regardons d'abord quelques exemples de marquage de routes :

1. Faire correspondre sans revenir en arrière

Utilisez [ab?c] pour faire correspondre « abc » . [a] Après l'appariement, l'état actuel du match est le suivant :

现在轮到[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程序设计有所帮助。

更多Définition du backtracking et analyse de lutilisation dans les expressions régulières [implémentation JS et Java]相关文章请关注PHP中文网！