Expression formelle du langage des modèles Perl

Question

Les expressions régulières classiques sont équivalentes aux automates finis. La plupart des implémentations actuelles d '"expressions régulières" ne sont pas à proprement parler des expressions régulières mais sont plus puissantes. Certaines personnes ont commencé à utiliser le terme «motif» plutôt que «expression régulière» pour être plus précis.

Quelle est la classification du langage formel de ce qui peut être décrit avec une «expression régulière» moderne telle que les modèles supportés dans Perl 5?

Mise à jour: Par "Perl 5", je veux dire que la fonctionnalité de correspondance de formes est implémentée en Perl 5 et adoptée par de nombreux autres langages (C#, JavaScript, etc.) et non spécifique à Perl. Je ne veux pas considérer, par exemple, des astuces pour incorporer du code Perl dans un motif.

Answer 1

Il y a eu une discussion récente sur ce sujet un PerlMonks: Turing completeness and regular expressions

Answer 2

J'ai toujours entendu l'implémentation de regex de perl décrite comme une NFA avec backtracking. Wikipedia semble avoir une petite section sur ce point:

Ceci est peut-être un peu trop floue, mais il est instructif non moins:

From Wikipedia:

Il y a au moins trois différents algorithmes qui décident si et comment une expression régulière correspond à une chaîne .

Le plus ancien et le plus rapide de deux comptent sur un résultat dans la théorie du langage formel qui permet à chaque machine d'état non déterministes finie (NFA) à transformer dans une machine d'état fini déterministe (DFA). Le DFA peut être construit explicitement et ensuite exécuter la chaîne d'entrée qui en résulte un symbole à la fois. Construire le DFA pour une expression régulière de taille m a le temps et le coût de la mémoire de O (2m), mais il peut être exécuté sur une chaîne de taille n en temps O (n). Une approche alternative est pour simuler le NFA directement, essentiellement la construction de chaque état DFA sur demande et ensuite l'éliminer à l'étape suivante , éventuellement avec la mise en cache. Cette conserve le DFA implicite et évite le coût de construction exponentiel , mais les coûts de fonctionnement augmentent à O (nm). L'approche explicite est appelée l'algorithme DFA et l'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 en les utilisant pour rappeler sous-expressions groupées, quantification paresseuse , et des caractéristiques similaires est difficile. [12] [13]

Le troisième algorithme doit faire correspondre le modèle à la chaîne d'entrée par retour arrière . Cet algorithme est communément appelé NFA, mais cette terminologie peut prêter à confusion.Son temps de fonctionnement peut être exponentielle, ce qui implémentations simples exposition lorsque correspondant contre des expressions comme (a | aa) * b qui contiennent à la fois l'alternance et la quantification et la force sans bornes l'algorithme d'envisager un nombre croissant de façon exponentielle de sous -cases. Les implémentations plus complexes identifient souvent et accélèrent ou annulent les cas courants où ils fonctionneraient autrement lentement.

Bien que les mises en œuvre ne donnent qu'une backtracking une garantie exponentielle le pire des cas, ils fournissent beaucoup une plus grande flexibilité et la puissance expressive . Par exemple, toute implémentation qui permet l'utilisation de références arrières , ou qui implémente les différentes extensions introduites par Perl, doit utiliser une implémentation backstracking .

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

Answer 3

Les expressions rationnelles Perl, comme celles de n'importe quel langage de modèle, où les références «arrières» sont autorisées, ne sont pas réellement «régulières».

Les références arrière sont le mécanisme de correspondant à la même chaîne qui a été appariée par un sous-modèle avant. Par exemple, /^(a*)\1$/ correspond uniquement aux chaînes avec un nombre pair de a s, car après certains a il devrait y avoir le même nombre de chaînes.

Il est facile de prouver, par exemple, que le motif /^((a|b)*)\1$/ correspond à des mots d'un langage non-régulier (*), donc il est plus expressif que l'automate fini-fini. Les expressions régulières ne peuvent pas "se souvenir" d'une chaîne de longueur arbitraire, puis la reconnecter (la longueur peut être très longue, tandis que la machine à états finis ne peut simuler qu'une quantité finie de "mémoire").

Une preuve formelle utiliserait le pumping lemma. (En passant, ce langage ne peut pas non plus être décrit par une grammaire sans contexte.)

Soit seul le tricks that allow to use perl code in perl regexps (langage non régulier de parenthèses équilibrées). (*) "Les langues régulières" sont des ensembles de mots qui sont appariés par des automates finis. J'ai déjà écrit an answer à ce sujet.