Discussion :

[fabrisss]

Bonjour,

Je cherche un algo capable, à partir de plusieurs chaines de caractères, de générer une expression régulière qui valide ces chaines et/ou de mettre à jour une expression régulière à partir d'une nouvelle chaine de caractères.

Exemples simples :
chaine "aaabb" et chaine "abc" génèrent l'expression "a+b+c?"
chaine "bbc" et expression "a+b+c?" génèrent l'expression "a*b+c?"

Auriez-vous des éléments de réponse qui puissent m'aider (je devrai, par la suite, implémenter cela en php) ?

Merci pour ce forum très enrichissant,

Fabrisss

[sovitec]

Salut,

Le problème AMHA c'est qu'il existe une infinité de solutions à ton problème, dont certaines triviales (il suffit de faire un ou entre toutes les entrées par exemple). Si tu n'impose pas de contraintes à tes expressions rationnelles je ne vois pas comment s'en sortir

[Nemerle]

pourrais-tu préciser un peu la grammaire que tu veux implémenter? Désolé, mais tes 2 exemples ne sont pas clairs pour moi!

[fabrisss]

Certes, j'admets que mon problème est encore un peu flou.

L'objectif est de trouver une grammaire commune (sous la forme d'une expression régulière) à un ensemble de chaines de caractères. Cette grammaire doit être la plus spécifique possible tout en factorisant les éléments communs. Trouver une grammaire la plus générique est en effet assez trivial : ".*" convient dans tous les cas ;-)

Je conviens donc que mes exemples ne sont pas pertinents.
chaine "aaabb" et chaine "abc" devraient plutôt donner l'expression "a{1-3}b{1-2}c?"

En espérant être plus clair ? Toute référence est la bienvenue.

[buzard]

Comme l'a dis sovitec, le choix est infini, et s'étend plus précisément de "u1|u2|...|un" à ".*"

la "plus petite" (dans le sens du language généré) expression régulière étant la simple disjonction des chaines en entrée. Et la "plus grande", etant le filtre tout.

Et, faire un compromis est une tâche bien ardue, et reviendrais à établir un ordre bien fondé (voir totale) (beacoup plus fin que la simple inclusion des languages associés) sur la structure des expressions régulières. Et plus précisément dans ton cas de construire un treillis complet.

C'est possible (à rapprocher avec les méthodes de simplification des expressions dans les outils de calcul formel), mais trés long à réaliser. C'est comme écrire un compilateur à l'envers.

Je te souhaite bon courage pour la réalisation de ce projet de grande envergure. et voilà un lien qui te permettra d'avoir une base formelle afin d'y parvenir :

http://www.lix.polytechnique.fr/Labo...%20libre%22%22

[buzard]

Il y a dans cette article un exemple complet de simplification (sur lequel tu peut te baser, pour faire ton algorithme)

[fabrisss]

Merci pour cette référence; je vais tenter de me plonger la dedans mais ça me semble bien complexe...enfin, si c'est le prix à payer... :-(

[buzard]

En vérité, ça fais peur à voir parce que ça touche la logique. Et c'est toujours un peu dure à saisire. du coup il emploi tout un vocabulaire plus ou moins obscure tournant autour de la logique (en particlier des systèmes de réecriture).
Mais l'idée essentielle est assez simple à retenir, utiliser des règles inductifs (récursif dans les cas de paramètres entier) pour résoudre le problème.

Pour ton cas, et pour t'orienter un peu. Cela se traduira tous bonnement par le choix des règles
- de factorisation (prefixes et sufixes communs)
- de généralisation (quand est-ce qu'on généralise avec l'étoile "*")
- de restriction (le langage est trop gros que dois-je enlever)

et toute les autres règles (heuristique ou exacte) plus subtile qui ne rentre pas dans une des ces catégories. toute les règles doivent garder une cohérence d'echelle afin de pouvoir garantir la terminaison de l'algo.

Une bonne connaissance du contexte d'application est en générale nécéssaire. Par exemple si le langage initiale est issue d'une grammaire hors contexte, Il sera beaucoup plus simple de trouver des bonnes factorisations. Parce que tu connais déjà les schémas (les calques) que tu peut appliquer. C'est en cela que je faisais le rapprochement avec un décompilateur (en entrée on a le code assembleur, et la grammaire du langage et en sortie un code "source" qui correspond)

En tous cas n'hésite pas à posé des questions. Je serais ravis de t'aider à comprendre ne serais-ce qu'un tout petit peu, les concepts qui sont cachés derrières.