Programmation Avancée

TP11: parsing monadique

On rappelle la signature des monades:

module type MONAD = sig
  type +'a m
  val return : 'a -> 'a m
  val bind : 'a m -> ('a -> 'b m) -> 'b m
end

Exercice 1: Monade de parsing

La monade de parsing combine la monade de lecture (on lit un flux de tokens) et la monade de non-déterminisme (par défaut, une grammaire est ambigue et le parsing peut avoir plusieurs résultats). Le type de la monade est 'a m = char list -> (char list * 'a) list. Les calculs représentés (des parsers) prennent en entrée une suite de tokens de type char et renvoient une liste d'alternatives, chacune étant composée:

d'un suffixe de la liste d'entrée représentant les tokens non lus;
du résultat du parsing.

Pour fixer les idées, cette monade va nous permettre d'écrire des parsers et de les composer. Par exemple le parser int lira un maximum de caractères de [0-9] dans le flux de tokens, et renverra (avec la liste de tokens restante) leur interprétation comme un int. Le parser plus pourra ensuite exécuter le parser d'entiers, récupérer son résultat n, puis lire le caractère + et relancer le parser d'entiers, récupérer son résultat m, et renvoyer m. On notera ici deux points: les caractères consommés dans la char list par un calcul de la monade ne sont plus disponibles pour les calculs suivants; dans cet exemple on retourne au plus un résultat, mais la structure de liste permet de modéliser les échecs (par exemple, sur l'entrée 123++).

Question 1

Construire un module Parsing de signature MONAD de telle sorte que les opérations return et bind respectent la sémantique attendue:

return ne consomme pas de token, et ne renvoie qu'un résultat possible;
bind m f va renvoyer chaque résultat possible de f x où x est un résultat possible de m, en chaînant les listes de tokens de sorte que les tokens soient consommés par m puis f.

Question 2

Etendre votre module, et lui attacher la signature suivante:

module type PARSING = sig
  include MONAD
  val plus : 'a m -> 'a m -> 'a m
  val zero : 'a m
  val read : char m
  val eos  : bool m
  val run  : 'a m -> char list -> (char list * 'a) list
end

Le plus correspond au choix non-déterministe entre deux calculs, et zero est l'échec (aucun résultat possible). L'opération read lit (et consomme) le premier char du flux d'entrée, échoue si le flux est déja terminé. L'opération eos (end of stream) indique enfin si le flux est terminé. Enfin, run exécute un calcul sur une entrée donnée.

Bonus (dur!)

La monade de parsing combine deux aspects: le non-déterminisme et la lecture. Chacun de ces aspects peut être implémenté séparemment comme un transformateur de monades (sans opérateur lift: on se contentera d'un foncteur de MONAD vers MONAD). Reconstruire ainsi la monade de parsing.

Exercice 2: parsing

L'objectif, à partir de maintenant, est de ne plus jamais s'appuyer sur la définition de 'a Parsing.m, mais d'utiliser uniquement les opérations élémentaires définies ci-dessus. (Techniquement, on s'appuiera sur le fait que le type 'a m est abstrait dans la signature PARSING et qu'on travaille désormais en dehors de ce module.)

On pose type word = char list. Nous allons définir des combinateurs de parsing qui permettent notamment de construire, pour tout langage régulier L, un parseur p(L) de type word m tel que, pour tout préfixe w du flux d'entrée, p(L) lit w et renvoie (au moins) une fois w ssi w appartient à L. L'opération zero : word m correspond déja au langage vide selon cette spécification, et plus correspond à l'union de langages.

Question 1

Définir one : char list m correspondant au langage contenant uniquement le mot vide: one ne doit donc rien lire et juste renvoyer [].

Définir char : char -> char list m tel que char c reconnaisse le mot restreint au caractère c; le calcul doit donc vérifier qu'il y a un caractère à lire, et qu'il s'agit bien de c.

Définir concat : char list m -> char list m -> char list m qui corresponde à la concaténation de langages.

Utiliser les opérations précédemment définies pour dériver le parser reconnaissant une chaîne donnée: string : string -> char list m. Tester:

let plength m l = List.length (Parsing.run m l)
let () =
  assert (plength (string "fo") ['b';'a';'r'] = 0) ;
  assert (plength (string "fo") ['f';'o';'o'] = 1) ;
  assert (plength (string "fo") ['f';'a'] = 0)

Question 2

Définir star : char list m -> char list m en suivant l'équation A* = 1 + AA*. Il faudra faire attention aux récursions, et introduire si besoin une notion de concaténation paresseuse qui ne calcule son second parseur qu'une fois qu'on a obtenu un résultat du premier parseur.

Tester:

let (!) = star
let (++) = plus
let () =
  assert (plength !(char 'a' ++ char 'b') ['a';'b';'a'] = 4)

Quels résultats obtenez vous pour !(char 'a' ++ string "aa") sur ['a';'a';'a']?

Question 3

Un parseur ne doit pas seulement servir à reconnaître des (sous-)mots, mais aussi à les structurer ou les interpréter. Nous allons donc arrêter de considérer uniquement des objets de type word m.

Définir digit : int m qui reconnaît les mots composés d'un seul chiffre et renvoie leur valeur numérique. En déduire un parser expr : int m qui reconnaît les expressions arithmétiques simples définies ci-dessous et renvoie leur interprétation dans int:

digit ::= ['0'-'9']
expr  ::= digit | digit '+' expr

Que se passe-t-il si on écrit le même langage par une grammaire récursive à gauche?

On pourra enfin ajouter la multiplication en respectant les priorités usuelles, du parenthésage, lire des entiers supérieurs à 9, etc.

Références

Functional Pearl: Monadic parsing in Haskell de Graham Hutton et Erik Meijer.