Précisions sur l'énoncé

1 Précisions sur l'énoncé

L'énoncé fait allusion à trois niveaux de motifs. Ils sont précisés ici. Le travail « normal » (genre PIa) est le premier niveau. Enuite, il y a deux niveaux genre PIb et PIc (!).

Le deuxième niveau est une extension naturelle du premier, c'est à dire qu'un programme conçu pour reconnaître les chaînes s'étend sans trop de peine en ajoutant un peu de code.

En revanche le PIc demande plus de conception personnelle, car la solution n'est pas donnée dans les articles. C'est plus dur, mais tellement plus formateur.

Dans tous les cas, on supposera que les motifs sont suffisamment petits pour que les ensembles d'états puissent être représentés par des entiers de type long.

Voici donc les trois niveaux de réponse possible, selon la complexité des motifs reconnus.

D'abord les chaînes elles mêmes, le filtrage se réduit donc à l'égalité. On notera qu'une chaîne peut être vide.
Ensuite les motifs sont des suites de motifs élémentaires, un motif élémentaire e est un caractère, l'attrape-tout des caractères « . », l'attrape-tout des mots « # », ou un motif élémentaire optionnel « e? ». Le sens de ces motifs est très classique : ainsi le motif cl?ou filtre les mots clou et cou, le motif .....? filtre les chaînes de quatre ou cinq caractères, tandis que le motif cou#cou filtre les chaînes de la forme coumcou où m est une chaîne de caractère quelconque. (Je m'excuse pour l'incohérence avec l'énoncé au sujet des motifs attrape-tout.)

On note que les caractères « . », « # » et « ? » ont un sens spécial, pour donner les motifs qui filtrent exactement ces caractères on a recourt à un mécanisme de citation simple : faire précéder le caractère par un backslash. Ainsi le motif qui filtre le point d'interrogation est écrit « \? », et celui qui filtre le backslash est écrit « \\ ».
Ensuite les expressions régulières. Afin de faciliter le test de votre programme, je vous demande de vous conformer à la syntaxe suivante : Les expression régulières p sont engendrées par la grammaire suivante :
p = | c | . | p* | p? | pp | p|p | (p)
Où «» (oui rien) est le motif vide, c est un caractère quelconque (éventuellement cité), . est le caractère attrape tout, p* est la répétition, p? est l'option, pp est la concaténation de deux motifs, p|p est l'alternative de deux motifs et (p) est un simple parenthésage. Comme cette grammaire est ambigüe, on convient de donner des priorités aux divers opérateurs, dans l'ordre décroissant, d'abord repétition et option (* et ? postfixes), puis concaténation (juxtaposition) et enfin alternative (| infixe). C'est à dire par exemple que ab*|cd se comprend comme ((a)(b)*)|(cd). Il faudrait pour faire bonne mesure définir également l'associativité des opérations infixes, mais cela n'a aucune importance, car comme on va le voir (a|b)|c et a|(b|c) on la même signification, on peut donc interpréter le motif non parenthésé a|b|c comme l'un où l'autre des motifs parenthésés précédents.

En effet, donnons nous un ensemble de caractères C soit alors M l'ensemble des mots que l'on peut former avec les caractères de C (suites finies de caractères de C, qui comprend la suite (le mot) vide notée є). On peut associer à chaque motif p l'ensemble F(p) des mots qu'il filtre :
- Le motif vide filtre le mot vide.
- F(c) = {c}.
- F(.) = C.
- F(p*) = {m₁m₂… m_k ∣ k ≥ 0, m_i ∈ F(p) } (ensemble des concaténations des mots de F(p)).
- F(p?) = {є} ∪ F(p)
- F(p₁p₂) = {m₁m₂ ∣ m₁ ∈ F(p₁) et m₂ ∈ F(p₂)}
- F(p₁|p₂) = F(p₁) ∪ F(p₂).
On notera que le # du niveau précédent est équivalent à .*.
On augmente traditionellement les expressions régulières par p+ (répétion au moins une fois) qui est équivalent à p(p)*.