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 !