TP 9: Flots et Automates

Le fichier à remplir est ici.

Nous allons définir une structure de données de flots afin de créer une fonction réalisant un automate à partir de sa description textuelle.

1 Flots

Pour geler un programme p, on le mets dans le corps d'une fonction fun () -> p. Ce programme ne sera exécuté que lorsque la fonction sera appliquée. Ceci permet de représenter des structures infinies sans que la définition ne boucle.

Un flot est soit le flot vide, soit une paire composée d'un élément et d'un flot gelé.

type 'a flot = Empty | Cons of 'a * (unit -> 'a flot)

Écrire une fonction les_entiers n rendant une liste de tous les entiers en partant de n.

val les_entiers : int -> int flot = <fun>

Écrire une fonction take_n f n qui retourne une liste composée des n premiers éléments du flot f (ou moins si le flot n'a pas assez d'éléments) et le flot des éléments restants.

val take_n : 'a flot -> int -> 'a list * 'a flot = <fun>

Écrire une fonction filter p f qui retourne le flot des éléments satisfaisant p. Attention, il ne faut pas que l'application à un flot infini donne un programme qui boucle.

val filter : ('a -> bool) -> 'a flot -> 'a flot = <fun>

Le crible d'Ératosthène (Wikipedia) transforme le flot d'entiers en partant de 2 en un flot de nombres premiers. Il consiste à prendre le premier élément n du flot d'entrée, à le retourner (c'est un nombre premier) en tête de flot, et à retourner comme reste du flot l'application récursive de cette fonction à un flot où on a enlevé tous les multiples de n. En pseudo-code, cela donne

crible (n,f) = n, (crible (enleve_multiple_de n f))

val crible : int flot -> int flot = <fun>

2 Automates

Dans un second temps nous allons lire puis analyser un automate d'états finis dont la fonction de transition figure ci-dessous.

Objective Caml ne sachant pas lire de schémas, nous donnons l'information équivalente sous forme textuelle.

(9,c) -> 4      (9,n) -> 2      (9,e) -> 9      
(5,e) -> 3
(4,j) -> 9      (2,k) -> 4;

Nous associons à chaque lexème (chaque caractère) une unité lexicale, avec pour certains un attribut lexical (la valeur transportée). Pour simplifier, les noms de symbole sont réduits à une lettre, les nombres ne comportent qu'un chiffre.

lexème	unité lexicale	attribut lexical
`(`	Parg
`)`	Pard
lettre	Ident	la lettre
chiffre	Nbre	le chiffre
`->`	Fleche
,	Virg
`;`	Ptvirg

Nous définissons deux règles TRANS et AUTO décrivant comment assembler des unités lexicales.

TRANS ::= parg nbre virg ident pard fleche nbre
AUTO  ::= TRANS AUTO | ptvirg

2.1 Préliminaires

Définir une fonction transformant une chaîne s en un flot de caractères. On peut accéder au kième caractère d'une chaîne s avec l'opération s.[k].
```
val flot_of_string : string -> char flot = <fun>
```
Les flots que nous manipulons dans la suite étant finis, écrire une fonction transformant intégralement un flot en une liste. Il est déconseillé d'appliquer cette fonction à un flot infini.
```
val to_list : 'a flot -> 'a list = <fun>
```
Définir une fonction flot prenant en argument un élément e et un flot f et retournant un nouveau flot dont le premier élément est e et dont le reste est f.
```
val flot : 'a -> 'a flot -> 'a flot = <fun>
```
Utiliser flot pour écrire une fonction créant un flot d'un seul élément.
```
val one : 'a -> 'a flot = <fun>
```
Définir une fonction eatall prenant en argument une liste l, un accumulateur initial init, et un flot f. La liste l est composée de paire p,t, où p est un prédicat pour les éléments du flot, et t est une fonction d'accumulation des éléments du flot. La valeur de retour de cette fonction est soit None, si le flot ne contenait pas des éléments satisfaisant la liste des prédicats, soit Some(acc,g) avec la valeur finale de l'accumulateur et le flot restant. Cette fonction s'exécute de la manière suivante:
- Si l est la liste vide, retourner Some(init,f).
- Sinon, soit (p,t) la tête de la liste et r le reste.
  - Si le flot est vide, retourner None.
  - Sinon, soit e le premier élément du flot et g le reste du flot.
    - Si p e retourne true, appeler récursivement eatall avec r, t e init, et g.
    - Sinon, retourner None.
```
val eatall :
  (('a -> bool) * ('a -> 'b -> 'b)) list ->
  'b -> 'a flot -> ('b * 'a flot) option = <fun>
```
Trois fonctions nous seront utiles pour utiliser avec eatall dans les cas simples.
1. Définir un prédicat egal qui teste si deux valeurs sont égales. Il sera utilisé en application partielle.
```
val egal : 'a -> 'a -> bool = <fun>
```
2. Définir une fonction d'accumulation nope qui ignore sont premier argument et renvoie directement son deuxième argument.
```
val nope : 'a -> 'b -> 'b = <fun>
```
3. Définir une fonction tsimple qui prend une liste l de prédicats, une valeur finale d, et un flot f, et renvoie Some(r, g) si le flot f commence par des éléments satisfaisant la liste l et continue par le flot g, et None sinon. Il est suggéré d'utiliser eatall et de transformer la liste l des prédicats en une liste de paires où le deuxième élément est toujours nope.
```
val tsimple :
  ('a -> bool) list -> 'b -> 'a flot -> ('b * 'a flot) option = <fun>
```
Définir une fonction append effectuant la concaténation de deux flots. Attention : cette fonction ne doit pas dérouler le premier flot jusqu'à la fin.
```
val append : 'a flot -> 'a flot -> 'a flot = <fun>
```
Définir une fonction comp effectuant la composition de deux transformations de flux. La première transformation, t, prend un flot de 'a et retourne de manière optionnelle une paire composée d'un flot de 'b et d'un flot de 'a. Cette première transformation est typiquement celle rendue par eatall. La deuxième transformation tf prend un flot de 'a et retourne un flot de 'b. La valeur de retour finale dépend du retour de t :
- si t retourne None, renvoyer None;
- si t retourne Some(b,g), renvoyer Some de la concaténation de b avec tf g.
```
type ('a, 'b) trans = 'a flot -> ('b flot * 'a flot) option
val comp :
  ('a, 'b) trans -> ('a flot -> 'b flot) -> 'a flot -> 'b flot option =
  <fun>
```
Définir une fonction par essayant d'appliquer une liste de transformation tl à un flot f et s'arrêtant à la première qui réussit. Si aucune transformation ne s'applique, renvoyer None.
```
val par : ('a, 'b) trans list -> ('a, 'b) trans = <fun>
```

2.2 Analyseur lexical

Les blancs (espace, tabulation(\t), passage à la ligne(\n)) n'étant pas significatifs, définir une fonction blcs prend un flot de caractères et retourne un flot de caractères sans les blancs.
```
val blncs : char flot -> char flot = <fun>
```
Définir le type unitlex dont les constructeurs sont les unités lexicales du tableau ci-dessus, avec éventuellement l'attribut lexical associé.
```
type unitlex =
    Parg
  | Pard
  | Ident of char
  | Nbre of int
  | Fleche
  | Virg
  | Ptvirg
```

Pour chaque unité lexicale, définir un analyseur qui consomme le lexème associé en tête de flot s'il est présent, et renvoie Some(f,g) où f est un flot comportant un seul élément de type unitlex et g et le reste du flot de caractères. Si le lexème n'est pas présent en tête de flot, renvoyer None. Il est suggéré d'utiliser tsimple quand c'est possible, et eatall sinon.

val tparg : char flot -> (unitlex flot * char flot) option = <fun>
val tpard : char flot -> (unitlex flot * char flot) option = <fun>
val tident : char flot -> (unitlex flot * char flot) option = <fun>
val tnbre : char flot -> (unitlex flot * char flot) option = <fun>
val tfleche : char flot -> (unitlex flot * char flot) option = <fun>
val tvirg : char flot -> (unitlex flot * char flot) option = <fun>
val tptvirg : char flot -> (unitlex flot * char flot) option = <fun>

Définir l'analyseur lexical analex qui consomme les lexèmes dans le flot de caractères, en ignorant les blancs, et rend le flot des unités lexicales associées.
```
exception LexError
```

val analex : char flot -> unitlex flot = <fun>

Tester.

2.3 Analyseur syntaxique

Définir l'analyseurs trans qui consomme, en tête du flot d'unitlex, la partie droite de la règle TRANS, et l'analyseur auto pour la règle AUTO.

exception ParseError
val isnbre : unitlex -> bool = <fun>
val getnbre : unitlex -> int = <fun>
val isident : unitlex -> bool = <fun>
val getident : unitlex -> char = <fun>
val trans : unitlex flot -> ('a flot * unitlex flot) option = <fun>

val auto : unitlex flot -> 'a flot = <fun>

L'analyseur auto est l'analyseur syntaxique capable de reconnaître la description d'un automate. Le tester sur la description de l'automate donné en exemple.

let ftest1 = analex(flot_of_string " ( a b c -> 123)  ")

val ftest1 : unitlex flot = Cons (Parg, <fun>)

let _ = auto ftest1

Exception: ParseError.

let ftest2 = analex(flot_of_string "  (9,c) -> 4      (9,n) -> 2      (9,e) -> 9      
    (5,e) -> 3
    (4,j) -> 9      (2,k) -> 4;")

val ftest2 : unitlex flot = Cons (Parg, <fun>)

let _ = auto ftest2

- : 'a flot = Empty

2.4 Compilateur d'automate

Les fonctions d'analyse syntaxique (trans et auto) sont à valeur dans unit. C'est-à-dire qu'elles ne produisent rien. Nous allons maintenant produire une représentation interne de l'automate reconnu. Cette représentation sera une fonction de transition.

Définissons tout d'abord les types nécessaires, ainsi qu'une exception.

type etat = Q of int
type symbole = X of char
type auto = etat * symbole -> etat
exception Automate of string * (etat * symbole)

La difficulté est de construire dynamiquement (au fur et à mesure de l'analyse) la fonction de type auto. Au début de l'analyse cette fonction n'est définie pour aucun couple de etat * symbole (l'automate est vide).

Commençons par les 3 fonctions d'intendance qui vont servir plus tard.

Définir la fonction ftransvide qui pour tout argument déclenche Automate.
```
val ftransvide : etat * symbole -> 'a = <fun>
```
Pour la chaîne de caractères à utiliser, voir cet exemple:
```
Exception:
Automate ("fonction de transition non definie en ", (Q 9, X 'c')).
```

Définir la fonction deffonctpart a b qui rend la fonction qui retourne b quand on lui donne a comme argument, et qui déclenche une exception pour toute autre valeur.

val deffonctpart : etat * symbole -> 'a -> etat * symbole -> 'a = <fun>

Tester cette fonction.

let test = deffonctpart (Q 9, X 'c') (Q 4)
let _ = test (Q 9, X 'c')

val test : etat * symbole -> etat = <fun>

let _ = test (Q 8, X 'c')

Exception:
Automate ("fonction de transition non definie en ", (Q 8, X 'c')).

Définir la fonction ajttrans f g qui à un argument x rend f x si celui-ci est défini (ne retourne pas l'exception Automate), et g x sinon.

val ajttrans : ('a -> 'b) -> ('a -> 'b) -> 'a -> 'b = <fun>

Tester.

let t1 = ajttrans (deffonctpart (Q 9, X 'c') (Q 4)) ftransvide

val t1 : etat * symbole -> etat = <fun>

let t2 = ajttrans (deffonctpart (Q 9, X 'n') (Q 2)) t1

val t2 : etat * symbole -> etat = <fun>

let _ = t2 (Q 9, X 'c')

- : etat = Q 4

Définir l'analyseur trans2 qui consomme, en tête du flot de unitlex, la partie droite de la règle TRANS et rend un flot composé d'un triplet int * char * int.
```
val trans2 :
  unitlex flot -> ((int * char * int) flot * unitlex flot) option =
  <fun>
```
Définir l'analyseur auto2 qui consomme, en tête du flot d'unitlex, la partie droite de la règle AUTO et rend un flot de triplets.
```
val auto2 : unitlex flot -> (int * char * int) flot = <fun>
```

Définir la fonction build_automate qui construit la fonction de transition.

val build_automate : (int * char * int) flot -> etat * symbole -> etat =
  <fun>

Tester sur l'exemple.

let automate = build_automate (auto2 ftest2)

val automate : etat * symbole -> etat = <fun>

let s0 = Q 9
let s1 = automate (s0, X 'n')
let _ = automate (s1, X 'k')

val s0 : etat = Q 9
val s1 : etat = Q 2