expression régulière "contient" une autre expression régulière

Existe-t-il un moyen de tester si une expression régulière "contient" une autre expression régulière?
Par exemple:
expression régulière "contient" une autre expression régulière

RegEX1 = "a.*b"; 
RegEx2 = "a1.*b";

RegEX1 "contient" RegEX2. Pour autant que je sache - cela ne peut pas être fait, ai-je tort? OK, joel.neely a montré que cela peut être fait (je ne l'ai pas encore lu ...) académiquement. Peut-il être fait dans un langage de programmation, disons C#?
À quel point cela sera-t-il efficace? Combien de temps faudra-t-il pour tester 1000 paires?

Source

2009-01-06 Dror

Oui.

This paper contient une discussion détaillée du sujet (voir section 4.4).

Source

2009-01-06 13:20:29

Pouvez-vous clarifier votre «oui». Je pense que vous dites "Oui, vous avez tort" et citant le papier qui montre comment cela peut être fait (à partir d'un coup d'oeil rapide sur le papier). Mais cela vaudrait la peine d'en parler explicitement. –

L'article mentionné ne dit que "Il est bien connu que pour deux expressions régulières B et R, il est facile de décider si B subsume R" et ensuite de décrire les "modèles de contenu". De plus, la méthode de l'article semble simplement énumérer toutes les chaînes de longueur Clueless

Accepté mais ne donnant pas de moyen pratique d'atteindre ... – Dror

La conversion des deux expressions en machines d'état équivalentes et la vérification de tous les chemins des deux machines permettent les mêmes correspondances. Le lemme de pompage devrait évidemment être pris en compte, alors évitez de revisiter les anciens nœuds.

Cela ne fonctionnerait que pour les expressions régulières "simples" (ou réelles, ce que vous avez, les expressions récursives de Perls sont beaucoup plus expressives).

Alors qu'un graphique de la machine d'état pourrait avoir un grand nombre de chemins, il devrait toujours être limité (surtout si la source pour les expressions est humaine). Donc, vous trouverez tous les chemins autorisés de RegEX1, et vérifiez, chacun à son tour, si c'est permis dans RegEX2. Si tous les chemins sont valides, vous savez que l'un est contenu dans l'autre.

Source

2009-06-10 12:41:52 Svend

Est-il possible (dans un délai raisonnable) d'effectuer un test pour obtenir une hiérarchie d'expressions régulières (plusieurs centaines d'entre elles)? pouvez-vous fournir des pointeurs sur le code qui fait cela? – Dror

Je ne vois pas pourquoi cela ne serait pas possible, et dans un temps décent aussi. Vous devriez construire cela à partir de rien, ce qui n'est pas trivial. – Svend

vérifier "tous les chemins sont valides" pour toutes les paires prendrait probablement très longtemps. "vérifier tous les chemins dans les deux machines" comme vous le dites peut être infini, ou ai-je raté quelque chose? – Dror

expression régulière "contient" une autre expression régulière

Répondre

Questions connexes