Parsing de fichiers RIB avec Boost.Spirit

Dans la petite famille des parsers C++, Boost nous fournit une bibliothèque de grande qualité, nommé Spirit.
Spirit est un analyseur syntaxique LL, c'est à dire qu'il va parser l'entrée de gauche à droite et parser récursivement par la gauche (en anglais LL signifie Left to right -pour le parcours- et Leftmost derivation -pour préciser où se fait l'analyse récursive).
La syntaxe choisie par l'auteur se veut proche de la syntaxe EBNF (Extended Bachus-Normal Form); cette syntaxe est possible grâce à un usage poussé des templates C++.
Voici, tiré de la page d'introduction de cette bibliothèque, une syntaxe EBNF suivi de sa correspondance avec Spirit:

    group       ::= '(' expression ')'
    factor      ::= integer | group
    term        ::= factor (('*' factor) | ('/' factor))*
    expression  ::= term (('+' term) | ('-' term))*

    group       = '(' >> expression >> ')';
    factor      = integer | group;
    term        = factor >> *(('*' >> factor) | ('/' >> factor));
    expression  = term >> *(('+' >> term) | ('-' >> term));

Quelques concessions ont due être faites afin de coller à la syntaxe du C++ : les espaces signifiant un enchainement de règles sont remplacés par l'opérateur d'extraction de flux ('>>'), ou encore l'étoile servant à indiquer la présence de 0 ou plusieurs éléments répondant à une règle précéde la règle au lieu de la suivre.
En sus de cette syntaxe, Spirit permet de définir des actions sémantiques a exécuter lors du succès de l'analyse d'une règle:

    std::vector<double> v;
    
    numbers      = *(real_p[push_back_a(v)] >> *space_p);

Dans cet exemple, le vector v sera rempli de tout les chiffres présent dans l'entrée et séparés par un ou plusieurs espaces. Si l'entrée est "1 2 3.14 42 5", alors le contenu du vector v sera

    v[0] == 1,
    v[1] == 2,
    v[2] == 3.14,
    v[3] == 42,
    v[4] == 5

Les règles real_p (reconnaissance d'un réel) et space_p (tout caractère d'espacement), ainsi que l'action push_back_a (empilement de la valeur reconnue dans un conteneur exposant la méthode push_back()) sont fournies par Spirit. Nous reviendrons plus tard à tout ceci, ne paniquez pas si vous ne comprenez pas encore !

Pixar a publié en 1988 des spécifications permettant de standardiser un format de fichier entre applications de modélisations et systèmes de rendu désirant être compatible RenderMan. Cette spécification, nommée RenderMan Interface Specification, a depuis vu quelques mises à jours. La version actuelle est la 3.2.1 (datant de Novembre 2005) et est disponible sous la forme d'un PDF à cette adresse (la version 3.1 est consultable en ligne).

Ce document contient principalement 2 parties:

1. Interface RenderMan
2. Langage de Shading RenderMan

Nous allons nous intéresser à la première partie de ce document, l'Interface RenderMan. Cette interface formalise la description d'une scène 3D sous la forme d'un fichier texte (ASCII) ou binaire. La première forme sera celle que nous allons parser avec Boost.Spirit.
Cette description peut prendre la forme suivante:

# tutoriel.rib
# Exemple de fichier RIB
 
Display "exemple.tif" "file" "rgb"
Projection "perspective" "fov" 40
Format 320 240 1

ColorSamples [1 0 0 0 1 0 0 0 1] [1 0 0 0 1 0 0 0 1]

LightSource "distantlight" 1 "intensity" 1 
            "from" [1 0 0] "to" [0 0 1]

LightSource "ambientlight" 2 "lightcolor" [0.3 0.3 0.3]

# définition du placement de la caméra
Translate 0 0 5
Rotate 45 0 0 1
Rotate 5 0 1 0

WorldBegin
    # définition d'un (pseudo-) pacman :)
    Color 1 1 0
    Surface "plastic" "Kd" 0.75
    Sides 2
    Sphere 1 -1 1 280

    # Une grosse sphère grise entourant la précédente
    Color [.5 .5 .5]
    Surface "matte"
    Sphere 10 -10 10 360
WorldEnd

Dans le cas où vous voudriez vous initier à l'écriture de scènes sous ce format, il existe diverses implémentations compatibles RenderMan dont Aqsis ou encore Pixie (tout 2 des implémentations gratuites et open source).
L'image produite (Aqsis) par ce fichier est la suivante :

Ce tutoriel a pour but de parser le fichier RIB présenté ci-dessus grâce à Boost.Spirit. Le parser étudié au long de ce tuto sera capable de reconnaître les commandes utilisées dans ce fichier, non seulement pour les valeurs données ci-dessus, mais pour toutes les valeurs possibles pour les commandes utilisées.

Pour suivre ce tuto, je vous recommande de vous munir de la spécification RenderMan 3.2.1 ainsi que de garder la documentation de Spirit à portée de main.
L'affichage du résultat de ce fichier ne sera pas étudié dans ce tutoriel.

Lors de l'analyse de tels fichiers, il y a toute une infrastructure à avoir: gestion de la scène bien sûr, mais aussi des couleurs ou encore des transformations. Ces classes n'étant pas l'objet de ce tutoriel, elles n'y seront pas étudiées (sauf dans le cas où une connaissance approfondie d'une méthode est nécessaire à la compréhension de l'analyse syntaxique). L'archive fournissant le code final du tutoriel, disponible en fin de ce tutoriel, les contiendra mais rien n'est fourni pour l'affichage.

Voici une courte présentation des modules utilisés:

• math: contient les classes mathématiques nécessaires aux positions, aux informations de directions etc...
• rib: permet de charger un fichier rib, c'est le module qui nous intéresse ici; voici donc quelques infos supplémentaires
  • Loader: cette classe permet de charger un fichier et lancer le parsing
  • Syntax: cette structure définit la syntaxe d'un fichier rib, ainsi que les actions à entreprendre quand une régle correspond

Nous allons voir rapidement comment lancer l'analyse d'une chaîne de caractères (nous reprendrons l'exemple donné en ):

#include <algorithm>
#include <iostream>

#include <boost/spirit.hpp>

using namespace boost::spirit;
using namespace std;

int main(int argc, char **argv)
{
    const string input("1 2 3.14 42 5");
    vector<double> values;
    parse_info<string::const_iterator> pInfo = parse(input.begin(), input.end(),
                                                     *(real_p[push_back_a(values)] >> *space_p)
                                                    );

    copy(values.begin(), values.end(), ostream_iterator<double>(cout, "\n"));
        
    return 0;
}

Sur la ligne de commande, nous obtenons bien les 5 doubles contenus dans notre string:

1
2
3.14
42
5

Analysons d'un peu plus près la ligne qui s'est occupé d'analyser la chaîne:

    parse_info<string::const_iterator> pInfo = parse(input.begin(), input.end(),
                                                     *(real_p[push_back_a(values)] >> *space_p)
                                                    );

Nous passons ici à la fonction template boost::spirit::parse(...) 3 arguments:

1. IteratorT const& first : itérateur vers le premier caractère à analyser,
2. IteratorT const& last : itérateur vers le dernier caractère à analyser + 1,
3. parser<DerivedT> const& p : la règle servant à l'analyse.

Notons ici que cette fonction dispose d'une surcharge acceptant un paramètre optionnel qui est le parser skip. Lorsque la fonction est utilisée sans ce parser, l'analyse se fait au niveau du caractère (plus petit élément analysable). S'il est fourni, alors l'analyse est faite au niveau de la phrase. Le choix est fait ici de travailler par caractère car tout les caractères sont essentiels. En effet, si nous décidions de sauter les espaces et de procéder à une analyse par phrase, nous aurions obtenu la sortie 123.14425, car les espaces auraient été ignorés lors de l'analyse.
Par contre, si la syntaxe à analyser dispose de séparateurs clairs, alors l'analyse et l'écriture de règles sont plus simples au niveau de la phrase. Le C++, le C... sont tous des langages pouvant être analysés à ce niveau car les espaces et les commentaires ne sont pas utiles à l'analyse et les ignorer ne brise pas la syntaxe.

Après ce petit détour, revenons à notre analyse, et plus précisément au type de retour de parse(). La structure template boost::spirit::parse_info<IteratorT> doit avoir pour paramètre template le même type que les itérateurs spécifiés pour parse(). Cette structure nous donne quelques informations sur l'état de l'analyseur après l'analyse ; en voici sa composition:

• bool full : true si l'analyse a consommée tout les éléments fournis, false dans le cas contraire,
• bool hit : true si l'analyse a pu consommé au moins une partie de l'entrée, false dans le cas contraire,
• IteratorT stop : itérateur pointant vers l'élément où le parser s'est arrêté (input.end() si full est true),
• size_t length : indique le nombre de caractère(s) ayant été consommé par l'analyseur.

Il est donc aisé de fournir un retour minimal sur l'erreur (offset depuis le début de l'entrée, élément ayant causé problème) sans entrer dans d'autres détails (un code illustrant ceci sera donné plus bas).

Voyons maintenant le coeur de l'analyse, la règle :

    *(real_p[push_back_a(values)] >> *space_p)

Qu'est-ce donc que cet enchaînement cryptique ? Cette règle se décompose en plusieurs éléments:

• real_p : cette règle permet de reconnaître des nombres réels (des doubles plus précisément),
• space_p : il s'agit d'une règle qui saura reconnaître tout type d'espacements (espaces, tabulations, retours chariot et nouvelles lignes)
• push_back_a : il s'agit d'une action sémantique qui va ajouter l'élément au conteneur passé en paramètre (le conteneur doit disposer de la méthode push_back(), et les objets contenus doivent être du type de ce que la règle va renvoyer)

Spirit suit une convention de nommage qui permet d'identifier facilement plusieurs éléments :

• ce qui finit par _p (real_p, space_p...) correspond aux analyseurs fournit avec Spirit,
• ce qui finit par _a (push_back_a, assign_a...) correspond à des actions sémantiques

Le principe des actions sémantiques est d'exécuter du code lorsque la règle à laquelle l'action est rattachée est analysée avec succès. Ce rattachement est signifié en l'écrivant entre crochets, après la règle qui lui est liée. Les actions sémantiques sont en quelque sorte des wrappers vers du code à exécuter car ils ne sont pas utilisés immédiatements. Pour cette raison, il ne faut pas utiliser une fonction normale directement: real_p[values.push_back] ne compilera pas!

Nous savons que nos chiffres sont séparés d'au moins un espace, sauf le dernier élément. Cet enchaînement est signifié par l'utilisation de l'opérateur >> qui indique qu'une règle, si elle est matchée, est suivi d'une autre régle. La quantité d'espacements étant variables, nous utilisons ici l'opérateur * qui indique que la règle qui suit immédiatement peut être répétée 0 ou n fois.
Dernier point, nous ne savons pas combien de couple "réel/espacement(s)" nous avons dans la chaîne. Il est donc nécessaire de la répéter 0 ou n fois elle aussi, mais comment faire ? Une règle peut être créée par une combinaison de plusieurs règles entourées de parenthèses. Par déduction, faire précéder notre règle nouvellement créée par l'opérateur * permet de formaliser cette répétition éventuelle.

Analyser une chaîne, c'est bien pratique, mais comment analyser un fichier texte ?
La librairie Spirit fournit à cet effet un itérateur bien particulier, j'ai nommé file_iterator. Il différe des itérateurs fournis par la STL en ceci qu'il n'est pas seulement un input iterator, mais surtout un random access iterator. Les input iterator ne peuvent être utilisés avec Spirit dû à sa méthode d'analyse. Voici comment l'utiliser:

#include <boost/iterator/file_iterator.hpp>

typedef char                     char_t;
typedef file_iterator<char_t>    iterator_t;
(...)
string filepath("file.txt");
iterator_t fileStart(filepath);
if (!fileStart)
{
    cout << "Impossible d'ouvrir " << filepath << " !" << endl;
    return;
}

iterator_t fileEnd = fileStart.make_end();
parse_info<iterator_t> pInfo = parse(fileStart, fileEnd, *(real_p >> *space_p));

Un file_iterator doit être paramétré par le type de base qu'il est sensé lire à partir du fichier. Le constructeur prend 3 formes:

• file_iterator() : le constructeur par défaut construit un itérateur invalide,
• file_iterator(std::string filename) : ce constructeur accepte le nom du fichier à ouvrir,
• file_iterator(const base_t& iter) : ce constructeur accepte une référence vers le type de base défini (dans l'exemple, un char_t, c'est à dire, un char.

Si le fichier a pu être ouvert, alors l'itérateur est valide. La création de l'itérateur marquant la fin de l'entrée se fait en appelant la méthode file_iterator<>::make_end().
Il ne reste plus qu'à passer ces 2 itérateurs à la fonction parse, et le tour est joué!

Avant d'entrer dans le vif du sujet, il nous faut un moyen de savoir à quel endroit de la chaîne l'analyse échoue. Le debugger pourrait l'indiquer, mais l'obtension de la ligne ayant fait échouer l'analyse peut être un peu laborieux, sans compter que des erreurs de ce type, au cours de la rédaction d'une grammaire, on en rencontre souvent :)
Voici donc le snippet que j'utilise après un appel à parse pour indiquer le lieu de l'erreur:

    if (!pInfo.full)
    {
        if (pInfo.hit)
            cout << "Erreur d'analyse (offset " << pInfo.length << ") a la ligne: \"";
        else
            cout << "Erreur d'analyse (offset 0) a la ligne: \"";

        while (*pInfo.stop != 0 && *pInfo.stop != '\n' && *pInfo.stop != '\r')
        {
            cout << *pInfo.stop;
            ++pInfo.stop;
        }
        cout << "\"" << endl;
    }