Discussion :

[David.Schris]

Bonjour,

Je tiens à vous prévenir : les termes que j'emploierai dans ce message (et ceux employés dans son sujet) sembleront probablement incorrects aux yeux des puristes mais je fais ce que je peux avec mon vocabulaire plus que limité.
Afin que chacun puisse comprendre, j'essaierai d'expliquer ce que j'entends par "ambiguïté", "expression rationnelle", 'collision" (voir plus loin), et autres.
Afin que je puisse vous comprendre, vous avez le choix : soit vous utilisez mes termes, soit vous définissez ceux que vous utilisez d'une façon facilement compréhensible pour un non initié (et non puriste).

Première chose : quand j'écris "expression rationnelle" (dans ce message) je parle de ce que d'autres appellent "expressions régulières" ("regular expressions" en anglais).
Il s'agit d'expressions telles que celles utilisées par les commandes grep et sed.
Voyez http://etna.int-evry.fr/COURS/UNIX/f...n1/grep.1.html si vous n'êtes pas sûrs de savoir de quoi je parle.
Il est fortement probable que j'utilise les termes "expression régulière", "expression", ou "regex" pour désigner une (i.e. en lieu et place de) "expression rationnelle".

Cette première mise au point étant faite, passons à mon but...

Les regex sont souvent utilisées pour "filtrer" du texte : on donne à un programme (comme grep ou sed) du texte et une expression régulière et le programme effectue un traitement (affichage, modification) sur les parties du texte qui correspondent (ou pas) à l'expression régulière fournie.
Dans ces cas, on fournit une regex et des données en entrée à un programme.
Ce que je souhaite faire, c'est "l'inverse". Je veux fournir une expression à un programme et je veux qu'il me fournisse des données en sortie (sans autre entrée que l'expression) : je veux écrire un programme qui, étant donné une regex, génère toutes les chaînes de caractères qui correspondent à cette dernière.
A noter que le sujet de ce message n'est pas de discuter de l'utilité d'un tel programme, mais de discuter de comment l'écrire.
Exemples :
1) je fournis "[01]" (sans les guillemets) à mon programme et il me donne "0" puis "1", soit les chaînes composées d'un caractère pris parmi "0" ou "1" (vous noterez que je n'utilise pas les méta-caractères "^" et "$").
2) pour "abc{3,5}", le programme écrit "abccc" puis "abcccc" puis "abccccc", soit les chaînes composées d'un "a" suivi d'un "b" suivi de 3 à 5 "c".
3) pour "[A-E][0-9]", le programme écrit "A0", "A1", ... "A9", "B0", "B1", ... "B9", ... "E9", soit les chaînes composées d'un caractère parmi "A" ou "B" ou "C" ou "D" ou "E" suivi par un caractère parmi les chiffres de "0" à "9".
4) pour "[A-Z]{3,10}[0-9]{5,9}", le programme écrit les chaînes composées d'une suite de 3 à 10 lettres majuscules suivie d'une suite de 5 à 9 chiffres de "0" à "9".
Vous suivez toujours ?

Enchaînons sur mon problème : certaines expressions sont, selon mes termes, "ambigües".
Commençons par un exemple : considérez l'expression "[AB01]{3,10}[01]{5,9}".
Elle doit permettre de générer toutes les chaînes composées de 3 à 10 caractères pris parmi "A" ou "B" ou "0" ou "1" suivis de 5 à 9 caractères pris parmi "0" ou "1".
Vous noterez que j'ai écrit mon expression en utilisant deux couleurs : le but est de faire ressortir le fait que cette expression peut être découpée en deux sous-expressions plus simples et de mieux vous faire comprendre d'où vient mon problème.
Quand mon programme génère les chaînes correspondantes, il génère en fait les chaînes formées par la concaténation des chaînes générées par les deux sous-expressions.
Note: dans ce qui suit j'utiliserai "expansion d'une expression" pour désigner "la génération de toutes les chaînes de caractères formées en suivants les règles de génération énoncées par l'expression".
Donc, l'expansion de l'expression donnée en exemple se fait par concaténation de chaque chaîne générée par expansion de la première sous-regex avec chacune des chaînes résultant de l'expansion de la deuxième sous-regex.
Par exemple, parmi les chaînes générées on trouvera :
"ABBA00100110"
"BBAABA111100110"
Mais on trouvera aussi :
"ABBA00100110"
"BBAABA111100110"
Voilà mon problème : mon programme génère des doublons.
C'est pour cette raison que je qualifie mon expression d'ambigüe : par expansions différentes des sous expressions qui la composent, on obtient des résultats identiques.
Autrement dit : un même résultat peut être obtenu de deux façons (ou plus) différentes (c'est dans ce cadre que je parle de "collision").

Je ne veux pas filtrer ce qui sort de mon programme pour éliminer les doublons : je veux que mon programme n'en produise pas.
D'ailleurs, dans la pratique, filtrer les doublons après coup risque de trouver ses limites : grosse consommation de mémoire, perte de temps, etc.

Ce que je pensais faire peut être résumé ainsi : transformer l'expression de départ en une ou plusieurs expressions "non ambigües" de telle façon que les chaînes générées à partir de ces expressions soient les mêmes que celles qui auraient été obtenue par expansion de l'expression de départ mais sans les doublons.
Par exemple, soit une expression E0 telle que E0="[AB01]{3,10}[01]{5,9}". J'aurai (si ce que je souhaite est possible) : E0="[AB01]{2,9}[AB][01]{5,9}|E1" avec E1 une autre expression à déterminer (et "|" dénotant une alternative, un "OU" si vous préférez).
Comment trouver "E1" ?

J'espère avoir réussi à expliquer mon problème de façon compréhensible.
Evidemment, je préfèrerai obtenir des réponses qui soient plus détaillées et compréhensibles qu'un simple "t'as qu'à lire le théorème de Truc et l'appliquer à la conjecture Muche dans les cas ou la condition de Bidule est réalisée"

Merci pour votre attention.

[méphistopheles]

Bonjour.
Je dois bien avouer que c'est un des plus beaux posts que j'ai jamais vus. (surtous si on le compare que posts du type "c'est dans le tirtre".)

Pour ce qui est de ton problème, je ne comprend pas ce que tu entent par une troisième expression à déterminer: comment cette troisième fonction pourrais-elle éliminer les doublons?

par contre, je me demandais s'il n'étais pas possible de générer une liste de doublons et de les éliminer dés leur création (lorsque l'un est éliminé, on retire la possibilité de la liste).

pout ton exemple, ton expression serais:[AB]{0,9}[01]{1,9}[01]{1,(19-x)}
ou x est le nombres de caractères de ton expression.

c'est une idée, je suis pas sûr qu'elle soit bonne mais comme, à moins de chercher une expression équivalente sans doublets, je ne vois pas d'autres solution...

bonne chance

[Sib]

Les expressions rationnelles sont en fait une représentation de langages réguliers (représentés sous forme de grammaires régulières)..

Tous les problèmes que tu exposes sont à peu de choses près ceux que l'on peut rencontrer en théorie des langages, en compilation, en interprétation de code..


Les ambiguités font aussi parti des problèmes que l'on peut y rencontrer..
Il faut alors trouver / choisir la facon d'analyser le texte pour lever cette ambiguité (par exemple, en choisissant des priorités sur les opérateurs lorsqu'on reconnait une expression arithmétique)..

Un exemple typique d'ambiguité rencontré lors de la compilation / interprétation de code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

if Cond1 then if Cond2 then Instr else Instr;

Si dans notre langage, on a le choix entre la conditionnelle "if then" et la conditionnelle "if then else", alors lors de la compilation de ce code, on ne sait pas si le mot clé "else" correspond au premier "if" ou au deuxième "if"..
Il est alors nécessaire de faire un choix, via un choix dans l'ordre d'analyse (typiquement, le mot clé "else" appartiendra au deuxième "if", levant alors l'ambiguité)..


Il serait à mon avis bien trop long de t'exposer en détail toutes les solutions à tes problèmes.. Le mieux serait de lire un bon cours de Théorie des Langages..


Plus "simplement", il existe des outils tels que Yacc / Bison, qui permettent de générer automatiquement (dans un langage de programmation donné (C, C++, Caml, Java,..) un analyseur syntaxique à partir d'une grammaire hors-contexte (donc également à partir d'un langage régulier, donc d'une expression rationnelle)..
Il existe des versions de Yacc (et compagnie) pour pas mal de langages de programmation.. A toi de choisir celui qui génèrera le code dans le langage de programmation que tu préfères ..

En partant de l'analyseur syntaxique généré, tu dois alors pouvoir le modifier pour qu'au lieu de reconnaitre des mots correspondants à une expression rationnelle, il génère tous les mots reconnus par cette dernière..


Bonne recherches !

[sylk974]

Héhé, merci joli cours qui ne semble pas correspondre au pb
Lex / Yacc sont des analyseurs syntaxiques et sémantiques, qui permettent à partir d'un flux de vérifier s'il suit une grammaire donnée et à ce moment là, faire des traitements selon cette grammaire.
Issu on veut générer ces flux ...

En ce qui concerne le problème, il semblerait que l'obtention de doublons intervient lorsque qu'il y a un certain nombre de caractères communs entre 2 morceaux d'expressions rationnelles.

[AB01]{3,10} [01]{5,9}

La on voit bien qu'il y a 0 et 1 dans les 2 morceaux, et donc la possibilité pour le caractère en question de se trouver dans un des morceaux ou dans l'autre. En marquant ces cas comme étant 'cas à risques' par un flag par exemple, tu peux rajouter dessus un traitement sur des doublons.
Ainsi t'as pas à filtrer toutes les chaînes en entier.

Sinon, en version plus porcos, tu fais un INSERT INTO dans une base genre mysql. Quand t'as fini tu fais un SELECT DISTINCT, et ca y est, t'as ta gestion de doublons qui elle est efficace dans les bases de données

Là où l'intervention de Sib est intéressante, c'est que les expressions rationnelles sont effectivements issues des grammaires régulières, donc de niveau 4 en théorie des langages. Le gros intérêt, c'est qu'elles s'implémente sous forme d'automates finis !!!! Et ca c'est génial !!!!
Ca peut s'implémenter en chaînes de markov.
Mais apparement tu ne t'es pas orienté théorie des langages mais tu gagnerais vraiment à analyser ce coté là. Pour travailler sur les expression s rationnelles, c'est indispensable je pense.

Le meilleur compromis entre rapidité d'implémentation et efficacité est la solution base de données je pense.

PS : tu te limites à des expressions rationelles finis ? tu traites les [AB]+ par exemple ? ce qui me paraitrait difficile vu que ca génère une infinité de chaînes.

Très intéressant comme projet en tout cas !

[Sib]

Yacc et compagnie permettent de générer un analyseur syntaxique d'une grammaire donnée.. Bien sûr, cet analyseur analyse le flux, il ne le génère pas..

Je pensais, cependant, utiliser l'analyseur syntaxique généré, pour le modifier, et lui faire générer le flux au lieu de le reconnaitre ..

L'automate fini en question peut effectivement être très utile.. Le tout est, bien entendu, de le rendre déterministe ..

Dans tous les cas, je ne pense pas que chercher à générer tous les mots reconnus par une grammaire de façon bourrine soit judicieux (ça pourra marcher pour des expressions rationnelles simples, mais dès qu'elles se compliqueront, ça deviendra vraiment hard)..

C'est pour cela que je pensais utiliser ce que nous donnent les outils existants pour se "simplifier" la tâche lol..

[Jean-Marc.Bourguet]

Petite question préalable, tes expressions sont-elles réellement rationelles (au sens théorie des langages) ou bien peut-il y avoir une de ces extentions bien pratique mais qui empèche d'utiliser cette théorie?

Si j'avais à générer explicitement le langage correspondant à une expression rationelle au sens strict, je génèrerais l'automate déterministe correspondant, le rendrait minimum (voir n'importe quel bouquin sur la compilation, à coup sur c'est dans le dragon book) et partirait de cela. En fait, j'ai l'impression qu'à partir de l'automate minimum, on peut batir facilement ton "expression non ambigue".

S'il peut y avoir des extensions, là le problème se complique sérieusement.

[David.Schris]

Bonsoir,

Je dois bien avouer que c'est un des plus beaux posts que j'ai jamais vus. (surtous si on le compare que posts du type "c'est dans le tirtre".)

Merci. Ce n'est évidemment pas un hasard : je reproche régulièrement (<- sans jeu de mot) à d'autres d'être imprécis, je me dois donc d'essayer de l'être.

Pour ce qui est de ton problème, je ne comprend pas ce que tu entent par une troisième expression à déterminer: comment cette troisième fonction pourrais-elle éliminer les doublons?

Je pense finalement qu'on peut ignorer partiellement cette partie de mon message. C'est apparemment (<- je reste prudent) une fausse piste que j'ai empruntée dans mes recherches.
En fait, le fait qu'elle soit fausse vient de la manière dont j'essayais de décomposer l'expression problématique. Par contre, je pense qu'il faudra décomposer l'expression générant des doublons pour éviter ces derniers. Le but de cette décomposition d'une expression en plusieurs étant que l'expansion de toutes les expressions obtenues génère les mêmes chaînes que l'expression originale...sans les doublons.

par contre, je me demandais s'il n'étais pas possible de générer une liste de doublons et de les éliminer dés leur création (lorsque l'un est éliminé, on retire la possibilité de la liste).

Je ne suis pas sûr de bien comprendre ici.
Pour générer les doublons, il faut générer les chaînes à partir de l'expression problématique, hors j'ai bien précisé :

Je ne veux pas filtrer ce qui sort de mon programme pour éliminer les doublons : je veux que mon programme n'en produise pas.

pout ton exemple, ton expression serais:[AB]{0,9}[01]{1,9}[01]{1,(19-x)}
ou x est le nombres de caractères de ton expression.

Là non plus, je ne suis pas sûr de bien comprendre : la regex que tu donnes ne génèrera que des chaînes commençant par "A" ou "B" ou des chaînes ne contenant pas du tout "A" ou "B". Quid de chaînes (qui devront être générées) comme "0A011111" ?

c'est une idée, je suis pas sûr qu'elle soit bonne mais comme, à moins de chercher une expression équivalente sans doublets, je ne vois pas d'autres solution...

C'est au fond ce que je cherche à faire : trouver à partir d'une expression une regex "équivalente" qui ne produise pas de doublons.

bonne chance

Merci

Les expressions rationnelles sont en fait une représentation de langages réguliers

Oui.

Tous les problèmes que tu exposes sont à peu de choses près ceux que l'on peut rencontrer en théorie des langages

Oui, je suppose.

en compilation, en interprétation de code..

Non. Depuis quand la compilation/l'interprétation produit-t-elle tous les codes source possibles pour une syntaxe donnée ? Car c'est un peu ce que je cherche à faire si on fait le parallèle...

Il faut alors trouver / choisir la facon d'analyser le texte pour lever cette ambiguité

Quand on veut analyser du texte, oui. Mais je ne veux pas analyser du texte, je veux en produire. Peut-être ai-je mal choisi mon terme en parlant "d'ambiguïté" ? Si c'et le cas et si cela vous perturbe, faites comme si je ne l'avais pas utilisé.

Il serait à mon avis bien trop long de t'exposer en détail toutes les solutions à tes problèmes

Ah, là cela devient intéressant. Si vous êtes capble d'évaluer le temps nécessaire pour exposer les solutions à mon problème (cf. "il serait [...] bien trop long"), c'est que vous connaissez ces solutions. Donc si je comprends bien, c'est juste par manque de temps que vous ne me les donnez pas ? C'est dommage.

Le mieux serait de lire un bon cours de Théorie des Langages..

Merci mais...

Evidemment, je préfèrerai obtenir des réponses qui soient plus détaillées et compréhensibles qu'un simple "t'as qu'à lire le théorème de Truc et l'appliquer à la conjecture Muche dans les cas ou la condition de Bidule est réalisée"

Et puis comment suis-je censé trouver un bon cours ? Jusqu'à preuve du contraire, pour trouver un bon cours sans que quelqu'un ne vous donne d'indication il faut en lire un puis, si il ne semble pas bon, en lire un autre, etc... Ce n'est pas que je ne veuille pas lire, mais si je peux éviter de passer un doctorat en math pour trouver une solution à mon problème...

Plus "simplement", il existe des outils [...] qui permettent de générer [...] un analyseur syntaxique

Rappel : je ne veux pas analyser du texte, je veux en produire.

En partant de l'analyseur syntaxique généré, tu dois alors pouvoir le modifier pour qu'au lieu de reconnaitre des mots correspondants à une expression rationnelle, il génère tous les mots reconnus par cette dernière..

Comment ? Cela a l'air tellement simple quand on le lit, j'avoue que cela dépasse mon sens de la logique.

Bonne recherches ! :Wink:

Merci.

En ce qui concerne le problème, il semblerait que l'obtention de doublons intervient lorsque qu'il y a un certain nombre de caractères communs entre 2 morceaux d'expressions rationnelles.

Exact, mais ce n'est pas la seule condition. Exemple : "[A0]{1,1}[B0]{1,1}". Il faut aussi qu'un caractère à la position P d'une chaîne de longueur N puisse avoir été généré par la première ou la seconde expression.

En marquant ces cas comme étant 'cas à risques' par un flag par exemple, tu peux rajouter dessus un traitement sur des doublons.

Sauf que je ne veux pas faire de "traitement sur des doublons". Faire un "traitement sur des doublons" implique qu'il puisse y avoir des doublons, or je ne veux pas qu'il y en ait.

Sinon, en version plus porcos, tu fais un INSERT INTO dans une base genre mysql. Quand t'as fini tu fais un SELECT DISTINCT, et ca y est, t'as ta gestion de doublons qui elle est efficace dans les bases de données

Tout dépend de ce que l'on entend par "efficace". Personnellement, je ne trouve pas efficace le fait de devoir produire toutes les chaînes (et les stocker !) pour ensuite en éliminer les doublons avec une base de données qui devra avoir été préalablement installée... A mon sens, c'est plus facile à faire, pas plus efficace.

Là où l'intervention de Sib est intéressante, c'est que les expressions rationnelles sont effectivements issues des grammaires régulières, donc de niveau 4 en théorie des langages. Le gros intérêt, c'est qu'elles s'implémente sous forme d'automates finis

Oui, c'est ce qui me permet de facilement écrire du code qui génère les chaînes correspondant à une regex. Mais automate fini ou pas : j'ai toujours des doublons

Ca peut s'implémenter en chaînes de markov.

Comment ? J'ai fait une recherche sur le sujet et n'ai rien trouvé qui corresponde à mon problème et/ou que je sois capable de comprendre. Rappel :

je préfèrerai obtenir des réponses qui soient plus détaillées et compréhensibles qu'un simple "t'as qu'à lire le théorème de Truc

N'ayez pas peur de me considérer comme n'ayant aucune connaissance en maths : vous ne serez pas loin de la vérité (et je n'en ai pas honte).

Le meilleur compromis entre rapidité d'implémentation et efficacité est la solution base de données je pense.

Mais je suis difficile et têtu, je ne veux pas d'une telle solution, et je précise pour ceux à qui l'idée viendrait : même sans base de données.

PS : tu te limites à des expressions rationelles finis ? tu traites les [AB]+ par exemple ? ce qui me paraitrait difficile vu que ca génère une infinité de chaînes.

Bonne question. Non, pour l'instant je ne m'occupe pas des opérateurs de répétition "*" et "+". Le fait que les chaînes générées pourront théoriquement être de longueur infinie va à l'encontre d'une hypothèse dont on n'a pas prouvé qu'elle était fausse : la mémoire d'un ordinateur est finie. De même, pour générer N fois un caractère il faudra à un moment ou à un autre que je compte ce nombre N de fois, donc que ce nombre soit stocké. La taille d'une variable étant souvent fixe et toujours limitée, cela serait impossible. Peut-être que je permettrai à l'utilisateur d'utiliser ces opérateurs, mais le programme les remplacera (respectivement) par "{0,unGrandNombre}" et "{1,unGrandNombre}".
Les expressions qui devront être acceptée peuvent être définies comme suit :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
expression := (sous-expression)*
sous-expression := caracteres repetitions
caracteres := unCaractere | uneClasseDeCaracteres
unCaractere := "a" | "b" | "c" | "d" | ... | "A" | "B" | "C" | "D" | ... | "0" | ... | "9" ...
uneClasseDeCaracteres := "[" ("^")? (uneListeDeCaracteres | unePlageDeCaracteres)+ "]"
uneListeDeCaracteres := (unCaractere)+
unePlageDeCaracteres := unCaractere "-" unCaractere
repetitions := "{" nombreMini "," nombreMaxi "}"
nombreMini := unNombreEntierPositifOuNul
nombreMaxi := unNombreEntierStrictementPositif
unNombreEntierPositifOuNul := "0" | unNombreEntierStrictementPositif
unNombreEntierStrictementPositif := unChiffreAutreQueZero (unChiffre)*
unChiffreAutreQueZero := "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
unChiffre := "0" | unChiffreAutreQueZero

...J'espère ne pas avoir fait d'erreur...
Bref : pas de méta-caractères indiquant le début et la fin d'une chaîne ("^" et "$") car cela n'a à mon sens pas de raison d'être dans mon cas, pas de méta-caractères indiquant le début et la fin d'un mot ("\<" et "\>") car je considère que je génèrerai des mots, pas d'alternatives ("|") ni de regroupements (avec "(" et ")") pour l'instant car...je ne suis pas complètement fou (mais si vous savez comment faire, je suis preneur).

Très intéressant comme projet en tout cas !

Très "prenant" dirais-je : cela fait plusieurs jours que j'ai des expressions régulières plein la tête (et plusieurs jours que mon stylo me supplie d'arrêter d'écrire cinq minutes)

Je pensais, cependant, utiliser l'analyseur syntaxique généré, pour le modifier, et lui faire générer le flux au lieu de le reconnaitre

Généré à partir de quoi ? A partir de la grammaire des expressions acceptées par mon programme ? J'en doute car cette dernière ne donne pas la forme des chaînes à générer. A partir de l'expression entrée par l'utilisateur utilisée comme grammaire ? Dans ce cas il faudrait générer (et compiler) un analyseur syntaxique à chaque nouvelle expression entrée par l'utilisateur... Et puis un analyseur...analyse. Il ne génère pas.

Dans tous les cas, je ne pense pas que chercher à générer tous les mots reconnus par une grammaire de façon bourrine soit judicieux

Ce à quoi je répondrai :

A noter que le sujet de ce message n'est pas de discuter de l'utilité d'un tel programme, mais de discuter de comment l'écrire.

ça pourra marcher pour des expressions rationnelles simples, mais dès qu'elles se compliqueront, ça deviendra vraiment hard

Cela tombe plutôt bien : je me limite à des expressions simples (cf. un peu plus haut).

C'est pour cela que je pensais utiliser ce que nous donnent les outils existants pour se "simplifier" la tâche

J'ai effectivement cherché des outils existant pour essayer de me simplifier la tâche, mais n'en ai trouvé aucun qui GENERE du texte correspondant à une regex...d'où ma tentative d'en écrire un...

Merci en tous cas (à tous) d'avoir fait des propositions.
Si au moins ma question pouvait croiser la route d'une personne se l'étant déjà posée...je croise les doigts...

Bonne soirée et bonne nuit !


PS : promis, si je me réveille en pleine nuit avec la solution, je vous la donne aussitôt !

[Sib]

Bon eh bien, la résolution de ce problème se résume en :
- Générer (sous forme de graphe) l'automate (déterministe et minimum si possible) correspondant à l'expression rationnelle
- Parcourir tous les chemins du graphes allant de l'état initial aux états finaux, et affichage de ces chemins

Ca ne veut pas dire pour autant que cette résolution est simple, et je ne saurais te dire comment le générer et comment le parcourir (de la façon la plus efficace possible)..

[méphistopheles]

par contre, je me demandais s'il n'étais pas possible de générer une liste de doublons et de les éliminer dés leur création (lorsque l'un est éliminé, on retire la possibilité de la liste).

Je ne suis pas sûr de bien comprendre ici.
Pour générer les doublons, il faut générer les chaînes à partir de l'expression problématique, hors j'ai bien précisé :

Je ne veux pas filtrer ce qui sort de mon programme pour éliminer les doublons : je veux que mon programme n'en produise pas.

Désolé , mais je ne vois absolument pas de methode de génération de chaines sans doublons avec ton système. je pensait que trouvaer l'algorhytme qui générais tous les doublmons avait l'avantage d'accelérer ton filtrage puisque cela est normalement plus ou moins généré dans le même ordre que ta chaine principale et qu'il sufit de faire une élimination par teme généré. (ex: on à généré les deux listes, A la principale, B celle des doublons, je prend le priemier terme de B, je parcourt la chaine A jusqu'a en trouver un égual, je le suprimme, je passe au sivant où je part DU POINT OU JE ME SUIS ARRETE, puis je reccommence).
cette solution a l'avantage d'être beaucoup plus rapide que la recherche de doublons et beaucoup plus simple que celle de génération de chaine sans doublons.
Par contre, je n'ai pas trouvé (et pas vraiment cherché non plus), comment générer cette chaine à partir de n'importe quelle autre, mais j'espère que ça viendra (enfin, dis mois si ça te conviens pas du tout, que j'évite de passer une nuit blance. )


salut

[David.Schris]

Re-Bonsoir,

Petite question préalable, tes expressions sont-elles réellement rationelles (au sens théorie des langages) ou bien peut-il y avoir une de ces extentions bien pratique mais qui empèche d'utiliser cette théorie?

Je ne saurai dire si mes expressions sont "réellement rationelles (au sens théorie des langages)", mais peut-être mon précédent message répond-il indirectement à cette question ?

Si j'avais à générer explicitement le langage correspondant à une expression rationelle au sens strict, je génèrerais l'automate déterministe correspondant, le rendrait minimum (voir n'importe quel bouquin sur la compilation, à coup sur c'est dans le dragon book) et partirait de cela. En fait, j'ai l'impression qu'à partir de l'automate minimum, on peut batir facilement ton "expression non ambigue".

"Facilement" ? Une lueur d'espoir !
En fait, je n'ai pas l'impression que le problème soit excessivement difficile, je "sens" (<- c'est difficile à expliquer) que je suis juste en train de regarder les choses du mauvais côté et que trouver comment voir les choses me permettra de trouver la solution.

S'il peut y avoir des extensions, là le problème se complique sérieusement.

Il est déjà assez compliqué comme ça pour l'instant.
Les seules expressions autorisées sont formées de la concaténation de 0 à N sous-expressions elles-mêmes (en gros) formées d'une liste de caractères suivie des nombres minimum et maximum de répétition pour cette liste.
D'ailleurs, je m'aperçois que j'ai fait une petite erreur dans ma définition des expressions acceptées dans mon précédent message...
Au lieu de :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

sous-expression := caracteres repetitions

...il faut lire :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

sous-expression := caracteres (repetitions)?

Autrement dit, si il n'y a pas d'indication de répétition on considère que c'est "{1,1}".

Et cette fois, je vais me coucher...

Bonne nuit !

[Jedai]

Bon eh bien, la résolution de ce problème se résume en :
- Générer (sous forme de graphe) l'automate (déterministe et minimum si possible) correspondant à l'expression rationnelle
- Parcourir tous les chemins du graphes allant de l'état initial aux états finaux, et affichage de ces chemins

Ca ne veut pas dire pour autant que cette résolution est simple, et je ne saurais te dire comment le générer et comment le parcourir (de la façon la plus efficace possible)..

L'avantage de cette méthode, c'est qu'elle éliminera les doublons (sinon l'automate n'est pas minimal). De plus le parcours est très simple : puisque l'on n'accepte pas l'"*" et le "+", il n'y a pas de cycle dans l'automate, il suffit de faire une fonction récursive qui explore chacun des chemins pour chaque noeud rencontré durant le parcours (et qui écris le mot déjà formé lorsqu'elle rencontre un état final).

Pour ce qui est de la génération de l'automate minimal, le plus simple est de générer l'automate fini non-déterministe équivalent à la regex (trivial), puis le déterminiser (l'algorithme est simple, une courte réflexion devrait te le donner), et ensuite le minimiser (il y a alors plusieurs algorithmes, je te laisse chercher, j'en connais un moi-même, mais je ne suis pas sûr que ce soit le meilleur).

--
Jedaï

[GrandFather]

Bonjour,

ce n'est encore qu'une vague idée, mais plutôt qu'un graphe, le programme devrait générer un arbre (qui n'est après tout qu'un graphe non connexe) des chaînes générées par ta grammaire. Chaque noeud contiendrait la chaîne minimale générée correspondante à une étape de l'interprétation de l'expression régulière et conserverait d'autre part l'état correspondant de l'automate (la position courante dans le cas d'une itération induite par {x,y}, la sous-expression qui sera évaluée par les sous-arbres). Ainsi, l'expression régulière suivante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

[AB]{0,1}C

génèrerait l'arbre suivant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
/ | \
C A B
  | |
  C C

Il suffit ensuite d'un parcours en préordre de l'arbre pour récupérér toutes les chaînes produites par la grammaire.

De deux choses l'une : soit l'arbre est construit implicitement par l'enchaînement des appels récursifs des fonctions de ton analyseur, soit itérativement en passant par plusieurs étapes, l'analyse puis la "compilation" dans une suite de fonctions atomiques qui te généreront l'arbre.

[Jean-Marc.Bourguet]

Je ne saurai dire si mes expressions sont "réellement rationelles (au sens théorie des langages)", mais peut-être mon précédent message répond-il indirectement à cette question?

J'ai regarde rapidement et il me semble qu'effectivement il n'y a pas ce qui generait.

"Facilement" ? Une lueur d'espoir ! En fait, je n'ai pas l'impression que le problème soit excessivement difficile, je "sens" (<- c'est difficile à expliquer) que je suis juste en train de regarder les choses du mauvais côté et que trouver comment voir les choses me permettra de trouver la solution.

En fait, si tout ce que tu veux c'est generer tout le langage (et pas particulierement avoir l'expression simplifiee, en y reflechissant je suis un peu moins confiant sur la possibilite de generer celle-ci facilement), tu peux directement utiliser l'automate en le parcourant de la maniere que tu veux.

[Sib]

ce n'est encore qu'une vague idée, mais plutôt qu'un graphe, le programme devrait générer un arbre (qui n'est après tout qu'un graphe non connexe) des chaînes générées par ta grammaire.

Petit erratum : Un arbre est un graphe connexe, mais sans cycle

[GrandFather]

ce n'est encore qu'une vague idée, mais plutôt qu'un graphe, le programme devrait générer un arbre (qui n'est après tout qu'un graphe non connexe) des chaînes générées par ta grammaire.

Petit erratum : Un arbre est un graphe connexe, mais sans cycle

Merci pour la rectification.

[hansaplast]

de mon cerveau de debutant, je voit diverses choses (vous pouvez m'ignorer, si je ne dit rien de bien...)

1/ la methode de l'arbre me semble bien.

mais, ma facon de voir l'implementation est ainsi :

utilisation d'une suite d'arbres XML

arbre de [A,B]{0,2}
ex :

/\
A B
/ \ / \
B A B A

comment gérer le fait que ce soir present 0 a 2 fois?

a l'aide de metha données, stockées par exemple dans l'arbre en XML


chaque REGEX minimal etant géerée l'une a la suite de l'autre.

mais le pb de doublon se situe au niveau de deux regex connexes pouvant gérer deux chaine identiques une fois concatenées...

donc, il faut regouper les deux arbres XML dans une meme sur-arbre.

pour ce faire, il faut recopier le premier, puis lui ajouter le second et faisant un "si le caractere est la, j'ajoute pas"...

ca semble simple, mais que faire des methadonnées?

ex :
prenons : "[AB01]{3,10}[01]{5,9}". (ton exemple d'intro)
là ou
"ABBA001 00110"
"ABBA 00100110"

sont des doublons...

les chaine "001" donc les noeuds de l'arbre devront posseder deux meta données, non?

là s'arretes mes capacitées d'analyse :

je n'ai pas ma connaissance nescessaire pour definir ces methadonnées d'une maniere ensembliste, donc je ne peut pas parler des pb qui seront recontrés plus en detail...

mais, je sent que la solution d'un arbre XML peut etre une bonne solution, la, va venir ta reponse :

"peut etre, mias ca me fait génerer des doublons pour en enelever..."

donc ma reponse sera : jusqu'on va ta notion de "generation de doublon"?

jusqu'aux variables stockées en memoire de facon temporaire?

donc, ta seule solution, il me semble sera de re-génerer une regex regroupant les deux precedentes, et ce de facon recursive, jusqu'a ne plus en avoir qu'une seule...

et là se trouve (<---je le sent) la limite de ta faconde proceder : tu limite le "langage" des regex a une partie basique, mais tu veut utiliser des regex complexes afin de re-generer le meme (met ton mot...))

en effet : factoriser, sans rajouter de chaines en plus est autrment plus complexe que (met ta phrase...)

dsl, je doit partier manger...

[Jedai]

hansaplast... Tu es victime du syndrome "XML" : dans un exercice où un arbre est apparu, tu as immédiatement pensé à du XML alors que le XML rajoute une couche d'abstractions et de notions parfaitement inutiles dans notre cas.
Par ailleurs tu sembles n'avoir pas compris que la théorie a une réponse déjà toute prête à la question de la suppression de doublon : il suffit de minimiser l'automate (dont le graphe est un arbre dans notre cas, mais cela n'a aucune influence).

--
Jedaï

[hansaplast]

alors : voui, j'ai commis plein d'erreures, je t'en donne la confirmation, alors pourquoi avoir posté : car je ne suis pas du tout assez experimenté pour repondre a ce genre de question (je ne sait meme pas ce qu'est un automate dont ovus parlez tous...)

je repete ma question : pourquoi avoir posté? -> pour apporter ma pierre a l'edifice, meme si ce que je dit est faux, et inutil, il se peut que je puisse aier (j'espere...)

et puis, reflechir a ce pb, m'a refraichit l'esprit, il me fallait bien un pretexte pour y reflechir.. j'ai trouvé ce moyen par mon post...

ps : pourquoi du xml : justement pour la couche d'abstraction permettant mes "meta données"...

mais bon :

vous pouvez m'ignorer, si je ne dit rien de bien

[Jean-Marc.Bourguet]

et puis, reflechir a ce pb, m'a refraichit l'esprit, il me fallait bien un pretexte pour y reflechir.. j'ai trouvé ce moyen par mon post...

Poster pour "réfléchir" mais sans admettre les commentaires sur ces réflexions me semble un peu étrange, surtout en admettant son incompétance par ailleurs. J'aurais compris que tu postes pour avoir justement ces critiques...

[hansaplast]

et puis, reflechir a ce pb, m'a refraichit l'esprit, il me fallait bien un pretexte pour y reflechir.. j'ai trouvé ce moyen par mon post...

Poster pour "réfléchir" mais sans admettre les commentaires sur ces réflexions me semble un peu étrange, surtout en admettant son incompétance par ailleurs. J'aurais compris que tu postes pour avoir justement ces critiques...

mais heu! j'ai aucun^pb avec les critiques ^^
je disait juste que je savait par avance que ca allait pas etre LA solution, que ma reponse risquait meme d'etre inutile^^

ma citation

vous pouvez m'ignorer, si je ne dit rien de bien

est extraite du debut de mon premier post ^^

bon, arretons le troll

as tu trouvé ton bonheur dans l'automate minimal?

ca consiste en quoi?
tu doit "factoriser" ton expression reguliere?
ou l'automate est il l'arbre en question?