1. Analyse lexicale
2. Analyse syntaxique
3. Grammaires formelles
4. Graphes
5. Parcours en profondeur ou largeur d'abord
6. Connexité
7. Exercices

let rec cur_char = ref ' ' 
and next_char() = cur_char := input_char(stdin);;
let is_letter c = ('A' <= c && c <= 'Z') || ('a' <= c && c <= 'z');;
let is_digit c = ('0' <= c && c <= '9') ;;
let is_blank c = c = ' ' || c = '\t' || c = '\r' || c = '\n' ;;
let skip_blanks () = while is_blank (!cur_char) do next_char() done;;

let next_ident() = 
   let buf = String.make 100 ' ' and i = ref 0 in 
   while is_letter (!cur_char) || is_digit (!cur_char) do
       buf.[!i] <- !cur_char; incr i;
       next_char()
   done;
   sub_string buf 0 !i;;

let next_number() = 
   let res = ref 0 in
   while is_digit (!cur_char) do
       res := !res*10 + Char.int (!cur_char) - Char.int ('0');
       next_char()
   done;
   !res;;

let erreur s = failwith ("Erreur: " ^ s) ;;

type lexem = 
      L_Ident of string  (* identificateur *)
    | L_Nb of int        (* nombre *)
    | L_Plus             (* + *)        | L_Moins            (* - *)
    | L_Mult             (* * *)        | L_Div              (* / *)
    | L_Opar             (* ( *)        | L_Fpar             (* ) *)
    | L_Assign1          (* := *)       | L_Assign2          (* <- *)
    | L_EOF              (* end of file *) ;;

let cur_lexem = ref L_EOF   and  next_lexem () = 
   cur_lexem := try
     skip_blanks ();
     match !cur_char with
      'a'..'z' | 'A'..'Z' -> L_Ident(next_ident ())
     |'0'..'9' -> L_Nb(next_number ())
     |'+' -> begin next_char(); L_Plus end
     |'-' -> begin next_char(); L_Moins end
     |'*' -> begin next_char(); L_Mult end
     |'/' -> begin next_char(); L_Div end
     |':' -> begin next_char(); 
             if !cur_char <> '=' then L_Div
             else begin next_char(); L_Assign1 end
             end
     |'(' -> begin next_char(); L_Opar end
     |')'  -> begin next_char(); L_Fpar end
     | _ -> erreur "forbidden char"
   with
   End_of_file -> L_EOF;;

, on veut générer l'arbre de syntaxe abstraite suivant (cf PC8 pour le type des termes).

let rec terme () =
  let a = produit () in
  match !cur_lexem with
    L_Plus -> begin next_lexem(); Add (a, terme ()) end
  | L_Moins -> begin next_lexem(); Sub (a, terme ()) end
  | _  -> a

and produit () =
  let a = facteur () in
  match !cur_lexem with
    L_Mult -> begin next_lexem(); Mul (a, produit ()) end
  | L_Div -> begin next_lexem(); Div (a, produit ()) end
  | _  -> a

and facteur () =
  match !cur_lexem with
    L_Opar -> begin next_lexem(); 
        let a = terme () in
           if !cur_lexem = L_Fpar then begin next_lexem(); a end
           else erreur "missing right parenthesis" end
  | L_Ident(s) ->  begin next_lexem(); Var (s) end
  | L_Nb (x) ->  begin next_lexem(); Const (x) end
  | _  ->  erreur "forbidden character";;

• Matrice de connexion M, où m_i,j=1 ssi (n_i,n_j) est un arc du graphe. Matrice symétrique pour un graphe non orienté.
  
  

  let nMax = 100;;
  let graphe = Array.make_matrix nMax nMax false;;
  let mk_arc i j = graphe.(i).(j) <- true;;
  

• Tableau de listes de successeurs:
  
  

  let graphe = Array.make nMax [];;
  let mk_arc i j = graphe.(i) <- j :: graphe.(i);;
  

• On peut stocker la liste précédente dans un tableau, si les noeuds ont tous à peu près le même nombre de successeurs, et on met une sentinelle W après le dernier successeur. Pour remplir l'entrée i, on fera:
  
  

  let Omega = -1 and n = ref 0;;
  let graphe = Array.make nMax vMax Omega;;
  let mk_arc i j = begin graphe.(i).(!n) <- j; incr n end;;
  

let num = Array.make (Array.length graphe) (-1) and id = ref (-1);;

let rec dfs k = 
  incr id;
  num.(k) <- !id;
  List.iter (function x -> if num.(x) = -1 then dfs (x))
    graphe.(k);;

let visit () =
  for i=0 to Array.length graphe - 1 do
    if num.(i) = -1 then dfs i;
  done;;

1. d'un noeud de l'arbre à un de ses fils dans l'arbre
   
   
2. d'un noeud de l'arbre à un de ses ancètres dans l'arbre
   
   
3. d'un noeud de l'arbre à un de ses descendants non direct dans l'arbre
   
   
4. d'un noeud à un de ses cousins dans l'arbre

let num = Array.make (Array.length graphe) (-1) and id = ref (-1);;

let bfs q = 
  while not (FIFO.vide(q)) do
    let k = FIFO.supprimer(q) in
    incr id;
    num.(k) <- !id;
    List.iter (function x -> if num.(x) = -1 then 
      begin FIFO.ajouter x q; num.(x) <- -2 end)
      graphe.(k)
  done;;

let visit() =
  let q = FIFO.make() in
  for i=0 to Array.length graphe - 1 do
    if num.(i) = -1 then 
       begin FIFO.ajouter i q; num.(i) <- -2; bfs q end;
  done;;

• Sortie de labyrinthe (dans un graphe non-orienté)
  
  
• Test de non-cyclicité dans un graphe orienté
  
  
• Tri topologique dans un graphe orienté (Makefiles)
  
  
• Planarité (Tarjan)
  
  
• Connexité dans un graphe non orienté
  
  
• Plus court chemin

let rec chemin d s =
  num.(d) <- true; 
  let p = ref [] in
  List.iter (function x -> 
      if not num.(x) && !p = [] then 
        if x = s then p := [s] else p := chemin x s)
     graphe.(d);
  if !p = [] then [] else d :: !p;;

let min = ref nMax;;

let rec visit k = 
  incr id;
  num.(k) <- !id; min := !id;
  List.iter (function x -> 
      if num.(x) = -1 then begin
        let m = visit x in
        if m < !min then min := m;
        if m >= num.(k) then printf "%d " k
      end else
      if num.(x) < !min then min := num.(x))
     graphe.(k);
  !min;;

• Faire une calculette avec entrée textuelle
  
  
• Calculer les composantes connexes dans un graphe non orienté

This document was translated from L^AT_EX by H^EV^EA.