TD 3 - Construction d'automates déterministes à partir d'expressions régulières

Dans ce TD, on étudie une méthode de construction directe d'un automate fini déterministe à partir d'une expression régulière. Il s'agit d'un algorithme efficace, utilisé notamment dans ocamllex.

L'idée de départ est la suivante : si un automate fini reconnaît le langage correspondant à l'expression régulière r, alors à toute lettre d'un mot reconnu on peut faire correspondre une occurrence d'une lettre apparaissant dans r. Pour distinguer les différentes occurrences d'une même lettre dans r, on va les indexer par des entiers. Considérons par exemple l'expression régulière (a|b)* a (a|b), qui définit les mots sur l'alphabet {a,b} dont l'avant-dernière lettre est un a. Si on indice les caractères, on obtient 

(a1|b1)* a2 (a3|b2)
Si on considère le mot aabaab, alors il correspond à l'expression régulière de la manière suivante 
a1a1b1a1a2b2

L'idée est alors de construire un automate dont les états sont des ensembles de lettres indexées, correspondant aux occurrences qui peuvent être lues à un instant. Ainsi l'état initial contient les premières lettres possibles des mots reconnus. Dans notre exemple, il s'agit de a1,b1,a2. Pour construire les transitions, il suffit de calculer, pour chaque occurrence d'une lettre, l'ensemble des occurrences qui peuvent la suivre. Dans notre exemple, si on vient de lire a1, alors les caractères possibles suivants sont a1,b1,a2 ; si on vient de lire a2, alors ce sont a3,b2.

Question 1. Nullité d'une expression régulière

On considère le type Caml suivant pour les expressions régulières dont les lettres sont indexées par des entiers (type ichar). 
type ichar = char * int

type regexp =
  | Epsilon
  | Character of ichar
  | Union of regexp * regexp
  | Concat of regexp * regexp
  | Star of regexp
Écrire une fonction 
val null : regexp -> bool
qui détermine si epsilon (le mot vide) appartient au langage reconnu par une expression régulière.

Tester avec 

let () =
  let a = Character ('a', 0) in
  assert (not (null a));
  assert (null (Star a));
  assert (null (Concat (Epsilon, Star Epsilon)));
  assert (null (Union (Epsilon, a)));
  assert (not (null (Concat (a, Star a))))

Question 2. Les premiers et les derniers

Pour représenter les ensembles de lettres indexées, on se donne le type Caml suivant : 
module Cset = Set.Make(struct type t = ichar let compare = Stdlib.compare end)

Écrire une fonction 

val first : regexp -> Cset.t
qui calcule l'ensemble des premières lettres des mots reconnus par une expression régulière. (Il faut se servir de null.)

De même, écrire une fonction 

val last : regexp -> Cset.t
qui calcule l'ensemble des dernières lettres des mots reconnus.

Tester avec 

let () =
  let ca = ('a', 0) and cb = ('b', 0) in
  let a = Character ca and b = Character cb in
  let ab = Concat (a, b) in
  let eq = Cset.equal in
  assert (eq (first a) (Cset.singleton ca));
  assert (eq (first ab) (Cset.singleton ca));
  assert (eq (first (Star ab)) (Cset.singleton ca));
  assert (eq (last b) (Cset.singleton cb));
  assert (eq (last ab) (Cset.singleton cb));
  assert (Cset.cardinal (first (Union (a, b))) = 2);
  assert (Cset.cardinal (first (Concat (Star a, b))) = 2);
  assert (Cset.cardinal (last (Concat (a, Star b))) = 2)

Question 3. Les suivants

En se servant des fonctions first et last, écrire une fonction 
val follow : ichar -> regexp -> Cset.t
qui calcule l'ensemble des lettres qui peuvent suivre une lettre donnée dans l'ensemble des mots reconnus.

On notera que la lettre d appartient à l'ensemble follow c r si et seulement si

Tester avec 

let () =
  let ca = ('a', 0) and cb = ('b', 0) in
  let a = Character ca and b = Character cb in
  let ab = Concat (a, b) in
  assert (Cset.equal (follow ca ab) (Cset.singleton cb));
  assert (Cset.is_empty (follow cb ab));
  let r = Star (Union (a, b)) in
  assert (Cset.cardinal (follow ca r) = 2);
  assert (Cset.cardinal (follow cb r) = 2);
  let r2 = Star (Concat (a, Star b)) in
  assert (Cset.cardinal (follow cb r2) = 2);
  let r3 = Concat (Star a, b) in
  assert (Cset.cardinal (follow ca r3) = 2)

Question 4. Construction de l'automate

Pour construire l'automate déterministe correspondant à une expression régulière r, on procède ainsi :
  1. on ajoute un nouveau caractère # à la fin de r ;
  2. l'état de départ est l'ensemble first r ;
  3. on a une transition de l'état q vers l'état q' à la lecture du caractère c (il s'agit là d'une lettre non indexée) si q' est l'union de tous les follow ci r pour tous les éléments ci de q tels que fst ci = c ;
  4. les états d'acceptation sont ceux qui contiennent le caractère #.

Écrire une fonction 

val next_state : regexp -> Cset.t -> char -> Cset.t
qui calcule l'état résultant d'une transition.

Pour représenter l'automate fini, on se donne le type autom suivant : 

type state = Cset.t  (* un état est un ensemble de caractères *)

module Cmap = Map.Make(Char) (* dictionnaire dont les clés sont des caractères *)
module Smap = Map.Make(Cset) (* dictionnaire dont les clés sont des états *)

type autom = {
  start : state;
  trans : state Cmap.t Smap.t  (* dictionnaire état -> (dictionnaire caractère -> état) *)
}
On peut choisir de représenter ainsi le caractère # : 
let eof = ('#', -1)
Écrire une fonction 
val make_dfa : regexp -> autom
qui construit l'automate correspondant à une expression régulière. L'idée est de construire les états par nécessité, en partant de l'état initial. On pourra par exemple adopter l'approche suivante : 
let make_dfa r =
  let r = Concat (r, Character eof) in
  (* transitions en cours de construction *)
  let trans = ref Smap.empty in
  let rec transitions q =
    (* la fonction transitions construit toutes les transitions de l'état q,
       si c'est la première fois que q est visité *)
    ...
  in
  let q0 = first r in
  transitions q0;
  { start = q0; trans = !trans }

Note : il est bien entendu possible de construire au final un automate dont les états ne sont pas des ensembles mais, par exemple, des entiers, pour plus d'efficacité dans l'exécution de l'automate. Cela pourrait d'ailleurs être fait pendant la construction, ou a posteriori. Mais ce n'est pas ce qui nous intéresse ici.

Visualisation avec l'outil dot

Voici du code pour imprimer un automate dans le format d'entrée de l'outil dot : 
let fprint_state fmt q =
  Cset.iter (fun (c,i) ->
    if c = '#' then Format.fprintf fmt "# " else Format.fprintf fmt "%c%i " c i) q

let fprint_transition fmt q c q' =
  Format.fprintf fmt "\"%a\" -> \"%a\" [label=\"%c\"];@\n"
    fprint_state q
    fprint_state q'
    c

let fprint_autom fmt a =
  Format.fprintf fmt "digraph A {@\n";
  Format.fprintf fmt "  @[\"%a\" [ shape = \"rect\"];@\n" fprint_state a.start;
  Smap.iter
    (fun q t -> Cmap.iter (fun c q' -> fprint_transition fmt q c q') t)
    a.trans;
  Format.fprintf fmt "@]@\n}@."

let save_autom file a =
  let ch = open_out file in
  Format.fprintf (Format.formatter_of_out_channel ch) "%a" fprint_autom a;
  close_out ch
Pour tester, on reprend l'exemple ci-dessus : 
(*  (a|b)*a(a|b)  *)
let r = Concat (Star (Union (Character ('a', 1), Character ('b', 1))),
		Concat (Character ('a', 2),
			Union (Character ('a', 3), Character ('b', 2))))
let a = make_dfa r
let () = save_autom "autom.dot" a

L'exécution produit un fichier autom.dot qui peut être ensuite visualisé avec la commande Unix 

  dotty autom.dot
ou encore avec l'une des deux commandes suivantes : 
  dot -Tps autom.dot | gv -
  dot -Tpdf autom.dot > autom.pdf && evince autom.pdf
On doit obtenir quelque chose comme la figure de droite.

Question 5. Reconnaissance d'un mot

Écrire une fonction 
val recognize : autom -> string -> bool
qui détermine si un mot est reconnu par un automate.

Voici quelques tests positifs : 

let () = assert (recognize a "aa")
let () = assert (recognize a "ab")
let () = assert (recognize a "abababaab")
let () = assert (recognize a "babababab")
let () = assert (recognize a (String.make 1000 'b' ^ "ab"))
et quelques tests négatifs : 
let () = assert (not (recognize a ""))
let () = assert (not (recognize a "a"))
let () = assert (not (recognize a "b"))
let () = assert (not (recognize a "ba"))
let () = assert (not (recognize a "aba"))
let () = assert (not (recognize a "abababaaba"))

Voici un autre test avec une expression régulière caractérisant un nombre pair de b : 

let r = Star (Union (Star (Character ('a', 1)),
		     Concat (Character ('b', 1),
			     Concat (Star (Character ('a',2)),
				     Character ('b', 2)))))
let a = make_dfa r
let () = save_autom "autom2.dot" a
Quelques tests positifs : 
let () = assert (recognize a "")
let () = assert (recognize a "bb")
let () = assert (recognize a "aaa")
let () = assert (recognize a "aaabbaaababaaa")
let () = assert (recognize a "bbbbbbbbbbbbbb")
let () = assert (recognize a "bbbbabbbbabbbabbb")
et quelques tests négatifs : 
let () = assert (not (recognize a "b"))
let () = assert (not (recognize a "ba"))
let () = assert (not (recognize a "ab"))
let () = assert (not (recognize a "aaabbaaaaabaaa"))
let () = assert (not (recognize a "bbbbbbbbbbbbb"))
let () = assert (not (recognize a "bbbbabbbbabbbabbbb"))

Question 6. Génération d'un analyseur lexical

Dans cette dernière question, on se propose de construire automatiquement, à partir de l'automate correspondant à une expression régulière, un code OCaml qui réalise une analyse lexicale, c'est-à-dire qui découpe une chaîne de caractères en lexèmes les plus longs possibles.

Plus précisément, on va produire un code de la forme suivante : 

type buffer = { text: string; mutable current: int; mutable last: int }

let next_char b =
  if b.current = String.length b.text then raise End_of_file;
  let c = b.text.[b.current] in
  b.current <- b.current + 1;
  c

let rec state1 b =
  ...
and state2 b =
  ...
and state3 b =
  ...
Le type buffer contient la chaîne à analyser (champ text), la position du prochain caractère à examiner (champ current) et la position suivant le dernier lexème reconnu (champ last). La fonction next_char renvoie le prochain caractère à analyser et incrémente le champ current. Si la fin de la chaîne est atteinte, elle lève l'exception End_of_file.

À chaque état de l'automate correspond une fonction statei avec un argument b de type buffer. Cette fonction réalise le travail suivant :

  1. Si l'état est acceptant, alors on affecte à b.last la valeur de b.current.
  2. Puis on appelle next_char b et on examine son résultat. S'il s'agit d'un caractère pour lequel une transition existe, alors on appelle la fonction correspondante. Sinon, on lève une exception (par exemple, avec failwith "lexical error").
On note que les fonctions statei ne renvoient rien. Elles ne peuvent terminer que sur une exception (soit End_of_file pour signifier que la fin de la chaîne est atteinte, soit Failure pour signifier une erreur lexicale).

Écrire une fonction 

  val generate: string -> autom -> unit
qui prend en arguments le nom d'un fichier et un automate et produit dans ce fichier le code OCaml correspondant à cet automate, selon la forme ci-dessus. Indications : Note : Il sera utile d'ajouter au code produit une dernière ligne de la forme 
  let start = state42
correspondant à l'état initial de l'automate.

Pour tester, écrire (dans un autre fichier lexer.ml, cette fois écrit à la main) un programme qui découpe une chaîne de caractères en lexèmes en utilisant le code produit automatiquement (en fixant le nom du fichier, par exemple a.ml). Le principe est une boucle qui effectue les actions suivantes :

  1. on positionne le champ last à -1 ;
  2. on appelle la fonction start et on rattrape l'exception e qu'elle lève ;
  3. si le champ last vaut toujours -1, alors aucun lexème n'a été reconnu et on termine en relançant l'exception e ;
  4. sinon, on affiche le lexème qui a été reconnu et on affecte au champ current la valeur du champ last.
Attention à traiter correctement l'arrêt du programme.

On pourra tester par exemple avec l'expression régulière a*b, en exécutant 

let r3 = Concat (Star (Character ('a', 1)), Character ('b', 1))
let a = make_dfa r3
let () = generate "a.ml" a
puis en liant le code produit avec le fichier lexer.ml : 
  % ocamlopt a.ml lexer.ml
Sur la chaîne abbaaab, l'analyse doit produire trois lexèmes et réussir : 
--> "ab"
--> "b"
--> "aaab"
Sur la chaîne aba, l'analyse doit produire un premier lexème puis échouer : 
--> "ab"
exception End_of_file
Enfin, sur la chaîne aac, l'analyse doit échouer sur une erreur lexicale : 
exception Failure("lexical error")
On pourra aussi tester avec l'expression régulière (b|espilon)(ab)*(a|epsilon) des mots alternant les lettres a et b. Sur la chaîne abbac, on doit obtenir trois lexèmes : 
--> "ab"
--> "ba"
--> ""
would now loop
Le dernier lexème étant la chaîne vide, le programme s'arrête en signifiant qu'on obtiendrait maintenant indéfiniment ce lexème vide.

solution / lexer.ml
Cet algorithme est connu sous le nom d'algorithme de Berry-Sethi. Il est notamment décrit dans le dragon (Aho, Sethi, Ullman, Compilateurs), section 3.9.
retour à la page du cours