← Cours 3 : Monades Cours 5 : Mini Excel →

Parseurs & Documents

CSV, XML, HTML… la monade Parsec à la conquête du texte

1. Introduction

Dans le cours précédent, on a découvert les monades : des motifs de composition pour des calculs contextualisés. On a vu la monade Liste (non-déterminisme), Option (échec), State (état), Reader (environnement), et Cont (continuation).

Il est temps de les mettre en pratique sur un problème concret : lire des documents textuels. CSV, XML, HTML… ces formats sont partout. Et pour les analyser, on va construire une petite bibliothèque de parseurs basée sur… une monade !

Un parseur (ou analyseur syntaxique) est un programme qui lit du texte brut et le transforme en une structure de données. C'est comme un traducteur : le texte est une langue étrangère, la structure de données est votre langue maternelle.

Parsec est une bibliothèque de parseurs combinatoires écrite en Haskell par Daan Leijen (et plus tard Paolo Martini). Le nom vient de "Parser Combinator". Le principe est simple : on combine de petits parseurs élémentaires pour former des parseurs complexes, exactement comme on combine des fonctions pour former des programmes. En OCaml, des bibliothèques comme Angstrom, Sedlex, ou Menhir (pour les grammaires) reprennent ces idées.

Ce cours va construire notre propre bibliothèque Parsec pas à pas, puis l'utiliser pour :

  1. Parser du CSV (tableaux de données).
  2. Parser du XML / HTML (documents arborescents).
  3. Transformer ces structures pour extraire ou générer de l'information.

Ces techniques préparent les deux derniers cours : une application Excel-like (cours 5) et une application jQuery-like (cours 6).

Parser du texte à la main, c'est comme éplucher des oignons avec une tronçonneuse : ça marche, mais c'est moche, dangereux, et ça fait pleurer. Les parseurs combinatoires, c'est le couteau de chef : précis, élégant, et on peut bluffer les amis.

2. La monade Parsec

Un parseur, c'est quoi ? C'est une fonction qui prend une chaîne (du texte non lu) et produit optionnellement une valeur et le reste de la chaîne :

OCaml
// Un parseur : lit 'a au début de la chaîne, ou échoue *)
type 'a parser = P of (string -> ('a * string) option)

Vous reconnaissez ? C'est une combinaison de deux monades du cours 3 :

Un parseur est une monade State + Option. C'est la magie des monades : on les compose pour en créer de nouvelles !

2.1 Type, return et bind

Commençons par définir notre type et ses deux opérateurs fondamentaux :

OCaml
---------- Notre bibliothèque Parsec maison ----------

(* Type d'un parseur *)
type 'a parser = P of (string -> ('a * string) option)

(* Exécuter un parseur sur une entrée *)
let run (P p) s = p s

// return : toujours réussir, sans consommer d'entrée *)
let return x = P (fun s -> Some (x, s))

// bind : exécuter un parseur, puis le second avec le reste *)
let (>>=) (P p) f =
  P (fun s ->
    match p s with
    | None          -> None
    | Some (a, s')  -> let (P q) = f a in q s')

// let* pour le sucre monadique *)
let (let*) = (>>=)

Déjà, avec juste return et bind, on a une monade ! Mais pour faire des parseurs utiles, il faut des primitives qui lisent du texte.

2.2 Combinateurs de base

OCaml
---------- Primitives ----------

// Lire n'importe quel caractère *)
let any_char =
  P (fun s ->
    if String.length s = 0 then None
    else Some (s.[0], String.sub s 1 (String.length s - 1)))

// Lire un caractère spécifique *)
let char c =
  let* x = any_char in
  if x = c then return x
  else P (fun _ -> None)

// Lire un caractère satisfaisant un prédicat *)
let satisfy p =
  let* x = any_char in
  if p x then return x
  else P (fun _ -> None)

---------- Combinateurs ----------

// Choix : essayer p1, si échec essayer p2 *)
let (<|>) (P p1) (P p2) =
  P (fun s ->
    match p1 s with
    | Some r -> Some r
    | None    -> p2 s)

// zero or more *)
let rec many p =
  P (fun s ->
    let rec loop s acc =
      match run p s with
      | None          -> Some (List.rev acc, s)
      | Some (a, s') -> loop s' (a :: acc)
    in loop s [])

// one or more *)
let many1 p =
  let* a = p in
  let* lst = many p in
  return (a :: lst)

Testons ces primitives !

OCaml
run (char 'a') "abc"
(* = Some ('a', "bc") *)

run (char 'x') "abc"
(* = None *)

run (char 'a' <|> char 'b') "bcd"
(* = Some ('b', "cd") *)

run (many (char 'a')) "aaab"
(* = Some (['a'; 'a'; 'a'], "b") *)
many et many1, c'est le "je bouffe tant que ça marche" des parseurs. many est optimiste : il essaie même si ça peut marcher zéro fois. many1 est exigeant : "si tu commences, tu finis !" C'est le "buffet à volonté" vs "le menu dégustation".

2.3 Parseurs spécialisés

Maintenant, construisons des parseurs plus utiles à partir de ces briques :

OCaml
---------- Parseurs spécialisés ----------

// Un chiffre *)
let digit = satisfy (fun c -> c >= '0' && c <= '9')

// Une lettre *)
let letter = satisfy (fun c ->
  (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'))

// Un entier (naturel) *)
let int =
  let* lst = many1 digit in
  return (int_of_string (String.of_list lst))

// Une chaîne littérale *)
let string str =
  let rec check i =
    if i >= String.length str then return ()
    else
      let* c = char str.[i] in
      check (i + 1)
  in
  let* _ = check 0 in
  return str

// Espaces blancs (optionnels) *)
let spaces = many (satisfy (fun c -> c = ' ' || c = '\t' || c = '\n' || c = '\r'))

On a maintenant une petite bibliothèque Parsec opérationnelle. Une cinquantaine de lignes, et on peut déjà analyser des chiffres, des lettres, des chaînes. C'est la puissance des combinateurs : on assemble de petites pièces pour en faire de grandes.

Les origines : Les parseurs combinatoires ont été popularisés par Graham Hutton et Erik Meijer dans les années 90. L'idée vient du combinatoire (SKI, etc.) et du lambda-calcul : on combine des fonctions élémentaires pour en former de plus complexes. En Haskell, la bibliothèque Parsec est devenue la référence. En OCaml, on a Angstrom (léger et rapide) et Menhir (pour les grammaires LR). Mais construire la sienne, c'est comprendre comment ça marche vraiment.

3. Parsing CSV

Le CSV (Comma-Separated Values) est le format tabulaire le plus simple qui soit : des lignes, des colonnes séparées par des virgules. Pas de XML, pas de JSON, juste du texte brut avec des virgules. C'est le "papier et crayon" des formats de données.

CSV
Nom,Âge,Ville
Alice,30,Paris
Bob,25,Lyon
Eve,35,"Marseille, France"

Un CSV, c'est :

3.1 Parseur de cellule

Commençons par la cellule, l'unité de base du CSV :

OCaml
// Parseur d'une cellule CSV : brute ou entre guillemets *)
let cell =
  // Cellule entre guillemets : "..." avec \" pour échapper *)
  let quoted =
    let* _ = char '"' in
    let* content =
      many (satisfy (fun c -> c <> '"')
            <|> (let* _ = string "\"" in return '"'))
    in
    let* _ = char '"' in
    return (String.of_list content)
  in
  // Cellule brute : pas de virgule, pas de saut de ligne *)
  let bare =
    let* chars =
      many (satisfy (fun c -> c <> ',' && c <> '\n' && c <> '\r'))
    in
    return (String.of_list chars)
  in
  quoted <|> bare

Le parseur cell essaie d'abord de lire une cellule entre guillemets (avec gestion de l'échappement "" → "), et si ça échoue, lit une cellule brute (tout ce qui n'est pas virgule ou saut de ligne).

Les guillemets dans le CSV, c'est comme les bagages en soute : on espère ne pas en avoir besoin, mais quand on en a besoin, on est bien content qu'ils soient là. Imaginez devoir écrire "Marseille, France" sans guillemets — la virgule ferait croire à une nouvelle colonne. Catastrophe !

3.2 Parseur de tableau complet

Maintenant qu'on a la cellule, on peut construire le parseur de tableau complet :

OCaml
// Type pour représenter une table CSV *)
type csv = {
  headers: string list;     // noms des colonnes *)
  rows:    string list list;  // données (une liste par ligne) *)
}

// Une ligne CSV : des cellules séparées par des virgules *)
let row =
  let* first = cell in
  let* rest  = many (let* _ = char ',' in cell) in
  return (first :: rest)

// CSV complet : header puis lignes *)
let csv =
  let* h  = row in
  let* _  = string "\n" in
  let* rs = many (let* r = row in let* _ = string "\n" in return r)
             <|> return []
  in
  return { headers = h; rows = rs }

Testons sur notre exemple !

OCaml
let data = "Nom,Âge,Ville\nAlice,30,Paris\nBob,25,Lyon\nEve,35,\"Marseille, France\"\n"

match run csv data with
| None -> print_endline "Échec du parse !"
| Some (t, _) ->
    List.iter (fun l ->
      print_endline (String.concat " | " l))
    (t.headers :: t.rows)
Nom | Âge | Ville
Alice | 30 | Paris
Bob | 25 | Lyon
Eve | 35 | Marseille, France

Le CSV est parsé ! Notez que "Marseille, France" a été correctement traité comme une seule cellule (la virgule à l'intérieur des guillemets n'est pas un séparateur).

3.3 Interrogation du CSV

Une fois le CSV parsé, on peut l'interroger. Par exemple, avec la monade Liste (cours 3) :

OCaml
// Trouver l'index d'une colonne par son nom *)
let col_index t name =
  let rec find i lst =
    match lst with
    | []      -> None
    | h :: _ when h = name -> Some i
    | _ :: t  -> find (i + 1) t
  in find 0 t.headers

// Obtenir une colonne sous forme de liste *)
let col t name =
  match col_index t name with
  | None      -> []
  | Some i   -> List.map (fun r -> List.nth r i) t.rows

// Filtrer les lignes selon une condition sur une colonne *)
let filter_rows t col_name pred =
  match col_index t col_name with
  | None      -> { t with rows = [] }
  | Some i   ->
      { t with rows =
          List.filter (fun r -> pred (List.nth r i)) t.rows }

// Exemple : les gens de plus de 28 ans *)
let filtered = filter_rows table "Âge" (fun a -> int_of_string a > 28)

Variation : on peut combiner la monade Liste avec le CSV pour faire des requêtes complexes :

OCaml
// Avec la monade liste : toutes les paires (Nom, Ville) des gens de > 25 ans *)
let (let*) = List.bind

let requete =
  let* ligne  = table.rows in
  let age     = int_of_string (List.nth ligne 1) in
  let* _       = if age > 25 then [()] else [] in
  let nom     = List.nth ligne 0 in
  let ville   = List.nth ligne 2 in
  [(nom, ville)]

C'est exactement une requête SQL : SELECT nom, ville FROM table WHERE age > 25. La monade Liste fait la jointure implicite, le if fait le WHERE, et la liste en retour fait le SELECT.

SQL comme monade : La bibliothèque LINQ en C# est une implémentation directe de cette idée. List comprehensions en Haskell et Python aussi. Le pattern est partout : prendre une collection, la filtrer, la transformer. La monade Liste avec let* est une façon de faire des requêtes dans le langage lui-même, sans SQL string.

4. Parsing XML / HTML

Le CSV c'est linéaire. Le XML c'est arborescent — et on sait depuis le cours 2 que les arbres se manipulent avec des ADT récursifs et des folds !

Commençons par définir l'AST (Arbre de Syntaxe Abstraite) pour XML :

OCaml
---------- AST XML ----------

type attr  = string * string       // nom = "valeur" *)

type xml =
  | Text    of string              // contenu textuel *)
  | Elem    of string              // balise orpheline : <br/> *)
            * attr list
            * xml list             // enfants *)

Un document XML est un arbre de nœuds. Chaque nœud est soit du texte, soit un élément avec un nom, des attributs, et des enfants.

XML, c'est comme les poupées russes : des éléments dans des éléments dans des éléments. Au centre, il y a soit du texte, soit le vide existentiel. C'est beau, c'est structuré, c'est verbeux — le XML c'est le candidat idéal pour un concours d'éloquence.

4.1 Balises et attributs

Commençons par les petites briques : nom, attribut, balise ouvrante, fermante, auto-fermante.

OCaml
// Un nom XML : lettre puis lettres/chiffres/tirets *)
let xml_name =
  let* c    = letter in
  let* cs   = many (letter <|> digit <|> char '-') in
  return (String.of_list (c :: cs))

// Une valeur d'attribut : entre guillemets *)
let attr_value =
  let* _ = char '"' in
  let* cs = many (satisfy (fun c -> c <> '"')) in
  let* _ = char '"' in
  return (String.of_list cs)

// Un attribut : nom="valeur" *)
let attr =
  let* n = xml_name in
  let* _ = spaces in
  let* _ = char '=' in
  let* _ = spaces in
  let* v = attr_value in
  return (n, v)

Maintenant les balises :

OCaml
// Des attributs (zéro ou plus) *)
let attrs =
  let* a  = attr in
  let* as = many (let* _ = spaces in attr) in
  return (a :: as)

// Balise ouvrante : <nom attributs> *)
let open_tag =
  let* _ = char '<' in
  let* n = xml_name in
  let* a = spaces >>= (fun _ -> attrs <|> return []) in
  let* _ = spaces in
  let* _ = char '>' in
  return (n, a)

// Balise fermante : </nom> *)
let close_tag expected =
  let* _ = string "</" in
  let* n = xml_name in
  let* _ = spaces in
  let* _ = char '>' in
  if n = expected then return ()
  else P (fun _ -> None)

// Balise auto-fermante : <br/> *)
let self_close =
  let* _ = char '<' in
  let* n = xml_name in
  let* a = spaces >>= (fun _ -> attrs <|> return []) in
  let* _ = spaces in
  let* _ = string "/>" in
  return (n, a)

4.2 Parseur XML complet

Le parseur complet d'élément XML utilise la récursion mutuelle : un élément peut contenir du texte ou d'autres éléments.

OCaml
// Texte jusqu'à la prochaine balise *)
let text =
  let* cs = many (satisfy (fun c -> c <> '<')) in
  match cs with
  | []  -> P (fun _ -> None)  // il faut au moins un caractère *)
  | _   -> return (Text (String.of_list cs))

// Un élément XML (récursif) *)
let rec element =
  // Contenu d'un élément : texte ou éléments imbriqués *)
  and content =
    many (text <|> element)
  in
  // On essaye d'abord l'auto-fermante, puis l'ouvrante + contenu + fermante *)
  let self =
    let* (n, a) = self_close in
    return (Elem (n, a, []))
  in
  let nested =
    let* (n, a)  = open_tag in
    let* cs       = content in
    let* _        = close_tag n in
    return (Elem (n, a, cs))
  in
  self <|> nested

// Un document XML complet (peut avoir plusieurs enfants racines) *)
let document =
  let* _  = spaces in
  let* e  = element in
  let* _  = spaces in
  return e

Testons sur un petit document :

OCaml
let html_doc = {|
  <div class="container">
    <h1 id="title">Bonjour</h1>
    <p>Ceci est un <strong>test</strong>.</p>
    <br/>
  </div>
|}

match run document html_doc with
| None      -> print_endline "Échec !"
| Some (e, _) -> print_xml e

Et on pourrait écrire une fonction print_xml pour afficher l'arbre — mais vous l'imaginez déjà.

Note : Ce parseur XML est une version simplifiée. Le vrai XML gère les commentaires, les CDATA, les entités (&amp;), les namespace, etc. Mais l'architecture est la même : on combine des parseurs pour lire des textes structurés. Les vrais parseurs XML comme Xmlm en OCaml ou lxml en Python font exactement ça, mais avec plus de cas particuliers. C'est le "90% du code gère 10% des cas" — un grand classique.

5. Transformations

Parser, c'est bien. Mais le but final, c'est de transformer les données : extraire de l'information, générer du nouveau contenu, faire des rapports.

5.1 Extraction (XPath-like)

On peut écrire des fonctions pour naviguer dans l'arbre XML, un peu comme XPath :

OCaml
---------- Navigation dans l'arbre XML ----------

// Récupérer les enfants d'un élément *)
let children e =
  match e with
  | Text _        -> []
  | Elem (_, _, cs) -> cs

// Trouver tous les éléments avec un nom donné (recherche profonde) *)
let rec find_all name e =
  match e with
  | Text _ -> []
  | Elem (n, _, cs) ->
      (if n = name then [e] else [])
      @ List.concat (List.map (find_all name) cs)

// Extraire le texte d'un élément et ses enfants *)
let rec text_content e =
  match e with
  | Text s      -> s
  | Elem (_, _, cs) -> String.concat "" (List.map text_content cs)

// Trouver la valeur d'un attribut *)
let attr_value e name =
  match e with
  | Text _         -> None
  | Elem (_, attrs, _) ->
      List.find_opt (fun (k, _) -> k = name) attrs
      |> Option.map snd

En combinant ces fonctions, on peut écrire des requêtes puissantes :

OCaml
// Exemple : extraire tous les textes des <li> dans un <ul class="menu"> *)
let menu_items doc =
  find_all "li" doc
  |> List.map text_content
  |> List.filter (fun s -> String.length s > 0)

Ce style de programmation — navigation dans un arbre avec des combinateurs — est exactement ce que fait jQuery avec le DOM HTML. La monade Liste (cours 3) et les fonctions map/filter (cours 2) deviennent ici des outils de requêtage de documents.

XPath est un langage de requêtage pour XML. Une expression comme //ul[@class="menu"]/li/text() sélectionne le texte de tous les li dans un ul de classe "menu". Avec notre bibliothèque, on écrit la même chose en OCaml pur : find_all "li" doc |> List.map text_content. C'est plus verbeux, mais c'est dans le langage — pas de nouvelle syntaxe à apprendre.

5.2 Génération (templates)

On peut aussi générer du XML/HTML à partir de données. C'est la base des templates (Moustache, Jinja, etc.) :

OCaml
---------- Génération HTML ----------

// Fonctions pour construire du HTML *)
let tag name attrs children = Elem (name, attrs, children)
let txt s = Text s
let (=>) k v = (k, v)

// Un template pour une page HTML *)
let page title items =
  tag "html" [] [
    tag "head" [] [
      tag "title" [] [txt title]
    ];
    tag "body" [] [
      tag "h1" ["class" => "main"] [txt title];
      tag "ul" [] (
        List.map (fun item ->
          tag "li" [] [txt item])
        items)
    ]
  ]

On peut combiner parsing et génération pour faire de la transformation de documents. Par exemple, prendre un CSV de produits et générer un catalogue HTML :

OCaml
// Transformer un CSV en page HTML *)
let csv_to_html csv_data =
  match run csv csv_data with
  | None -> Text "Erreur CSV"
  | Some (t, _) ->
      tag "table" [] (
        // Ligne d'en-tête *)
        [tag "thead" [] [
          tag "tr" [] (List.map (fun h -> tag "th" [] [txt h]) t.headers)
        ]]
        // Lignes de données *)
        @ [tag "tbody" [] (
            List.map (fun row ->
              tag "tr" [] (List.map (fun c -> tag "td" [] [txt c]) row))
            t.rows)]
      )

On a ainsi un pipeline complet : CSV → parse → structure → transformation → HTML. C'est ce qu'on appelle un ETL (Extract, Transform, Load) dans le monde des données.

Parser du CSV pour générer du HTML, c'est le cycle de l'eau en informatique : les données s'évaporent d'un format, se condensent en structures, et retombent en pluie dans un autre format. La monade Parsec est le nuage qui fait la liaison.

6. Conclusion

Ce cours a montré qu'avec une petite bibliothèque de parseurs combinatoires (50 lignes), on peut analyser des formats complexes comme CSV et XML/HTML. La clé, c'est la composition :

Ce qu'il faut retenir

  • Un parseur est une monade : State (l'entrée) + Option (l'échec).
  • Les combinateurs sont des Lego : on construit des parseurs complexes à partir de primitives simples.
  • CSV se parse linéairement : cellules, lignes, tableau.
  • XML/HTML se parse récursivement : l'arbre se construit avec des appels mutuellement récursifs.
  • Les transformations (extraction, génération) sont de simples fonctions sur les ADT.

Ce cours prépare directement les deux suivants :

← Cours 3 : Monades Cours 5 : Mini Excel →

Fait avec ❤️, beaucoup de bind, et un parse réussi

© 2026 — laurent.thiry@uha.fr