(*** 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;;