Comment simuler des références arrières, des anticipations et des arrière-plans dans des automates à états finis?

J'ai créé un lexer et un analyseur d'expressions régulières simples pour prendre une expression régulière et générer son arbre d'analyse. La création d'un automate à états finis non déterministe à partir de cet arbre d'analyse est relativement simple pour les expressions régulières de base. Cependant, je n'arrive pas à comprendre comment simuler les références arrières, les anticipations et les regards.

D'après ce que j'ai lu dans le livre du dragon violet, j'ai compris que pour simuler un lookahead où l'expression régulière r est mise en correspondance si et seulement si la correspondance est suivie d'une correspondance de l'expression régulière s , vous créez un fini non déterministe automate d'état dans lequel / est remplacé par ε . Est-il possible de créer un automate à états finis déterministe qui fasse de même?$r/s$$r$$s$$/$$\varepsilon$

Qu'en est-il de la simulation d'anticipations négatives et d'arrière-plans? J'apprécierais vraiment que vous me liez à une ressource qui décrit comment procéder en détail.

([ab]^*)\1$\{ww \mid w \in \{a,b\}^*\}$

L'avance et le recul n'ont rien de spécial dans le monde des automates finis, car nous ne faisons correspondre ici que des entrées entières . Par conséquent, la sémantique spéciale de "juste vérifier mais ne pas consommer" n'a pas de sens; vous venez de concaténer et / ou de recouper des expressions de vérification et de consommation et d'utiliser les automates résultants. L'idée est de vérifier les expressions d'anticipation ou d'arrière-plan pendant que vous "consommez" l'entrée et stockez le résultat dans un état.

Lorsque vous implémentez des expressions rationnelles, vous souhaitez exécuter l'entrée via un automate et récupérer les indices de début et de fin des correspondances. C'est une tâche très différente, donc il n'y a pas vraiment de construction pour les automates finis. Vous construisez votre automate comme si l'expression d'anticipation ou d'arrière-plan consommait, et modifiez votre stockage d'index resp. faire rapport en conséquence.

/(?=c)[ab]+/$\{a,b,c\}$$\{a,b,c\}^*c\{a,b\}^+\{a,b,c\}^*$

^{[ source ]}

et il faudrait

• $i$$q_2$$q_2$
• $i$$-1$$q_2$

Notez comment la partie gauche de l'automate est l'automate parallèle des automates canoniques pour [abc]*et c(itéré), respectivement.

$i$$j$$i$$j$

Notez que le non-déterminisme est inhérent à cela: l'automate principal et le prospect / / derrière peuvent se chevaucher, vous devez donc stocker toutes les transitions entre elles afin de signaler les correspondances plus tard, ou revenir en arrière.

La référence faisant autorité sur les problèmes pragmatiques derrière la mise en œuvre des moteurs regex est une série de trois articles de blog de Russ Cox . Comme décrit ici, étant donné que les références arrières rendent votre langue non régulière, elles sont implémentées en utilisant le retour arrière .

Les lookaheads et lookbehinds, comme de nombreuses fonctionnalités des moteurs de recherche de motifs d'expression régulière, ne correspondent pas tout à fait au paradigme de décider si une chaîne est membre d'une langue ou non. Plutôt avec des expressions rationnelles, nous recherchons généralement des sous-chaînes dans une chaîne plus grande. Les "correspondances" sont des sous-chaînes qui sont membres du langage, et la valeur de retour correspond aux points de début et de fin de la sous-chaîne dans la chaîne plus grande.

Le point de lookaheads et lookbehinds n'est pas tant d'introduire la possibilité de faire correspondre des langues non régulières, mais plutôt d'ajuster où le moteur signale les points de début et de fin de la sous-chaîne correspondante.

Je m'appuie sur la description à http://www.regular-expressions.info/lookaround.html . Les moteurs regex qui prennent en charge cette fonctionnalité (Perl, TCL, Python, Ruby, ...) semblent tous être basés sur le backtracking (c'est-à-dire qu'ils prennent en charge un ensemble de langues beaucoup plus large que les langues normales). Ils semblent implémenter cette fonctionnalité comme une extension relativement "simple" du retour arrière, plutôt que d'essayer de construire de vrais automates finis pour effectuer la tâche.

Lookahead positif

La syntaxe de l' anticipation positive est l' (?=expression régulière) . Ainsi, par exemple q(?=u), qne correspond que s'il est suivi de u, mais ne correspond pas à u. J'imagine qu'ils implémentent cela avec une variation sur le retour en arrière. Créez un FSM pour l'expression avant l'anticipation positive. Lorsque ces correspondances se souviennent de l'endroit où elles se sont terminées et démarrent un nouveau FSM qui représente l'expression à l'intérieur de l'anticipation positive. Si cela correspond alors vous avez une "correspondance", mais la correspondance "se termine" juste avant la position où la correspondance positive a commencé.

La seule partie de cela qui serait difficile sans retour en arrière est que vous devez vous rappeler le point dans l'entrée où commence la recherche et déplacer votre bande d'entrée vers cette position après avoir terminé la correspondance.

Lookahead négatif

La syntaxe de l'anticipation négative est l' (?!expression régulière) . Ainsi, par exemple q(?!u), qne correspond que s'il n'est pas suivi u. Cela peut être soit un qsuivi d'un autre caractère, soit un tout qà la fin de la chaîne. J'imagine que cela est mis en œuvre en créant un NFA pour l'expression d'anticipation, puis en ne réussissant que si le NFA ne correspond pas à la chaîne suivante.

Si vous voulez le faire sans compter sur le retour en arrière, vous pouvez annuler le NFA de l'expression de l'anticipation, puis traitez-le de la même manière que vous traitez l'anticipation positive.

Lookbehind positif

(?<=)(?=q)uuqq$n$$n$$n$

Vous pourriez être en mesure d'implémenter cela sans retour en arrière en prenant l'intersection de "chaîne qui se termine par regex " avec n'importe quelle partie de l'expression régulière qui précède l'opérateur lookbehind. Cela va cependant être délicat, car l' expression rationnelle derrière peut avoir besoin de regarder plus en arrière que le début actuel de l'entrée.

Lookbehind négatif

La syntaxe pour lookbehind négatif est (?<!regex) . Ainsi, par exemple, (?<!q)ucorrespond u, mais uniquement s'il n'est pas précédé de q. Cela correspondrait donc à l' uentrée umbrellaet à l' uentrée doubt, mais pas à l' uentrée quick. Encore une fois, cela semble être fait en calculant la longueur de l' expression régulière , en sauvegardant autant de caractères, en testant la correspondance avec l' expression régulière , mais en échouant maintenant toute la correspondance si le lookbehind correspond.

Vous pourriez être en mesure de mettre en œuvre cela sans retour en arrière en prenant la négation de l' expression régulière , puis en faisant de même que vous le feriez pour un lookbehind positif.

Au moins pour les références arrières, ce n'est pas possible. Par exemple, l'expression (.*)\1régulière représente une langue qui n'est pas régulière. Cela signifie qu'il est impossible de créer un automate fini (déterministe ou non) qui reconnaîtrait ce langage. Si vous voulez le prouver formellement, vous pouvez utiliser le lemme de pompage .

Je me suis penché sur cette question moi-même, et vous devriez pouvoir implémenter l'anticipation à l'aide d'un automate fini alternatif . Lorsque vous rencontrez l'anticipation, vous exécutez de manière non déterministe à la fois l'anticipation et le reste de l'expression, en acceptant uniquement si les deux chemins acceptent. Vous pouvez convertir un AFA en NFA avec une explosion raisonnable (et donc en DFA), bien que je n'ai pas vérifié que la construction évidente fonctionne bien avec les groupes de capture.

L' arrière -plan à largeur fixe devrait être parfaitement possible sans retour en arrière. Soit n la largeur. En partant du point dans votre NFA où le lookbehind a commencé, vous divisez les états en regardant en arrière de sorte que chaque chemin dans le lookbehind se termine par n caractères valant des états qui ne sont entrés que dans le lookbehind. Ensuite, ajoutez l'anticipation au début de ces états (et compilez immédiatement le sous-graphique de AFA à NFA si vous le souhaitez).

Les références arrières ne sont pas, comme d'autres l'ont mentionné, régulières, elles ne peuvent donc pas être implémentées par un automate fini. En fait, ils sont NP-complets. Dans l'implémentation sur laquelle je travaille, la correspondance rapide oui / non est primordiale, j'ai donc choisi de ne pas implémenter les références arrières du tout.