Nous terminons avec un exemple plus complet. Ce serait ambitieux de vouloir parser un langage de programmation complet, on va donc se contenter d'un sous-langage contenant déjà les principales difficultés : les expressions arithmétiques. Nous allons aussi utiliser des combinateurs un peu plus complexes, notamment capable de reporter plus précisément les erreurs, en indiquant quels règles ont été utilisées jusqu'à la situation d'échec.
Nous allons donc considérer les expressions arithmétiques, construites comme des sommes et des produits d'entiers et de variables. Nous pourrions considérer plus d'opérateurs, des nombres flottants, des fonctions, mais cela ne changerait pas fondamentalement le problème.
Commençons par donner une représentation des expressions arithmétiques. Cette représentation servira d'arbre abstrait pour le langage des expressions arithmétiques. Les arbres abstraits sont en général représentés en OCaml pour un type algébrique inductif :
Nous allons avoir besoin de la fonction de conversion des listes de caractères vers les chaînes de caractères :
On définit ensuite les actions qui seront appliquées à chaque règle de la grammaire. Le produit et la somme prennent un argument qui correspond à l'opérateur arithmétique, mais cet argument n'est pas utilisé.
Nous allons, par convénience et pour un maximum de lisibilité, définir des règles pour les terminaux correspondant aux symboles utilisés dans les expressions arithmétiques : les opérateurs et les parenthèses. On donne un nom à chaque règle de dérivation, pour avoir des explications les plus complètes possibles lors de la détection d'une erreur.
Nous passons maintenant au cœur de la grammaire. Les littéraux entiers seront traitables directement avec le parseur d'entiers défini plus tôt. Nous devons donc faire un parseur pour les variables, qui sont des séquences des lettres et de chiffres, commençant par une lettre :
Nous avons les éléments principaux pour mettre en place la grammaire du langage. Il reste néanmoins une difficulté : gérer les règles de parenthésages, les précédences entre opérateurs. Une façon classique de le faire est décrire la grammaire en séparant les expressions générales, les termes (qui sont sommés) et les facteurs (qui sont multipliés). On obtient alors trois non-terminaux avec plusieurs règles de dérivation pour chacun.
Un souci est que toutes ces règles sont mutuellement récursives, et OCaml n'autorise pas certaines formes de récursions. Toute valeur récursive doit soit être une fonction (donc prend un argument), soit commencer par un constructeur. Ici, on choisit d'ajouter un argument inutile à chacune des fonctions pour satisfaire à la règle. Hormis ce détail technique, nous obtenons bien une grammaire. Chaque règle est introduite en lui donnant un nom, puis une action et une séquence de non-terminaux.
Faisons quelques tests, essayons d'abord de lire une expression correcte :
Impeccable. Essayons maintenant avec une expression mal-formée :
L'erreur est détecté au 15 e caractère. Très précisément, il nous dit que le parseur a utilisé la règle sum à partir du caractère 1 , la règle d'un terme à partir du caractère 4 , etc, et il attend donc une parenthèse fermante au caractère 15 , à la place du 4 . Il a bien repéré l'emplacement de l'erreur de syntaxe, mais surtout il nous indique précisément comment il a compris le texte donné.
La fonction show_stack utilisée est la suivante :
L'ensemble du programme est dans cette archive.
