Détecter un conflit entre deux expressions régulières

[Picsonald]

Bonjour à tous,

Après des recherches sur votre forum et ailleurs, je reste bloqué devant un défi technique : je n'arrive pas à détecter un conflit entre deux expressions régulières. Illustration (schématique) :

Les expressions régulières ont la syntaxe de « filtres » de fichiers Windows.

Voici un nom de fichier : « ALIB.TXT »

Et trois expressions régulières, et le résultat qu'elles renvoient (Match) :

• Expression 1 : « A*B.TXT » = OUI
• Expression 2 : « AL*.TXT » = OUI
• Expression 3 : « B*.TXT » = NON

Conclusion :

• Les expressions 1 & 2 peuvent être en conflit
• Les expressions 1 & 3, et 2 & 3 ne peuvent jamais être en conflit (impossible)

La question à laquelle je ne trouve pas de réponse est... :
Comment faire pour détecter que les expressions 1 & 2 peuvent être en conflit ?

Je code en C#, et j'ai besoin de coder une méthode qui ressemblerait à

Code :

1
2
3
4
5
bool IsConflitualRegex(string expr1, string expr2)
{
  // Code difficile à écrire
  // return true ou false;
}

Est-ce que l'un d'entre vous aurait des pistes à me soumettre ?

Merci d'avance,

Picsonald.

[mokfajri]

Je crois que c'est un problème assez difficile pour être codé dans une fonction, car si je comprends bien, tu cherche un moyen qui permet de dire que deux Regex sont équivalentes (Dans le monde des Maths cela revient à trouvé un invariant).
Voilà un lien où on parle de ce problème
http://fr.softuses.com/73604

[Picsonald]

Merci pour ta réponse !

En effet, ton lien m'a mené vers les liens suivants :

• http://www.perlmonks.org/index.pl?node_id=423487
• http://www.perlmonks.org/index.pl?node_id=531661
• http://search.cpan.org/search?mode=m...xp%3A%3AParser
• http://stackoverflow.com/questions/1...a-minimization
• http://www.codeproject.com/Articles/...sion-Parser-in

Je ne connaissais pas du tout ces notions mathématiques autour des expressions régulières. Une piste pour moi sera de déterminer le DFA minimal de mes regex, pour ensuite les comparer... Sachant qu'en plus, en C#, on a un moteur NFA.

Je crois bien que c'est trop dur pour moi. Je vais abandonner le développement de cette méthode.

Merci pour ton aide, mokfajri.