04 sept. 2012

Modification du générateur de parseurs Coco/R

Cet article est une mise à jour d'un ancien article qui avait disparu de ce blog pour de mystérieuses raisons. Avant sa disparition, il est resté en lignes environ un mois, donc il est probable que peu d'entre vous ait eu le temps de le lire. Vous pouvez maintenant en profiter.

Coco/R, développé par Hanspeter Mössenböck, Markus Löberbauer et Albrecht Wöß de l'Université de Linz est un générateur de compilateurs LL(1). Il permet, avec un seul fichier, de créer un couple scanner/parser intégrable en C++, C#, Java et bien d'autres langages encore. L'intérêt du compilateur généré est qu'il est complètement orienté objet : il ne s'agit pas d'un code procédural qu'il faut tenter d'encapsuler au mieux, comme celui qui pourrait être généré par flex+bison. Le code source généré souffre de quelques problèmes - mais au regard du service rendu, on laissera ceux-ci de coté pour l'instant.

Cet article traite d'une modification que j'ai du effectuer dans le code du générateur lui-même, afin de traiter un cas qui n'était pas prévu par les développeurs. Je me suis basé sur la version C++ datée de Novembre 2010 (la dernière version du code source est disponible sur la page web de Coco/R).

Vision d'ensemble du générateur

Coco/R est composé d'un générateur d'automates fini déterministes et d'un générateur d'analyseur syntaxique (tous deux sont basés sur un moteur de génération de fichiers basés sur des patrons : les fichiers *.frame). Les données utilisés par ces générateurs sont récupérées grâce à un analyseur lexical et syntaxique intégré (et lui-même généré avec Coco/R).

Le principe de génération est le suivant :

  1. Lecture de la grammaire (fichier ATG).
  2. Analyse lexicale et syntaxique.
  3. Construction des automates pour la génération du scanner
  4. Génération du scanner
  5. Construction des automates pour la génération du parseur
  6. Génération du parseur

L'un des points intéressant dans ce travail est que contrairement à beaucoup d'autres produits, le parseur n'est pas basé sur des tables, mais est entièrement géré par le code. Ainsi, soit une production type :

production = nombre ( "+" nombre | "-" nombre) .

Cette production va être transformé dans un code ressemblant à :

fonction production()
  nombre()
  suivant = get next token()
  si (suivant == "+")
    expect (terminal "+")
    nombre()
  sinon si (suivant == "-")
    expect (terminal "+")
    nombre()
  sinon 
    erreur de syntaxe ("+ ou - attendu")
  fin si
fin fonction

Une production se servant d'une production va être transformé en une fonction appelant une autre fonction. Au final, le code est extrêmement simple à suivre et à déboguer : on sait où il faut mettre les points d'arrêt dans le code généré pour vérifier le fonctionnement du parseur.

Le scanner est quand à lui toujours basé sur des tables, mais dans un soucis d'efficacité.

Bien sûr, comme dans tous générateur de compilateur qui se respecte, on peut ajouter ici et là ce qu'on appelle des actions sémantiques, c'est à dire du code qui sera exécuté à un moment précis. Les actions sémantiques sont exécutées dans le contexte de fonction correspondant à la production impactée.

Je tiens à ajouter que les fichiers d'entrée au format ATG sont très simple à lire et à comprendre. Les expressions rationnelles utilisées ne sont pas celles de Perl ou d'autres langages : il s'agit d'une version très simplifiée que les auteurs ont choisi d'utiliser de manière uniforme. Ainsi, les lexèmes sont définis en utilisant la même syntaxe que les production:

  • [ X ] = 0 ou 1 occurrence de X
  • { X } = 0 ou plusieurs occurences de X
  • X | Y = X ou Y
  • X Y = X, puis Y
  • ( X ) = X (utiliser pour factoriser certaines définitions.

Malgré son apparente simplicité, ce langage est très puissant. Pour plus d'information, référez vous au manuel utilisateur de Coco/R (pdf).

Le problème

Le problème que j'ai rencontré est simple : si je simplifie un peu le débat, Coco/R prends sur lui de décider qu'il existe un caractère particulier (le caractère espace), et que ce caractère ne peut pas être traité par le parseur généré. Supposons que je crée un parseur de fichier pseudo-XML :

COMPILER SimpleXml
CHARACTERS letters = "abcdefghijklmnopqrstuvwxyz". number = "0123456789".
TOKENS tagname = letter { letter | number }. tagb = "<". tage = ">". tagbclose = "</". tageclose = "/>".
// IGNORE nothing
PRODUCTIONS SimpleXml = Tag. Tag = tagb tagname ( tageclose | tage TagList tagbclose tagname tage ). TagList = ( ANY | Tag ) { TagList }.
END SimpleXml.

(Il est possible que cet exemple ne soit pas complètement correct au niveau syntaxique. Je vous présente mes excuses par avance).

Le symbole ANY permet de valider n'importe quel caractère/ Ainsi, à l'intérieur d'un tag, on a soit du texte simple, soit d'autres tags. Aucun caractère spécial n'est ignoré (pas de clause IGNORE dans le fichier; ainsi, tous les caractères sont considérés. Tous, sauf le caractère espace, ainsi que je l'ai précisé auparavant.

Cela peut ne pas vous sembler cruel ; cependant, voyons ce que ça donne avec une simple règle sémantique permettant d'écrire sur la sortie standard tout ce qui n'est pas un tag.

TagList = (  (. std::wcout << la->val; .) ANY | Tag ) { TagList }.

Et exécutons le code généré sur l'entrée suivante :

<xml>Ceci est un test</xml>

Normalement, nous devrions obtenir la chaine "Ceci est un test". Mais en fait, nous obtenons "Ceciestuntest". Ça ne serait pas grave si cette chaîne n'avait pas de signification particulière, mais dans ce cas, pourquoi la stocker ? Non : il nous faut présumer que tout caractère est important, y compris les caractères blanc.

Il est relativement aisé de modifier le code source de Coco/R pour changer de manière drastique le comportement du scanner généré. Il suffit de supprimer le code ch == ' ' dans la méthode Scanner::NextToken() du fichier Scanner.frame. Le problème est alors que, le caractère ' ' n'étant plus ignoré, il faut le faire apparaitre explicitement dans les différentes productions si besoin - ou le mettre dans une clause IGNORE, ce qui nous ramène à l'existant. Si je penses par exemple que le tag "< xml >" est valide, alors il faut que je change ma grammaire ainsi :

Tag = tagb { " " } tagname { " " } ( tageclose | tage TagList tagbclose { " " } tagname { " " } tage ).

On obtient très rapidement une grammaire illisible, mais au final, on a bien tous les caractères souhaités dans notre chaîne.

Vers une meilleure solution

Pourrait-on imaginer une meilleure solution, qui me permettrais d'ignorer le caractère espace dans un contexte déterminé et de ne pas l'ignorer dans le cas général ? Lorsque j'analyse les tag, j'aimerais ignorer les espaces. Lorsque je suis à l'extérieur d'un tag, alors les espaces sont importants. J'ai clairement deux contextes différents, que je suis tout à fait en mesure de contrôler :

  • dès que je rencontre les tokens "<" ou "</", alors je suis dans le contexte tag.
  • lorsque je rencontre ">" ou "/>" alors je quitte le contexte tag.

Grâce à des actions sémantiques, je peux tout à fait traiter ces cas (J'ai éclairci le code pour en simplifier la lisibilité) :

Tag = (. enter_tag_context(); .) 
      tagb 
      tagname
    ( tageclose (. exit_tag_context(); .) 
    | tage (. exit_tag_context(); .) 
      TagList 
        (. enter_tag_context(); .)
      tagbclose 
      tagname 
      tage (. exit_tag_context(); .)
    )
    .

Reste a tester ce contexte lorsque je lis chaque caractère. Un nouveau problème se pose : les actions sémantiques sont exécutées dans le contexte de l'instance de l'analyseur syntaxique, tandis que le test des caractères est exécuté dans le contexte de l'instance de l'analyseur lexical. Plus ennuyeux, je peux rajouter du code dans la classe Parser générée, mais pas dans la classe Scanner.

En fait, à mieux y réfléchir, j'ai les besoins suivants :

  • Sans clause spécifique dans mon fichier ATG, je ne dois pas changer le comportement actuel de Coco/R. C'est nécessaire si je veux respecter l'existant.
  • Une clause spécifique doit me permettre de modifier de manière arbitraire le comportement du système généré par Coco/R en ce qui concerne le traitement des caractères spéciaux (et notamment " ").

La clause IGNORE actuelle permet de modifier la liste des caractères ignorés. Par défaut, cette liste est vide, et le caractère " " est ignoré. Je peux rajouter tous les caractères souhaités à cette liste (IGNORE ch + ch + ...) ; ils seront alors traités de la même manière que le caractère espace. Puisque c'est ce comportement que je souhaite changer, il est logique que je m'appuie sur le fonctionnement actuel de IGNORE afin de l'étendre. De plus, Coco/R fournit déjà une méthode pour injecter du du code arbitraire dans le parseur généré : les actions sémantiques ont déjà une grammaire définie, et il semblerait logique de la réutiliser.

C'est la solution que j'ai finalement implémenté : j'ai augmenté la grammaire des fichiers ATG pour que la construction IGNORE (. code .) soit possible. Le code ainsi spécifié n'est pas ajouté dans la classe Scanner, mais dans la classe Parser (un mécanisme de retour d'appel a été ajouté pour permettre cette opération). Dans le parseur que j'ai du générer, ma clause IGNORE est semblable à celle ci :

IGNORE (. return (in_specific_context() ? ch == ' ' : false); .)

Cette action sémantique peut être aussi complexe que souhaitée, mais elle a l'obligation de renvoyer un booléen. En paramètre, on a un entier ch qui correspond au caractère qui est testé.

Conclusion

Le code complet de la nouvelle version de Coco/R C++ est attaché à cet article. Vous pouvez le télécharger et expérimenter cette fonctionnalité. A noter que cette fonctionnalité peut servir dans de nombreux cas : parseur XML / HTML, pré-compilateur (par exemple, un pré-compilateur C), langage de script intégré dans un autre fichier (par exemple du PHP au milieu de code HTML), etc. Les applications sont nombreuses.

A vous de voir !

Commentaires

1. Le mercredi, février 23 2011, 12:24 par neilbgr

Bravo et merci pour la publication de ce boulot !
Avez-vous remonter cette suggestion aux développeurs d'origine (histoire d'éventuellement d'avoir une mise à jour pour les autres langages...) ?

2. Le jeudi, février 24 2011, 10:11 par Emmanuel Deloget

J'ai remonté l'info, et proposé un patch. Je ne sais pas si le code va être adopté pour les prochaines releases de Coco/R (j'aimerais bien ; cette fonctionnalité ne coute rien, et elle permet de modifier le comportement du scanner selon un contexte défini par le programmeur. Ceci dit, je ne suis pas sûr que ça fasse partie des plans des développeurs).

3. Le lundi, mars 14 2011, 14:38 par Brice

Salut Emmanuel,

Le fait que les parsers LL sont fait pour travailler sur des grammaires non contextuelles. En plus de ça Coco/R produit un code de type LL(1), donc le parser généré ne peut regarder que le prochain symbole pour décider de quelle type de construction il s'agit. Avec un parseur LL(k) tu peux déjà faire plus de chose parce que le parser peut regarder un peu plus loin.

Je ne suis pas sur que XML soit completement context-free, c'est peut-être pour ça aussi que je n'ai jamais vu de parser XML de type LL, mais toujours avec des approches DOM ou SAX. Mais je peux me tromper sur ce sujet.

Ce que tu fais me rappelle un peu les tweaks qu'il y avait dans GCC (partie C++) pour essayer de gérer les productions ou il y avait un contexte.

Sinon autre chose as tu essayé Spirit, c'est un générateur de parser directement en C++, ça fait aussi partie de la lib Boost, je n'ai pas trop eu le temps de regarder ce que ça valait, ça fait un bail que je n'ai plus fait de C++. Le projet est maintenu etc., et à l'époque ça avait l'air pas mal.

[http://boost-spirit.com/home/]

4. Le mardi, mars 15 2011, 14:44 par Emmanuel Deloget

Hello Brice,

Je sais tout ça (un de mes projets d'école il y a 12-13 ans traitait justement des grammaires LL(k), LR(k) et tout le toutim), et je dirais même que c'est ce qui m'a fait utilisé Coco/R : parseur LL(1) qu'on peut transformer en LL(k) (k petit) par le jeu des conditions qu'on peut appliquer à n'importe quel symboles. C'est ce coté qui m'a séduit, autant que le fait que le code généré soit orienté objet.

Sur le XML, il n'y a pas photo : le fait que le traitement des chaines entre tag (ou les caractères blancs peuvent être ou non importants (CDATA impose que tous les caractères soient importants, tandis qu'en temps normal, seul le caractère 0x20 (espace) a une signification) soit différent du traitement des chaines dans les tags (ou les espaces ne sont pas importants) montre clairement que la grammaire n'est pas context free.

Sur ce projet, je n'ai pas souhaité introduire boost - outre le fait que je n'apprécie pas cette librairie, ce qui devrait faire le sujet d'un futur billet entièrement dédié à ce sujet, il y a aussi le fait qu'utiliser un système débuggé pour contrôler la génération d'un parseur est un avantage considérable face à l'utilisation de boost.spirit et le besoin implicite que j'aurais de debugger moi même un code nettement plus complexe que j'aurais nécessairement écrit. Les erreurs produites par spirit sont moins explicites que les erreurs produites par un système dédié. Le fichier Coco/R est d'environ 100 lignes en comptant les lignes blanches ; avec boost.spirit, je pense qu'il m'aurait fallu 200 à 300 lignes pour faire la même chose ; quand au code de Coco/R, il est généré en bonne partie par Coco/R : à l'heure actuelle, j'ai une règle dans mon Makefile qui génère une version modifiée de Coco/R avant de générer le parseur dont j'ai besoin. Modifier boost a un impact autrement plus important, et aurait nécessité l'intégration dans notre système de version d'une version particulière de boost (avec tout ce que cela implique). Au delà de ces considérations, boost.spirit reste une solution parfaitement envisageable dans un contexte industriel, mais hélas difficile à mettre en oeuvre avec les contraintes que j'avais.

Ceci dit, le principe est quand même que boost.spirit est une très bonne librairie (en passe d'être supplantée par une solution encore supérieure ; mais boost.spirit est très bien). Si vous avez un parseur C++ a écrire, il serait anti-professionnel de ne pas considérer cette librairie.

Tu a cependant parfaitement raison lorsque tu parles de tweak ; à l'heure actuelle, je ne sais toujours pas si ma proposition de modification (qui ne coûte pas grand chose) va être accepté par les développeurs de Coco/R ; il faut les comprendre : Coco/R doit son existence à une recherche spécifique - d'une part sur la détection des conflits LL, et d'autre part sur le sujet des conditions qui permettent de transformer gratuitement un parseur LL(1) en parseur LL(k), qui permettent de résoudre ces conflits. Cette recherche étant "terminée", les développeurs maintiennent le système sans pour autant en faire un logiciel dynamique. Les percées de AntLR rendent les parseurs LL(k) un peu obsolètes : AntLR est un générateur de parseurs LR* (une heuristique déterministe a été développé en ce sens), capables de gérer des grammaires qui ne sont pas context-free (grâce à un système similaire aux conditions permettant de transformer le parseur LL(1) en parseur LL(k) dans Coco/R, et donc de prendre en compte le contexte en cour de route). S'il est convenu que la recherche sur les parseurs LL(k) ne doivent pas être abandonnées tant qu'on ne les maîtrise pas à 250%, en pratique, il est plus utile de travailler sur des systèmes plus évolués (pour ceux qui se posent la question : les grammaires LL(k) sont naïves et difficiles à écrire ; j'ai moi-même proposé de modifier Coco/R pour qu'il puisse résoudre de manière automatique certains conflits classiques en LL (notamment la réduction impossible en cas de récursivité à gauche), mais cette proposition est plus ou moins restée lettre morte (je ne souhaite cependant pas éliminer cette idée). Si Coco/R est un jour abandonné par l'université de Zurich, ce que je ne suis pas loin de souhaiter, je serait tout à fait prêt à en reprendre la maintenance - le produit lui même est très intéressant, principalement parce qu'il génère un code simple et aisément débuggable, parce que les fonctionnalités offertes mériterait un coup de jeune, et aussi parce que son architecture mériterait de subir quelques légères et sympathiques évolutions.

Ajouter un commentaire

Les commentaires peuvent être formatés en utilisant une syntaxe wiki simplifiée.

Fil des commentaires de ce billet