Bonjour. Je viens vers vous car j’aborde un nouveau thème et je suis vraiment perdu sur ce qu’il faut faire La première partie se passe bien
Mais pour la deuxième partie je ne comprend pas ce qui est demandé :
Est-ce que tu peux expliquer ce que tu ne comprends pas dans la deuxième partie? Ou au moins ce que tu comprends.
Alors j’ai réussi à faire toute la première partie sauf la fonction split.
Ensuite pour la deuxième, je comprend que l’on forme un type particulier formé d’expressions régulières de n’importe quel type 'a re. Ce type peut être un symbole 'a, une Union d’expressions régulières (’a re,’a re)
Et en reprenant l’explication, j’ai réussi à avancer un peu 
Je ne dis pas que le code fait ce qui est demandé, à savoir tester si le mot est reconnu par l’expression régulière, mais au moins ça compile
type 'a re =
| Symbole of 'a
| Union of 'a re * 'a re
| Produit of 'a re * 'a re
| Repetition of 'a re
let rec accept l expReguliere = match expReguliere with
|Symbole x -> exists (fun y -> y=x) l
|Union (x,y) -> (accept l x) && (accept l y)
|Produit (x,y) -> (accept l x) && (accept l y)
|Repetition x -> accept l x
Ce sont des notions difficiles à assimiler..
Effectivement le code que tu as écrit ne fait pas ce qui est demandé. Je ne sais pas si tu as bien compris la définition de "l’ensemble des mots reconnus par une expression régulière" donné dans le sujet, mais des petits exemples pourraient aider:
accept ['a'] (Symbole 'a')not (accept ['b'; 'a'] (Symbole 'a')) (ce test ne passe pas sur ton code)accept ['a'] (Union (Symbole 'a', Symbole 'b')) (ce test ne passe pas)accept ['a'; 'b'] (Produit (Symbole 'a', Symbole 'b')) (ce test ne passe pas)Je te conseille d’essayer de comprendre comment interpréter correctemenet Symbole, Union et Produit pour commencer, et réfléchir seulement ensuite à Repetition.
split peut s’implémenter assez facilement récursivement, surtout avec les fonctions créés plus tôt dans la partie 1. Hint: essaye de voire comment tu peux transformer le retour de split [2; 3] en le retour de split [1; 2; 3].
Une expression régulière permet de définir un schéma et d’ensuite vérifier si une entrée suis ce schéma. C’est typiquement utilisé sur les chaînes de caractères, par exemple pour vérifier si une chaîne de caractères ressemble à une adresse email1.
Une expression régulière se défini par composition d’expression régulières plus simples, jusqu’à ce qu’on n’utilise que les briques de base. Ici, la brique de base est Symbole 'a qui accepte un unique symbole. Union, Produit et Repetition sont utilisés pour composer des expressions régulière en une expression régulière plus complexe.
Par exemple, on peut vouloir réaliser la vérification suivante: la chaîne de caractère en entrée doit commencer par la lettre 'a’, suivi de soit 'b’, soit 'c' et enfin doit avoir plusieurs 'd’. Dans cet exemple "acddd" est valide, "abd" l’est aussi, mais "abc" et "bdd" ne le sont pas.
Dans cet exemple, le "suivi de" correspond à l’opération de Produit et le "soit x, soit y" correspond à l’opération d'Union. L’expression que j’ai décrite peut donc s’écrire Produit(Symbole 'a', Produit(Union (Symbole 'b', Symbole 'c'), Repetition (Symbole 'd'))).
Si j’ai une recommandation à avoir pour l’implémentation, c’est que tu écrives tout plein de tests les plus simple possible pour savoir ce qui fonctionne et ce qui ne fonctionne pas. Par exemple accept ['a'] (Symbole 'a') doit retourner True alors que accept ['a';'a'] (Symbole 'a') doit retourner False.
L’implémentation de chaque cas va en difficulté croissante: Symbole est plus simple à implémenter que Union, qui est plus simple que Produit, qui est plus simple que Repetition. Donc il vaut mieux commencer par des tests d’expression régulière utilisant Symbole uniquement, puis y ajouter Union, etc.
Merci. J’avance
let rec accept mot expReguliere = match (mot,expReguliere) with
|[m],Symbole x -> x = m
|mot,Union (x,y) -> (accept mot x) || (accept mot y)
|m::mot,Produit (x,y) -> (accept [m] x) && (accept mot y)
|m::mot,Repetition x -> (accept [m] x) && (accept mot x)
|_-> false
C'est faux pour répétition.
Arden nous donne :
L1 = a*λ
= a.L1 + λ
(*
accept ['b';'a'] (Produit(Symbole 'b', Symbole 'a'))
not accept ['a';'b'] (Produit(Symbole 'b', Symbole 'a'))
accept ['a'] (Union (Symbole 'b', Symbole 'a'))
accept ['a';'b';'b'] (Produit(Symbole 'a', Repetition (Symbole 'b')))
accept ['a';'b';'d'] (Produit(Symbole 'a', Produit(Union (Symbole 'b', Symbole 'c'), Repetition (Symbole 'd'))))
*)
Deux remarques:
Je stresse quand je vois [m] dans un pattern, et que les autres cas ne sont pas gérés.
Même si ça marchotte aujourd’hui grâce à ton | _ -> false, c’est un nid à bugs pour la suite quand ton code changera. Je te conseille vivement d’écrire le code avec seulement un filtrage sur l’expression régulière, et éventuellement des sous-filtrages sur le mot dans les cas où c’est utile.
Le cas du produit est faux car il suppose que x ne mange qu’un seul caractère, mais x peut être une expression qui matche plusieurs symboles. Considérer Produit(Produit(Symbole 'a', Symbole 'b'), Symbole 'c') par exemple.
Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte