Cours 5

Htmligure
Version & licenses
Creative Commons License

Exemples de lecteurs

Guyslain
Thursday, 21 July 2016

Retour au sommaire.

Exemples d'utilisation.

Pour l'instant, la librairie de lecture est assez brute et ne propose aucune construction de haut niveau. Par exemple, on voudrait probablement avoir des lecteurs prêts pour les types élémentaires, et des combinateurs pour lire des listes ou des paires comme dans les autres librairies. Commençons donc par là.

Lecture d'un entier.

Un entier est une séquence non-vide de chiffres, ne commençant pas par zéro, ou bien contenant uniquement 0 . On va donc commencer par écrire un combinateur lisant une séquence de valeurs. C'est donc une fonction prenant un lecteur, et lisant avec ce lecteur autant que possible. Nous allons l'écrire récursivement : on lit une valeur, puis on lit une séquence, ou bien on ne lit rien. D'ailleurs c'est ainsi que les grammaires sont écrites :

  1. seq :=
  2. elt seq
  3. | epsilon

La lecture d'une séquence produit une liste. Avec notre librairie :

  1. let rec sequence : 'value reader -> 'value list reader =
  2. fun reader ->
  3. (fun value seq -> value :: seq) *> reader <*> sequence reader
  4. || return []

Il y a juste un petit problème technique avec cette définition : c'est une récursion qui ne termine jamais, puisque l'appel récursif se fait sur le même argument. En pratique, si on essaie de s'en servir on obtient un exception pour dépassement de la pile. Moralement, sequence a deux arguments, le lecteur des valeurs de la séquence, et l'entrée puisqu'un lecteur est une fonction. Ici la récursion fait décroitre l'entrée, donc il faudrait explicitement prendre l'entrée en argument pour obtenir une récursion qui termine.

Un autre solution est d'utiliser un combinateur spécialisé dans les récursions. Le voici (c'est presque toujours la même définition dans toutes les librairies), il prend simplement à sa charge la récursion :

  1. let rec fix (make_reader : 'value reader -> 'value reader) : 'value reader =
  2. fun input ->
  3. make_reader (fix make_reader) input

On l'utilise ainsi pour construire le combinateur de séquence :

  1. let sequence : 'value reader -> 'value list reader =
  2. fun read_value ->
  3. fix @@ fun read_sequence ->
  4. (fun value seq -> value :: seq) *> read_value <*> read_sequence
  5. || return []

fix @@ fun reader_seq -> se comprend comme l'attribution du nom reader_seq à la valeur que l'on veut définir récursivement. Cela ne résoudra pas le problème de non-terminaison si read_value accepte le mot vide, mais ce serait une mauvaise grammaire dans ce cas. On utilise ce nom pour l'appel récursif. On en profite pour définir une séquence non-vide :

  1. let non_empty_sequence read_value =
  2. (fun value list -> value :: list) *> read_value <*> sequence read_value

Il nous faut ensuite tester si un caractère est un chiffre ou pas. Idéalement on utilise une librairie pour cela, en général les librairies pour unicode possède des prédicats pour les classes de caractères. En OCaml char ne représente pas les caractères unicodes (il faudrait le remplacer par uchar et modifier TextInput). On code donc les prédicats directement.

  1. let is_figure c = '0' <= c && c <= '9'
  2. let is_non_zero_figure c = '1' <= c && c <= '9'

On peut maintenant faire la lecture d'un entier en distinguant le cas du zéro :

  1. let make_int first_figure figures =
  2. first_figure :: figures
  3. |> List.map (fun c -> int_of_char c - int_of_char '0')
  4. |> List.fold_left (fun n figure -> 10 * n + figure) 0
  5. let make_zero _ = 0

  7. let int : int reader =
  8. make_int *> is_non_zero_figure @? char <*> sequence (is_figure @? char)
  9. || make_zero *> this_char '0'

Notons que grâce à l'ajout de la fonction sequence, nous avons tout ce qu'il faut pour faire un lecteur d'expressions régulières (et par exemple les entiers s'expriment comme des expressions régulières). Ce que les grammaires ont de plus que les expressions régulières, c'est la possibilité de faire des constructions récursives.

Lire une séquence donnée de caractères

On a souvent à lire une chaîne de caractères précise dans le texte, par exemple un mot-clé du langage... Écrivons donc une fonction qui à une chaîne de caractères construit le lecteur de cette chaîne.

Première étape, pour des raisons pratiques nous allons transformer la chaîne de caractères en liste de caractères, et inversement.

  1. let rec list_of_string ?(offset=0) string =
  2. if offset >= String.length string then []
  3. else String.get string offset :: list_of_string ~offset:(offset+1) string

  5. let string_of_list chars =
  6. chars
  7. |> List.map (fun c -> String.make 1 c)
  8. |> String.concat ""

Ensuite, on transforme chaque caractère par un lecteur pour ce caractère, et il nous reste alors à les séquencer. L'action associé à un séquencement va être d'ajouter le caractère lu à la liste des caractères. Notons que dans ce cas nous souhaitons un parenthésage à droite en priorité, pour pouvoir ajouter le premier caractère à la liste des autres caractères.

  1. let this_string string : string reader =
  2. let (++) read_char read_string =
  3. (fun c list -> c::list) *> read_char <*> read_string
  4. in
  5. let char_readers =
  6. string
  7. |> list_of_string
  8. |> List.map (fun c -> this_char c)
  9. in
  10. return []
  11. |> List.fold_right (++) char_readers
  12. |> ( *> ) string_of_list

  14. (* [this_string] is a bit long and will obfuscate the grammar,
  15. it is better to have a short name for it. *)
  16. let s = this_string

Lire des espaces.

On introduit les lecteurs suivants pour lire des espaces (ou autres caractères invisibles) : un, au moins un, ou n'importe quel nombre d'espaces.

  1. let is_space : char -> bool = String.contains " \t\r\n"

  3. let one_space : char reader = is_space @? char
  4. let skip_spaces : char list reader = sequence read_one_space
  5. let spaces : char list reader = non_empty_sequence read_one_space

Souvent les grammaires permettent de mettre des quantités quelconques d'espacement entre deux lexèmes. On ne souhaite pas avoir systématiquement à écrire explicitement où les espacements sont autorisés. La solution la plus simple est de définir une version de l'opérateur de séquencement qui lit automatiquement les espaces entre les deux valeurs lus.

  1. let (<+>) reader1 reader2 =
  2. (fun fct blanks arg -> fct arg) *> reader1 <*> skip_spaces <*> reader2

Lecteurs de paires et de triplets.

Les combinateurs de pairs ou de triplets se déduisent facilement à partir de séquencement.

  1. let pair left_reader right_reader : ('left * 'right) reader =
  2. let make_pair lparen left comma right rparen = (left,right) in
  3. make_pair *> s "(" <+> left_reader <+> s "," <+> right_reader <+> s ")"

  5. let triple left_reader middle_reader right_reader
  6. : ('left * 'middle * 'right) reader =
  7. let make_triple lparen left comma1 middle comm2 right rparen =
  8. (left,middle,right)
  9. in
  10. make_triple *> s "("
  11. <+> left_reader <+> s ","
  12. <+> middle_reader <+> s ","
  13. <+> right_reader
  14. <+> s ")"

Lecteur d'arbres.

Nous avons tout ce qu'il faut pour définir un lecteur d'arbres binaires :

  1. let make_leaf leaf = Leaf
  2. let make_node node (left,root,right) =
  3. Node (left,root,right)

  5. let bintree (elt: 'elt reader) : 'elt bintree reader =
  6. fix @@ fun tree ->
  7. make_node *> s "Node" <+> triple tree elt tree
  8. || make_leaf *> s "Leaf"

Peut-on faire plus simple ?

Retour au sommaire.