Retour au sommaire.
La plupart des données structurées sont décrites par des grammaires hors-contextes, en particulier les langages de programmation, mais aussi des formats comme XML ou json. Cela parait donc une bonne idée de vouloir écrire les fonctions de lectures sous la forme de grammaire aussi. Nous avons déterminé que ce que nous voulons est à l'image de cet exemple :
type 'elt bin_tree =
| Leaf
| Node of 'elt bin_tree * 'elt * 'elt bin_tree
let make_node (left,root,right) = Node (left,root,right)
let make_leaf () = Leaf
let bin_tree_to_string (elt: 'elt Read.t) : 'elt bin_tree Read.t =
let open Read in
fix @@ fun tree ->
(make_node *> cst "Node " ++ triple tree elt tree)
|| (make_leaf *> cst "Leaf")
Il nous reste donc à définir le type Read.t, puis les différents combinateurs permettant de la manipuler. Read.tdoit représenter les fonctions de lectures, qui fournissent une valeur à partir d'une chaîne de caractères. On peut donc poser comme définition :
type 'result t = string -> 'result
Il y a cependant plusieurs problèmes avec cette définition :
la lecture peut échouer, si le format de la chaîne de caractères n'est pas correct. La lecture ne devrait donc pas toujours retourner une valeur.
si la grammaire est ambigüe, il peut y avoir plusieurs façons de lire la chaîne de caractères, et donc plusieurs réponses possibles. On devrait donc retourner une liste de résultats, ce qui permettrait aussi de gérer la possibilité de ne pas avoir de résultat du tout.
ce type n'est pas combinable, parce que les lecteurs consomment toute la chaîne de caractères. On souhaite pouvoir enchaîner plusieurs lecteurs successivement qui chacun liront une partie de la chaîne de caractères. Pour cela, le résultat d'une lecture doit être composée de la valeur construite, et de ce qu'il reste à lire dans la chaîne de caractères.
en se restreignant aux chaînes de caractères, on perd en application. Par exemple pour lire un fichier il faudra d'abord extraire le fichier comme une chaîne de caractères, ce qui n'est pas souhaitable pour les grands fichiers. Si on lit dans la sortie d'un pipe, cela oblige à attendre la fin du pipe pour commencer à lire.
en cas d'erreur, il serait bon de pouvoir indiquer où l'erreur se produit, pourquoi, et même idéalement de pouvoir continuer la lecture.
pour des raisons d'efficacité, on voudrait aussi ajouter des structures de données efficaces pour encoder la fonction de lecture.
On ne va pas s'attaquer à tous ces problèmes, on va se contenter d'un petit prototype simple. D'abord on va abstraire les chaînes de caractères avec ce module, qui donne une interface itérable pour les séquences de caractères :
module TextInput : sig
module Position : sig
type t =
{ origin : string;
column : int;
line : int;
}
val compare : t -> t -> int
val min : t -> t -> t
val max : t -> t -> t
end
module TextInterval : sig
type t = Position.t * Position.t
val of_position : Position.t -> t
val merge : t -> t -> t
end
type t
val move_forward : t -> t option
val get_current_position : t -> Position.t
val get_current_char : t -> (char * Position.t) option
val observe : t -> ((char * Position.t) * t) option
val of_string : ?offset:int -> ?name:string -> string -> t
val of_list : ?name:string -> char list -> t
val of_file : filename:string -> t
val of_in_channel : ?name:string -> in_channel -> t
end
Le module Position permet de représenter en quelle position d'une séquence se trouve un caractère donné, en terme de numéros de ligne et de colonne. Le champ origin permet de retenir l'origine du caractère, par exemple un nom de fichier.
Le module TextInterval permet d'associer à chaque valeur lue la position de la sous-séquence de caractères ayant été lus pour la produire.
Deuxièmement, chaque résultat contiendra à la fois la valeur construite, l'intervalle des caractères lus pour construire la valeur, et le reste de la séquence à lire.
Finalement, la lecture d'une valeur peut échouer, dans ce cas on veut retourner la position d'échec et un message d'erreur. Idéalement, on veut aussi savoir la liste des règles de dérivation utilisée pour aboutir à cette erreur. On ne traitera pas les ambiguïtés (en cas d'ambiguïté de la grammaire, la première dérivation possible sera choisie). Cela nous donne le type suivant :
type 'value output =
{ value : 'value;
interval : TextInput.TextInterval.t option;
input : TextInput.t
}
type error =
{ stack : (string * TextInput.Position.t) list;
position : TextInput.Position.t
}
type 'value result =
| Output of 'value output
| Error of error
type 'value reader = TextInput.t -> 'value result option
mais on va, lors de la conception, considérer le type plus simple, qui concentre toute la partie calculatoire (pas de gestion des erreurs, des positions) :
type 'value reader = TextInput.t -> ('value * TextInput.) option
Retour au sommaire.
