Expressivité de langue formelle des modèles Perl

J'ai toujours entendu la mise en œuvre de la regex de Perl décrit comme une NFA à la retraite. Wikipedia semble avoir une petite section sur ceci:

Ceci est peut-être légèrement trop flou, mais il est informatif non le moins:

de Wikipedia:

Il y a au moins trois différents algorithmes qui décident si et comment un Étant donné l'expression régulière correspond à un chaîne.

Les deux les plus anciens et les plus rapides s'appuient sur un entraîner la théorie de la langue formelle que permet chaque fini nondéterministe Machine d'état (NFA) à transformer dans un état fini déterministe machine (DFA). La DFA peut être construit explicitement et ensuite exécuter la chaîne d'entrée résultante un symbole à la fois. Construire le DFA pour un expression régulière de taille m a le coût de temps et de mémoire de O (2m), mais il peut être exécuté sur une chaîne de taille n dans il est temps). Une approche alternative est simuler directement la NFA, essentiellement construire chaque état DFA sur demande puis le jeter à la prochaine étape, éventuellement avec la mise en cache. Cette garde la DFA implicite et évite le coût de construction exponentielle, mais COÛT COÛT DE LA RONDE À O (NM). Les L'approche explicite s'appelle la DFA algorithme et approche implicite l'algorithme NFA. Comme les deux peuvent être vus comme différentes manières d'exécuter le même DFA, ils sont aussi souvent appelés l'algorithme DFA sans faire de distinction. Ces algorithmes sont rapide, mais les utiliser pour rappeler Sous-expressions groupées, paresseux Quantification et caractéristiques similaires est délicat. [12] [13]

Le troisième algorithme est de correspondre à la Motif contre la chaîne d'entrée par retour en arrière. Cet algorithme est communément appelé nfa, mais cela La terminologie peut être déroutante. Son le temps de fonctionnement peut être exponentiel, lequel Des implémentations simples présentent quand correspondant contre des expressions comme (A | AA) * B contenant à la fois une alternance et quantification et force sans bornes l'algorithme à considérer un Nombre exponentiellement croissant de Sous-cas. Plus complexe Les implémentations identifieront souvent et accélérer ou abandonner les cas communs où ils courraient autrement courir lentement.

Bien que les implémentations de retour en arrière donner seulement une garantie exponentielle dans le pire des cas, ils fournissent beaucoup plus grande flexibilité et expressif Puissance. Par exemple, toute mise en œuvre qui permet l'utilisation de brouillards, ou implémente la Diverses extensions introduites par Perl, doit utiliser une backtracking Mise en œuvre.

Certaines implémentations tentent de fournir le meilleur des deux algorithmes en premier exécuter une correspondance rapide DFA pour voir si le la chaîne correspond à l'expression régulière du tout, et seulement dans ce cas se produisent un retour potentiellement plus lent match.

Perl Regexps, comme celles de tout langage de modèle, où des "branchement" sont autorisées, ne sont pas vraiment "régulières".

Les backresferences sont le mécanisme de correspondant à la même chaîne correspondant par un sous-motif avant . Par exemple, / ^ (a *) \ 1 $ / ne correspond que des chaînes avec un nombre même de A S, car après quelques a s devrait suivre le même nombre de ceux-ci.

Il est facile de prouver que, par exemple, modèle / ^ (((((b) *) \ 1 $ / correspond à des mots d'une langue non régulière (*), donc c'est plus Expressive de l'automate fini fini. Les expressions régulières ne peuvent pas "se rappeler" une chaîne de longueur arbitraire, puis la correspondre à nouveau (la longueur peut être très longue, tandis que la machine à états fini ne peut simuler que la quantité finie de "mémoire").

Une preuve formelle utiliserait le Pompage Lemma . (Au fait, cette langue ne peut également être décrite par la grammaire sans contexte.)

sans parler de astuces qui permettent d'utiliser le code PERL dans Perl Regexps (langue non régulière de parenthèses équilibrées).