détails de mise en œuvre d'expression régulière

A question that I answered got me demander:détails de mise en œuvre d'expression régulière

Comment sont des expressions régulières mises en œuvre en Python? Quel type de garanties d'efficacité y a-t-il? La mise en œuvre est-elle «standard» ou est-elle sujette à changement? Je pensais que les expressions régulières seraient implémentées en tant que DFA, et étaient donc très efficaces (nécessitant au plus un balayage de la chaîne d'entrée). Laurence Gonsalves a soulevé un point intéressant que toutes les expressions régulières Python ne sont pas régulières. (Son exemple est r "(a +) b \ 1", qui correspond à un certain nombre de a, de b, et ensuite au même nombre de a que précédemment). Ceci ne peut clairement pas être implémenté avec un DFA. Donc, pour réitérer: quels sont les détails d'implémentation et les garanties des expressions régulières Python?

Ce serait bien aussi que quelqu'un puisse expliquer (à la lumière de l'implémentation) pourquoi les expressions régulières "cat | catdog" et "catdog | cat" conduisent à des résultats de recherche différents dans la chaîne " catdog ", comme mentionné dans le question that I referenced before.

Source

2009-05-09 Tom

Les implémentations d'expressions régulières d'aujourd'hui ont beaucoup plus de fonctionnalités que ne le décrit la définition classique des expressions régulières. – Gumbo

@Gumbo: En effet, ils le font ... c'est en quelque sorte la raison de ma question. Je suis curieux d'une implémentation spécifique car il n'est pas sûr de supposer qu'un DFA est utilisé (à cause de ces fonctionnalités supplémentaires). – Tom

Utilisez la source, Luke (http://svn.python.org/view/python/trunk/Lib/re.py?view=markup). Cela semble en fait assez bien documenté. –

Le module re de Python était basé sur PCRE, mais est passé à sa propre implémentation.

Voici le lien vers le C code.

Il semble que la bibliothèque soit basée sur un retour arrière récursif lorsqu'un chemin incorrect a été emprunté.

alt text

expression régulière et la taille du texte n
a? ⁿ a ⁿ correspondant à un ⁿ

Gardez à l'esprit que ce graphique n'est pas représentatif des recherches regex normales.

http://swtch.com/~rsc/regexp/regexp1.html

Source

2009-05-09 23:03:17 Unknown

(Je me rends compte que ce commentaire est en retard) J'aime votre explication, sauf que je ne pense pas que la dernière partie soit correcte à propos de l'appariement "cat | catdog". Utiliser "cat | catdog" produit "cat" et "catdog | cat" produit "catdog". Bbasiquement, l'ordre compte. Il y a deux choses qui se passent. Tout d'abord, 'findall 'trouve seulement toutes les correspondances qui ne se chevauchent pas. Donc, vous ne devriez pas attendre "chat" ET "chat". Deuxièmement, si je mettais en œuvre ceci, je pense qu'il est facile de dire que le NFA peut être converti en un DFA et donc vous auriez "c -> a -> * t * -> d -> o -> * g *" où les astérisques indiquent un état final. – Tom

(suite ...): Donc, fondamentalement, le "t" est un état final, et j'ai l'impression que la recherche devrait toujours retourner "chat" parce que c'est aussi loin que nécessaire pour trouver une correspondance. Néanmoins, votre réponse a été utile, et je vais l'accepter (mois plus tard :-). – Tom

DFA ne sont pas une approche parfaite non plus. La correspondance '[ab] * b [ab]^n' nécessite une mémoire' O (2^n) 'en utilisant un DFA, mais peut être effectuée en temps linéaire et en mémoire en utilisant un NFA. –

Il n'y a pas de « garanties d'efficacité » sur Python REs plus que sur toute autre partie de la bibliothèque standard de la langue (C++ est la seule norme de langue répandue Je sais que tente d'établir ces normes - mais il n'y a pas de normes, même en C++, spécifiant que, disons, multiplier deux entiers doit prendre un temps constant, ou quoi que ce soit de ce genre); il n'y a aucune garantie que de grandes optimisations ne seront pas appliquées à tout moment. Aujourd'hui, F. Lundh (à l'origine responsable de la mise en œuvre du module RE actuel de Python, etc.), présentant Unladen Swallow à Pycon Italia, a mentionné qu'une des voies qu'ils explorent est de compiler des expressions régulières directement au code intermédiaire LLVM (plutôt que leur propre saveur bytecode à interpréter par une exécution ad-hoc) - puisque le code Python ordinaire est également compilé en LLVM (dans une prochaine version de Unladen Swallow), un RE et son code Python environnant pourraient alors être optimisés ensemble, même de manière assez agressive parfois. Je doute que quoi que ce soit de ce genre soit proche de la «production prête» très bientôt, cependant ;-).

Source

2009-05-10 21:01:56

Matching regular expressions with backreferences is NP-hard, qui est au moins aussi dur que NP-Complete. Cela signifie essentiellement que c'est aussi difficile que n'importe quel problème que vous êtes susceptible de rencontrer, et la plupart des informaticiens pensent que cela pourrait nécessiter un temps exponentiel dans le pire des cas.Si vous pouviez faire correspondre de telles expressions "régulières" (qui ne sont pas, techniquement parlant) en temps polynomial, vous pourriez gagner a million bucks.

Source

2009-10-28 04:24:21

détails de mise en œuvre d'expression régulière

Répondre

Questions connexes