Les expressions régulières ne sont pas

36

Demandez même à une personne ayant une formation en informatique ce qu’est une expression régulière et la réponse ira probablement au-delà de la contrainte d’être à la portée d’un automate à états finis.

Par exemple, l'expression «expression régulière»

/^1?$|^(11+?)\1+$/

créé par une personnalité notée de Perl, Abigail (et faisant partie de la suite de tests de Perl depuis 2002) décrit une machine qui accepte uniquement les nombres unaires composites, mais l’ exercice 4.5 (b) de la troisième édition de An Introduction to Formal Languages ​​and Automata a été utilisé par le lecteur. le lemme de pompage pour prouver que

L={an:n is not a prime number}

n'est pas une langue régulière.

Dans les contextes où la distinction est importante, comment devrions-nous appeler les expressions strictement plus puissantes?

Greg Bacon
la source

Réponses:

46

Larry Wall a proposé d'utiliser "expression régulière" pour le formalisme proposé par Kleene et "regex" pour les expressions des extensions largement utilisées. C'est une convention assez largement suivie. Si vous voulez préciser que vous parlez d'expressions régulières dans le sens formel des langues, il n'est généralement pas difficile de traduire en langage parlé.

La puissance des expressions rationnelles provient du retour arrière, et des travaux ont été effectués sur les automates pour les langages normaux avec retour arrière. Voir, en particulier, Becchi et Crowley, 2008, Extension des automates finis pour faire correspondre efficacement les expressions régulières compatibles Perl .

Charles Stewart
la source
5
Je suis d’accord, quelque chose comme “Perl regex” (“POSIX regex”, etc.) et “langage ordinaire” devrait être suffisamment clair pour éviter toute possibilité d’interprétation erronée.
Jukka Suomela
Les expressions rationnelles Perl ont beaucoup plus de fonctionnalités supplémentaires que le simple retour en arrière.
reinierpost
@reinierpost C'est vrai, mais je pense que le retour en arrière est le plus important du point de vue des langages formels. Les expressions rationnelles Perl ont des fonctionnalités telles que l'exécution de code Perl arbitraire, mais je pense que les expressions rationnelles devraient être interprétées de manière approximative comme couvrant les PCRE. Les PCRE contiennent des bizarreries telles que des modèles récursifs, mais ce sont des techniques obscures, qui vous mènent loin du domaine des langages normaux. Je pourrais mettre à jour ma réponse pour couvrir ceux-ci, cependant.
Charles Stewart
18

Ces expressions ont été examinées par Aho (Manuel d'informatique théorique, Vol. A, Chp. 5) et Campeanu, Salomaa, Yu ("Étude formelle d'expressions régulières pratiques", Revue internationale des fondements de l'informatique, 14: 1007 –1018, 2003), ainsi que certains documents de suivi.

Aho appelle les expressions plus puissantes "rewbr" (expression régulière avec références arrière), Campeanu et al. utilisez "expression régulière étendue" ainsi que "expression régulière pratique". Il semble que l'expression "expression régulière étendue" soit le terme le plus couramment utilisé dans la littérature récente.

S'appuyant sur le terme "expression rationnelle" de l'école française et compte tenu du fait que ces expressions sont utilisées dans le monde réel, j'aime moi-même "expression réelle".

Addendum: Un chapitre de ma thèse porte sur cette classe de langages formels (le document correspondant doit paraître à STACS 2011). En écrivant ce chapitre et le papier, j'ai expérimenté divers termes. Enfin, j'ai décidé d'utiliser des expressions régulières étendues pour le modèle avec des références arrières et des expressions régulières appropriées pour les expressions régulières sympas et normales. Comme il est assez agaçant de changer la terminologie dans un article déjà complètement (ou en grande partie) écrit, je pense que certains pourraient être intéressés par les expériences qui ont conduit à mon choix:

Tout d’abord, regex et rewbr ne font pas vraiment rouler la langue, et les utiliser encore et encore au cours d’un article entier devenait vraiment fastidieux à écrire et à lire, en particulier lorsqu’on utilisait l’une des formes plurielles possibles. Les expressions régulières de type PERL étaient également assez lourdes. Bien sûr, je ne suis pas un locuteur natif, donc YMMV.

Deuxièmement, dès que l’on souhaite parler des deux modèles, il convient d’utiliser des termes qui sont une variation de l’expression régulière , car cela permet de mettre l’accent sur les similitudes ou les différences nécessaires (par exemple, "une expression régulière, qu’elle soit appropriée ou non"). élargi"). En outre, cela permet de souligner facilement le cas particulier des "expressions régulières étendues sans références arrière", lorsque l’on parle de cas spéciaux dans l’ensemble de la classe, au lieu de comparer différents modèles.

Troisièmement, j'ai préféré utiliser un terme déjà utilisé dans la littérature par rapport à un terme nouvellement inventé, ce qui me laissait le choix entre des expressions régulières étendues et des expressions régulières pratiques . Le deuxième choix impliquait (au moins implicitement) que les expressions régulières appropriées étaient en quelque sorte impraticables, ce qui semblait plutôt étrange (d'autant plus que RE2 de Google n'utilise pas de arrière-plan et semble très pratique).

Bien entendu, ce choix n’est que mon "maximum local personnel" et, en fonction de vos besoins, d’autres choix pourraient être plus appropriés.

Dominik D. Freydenberger
la source
7
Malheureusement, le terme expression régulière étendue est déjà pris par POSIX, qui établit une distinction entre l' expression régulière de base (BRE) et l' expression régulière étendue (ERE) , qui sont toutes deux expressions rationnelles selon votre définition.
Jörg W Mittag
@ Jörg: En fait, selon cela, ni les expressions rationnelles POSIX de base, ni étendues, ni plus puissantes que les expressions rationnelles régulières. Et les BRE purs (non-GNU) semblent en réalité moins puissants que les expressions régulières (il manque un opérateur d'alternance).
sepp2k
Voir "On Extended Regular Expressions" de Carle et Narendran (2009) pour des résultats plus récents sur ce "texte": portal.acm.org/citation.cfm?id=1533235
Jakob le
Autres résultats récents concernant ce cours de langue: "À l'intersection de langages regex et de langages normaux" de Campeanu et Santean (TCS 410, 2009) "Test de correspondance temporelle polynomiale pour de grandes classes d'expressions régulières étendues" de Reidenbach et Schmid (CIAA 2010) ), et "Expressions régulières étendues: concision et décidabilité" (par moi, qui doit paraître à STACS 2011).
Dominik D. Freydenberger
6

On sait que ce que l'on appelle l'expression rationnelle de Perl est suffisamment puissant pour être complet. il y a même un compilateur du programme habituel à perl regexp.

Par conséquent, je doute qu'il soit logique de rechercher un nom pour ce type de "regexps".

Regardez par exemple à http://search.cpan.org/~asavige/Acme-EyeDrops-1.62/lib/Acme/EyeDrops.pm

Arthur MILCHIOR
la source
Avez-vous des indications?
András Salamon
5
@ András: Je pense qu'Arthur parle de la ?{CODE}directive de Perl , qui permet aux expressions de modèle d'entrelacer le code de programme dans les expressions régulières. Je comprends que les PCRE sont généralement définis comme étant la partie "déclarative" du langage, l'ensemble du langage étant appelé langage de modèle. Selon WP, Aho, 1990, "Algorithmes permettant de trouver des motifs dans des chaînes" montre que le problème de l'appartenance des langues ordinaires avec retour en arrière est NP complete. Il n'y a pas d'autres caractéristiques matérielles aux PCRE déclaratifs.
Charles Stewart
J'ai ajouté le lien; Je n'ai pas regardé le code source, donc je ne sais pas vraiment comment ça marche et s'il existe des preuves que la compilation est vraiment correcte.
Arthur MILCHIOR
1
Désolé, mais selon votre argument, puisque lambda-calcul est Turing-complete, il n’a pas de sens de chercher un nom. Idem pour tous les autres formalismes et langages de calcul Turing-complete. Plus précisément, la complétude de Turing ne décrit pas à quel point une langue est expressive; il est donc insensé d'identifier les langues simplement parce qu'elles sont complètes. Mon exemple sur le lambda-calcul était bien sûr extrême.
Blaisorblade
2

Je pense que le meilleur terme pour "expression régulière dans le contexte des automates" est "expression rationnelle", tel qu'utilisé, par exemple, dans "Elements of Automata Theory", ou "Handbook of Automata Weight" de Sakarovitch.

Michaël Cadilhac
la source
1
Pas très couramment utilisé, à mon humble avis.
Blaisorblade
Il / est / largement utilisé dans la théorie des automates pondérés, voir en.wikipedia.org/wiki/Rational_language . Je l'ai souvent vu dans le domaine des langues au fil des groupes.
Michaël Cadilhac
1

Compte tenu des autres réponses, je suggérerais que les "langages normaux" ne présentent aucun risque, et après avoir brièvement souligné la différence, parler des "expressions régulières pratiques" pour les expressions rationnelles (avec retour arrière).

Notez également que la même expression rationnelle, en tant qu’expression régulière et pratique, peut avoir une sémantique différente, car dans ce dernier cas, la sémantique est définie en terme de retour en arrière, avec des résultats différents. Les détails seraient hors sujet, mais je répondrai si vous posez une autre question à ce sujet (peut-être sur SO plutôt qu'ici, ne sais pas) et m'avertir par un commentaire.

Blaisorblade
la source
0

Nous pourrions les appeler des expressions de modèle . Cela pourrait introduire des confusions avec les langages de motifs, mais au moins, ils sont moins courants.

Raphaël
la source
2
En principe, je souscris à votre raisonnement, mais Campeanu, Santean et Yu ont déjà utilisé le terme expressions de modèle pour désigner une classe de langages similaire avec une définition "plus propre" (voir "Expressions de modèle et automates de modèle", IPL 92 (2004). )
Dominik D. Freydenberger