Retour arrière
Retour arrière (en anglais backtracking) : stratégie d'exécution qui explore les possibilités une à une, et revient au dernier point de choix quand une voie échoue. C'est le fonctionnement des moteurs d'expressions régulières de Perl, PCRE (grep -P), Python, Java ou JavaScript : il permet les références arrière et les regards en avant ou en arrière, mais le nombre d'essais peut croître exponentiellement avec la longueur du texte pour certains motifs, comme ^(a+)+$ face à une longue suite de a suivie d'un b. C'est l'origine des dénis de service ReDoS.
Les moteurs à automate fini, comme celui de GNU grep pour les BRE et ERE sans référence arrière, ne reviennent jamais en arrière et gardent un temps proportionnel au texte. Le mot désigne aussi l'évaluation des générateurs de jq, qui essaie toutes les combinaisons de valeurs produites.
Dans les cours
- Traiter du texte : grep, sed, awk, jq, leçon 2 : grep et les expressions régulières
- Traiter du texte : grep, sed, awk, jq, leçon 7 : jq : interroger du JSON