(*** TP : Algorithme de Berry-Sethi ***) (* type pour les regexp et les regexp linéarisées *) type regexp = Vide | Epsilon | C of char * int | Concat of regexp * regexp | Union of regexp * regexp | Etoile of regexp (* C of char*int permettra de linéariser la rexgep*) (* type pour représenter l'automate final. *) (* NB : les transitions sont représentées par une liste de triplets *) type autoND = { initial:int; final:int list; transitions:(int * char * int) list } (* fonctions d'affichage *) let rec afficheRegexp r = match r with | Vide -> print_string("vide") | Epsilon -> print_string("eps") | Concat (r1,r2) -> afficheRegexp r1; afficheRegexp r2 | Etoile (r) -> print_string("("); afficheRegexp r; print_string(")*") | Union (r1,r2) -> print_string("("); afficheRegexp r1; print_string("|"); afficheRegexp r2; print_string(")") | C (c,i) -> Printf.printf "%c%d" c i let afficheAutomate aut = Printf.printf "initial:%d\n" aut.initial; print_string "final:["; List.iter (fun q -> Printf.printf "%d," q) aut.final; print_string "]\n"; print_string "transitions:["; List.iter (fun (q1,c,q2) -> Printf.printf "%d-%c-%d," q1 c q2) aut.transitions; print_string "]\n";; (* exemples *) let r0 = Concat ( Concat (C('a', 0), Etoile (Concat (C('b',0), C('a',0)))), Etoile (C('c', 0)));; let r1 = Concat ( Etoile (Concat (C('a',0), C('b',0))), Concat (Concat (C('c',0), C('a',0)), Etoile (Union (C('c', 0), Concat (C('b',0), C('a', 0))))));; (*linéarise une regexp *) let linearise r = let indice = ref 0 in let rec auxlin r = (* décore l'arborescence en numétorant les caractères *) failwith "A faire" in auxlin r;; afficheRegexp r0;; print_newline ();; afficheRegexp (linearise r0);; print_newline ();; (* on représente les ensembles comme des listes sans doublons *) (* quelques fonctions utilitaires *) let rec ajouteSansDoublons l e = failwith "A faire" let rec unionSansDoublons l1 l2 = failwith "A faire" let rec produitListes l1 l2 = (* construit la liste des couples *) failwith "A faire" let rec contientVide r = (* vérifie si une regexp contient le mot vide *) failwith "A faire" (* renvoie P(L) -> (char * int) list *) let rec p r = match r with | _ -> failwith "A faire" (* renvoie S(L) -> (char * int) list *) let rec s r = match r with | _ -> failwith "A faire" (* renvoie F(L) -> ((char * int) * (char * int)) list *) let rec f r = match r with | _ -> failwith "A faire" let affichePSF p s f = print_string "P:["; List.iter (fun (c,i) -> Printf.printf "%c%d," c i) p; print_string "]\n"; print_string "S:["; List.iter (fun (c,i) -> Printf.printf "%c%d," c i) s; print_string "]\n"; print_string "F:["; List.iter (fun ((c1,i1),(c2,i2)) -> Printf.printf "%c%d%c%d," c1 i1 c2 i2) f; print_string "]\n";