Quels sont les combinateurs dont nous avons besoin pour pouvoir écrire des grammaires ? D'évidence, les grammaires sont formés de terminaux, de non-terminaux, et pour chaque non-terminal, une alternative entre plusieurs règles, pour chaque règle une action et une suite de terminaux et de non-terminaux. Il serait tentant, mais maladroit, d'introduire un type pour chacun de ces objets. Les terminaux et les non-terminaux correspondent à des valeurs à lire dans la séquence de caractères, ce sont donc des valeurs de notre type reader. Les suites de terminaux et non-terminaux de chaque règle sont par définition des combinaisons de terminaux et non-terminaux, il faut donc un opérateur de séquencement. Chaque non-terminal peut avoir plusieurs règles, il nous faut donc aussi un opérateur d'alternative. Quand à l'action, elle s'applique à une séquence, ou peut-être à un parseur, mais on peut légitimement penser qu'elle va être réalisée par un combinateur aussi.
L'alternative est le combinateur le plus simple. Il doit permettre un choix entre deux façons de parser, nous n'avons donc pas vraiment le choix pour son type :
On est bien parti pour avoir un monoïde avec un tel opérateur binaire. Il est associatif, il nous manque donc un neutre. Le neutre du ou est non, le neutre est donc le lecteur qui échoue tout le temps.
Passons à l'implémentation. or_else essaie le premier lecteur, s'il échoue il essaie le deuxième. 'value reader est TextInput.t -> ('value * TextInput.t) option on peut donc donner en troisième argument à or_else l'entrée de type TextInput.t.
On lit avec le premier lecteur, s'il échoue on lit avec le second. Dans une version plus avancée, il faudrait dans le cas où les deux échouent choisir de retourner celui qui échoue le plus loin dans la lecture.
fail est un lecteur, donc une fonction prenant une entrée. Elle échoue toujours, autrement dit elle retourne toujours None.
Le séquencement consiste à utiliser un lecteur pour lire une première valeur, puis utiliser un second lecteur pour lire une deuxième valeur, et produire un résultat à partir de ces deux valeurs. La principale interrogation est : quelle valeur retournée, en fonction des deux valeurs lues ? Une solution naïve serait de former un couple. Techniquement c'est réalisable, mais c'est une mauvaise idée. Potentiellement les séquences de lecteurs que nous pouvons vouloir écrire peuvent être arbitrairement longues. En couplant les résultats, sur une longue séquence de lecteurs, on va obtenir une longue imbrication de couples de couples de couples... La valeur obtenue au final ne sera pas pratique à utiliser.
La bonne façon de faire est la suivante. L'opération de base lorsqu'on a deux valeurs en programmation fonctionnelle, c'est d'appliquer l'une à l'autre. Autrement dit, on va supposer que la première valeur lue est une fonction, et que la deuxième est son argument. Cela peut paraître absurde car il n'y a pas de raisons que la première valeur que l'on souhaite lire soit une fonction, et il va effectivement falloir résoudre ce problème. Commençons néanmoins par écrire le combinateur.
Quel est son type ? On prend un lecteur d'une fonction, un lecteur d'un argument pour la fonction et cela nous donne un lecteur d'une image de la fonction.
Si la lecture de la fonction ou de l'argument échoue, la lecture de la séquence échoue. Sinon, les deux résultats sont combinés par une application et l'image obtenue est retournée. Comme précédemment, on cherche à construire un lecteur donc nous avons un troisième argument, l'entrée.
On utilise ici (>>=) qui permet d'appliquer une fonction au contenu d'une option, du moment que la fonction elle-même retourne une option. Autrement dit, (fct,remaining) est le contenu de l'option obtenue par fct_reader (si cette option est définie) et similairement (arg,final_input) est le contenu de l'option obtenue par arg_reader remaining_input.
L'avantage d'utiliser ce combinateur, qui combine les valeurs lues en applicant la deuxième comme argument de la première, est la bonne composabilité. Par exemple, si fct_reader : int -> int -> int et int_reader : int reader, on peut écrire :
On peut donc lire une fonction à $n$ arguments puis séquencer avec $n$ lecteurs, un par argument, tout cela simplement avec le combinateur (<*>).
Reste à résoudre la question de comment lire une fonction. En fait c'est très simple : en général, les fonctions ne viendront pas de la séquence de caractères à lire, mais du programme. On va donc faire semblant de les lire, avec une fonction construisant un lecteur à partir d'une valeur : ce lecteur consiste simplement à ne rien lire mais retourner sa valeur.
On peut maintenant écrire :
Il est même possible de simplifier le return avec le premier (<*>) :
(*>) n'est en fait rien d'autre que map (on peut interpréter cela comme une confirmation que cette façon de faire est la bonne). Et on a donc maintenant une jolie syntaxe pour ajouter des règles de dérivation à une grammaire.
Il nous manque une seule chose : de pouvoir lire des terminaux. Le plus basique est de lire des caractères, les autres terminaux pourront ensuite s'écrire par des grammaires en utilisant les caractères comme terminaux. Le plus simple est d'avoir plusieurs façons de lire les caractères :
Pour lire un caractère arbitraire, il suffit d'observer l'entrée et d'agir en fonction.
Les deux autres cas se construisent en rajoutant une condition sur la lecture. En fait, on peut vouloir mettre des conditions sur les lecteurs de façon plus générale, autrement dit avoir un combinateur de cette forme :
C'est assez facile : on lit, on vérifie la condition, sinon on retourne None.
Les deux autres lecteurs de caractères s'en déduisent facilement.
