<br />
<b>Deprecated</b>:  The each() function is deprecated. This message will be suppressed on further calls in <b>/home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php</b> on line <b>456</b><br />
(* TD 2 : Compilation d'automates *)

(* 2.1.1 Type d'un automate *)
type 'a automate = { n:int; i:int list; a:'a list; 
	t:((int*'a)*(int list)) list; f:int list };;

(* 2.1.2 Exemple d'automate reconnaissant (a+b)*ab *)
let a1 = { n=3; i=[1]; a=['a';'b']; 
	t=[((1,'a'),[1;2]);((1,'b'),[1]);((2,'b'),[3])]; f=[3] };;

(* 2.1.3 Conversion d'un fichier en automate *)
let lire_nombre_etats c = int_of_string (input_line c);;

let rec lire_alphabet c = let s = (input_line c).[0] in
	if s='.' then [] else s::(lire_alphabet c);;

let rec lire_etats c = let s = input_line c in
        if s.[0]='.' then [] else (int_of_string s)::(lire_etats c);;

let rec add_in_transition_list (a,b) = function [] -> [(a,[b])]
            | ((c,dl)::l) when c=a -> (c,b::dl)::l
            | (cd::l) -> cd::(add_in_transition_list (a,b) l);;
let rec lire_transitions c = let s = input_line c in
        if s.[0]='.' then [] else let b1 = (String.index s ' ')+1 in
	let i = int_of_string (String.sub s 0 (b1-1))
	and j = int_of_string (String.sub s (b1+2) (String.length s -b1-2) ) in
		add_in_transition_list ((i,s.[b1]),j) (lire_transitions c);;

let lire_automate fichier = let canal = open_in fichier in
	let n=lire_nombre_etats canal and a=lire_alphabet canal and
		i=lire_etats canal and t=lire_transitions canal and
		f=lire_etats canal in close_in canal; {n=n;a=a;i=i;t=t;f=f};;

let a2 = lire_automate "aut_deterministe";; (* l'automate de la section 1.3 *)

(* 2.1.4 Ecriture d'un automate en fichier *)
let rec ecrire_alphabet c = function [] -> output_string c ".\n"
	| (a::l) -> output_char c a; output_char c '\n'; ecrire_alphabet c l;;

let rec ecrire_etats c = function [] -> output_string c ".\n"
        | (a::l) -> output_string c ((string_of_int a)^"\n");
		ecrire_etats c l;;

let rec ecrire_transitions c = function [] -> output_string c ".\n"
     | (((i,a),tl)::l) -> List.iter (fun j -> output_string c ((string_of_int i)
		^" "^(String.make 1 a)^" "^(string_of_int j)^"\n") ) tl;
		ecrire_transitions c l;;

let ecrire_automate aut fichier = let canal = open_out fichier in
	output_string canal ((string_of_int aut.n)^"\n");
	ecrire_alphabet canal aut.a;
	ecrire_etats canal aut.i;
	ecrire_transitions canal aut.t;
	ecrire_etats canal aut.f;
	close_out canal;;

ecrire_automate a1 "automate1";;

(* 2.1.5 Algo impératif de reconnaissance pour automate déterministe *)
let fin_de_chaine = '\004';; (* ctrl+D *)
let carSuiv alphabet = let c = input_char stdin in
	if List.mem c alphabet then c else fin_de_chaine;;
let purger_reste_ligne () = ignore (input_line stdin);;

let reconnaitre aut = 
  let q = ref (List.hd aut.i) 
  and c = ref (carSuiv aut.a)
  and fin = ref false in 
  while (!c<>fin_de_chaine && not !fin) do
    try q:=List.hd (List.assoc (!q,!c) aut.t); 
        c:=carSuiv aut.a with 
    Not_found -> fin:=true 
  done; 
  purger_reste_ligne(); 
  (not !fin) && (List.mem !q aut.f);;

print_string "Entrez une ligne à reconnaitre (impératif) avec a2\n";;
reconnaitre a2;;

(* 2.1.6 Algo récursif de reconnaissance pour automate déterministe *)
let rec cheminer aut = let c = carSuiv aut.a in
	if c = fin_de_chaine then List.hd aut.i else try 
		cheminer {aut with i=List.assoc (List.hd(aut.i), c) aut.t}
	with Not_found -> 0;;
let reconnaitre_rec aut = let q = cheminer aut in purger_reste_ligne();
	List.mem q aut.f;;

print_string "Entrez une ligne à reconnaitre (récursif) avec a2\n";;
reconnaitre_rec a2;;

(* 2.1.8 Compilateur d'automate en programme CAML *)

let rec compil_par_etat aut n = if n>0 then (compil_par_etat aut (n-1))^
	"\t| "^(string_of_int n)^" -> ( match carSuiv !alphabet with \n"^
	(String.concat "" (List.map (function ((q,c),l) when q=n -> 
		"\t\t| '"^(String.make 1 c)^"' -> automate "^
		(string_of_int (List.hd l))^"\n" | _ -> "" ) aut.t))^
	(if List.mem n aut.f then "\t\t| c -> c=fin_de_chaine )\n" 
		else "\t\t| _ -> false )\n") else "";;
let alphabet = ref [];;
let compilateur aut = alphabet := aut.a; print_string 
	("let autom () = let rec automate = function \n"^
          (compil_par_etat aut aut.n)^
	  "\t| _ -> raise (Failure \"Erreur dans l'automate\") in \n"^
          "let r = automate "^(string_of_int (List.hd aut.i))^
	  " in \n purger_reste_ligne (); r;;\n");;

compilateur a2;;