(*** 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)));; afficheRegexp r0;;