Plan

1. exceptions
2. fichiers et canaux
3. analyse lexicale (rappel)
4. analyse syntaxique (rappel)
5. piles
6. graphes
7. depth first search
8. connexité dans un graphe non orienté
9. exercices

Exceptions

exception End_of_file;;
exception Empty;;
exception Division_by_zero;;
exception Sys_error of string;;
exception Out_of_memory;;
exception Invalid_argument of string;;
exception Failure of string;;
exception Not_found;;
exception Exit;;

try e with 
  exception_1 -> e_1
| exception_2 -> e_2
...
| exception_n -> e_n

Fichiers et canaux

open_in : string -> in_channel        (* fichier -> canal *)
open_out : string -> out_channel

stdin : in_channel                    (* canaux standards *)
stdout : out_channel
stderr : out_channel

input_char : in_channel -> char       (* input *)
input_line : in_channel -> string
input : in_channel -> string -> int -> int -> int

output_char : out_channel -> char -> unit   (* output *)
output_string : out_channel -> string -> unit
output : out_channel -> string -> int -> int -> unit
flush : out_channel -> unit

seek_in : in_channel -> int -> unit   (* positionnement *)
pos_in : in_channel -> int
in_channel_length : in_channel -> int
seek_out : out_channel -> int -> unit
...
close_in : in_channel -> unit         (* fermeture *)
close_out : out_channel -> unit

printf: ('a, out_channel, unit) format -> 'a
fprintf: out_channel -> ('a, out_channel, unit) format -> 'a

Analyse lexicale

Pour isoler les instructions des commentaires, pour distinguer les identificateurs, les chaînes de caractères, etc, on fait en général une 1ère passe sur un flot de caractères tapés sur l'entrée standard: c'est l'analyse lexicale qui consiste à supprimer les espaces, tabulations, retour à la ligne.

let cur_char = ref ` `
and advance() = 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
        advance()
    done;;

let next_ident() = 
   let buf = make_string 100 ` ` 
   and i = ref 0 in begin
   while is_letter (!cur_char)||  is_digit (!cur_char) do
       buf.[!i] <- !cur_char;
       incr i;
       advance()
   done;
   sub_string buf 0 !i
   end;;

let next_number() = 
   let res = ref 0 in begin
   while is_digit (!cur_char) do
       res := !res*10 + int_of_char (!cur_char) 
              - int_of_char (`0`);
       advance()
   done;
   !res
   end;;

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

Analyse lexicale -- programme

On ne garde plus qu'une suite de lexems, encore appelés tokens. On écrit une fonction next_lexem qui saute les espaces et retourne le prochain lexem dans la variable globale cur_item.

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 advance(); L_Plus end
     |`-` -> begin advance(); L_Moins end
     |`*` -> begin advance(); L_Mult end
     |`/` -> begin advance(); L_Div end
     |`:` -> begin advance(); 
             if !cur_char <> `=` then L_Div
             else begin advance(); L_Assign1 end
             end
     |`(` -> begin advance(); L_Opar end
     |`)` -> begin advance(); L_Fpar end
     | _ -> erreur "forbidden char"
   with
   End_of_file -> L_EOF;;

Analyse syntaxique des expressions arithmétiques

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

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

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

Grammaires et langages formels

Une grammaire (context-free) G=(Sigma, V_N, S, P) est définie par un alphabet Sigma, un ensemble de variables (non-terminales) V_N, un axiome S dans V_N et un ensemble fini de règles de production P de la forme E -> alpha où E dans V_N et alpha est un mot sur Sigma et V_N.

Une dérivation alpha ->^* beta est une chaîne alpha = alpha_0 -> alpha_1 -> ... alpha_n = beta où n >= 0 et pour tout i dans [0, n-1], on a alpha_i = uEv et alpha_{i+1} = u gamma v pour un E -> gamma dans P et deux mots u, v mots sur Sigma et V_N.

Le langage généré par G est l'ensemble L_G={w | w dans Sigma^*, S ->^* w }.

Exemples:

Sigma = {(, )}, V_N = {S}, 

S -> SS          S -> (S)          S -> () 

Sigma={ x, +, -, *, /, (, ) }, V_N={E, T, F},

E -> T+E         E -> T-E          E -> T 
T -> F*T         T -> F/T          T -> F 
F -> x           F -> (E)

Belle impression (pretty print)

On peut imprimer en inversant l'analyseur syntaxique

let rec print_expression (e) =
  match e with
   Add (e1, e2) -> begin
        print_terme (e1); printf " + ";
        print_expression (e2) end
   Sub (e1, e2) -> begin 
        print_terme (e1); printf " - ";
        print_expression (e2) end
   _ -> print_terme e

and print_terme (e) =
   Mult (e1, e2) -> begin 
        print_terme (e1); printf " * ";
        print_expression (e2) end
   Div (e1, e2)  -> begin
        print_terme (e1); printf " / ";
        print_expression (e2) end
   _ -> print_facteur e

and print_facteur (e) =
  match e with
    Var (s) -> printf "%s" s
  | Const (x) -> printf "%d" x
  | _ -> begin 
        printf "("; print_expression (e); 
        printf ")" end ;;

Piles

type 'a pushdown_stack;;
value make_pushdown_stack: unit -> 'a pushdown_stack;;
value push : 'a -> 'a pushdown_stack -> unit;;
value pop : 'a pushdown_stack -> 'a;;

type 'a pushdown_stack == 'a list ref;;

let make_pushdown_stack() = ref [ ];;

let push x p = p := x :: !p;;

let pop p = match !p with
   [ ] -> failwith "pile vide"
 | x :: p1 -> begin p := p1; x end;;

Graphes

Un graphe G=(V,E) a un ensemble de sommets V et d'arcs E sous-ensemble de V x V. Un arc v=(n_1,n_2) a pour origine org(v) = n_1 et pour extrémité ext(v) = n_2. Un exemple est le plan des rues de Paris ou le plan du métro.

G=(N,V) est un graphe non orienté ssi (n_1,n_2) dans V implique (n_2,n_1) dans V. Par exemple, les couloirs de l'X.

Un chemin est une suite d'arcs v_1, v_2, ... v_n, telle que n >= 0, org(v_{i+1}) = ext(v_i) pour 1 <= i < n. Un cycle est un chemin où ext(v_n) = org(v_1). Un arbre est un graphe orienté sans cycle, mais il existe des graphes orienté sans cycles plus généraux (dag pour directed acyclic graph).

On peut représenter un arbre par sa matrice de connexion M, où m_{i,j}=1 ssi (n_i,n_j) est un arc du graphe. La matrice de connexion d'un graphe non orienté est donc symétrique.

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

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

Profondeur d'abord, Depth-First Search

R. Tarjan (1972) a montré que c'était une méthode très utile sur les graphes. Son temps est en O(V+E), ie linéaire dans le nombre de noeuds et d'arcs.

let val = make_vect (vect_length graphe) (-1);;

let id = ref (-1);;

let rec dfs k =  begin
    incr id;
    val.(k) <- !id;
    let t = ref graphe.(k) in
    while !t <> [ ] do
        if val.(hd(!t)) = -1 then
            dfs (hd(!t));
        t := tl(!t);
    done
    end;;

let rec dfs k = begin
    incr id;
    val.(k) <- !id;
    do_list 
      (function  x -> if val.(x) = -1 then
            dfs (x))
      graphe.(k)
    end;;

let dfs_all() = begin
  fill_vect val 0 (vect_length graphe) (-1);
  do_vect 
    (function x -> if val.(x) = -1 then
         dfs (x))
    val
  end;;

Arbres de recouvrement

1. d'un noeud de l'arbre à un de ses fils dans l'arbre
2. d'un noeud de l'arbre à un des 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

Largeur d'abord, Breadth-First Search

let q = make_Q nMax (-1);;

let bfs k = begin
    enQ k q;
    while not (is_emptyQ q) do
        let k = deQ (q) in begin
        incr id;
        val.(k) <- !id;
        do_list 
          (function  x -> if val.(x) = -1 then
                enQ x q;
                val.(x) <-  -1)
          graphe.(k)
        end
    done
    end;;

Qques problèmes standards

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

Bi-connectivité

Dans un graphe non orienté, existe-t-il 2 chemins entre toute paire de noeuds? Un point d'articulation est un point qui sépare le graphe en parties non connexes si on l'enlève. Un graphe sans point d'articulation est un graphe bi-connexe. A partir de la procédure suivante, on teste facilement si un point est un point d'articulation et donc si le graphe est biconnexe.

let rec Visit k = begin
    incr id; val.(k) <- !id; 
    let min = ref !id in begin
      do_list
        (function x ->
         if val.(x) = -1 then begin
             let m = Visit (x) in begin
             if m < !min then
                 min := m;
             if m >= val.(k) then
                 printf "%d " k
             end
         end else
         if val.(x) < !min then
             min := val.(x))
        graphe.(k);
      !min
      end
    end;;

Composantes fortement connexes

Dans un graphe non orienté, on teste facilement la connexité. Mais dans un graphe orienté? La procédure ci-dessous trouve les composantes fortement connexes.

let rec Visit k = begin
    incr id; val.(k) <- !id; 
    push k p;
    let min = ref !id in begin
      do_list
        (function x ->
          let m = if val.(x) = -1 then 
                Visit (x) 
            else 
                val.(x) 
            in if m < !min then
                min := m)
         graphe.(k);
      if !min = val.(k) then 
        (try while true do
            printf "%d " (top(p));
            val.(top(p)) <- nMax;
            pop(p);
            if top(p) = k then raise Exit
            done
        with Exit -> printf "\n");
      !min
      end
    end;;

Points d'attache

Dans le ch5 du poly, on décrit la notion de point d'attache dans un graphe:

Exercice: le langage Quilt (cf la PC 8)

Pour faire de belles broderies

exp ::= C
  |     variable
  |     (exp)
  |     turn (exp)
  |     pile (exp1, exp2)
  |     sew(exp, exp)
  |     fonction (exp, exp, ... exp)
  | let déclarations in exp

déclarations ::=
        val ident = exp
  |     fun ident (arg1, arg2, ... argn) = exp

variable ::= ident
fonction ::= ident
arg ::= ident

où ident est un identificateur quelconque.

turn (exp) est la rotation de 90 degrés
sew(exp1,exp2) est la concaténation horizontale
pile (exp1, exp2, ...) est la concaténation verticale
let val ou let fun définissent des variables ou des fonctions.

Comment exécuter une expression de Quilt (R. Sethi)

Exercices en TD

reconnaître et interpréter Quilt

faire une interface d'analyse syntaxique au programme de la dernière fois.

faire une calculette avec les programmes de grands nombres ( bc de Unix).