Discussion :

[axel584]

Bonjour,
Je recherche un moyen pour, à partir d'une expression régulière, obtenir la liste exhaustives des phrases qui "match" (si celui ci n'est pas infini bien sûr).

Par exemple, à partir d'une expression du type :
a(b|c)d
Je voudrais obtenir un tableau : ['abd','acd']
Et à partir de l'expression :
a(b|c)d|e
Je voudrais obtenir un tableau : ['abd','acd','e']

Avez vous une idée de comment obtenir ça ?

A la base, je voudrais faire un outil qui demande une réponse textuelle et qui vérifie si la réponse est juste par rapport à différentes formulations possible. J'avais d'abord listé les réponses dans un tableau et je me suis rendu compte qu'une expression régulière était plus simple.

Mais je voudrais pouvoir afficher "toutes les réponses possibles".

Merci pour votre aide,

Axel

[Celira]

En d'autres termes, tu veux faire un genre de rétro-ingénierie de la regex ? et de façon automatique, je suppose.
Une recherche sur Internet me donne des fonctions/classes/librairies écrites par des gens comme ReverseRegex et GitHub - gajus/paggern: Pattern interpreter for generating random strings..
Donc a priori, c'est faisable, mais ça a l'air d'être compliqué.

[Dendrite]

Salut !

D'un côté, je me dis ça :
A quoi ça servira ?
A générer des chaînes à tester pour vérifier si une regex est correcte ?
Si c'est ça, je trouve que c'est un peu tautologique."Proposition complexe qui reste vraie en vertu de sa forme seule, quelle que soit la valeur de vérité des propositions qui la composent"

De l'autre, je trouve la problématique très amusante.
Alors j'ai commencé ce truc non testé et qui ne prend que tes exemples avec ET et OU...

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
$string='a(b|c)d(e|f)';
/*
BUT produire un tableau du type
0=>a
1=>sous tableau b,c
2=>d
3=>sous tableau e,f
*/
//on supprime d'abord toutes les parenthèses
$string=str_replace('(','',$string);
$string=str_replace(')','',$string);
$tableau=array();
$index=0;
//$string devient'ab|cde|f';
//1er tour : on retient tous les "ou" ET leur position
for($i=0;$i<strlen($string);$i++){
	if($string[$i]=='|'){
		$sous_tableau[0]=$string[$i-1];
		$sous_tableau[1]=$string[$i+1];
		$index=$index-2;
		$tableau[$index]=$sous_tableau;
	}
	$index++;
}
/*
Normalement tableau devient
1=>sous tableau b,c
3=>sous tableau e,f
*
//2nd tour : on bouche les trous avec le reste
//a tester et a finir...

[axel584]

Merci beaucoup Celira, ça me semble pas mal du tout (même si je ne suis pas sûr que ça me fasse une liste exhaustive).

Dendrite : ton code a l'air bien, et avant de passer aux expressions régulières, j'utilisais un système simple de propositions séparés par des | mais quand j'ai voulu ajouté les parenthèses, ça me semblait trop complexe à gérer.

[Invité]

Bonjour,

1- tu n'as toujours pas expliqué à quoi ça pouvait servir.
As-tu un exemple CONCRET à donner, dans un contexte précis ? (pas juste des abcd...)

2-

...je voudrais faire un outil qui demande une réponse textuelle et qui vérifie si la réponse est juste par rapport à différentes formulations possible...

C'est le principe même d'une regex !
Mais alors, PAS BESOIN de "lister" toutes les possibilités : il faut juste vérifier que la chaine fournie "match".

On n'a pas besoin d'une liste exhaustive de toutes les solutions possibles !

[Dendrite]

Un problème pour les fortiches du forum ? je sais qu'il y en a beaucoup ! Des problèmes... et des fortiches !
Moi je tourne en rond...
Je suis parvenue à passer de ça

Code :

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

$string='a (b|c) d (e|f) g h i (j|k|l) m';

A ca... Bon cool.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
	Array
	(
		[0] => a
		[1] => Array
			(
				[0] => b
				[1] => c
			)
 
		[2] => d
		[3] => Array
			(
				[0] => e
				[1] => f
			)
 
		[4] => g
		[5] => h
		[6] => i
		[7] => Array
			(
				[0] => j
				[1] => k
				[2] => l
			)
 
		[8] => m
	)

après je croyais que ce serait un jeu d'enfants de passer de ce tableau aux n possibilités de distribution d'un tableau matches...
Et là, SURPRISE ! Je ne vois pas comment distribuer pour trouver les n matches !
Je suis fatiguée ou quoi ?
Et surtout, il me manque quoi pour la distribution ? J'ai essayé une boucle à l'envers, qui concatène en commençant par la fin, me disant intuitivement que ça sera rapprochait plus de ma logique.
Mais non ! Ce n'est pas le fond du problème ! Je pense aux variables dynamiques... Bref, je ne sais plus avancer...
Ou faudrait-il que je revois ma façon même de construire le premier tableau associatif ? Ca doit être ça... Mais oui bien sûr ! J'y retourne immédiatement !
Les 9 tableaux doivent être imbriqués et distribués dès le départ.
C'est parfois merveilleux de se dire que ce que je peux faire empiriquement avec ma petite tête très facilement, je ne vois pas facilement comment le modéliser ! Ca m'étonnera toujours.

[Invité]

OK...

Il ne faut pas oublier qu'il faut partir d'une regex valide...

[Dendrite]

Toutafé Jreaux... Mais disons que je veux jouer d'abord sur 2 opérateurs très simples ET et OU, pour voir si ça passe, avant d'intégrer quoi que ce soit de plus torturé.
Pour l'instant, je ne fais que m'amuser pour me dé-rouiller les méninges.

J'ai discuté avec mon mari (matheux au demeurant) qui m'a soufflé une solution en 5 minutes dans le métro.
Et je crois que ça répond enfin essentiellement à la personne qui posait une question dans le premier message de ce fil (si elle est encore là ).
En tout cas, ça répond à une problématique combinatoire que je peux rencontrer à mon travail moi !
Mon mari dit ceci : J'ai retenu la méthode la plus simple et qui me permet de conserver mon premier tableau sans problème.
Je trouve la méthode magnifique !

Tu calcules d'abord le nombre de mots à l'arrivée : en multipliant la taille de chacun des 9 tableaux
Ici 1*2*1*2*1*1*1*3*1 = 12

Ensuite, (et c'est la que c'est particulièrement contre intuitif, car je vais intervertir les rows et les cols) je compose toutes mes lignes ainsi

Premier tour :

aaaaaaaaaaaa (12 lettres)


Second tour
aaaaaaaaaaaa (12 lettres)
bcbcbcbcbcbc (12 lettres)

3ème tour
aaaaaaaaaaaa
bcbcbcbcbcbc
dddddddddddd

et à l'arrivée je prendrai verticalement chaque "mot" de 9 lettres pour les ranger dans mon tableau.
Génial ! Je n'aurais jamais trouvé ça seule.
Je m'applique à coder maintenant.

[Dendrite]

Pour info la méthode ci dessus ne fonctionne pas.
Elle provoque des doublons et n'explore pas tous les arrangements.
On ne peut pas contourner une fonction récursive... que j'ai trouvée sur le net mais que je veux remettre sur un seul niveau de profondeur...

[CosmoKnacki]

Une solution pour php 7 avec un fonction qui construit un graphe (ce qui évite de dupliquer l'information), puis une autre qui délivre les chemins de manière paresseuse (generator) à partir de ce graphe:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
class Element
{
    const TYPE_LITERAL = 0;
    const TYPE_GROUP = 1;
    const END_OF_STRING = 2;
 
    public $type;
    public $value;    
    public $next = self::END_OF_STRING;
}
 
function buildGraph($tokens) {
    $root = new Element;
    $root->type = Element::TYPE_GROUP;
 
    while ( $tokens->valid() ) {
        $token = $tokens->current();
        $tokens->next();
        switch ($token) {
            case '(':
                if ( isset($current) ) {
                    $current->next = buildGraph($tokens);
                    $current = $current->next;
                } else {
                    $root->value[] = buildGraph($tokens);
                    $current = end($root->value);
                }
                break;
 
            case ')':
                $current->next = &$root->next;
                return $root;    
 
            case '|':
                $current->next = &$root->next;
                unset($current);
                break;
 
            default:
                if ( isset($current) ) {
                    $current->next = new Element;
                    $current = $current->next;
                } else {
                    $root->value[] = new Element;
                    $current = end($root->value);
                }
                $current->type = Element::TYPE_LITERAL;
                $current->value = $token;
        }
    }
    $root->next = Element::END_OF_STRING;
    return $root;
}
 
function getPaths($elt, $prefix = '') {
    if ( $elt === Element::END_OF_STRING ) {
        yield $prefix;
        return;
    }
 
    switch($elt->type) {
        case Element::TYPE_LITERAL:
            $prefix .= $elt->value;
            yield from getPaths($elt->next, $prefix);
            break;
 
        case Element::TYPE_GROUP:
            foreach ($elt->value as $value) {
                yield from getPaths($value, $prefix);
            }
            break;
    }
}
 
$pattern = 'chap(i|a) chap(o|a) p(a|i)t(a|i)p(o|a)';
 
// validation
$validationPattern = '~ \A ( [^()]+ | \( (?1)* \) )* \z ~x';
 
if ( !preg_match($validationPattern, $pattern) )
    throw new Exception('invalid pattern.');
 
// tokenization
$tokens = (function ($regex) {
    if ( preg_match_all('~ [^()|]+ | (?<![^(|]) (?![^|)]) | [()|] ~x', $regex, $matches) )
        yield from $matches[0];
})($pattern);
 
$graph = buildGraph($tokens);
 
foreach (getPaths($graph) as $path) {
    echo $path, PHP_EOL;
}

Les patterns avec parenthèses imbriquées sont gérées.

[Dendrite]

Knacki, merci. Mais j'ai rien pour tester PHP7 moi... Faut que j'installe wamp server 3 ?
Et bon, ça ne m'empêchera pas de me pencher sur ton code, qui a l'air bien costaud.

[Invité]

Code :

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

$pattern = 'chap(i|a) chap(o|a) p(a|i)t(a|i)p(o|a)';

Excellent !

Cela dit.... C'est tout ce que j'ai compris !

[CosmoKnacki]

Knacki, merci. Mais j'ai rien pour tester PHP7 moi... Faut que j'installe wamp server 3 ?
Et bon, ça ne m'empêchera pas de me pencher sur ton code, qui a l'air bien costaud.

Pour Wamp, je ne pourrai pas te dire. Mais il existe probablement une tactique pour faire coexister plusieurs versions de PHP sous Windows. Au pire tu peux essayer avec un testeur en ligne.

[CosmoKnacki]

Code :

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

$pattern = 'chap(i|a) chap(o|a) p(a|i)t(a|i)p(o|a)';

Excellent !

Cela dit.... C'est tout ce que j'ai compris !

C'est vrai que j'ai été un peu chiche en explications.

Attention, ce code est assez brut de décoffrage et à améliorer, il y a des choses inutiles dedans, mais surtout il gagnerait à être refactoriser (en réécrivant les fonctions pour en faire des méthodes de la classe Element par exemple). Mais bon, l'idée est là. Je vais un peu la décrire.

Je me suis d'abord rendu compte que le nombre de chaînes possibles croissait de manière exponentielle avec le nombre d'alternatives, par exemple: chap(i|a) chap(o|a) p(a|i)t(a|i)p(o|a) (2x2x2x2x2 = 2^5 = 32) ou chap(i|a|ou) chap(i|o|a) p(a|i)t(a|i)p(o|a) (3x3x2x2x2 = 3^2 x 2^3 = 72). Donc ça grimpe trés vite. C'est pour ça que j'ai choisi de construire une structure de données exploitable (du moins plus pratique qu'une chaîne de caractère) qui ne duplique pas l'information et qui permet de produire les chaînes à la demande.

Donc pour une pattern a(b|c)d(e|f)g on construit le graphe:

Code schema :

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

1
2
3
4
5
  b   e
 / \ / \
a   d   g
 \ / \ /
  c   f

Pour coder le graphe, j'utilise le principe de la liste chaînée dont chaque maillon (Element) est constitué d'une valeur et d'un pointeur vers le maillon suivant. Mais en PHP, il n'y a pas de pointeur, donc j'utilise à la place la propriété next de la classe Element comme prochain maillon.

Pour gérer les "bifurcations", j'ai ajouté une propriété type:

• Les maillons LITERAL dont la propriété value est une chaîne de caractère
• les maillons GROUP dont la propriété value est un tableau de maillons (qui correspondent au départ de chaque branche d'une alternative).

Prenons le début de la pattern, soit a(b|c)d, on obtiendra:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
Elt( type : LITERAL
     value: 'a'
     next : Elt( type : GROUP
                 value: [ Elt( type : LITERAL
                               value: 'b'
                               next : _ref_ ),
                          Elt( type : LITERAL
                               value: 'c'
                               next : _ref_ ) ]
                 next : Elt( type : LITERAL 
                             value: 'd'
                             next : ... ) ) )

(_ref_ est une référence vers la propriété next de l'Element GROUP "parent".)

C'est ce que buildGraph($tokens) a la charge de construire. Cette fonction renvoie toujours une élément de type GROUP et son rôle est notamment de construire chaque branche (les values) de ce groupe. Lorsque qu'une parenthèse ouvrante est rencontrée, cela signifie que le prochain élément est un groupe, donc la fonction s'appelle elle-même pour le construire. À noter aussi que lors du premier appel à la fonction, celle-ci englobe toute la pattern dans un groupe par défaut, ce qui permet d'avoir un point de départ unique avec une pattern du type a|b|c.

Au lieu d'un tableau de tokens, buildGraph prend en paramètre un générateur, ce qui permet de conserver la position dans la liste de tokens malgré les récursions.

$current désigne le maillon courant, c'est pourquoi on rencontre la ligne $current = $current->next qui change le maillon courant pour le prochain tour de boucle.

[Celira]

Wow ! ça me rappelle vaguement que j'ai eu un module sur la théorie des graphes en études... ya un certain temps... En tous cas, chapo chapeau !
Au passage, je (re)découvre les générateurs avec yield, que je n'avais jamais vu utilisé en conditions réelles.
Manuel PHP - Générateur

Knacki, merci. Mais j'ai rien pour tester PHP7 moi... Faut que j'installe wamp server 3 ?

Pour installer PHP sans installer un WampServer complet, je te conseille UwAmp, qui marche assez bien et peut tourner depuis une clé usb (ou un dossier dans un coin dans ton ordi). A priori, il y a aussi un serveur Mysql embarqué, mais je dois avouer ne l'avoir jamais lancé

[CosmoKnacki]

C'est vrai qu'on attend un peu le jour où le bagage algorithmique peut servir à quelque chose notamment dans le développement web. Youpi, C'est arrivé!

[Dendrite]

Si ça peut te rassurer, c'est comme ça dans tous les métiers : On étudie Shakespeare, James Joyce ou Hawthorne en fac d'anglais... pour se retrouver à rabâcher toute sa vie les verbes irréguliers à des collégiens boudeurs.

[axel584]

Un grand merci pour votre aide. Je me rends compte que je n'avais pas répondu à la question "mais à quoi ça va servir".

Je travaille pour un site web qui donne des cours d'espéranto : https://ikurso.esperanto-france.org
Le cours est relativement simple, des pages qui expliquent les règles de grammaire, qui donne du vocabulaire et des exercices de traduction. On a un service avec des correcteurs bénévoles qui reçoivent les réponses des élèves.
Les exercices sont des phrases assez simple, mais qui peuvent avoir plusieurs réponses différentes acceptables. Et pour éviter de surcharger les correcteurs, mais aussi pour permettre aux élèves de se relire ou de corriger des fautes simples, j'ai mis en place un système qui indique si la réponse donnée est "connue comme étant correcte".
Au début, j'avais enregistré les réponses séparées par des | (et je splittais ma "réponse type" pour comparer la réponse de l'élève avec l'une des réponses types)
Et puis pour certaines réponses, j'ai trouvé plus simple d'utiliser des expressions régulières.

Tout va pour le mieux dans le meilleur des mondes. Mais je constate que certains élèves font des erreurs vraiment bêtes sur un caractère ou deux. Et je trouve dommage de ne pas leurs indiquer plus précisément où se trouve l'erreur.
L'idée était donc d'avoir un algorithme du style :
Calculer la "distance" entre la réponse de l'élève et chacune des bonnes réponses. Si la réponse de l'élève diffère d'un seul caractère, alors on souligne le mot en question.

Mais ce sera peut être plus simple pour moi de transformer mes expressions régulières en liste de réponses acceptées (c'est à dire à la main plutôt que par programme "à la volée")

Axel

[badaze]

Je me disais qu'on peut y arriver par un autre moyen. A contrôler tout de même.

Code php :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
<?php
//--------------------------------------------------------------------
// Effectue le produit cartésien d'un tableau de tableaux
// Retourne un tableau
//--------------------------------------------------------------------
function cartesien($arrayOfArrays)
{
   $result = array();
   $arrLen = count($arrayOfArrays);
   for ($i=0;$i < $arrLen;$i++) 
   {
       foreach ($arrayOfArrays[$i] as $currentValue) 
    {
           if (isset($result[$i-1])) 
     {
               foreach($result[$i-1] as $previousArray) 
      {
                   $result[$i][] = array_merge($previousArray, array($currentValue));
               }
           }
           else 
     {
               $result[$i][] = array($currentValue);
           }    
       }
   }    
   return $result[$arrLen-1];
}
//--------------------------------------------------------------------
 
// EXEMPLE $pattern = 'chap(i|a) chap(o|a) p(a|i)t(a|i)p(o|a)';
foreach(cartesien(array(
     cartesien(array(array('chap'),array('i','a'))),
     cartesien(array(array('chap'),array('o','a'))),
     cartesien(array(array('p'),array('a','i'))),
     cartesien(array(array('t'),array('a','i'))),
     cartesien(array(array('p'),array('o','a')))
     )) as $sousTableau)
{
 foreach($sousTableau as $value)
 {
  echo implode(' ',$value)."&nbsp;";
 }
  echo "<br/>";
}

Donne 32 possibilités

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 
chap i chap o p a t a p o 
chap a chap o p a t a p o 
chap i chap a p a t a p o 
chap a chap a p a t a p o 
chap i chap o p i t a p o 
chap a chap o p i t a p o 
chap i chap a p i t a p o 
chap a chap a p i t a p o 
chap i chap o p a t i p o 
chap a chap o p a t i p o 
chap i chap a p a t i p o 
chap a chap a p a t i p o 
chap i chap o p i t i p o 
chap a chap o p i t i p o 
chap i chap a p i t i p o 
chap a chap a p i t i p o 
chap i chap o p a t a p a 
chap a chap o p a t a p a 
chap i chap a p a t a p a 
chap a chap a p a t a p a 
chap i chap o p i t a p a 
chap a chap o p i t a p a 
chap i chap a p i t a p a 
chap a chap a p i t a p a 
chap i chap o p a t i p a 
chap a chap o p a t i p a 
chap i chap a p a t i p a 
chap a chap a p a t i p a 
chap i chap o p i t i p a 
chap a chap o p i t i p a 
chap i chap a p i t i p a 
chap a chap a p i t i p a

[badaze]

En changeant l'appel

Code php :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
// EXEMPLE $pattern = 'chap(i|a) chap(o|a) p(a|i)t(a|i)p(o|a)';
foreach(cartesien(array(
     cartesien(array(array('chap'),array('i','a'))),
     cartesien(array(array(' '),array(' '))),
     cartesien(array(array('chap'),array('o','a'))),
     cartesien(array(array(' '),array(' '))),
     cartesien(array(array('p'),array('a','i'))),
     cartesien(array(array('t'),array('a','i'))),
     cartesien(array(array('p'),array('o','a')))
     )) as $sousTableau)
{
 foreach($sousTableau as $value)
 {
  echo implode('',$value);
 }
  echo "<br/>";
}

On obtient.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
chapi  chapo  patapo
chapa  chapo  patapo
chapi  chapa  patapo
chapa  chapa  patapo
chapi  chapo  pitapo
chapa  chapo  pitapo
chapi  chapa  pitapo
chapa  chapa  pitapo
chapi  chapo  patipo
chapa  chapo  patipo
chapi  chapa  patipo
chapa  chapa  patipo
chapi  chapo  pitipo
chapa  chapo  pitipo
chapi  chapa  pitipo
chapa  chapa  pitipo
chapi  chapo  patapa
chapa  chapo  patapa
chapi  chapa  patapa
chapa  chapa  patapa
chapi  chapo  pitapa
chapa  chapo  pitapa
chapi  chapa  pitapa
chapa  chapa  pitapa
chapi  chapo  patipa
chapa  chapo  patipa
chapi  chapa  patipa
chapa  chapa  patipa
chapi  chapo  pitipa
chapa  chapo  pitipa
chapi  chapa  pitipa
chapa  chapa  pitipa