Analyse des pires cas pour les expressions régulières

Question

Existe-il des outils qui permettront de prendre une expression régulière et retour le pire des cas, en termes de nombre d'opérations nécessaires pour un certain nombre de caractères que l'expression régulière est mise en correspondance avec?

Ainsi, par exemple, étant donné un (f|a)oo.*[ ]baz, combien de mesures pourrait le moteur peut-être bien que par le biais de match de 100 caractères?

Je serais aussi intéressé de savoir si il existe un outil qui peut prendre un tas d'exemples de texte et affiche la moyenne des opérations pour chaque exécution.

Je me rends compte de cela dépendra beaucoup sur le moteur utilisé et de la mise en œuvre, mais je suis ignorant de la façon commune c'est. Donc, si il est commun pour de nombreux langages (prise de ma question trop vague), je serais particulièrement intéressé par Perl et Python.

Answer 1

Regexbuddy du débogueur affiche le nombre de pas du moteur prendrait pour conclure le match ou pas sur un échantillon donné. Plus d'informations sur catastrophiques retour en arrière et le débogage des expressions régulières.

PS: Il n'est pas libre, mais ils offrent un 3 mois de garantie de remboursement.

Answer 2

Notez que cela dépend du moteur . Bien que la théorie des expressions rationnelles soit basée sur la théorie des automates simples, la plupart des moteurs ne sont pas des traductions strictes de ces théories. Pour cette raison, par exemple, certains moteurs sont soumis à un temps exponentiel, contrairement à un traitement NFA strict.

Answer 3

Vous obtiendrez peut-être ce que vous cherchez, par exemple, en utilisant re.compile avec re.DEBUG . Consultez cette excellente réponse du wiki Python Hidden Features Community pour une explication détaillée.