Journal quick start pour coco/R

Sommaire

• choix de coco/R
  • autres fonctionnalités
  • mais ou est la doc?!?
• quick-start
  • fichiers d'exemple
  • compilation et usage
• explications
  • quelques termes utilisés
  • cococpp
  • syntaxe du fichier source
    • commentaires
    • sections
      • COMPILER:
      • IGNORECASE:
      • CHARACTERS:
      • TOKENS:
      • PRODUCTIONS:
      • PRAGMAS:
      • COMMENTS:
      • IGNORE:
    • nom du langage
• conclusion

Salut.

Ces derniers jours, je me suis mis en tête d'apprendre a cesser d'écrire des parseurs à la main, qui est quelque chose d'assez pénible a mes yeux, surtout quand il s'agit de parser du texte dont on ne peut prévoir la taille totale dès le début.

Je préfère prévenir:

1. ce journal n'est pas le point de vue d'un expert, et reflète certaines de mes opinions sur divers points, qui ne sont pas nécessairement les plus répandues ni les plus pertinentes.
2. ce journal s'adresse aux gens qui ont des notions de C++ et connaissent la notation BNF
3. la plupart des liens sont en http
4. mon clavier est merdique, parfois les frappes ne passent pas, parfois elles passent en double, notamment pour la barre d'espacement. Évitez d'acheter le K280e de logitech: c'est de la merde (mais il me fallait un clavier rapidement et il ne coûtait pas trop cher: ~30€).
5. les informations contenues sont issue de la pratique et de la lecture du source, principalement. Je manque encore de recul et d'expérience, donc tout ne sera pas nécessairement exact ou précis.

choix de coco/R

La solution la plus «simple» pour ça est d'utiliser un compilateur de compilateur, le couple UNIX lex/yacc et son couple de clones flex/bison étant probablement les plus célèbres (en tout cas, ça fait pas mal d'années que je les connais de nom).

Après quelques recherches sommaires la semaine dernière, j'ai appris qu'il en existe d'autres et j'ai jeté mon dévolu sur coco/R pour plusieurs raisons (basées sur des à-priori hein):

• il est implémenté en C++, pas besoin d'installer le support d'un langage (pas de JVM ou autres nécessaire, juste libstdc++ qui est de toute façon déjà installée sur toutes mes machines);
• c'est un logiciel sous GPL modifiée, mais il est spécifié explicitement que la GPL ne s'applique pas au code généré;
• il est présent dans les dépôts de ma distribution préférée;
• il prétend utiliser la notation EBNF. Je dis bien: prétends;
• un avis positif dessus trouvé sur stackoverflow (qui m'a fait le connaître en vrai);

autres fonctionnalités

Personnellement ça ne m'intéresse pas plus que ça, mais coco/R peut générer du code en Java et en C# en plus de C++.
En fait, je pense que l'outil a d'abord été écrit en C# pour Windows, opinion tirée de la construction du manuel utilisateur et des choix dans le code (l'usage de wchar_t notamment, qui me rappelle la winapi).

Il y a aussi le jargon dont je ne comprend pas vraiment les implications techniques, notamment il use une analyse LL(1), en gros (de ce que j'ai compris):

• une seule passe pour parser
• une fenêtre d'un seul «token»

Il est aussi possible de remplacer le «tokenizer» de coco/R par un autre, soit codé à la main (mais pourquoi faire?) soit lex ou autre.

mais ou est la doc?!?

Sauf que, apprendre à l'utiliser (et je n'ai encore que les bases) n'a pas été simple:

• le manuel n'est selon moi pas hyper clair, il n'y est même pas indiqué comment invoquer l'outil!
• l'un des tutoriels est une présentation powerpoint (en vrai j'ai réussi a trouver un pdf sur le net, mais j'ai perdu l'adresse désolé) et l'autre est plus un tas de tests unitaires sans explications, y compris sans indiquer quel outil est censé compiler ces foutus tests unitaires! Sérieux, faut arrêter avec "les TU c'est de la doc" c'est des foutaises ça!
• le dossier "examples" fournit ne contiens en vrai que des tests unitaires, sans la moindre instruction de comment générer un exécutable. D'ailleurs, la plupart ne compilent pas. Dans mes notes, j'ai écrit: conclusion: this sucks.
• pas vraiment de manpage. Allez, pour le fun, je vous la colle ici (elle est pas très grosse):

.TH cococpp 1 "Jan 02, 2012" "Coco/R Compiler Generator (C++ Version)"

.SH NAME
cococpp \- Coco/R Compiler Generator (C++ Version)

.SH HINT

By default cococpp expects the Parser.frame and Scanner.frame file to be
in the same directory as the grammar (atg-file) to translate. As the 
frame files are architecture independent, the default frame files can be
found in /usr/share/coco-cpp/.

.SH SEE ALSO

See package coco-doc for documentation.

Du coup, en jonglant avec les 2 tutoriels, le manuel utilisateur, et le code source, j'ai fini par réussir à comprendre le fonctionnement de base et a me constituer un petit fichier de notes personnelles, sur lesquelles je me base pour écrire ce journal, que j'espère être un «quick-start» plus efficace que ce que j'ai pu trouver.

quick-start

Le programme que je vais mettre ici est un exemple dont la seule utilité est de montrer comment utiliser coco/R: il s'agit de parser cough une ligne de commande bash cough et d'indiquer pour chaque option le nom de l'option et sa position dans la ligne.
Comme je l'ai dis, c'est super utile… (j'aurai été plus vite à l'écrire directement en C, clairement)

fichiers d'exemple

Voici donc le fichier nommé cmdline.atg (pour info, vim a une coloration syntaxique pour les fichiers .atg mais pas .ATG je l'ai découvert en lisant le code source de cococpp):

/* place includes here! */

COMPILER argv

/* IGNORECASE */ /* optional: makes compiler case-insensitive*/

/* place Parser.h custom attributes/methods here */

CHARACTERS

/* place character set definitions here */
digit = '0'..'9' .
alpha = 'a'..'z' + 'A'..'Z' .
stringch  = ANY - '"' - '\\' - '\n' - '\r' .

TOKENS

/* place terminal symbols here */
identifier = alpha {digit|alpha} .
integer    = [ '+' | '-' ] digit {digit} .
decimal    = '.' {digit} .
string     = '"' { stringch | '\\' printable } '"' .

PRODUCTIONS

argv =
    identifier
    { option }
    .

option =                     (. static int foobar = 0; .)
    "--" option_name<foobar>
    [ "="
        (
                string
            | integer { decimal}
            | identifier
        )
    ]   (. ++foobar; .)
    .

option_name<int &foobar> =
    (
            "help"
        | "version"
        | identifier
    )                          (. printf( "%S found as option number %d\n", t->val, foobar ); .)
    .

END argv .

Et bien entendu le très complexe fichier main.cpp qui va avec:

#include "Parser.h"

int main()
{
    Scanner scanner( stdin );
    Parser parser( &scanner );
    parser.Parse();
    return 0;
}

compilation et usage

Avant toute explication, commençons par générer un binaire avec ça:

mkdir generated_code
cococpp -frames /usr/share/coco-cpp -o generated_code cmdline.atg
clang++ main.cpp generated_code/*.cpp -o cmdline

J'aurai aimé écrire un Makefile pour ça, mais mes essais se sont tous soldés par un échec. Je verrais sûrement ça plus tard.

Et un exemple d'usage: printf 'foo --bar="" --bla=+1.5 --version --str="hello world" --version --help | ./cmdline

qui donne:

bar found as option number 0
bla found as option number 1
version found as option number 2
str found as option number 3
version found as option number 4
help found as option number 5


Voila pour ce qui est d'avoir un truc avec lequel on peut jouer. Ce n'est certes pas une méthode très académique, mais c'est comme ça que je marche le mieux moi.

explications

Étant une suite complète pour écrire des compilateurs, coco/R mêle le «tokenizer» et le «parser».

quelques termes utilisés

Vu que c'est un sujet assez spécifique, il y a quelques termes techniques, que je ne prétend pas comprendre très bien, le mieux est encore d'aller se documenter sur wikipedia, mais quelques définitions ne peuvent pas faire de mal:

• stream/flux: source des données à parser
• token: bloc de données reconnu, autrement dit, un «mot» (je n'ose utiliser de terme genre lexème, je risque de me planter comme une merde)
• symbole terminal: élément reconnu par le langage (dont on écrit le compilateur)
• symbole non-terminal: euh… disons que c'est, en gros, entre le token et le symbole terminal? Un élément dont l'analyse grammaticale est en cours, mais pas finie.
• production: règle qui permets de traiter un token

cococpp

La commande cococpp sans paramètres indique les possibilités, mais je n'ai pas trouvé plus de documentation sur le sujet, je me suis contenté de ce que j'avais et d'expérimentations.

Pour rappel, la commande qui génère les fichiers est cococpp. Voici les arguments que j'ai utilisés:

• -frames /usr/share...: il s'agit de l'endroit ou cococpp va chercher les fichiers qui servent de modèle pour générer les fichiers finaux: Parser.frame et Scanner.frame
• -o generated_code: l'endroit ou les fichiers seront générés
• cmdline.atg: le nom du fichier à compiler

En cas de succès, la commande va générer 4 fichiers:

• Parser.cpp
• Parser.h
• Scanner.cpp
• Scanner.h

En cas d'échec, un fichier traces.txt est généré, probablement pour aider à résoudre le problème.

syntaxe du fichier source

Le fichier atg me semble assez lisible dans l'ensemble, mais quelques précisions me semblent nécessaires.

commentaires

Comme vous l'aurez noté, les commentaires utilisés dans le source sont de type C: /* bla */. Il est peut-être possible d'utiliser ceux du C++ aussi (//).

sections

Le fichier est composé de plusieurs «sections», plusieurs d'entre elles sont optionnelles (notamment certaines que je n'ai pas utilisés dans l'exemple):

COMPILER:

Contrairement a ce que je pensais au début, ce n'est pas nécessairement le 1er élément du fichier: il est possible de mettre du code avant, qui se retrouveras dans les premières lignes du fichier "Parser.h", entre le header guard et #include "Scanner.h"

Il est aussi possible d'insérer du code après, qui sera inséré en tant que code public dans class Parser. Mieux vaut expérimenter ou lire le code/la doc plutôt que de se fier a mes mots sur ce coup, par contre.

IGNORECASE:

Optionnel. Si présent, indique que le langage généré ne prendra pas compte de la casse.

CHARACTERS:

Définit des jeux de caractères qui peuvent être réutilisés dans les autres sections. Je ne me souviens plus s'il est possible d'utiliser un jeu précédemment défini dans un nouveau jeu, mais personnellement si c'est possible, je n'en vois pas l'intérêt.

Le mot-clé ANY représente n'importe quel caractère encodé sur 2 octets, comme tous les caractères d'ailleurs, puisqu'on travaille avec wchar_t.

La syntaxe est un dérivé d'EBNF.
Je suis quasi-sûr qu'EBNF n'implémente pas les opérateurs + et -, par exemple. Il faudrait que j'aille vérifier… ce qui est sûr, c'est que l'opérateur | par exemple n'est pas supporté. Toujours est-il que ça reste simple et lisible je trouve.

J'ai utilisé 5 «opérateurs»:

• =: affectation, attribue une règle a nom
• ..: éventail de valeurs, «range» comme on dit de l'autre côté de la mer (si vous avez une meilleure traduction, je suis preneur par contre)
• +: union
• -: exclusion
• .: fin de la règle

Il est possible d'utiliser le \\ comme en C pour les caractères spéciaux ou des valeurs binaires brutes.

TOKENS:

Syntaxe de type EBNF.

Cette section décrit les symboles terminaux (selon mes notes), c'est à dire soit les éléments littéraux comme les opérateurs et les mots-clés d'un langage, soit les «classes» qui permettent de définir un symbole, par exemple comment on définit un nom de variable.

PRODUCTIONS:

Il s'agit des règles qui permettent d'exécuter du code lors de détection d'un token précis.
La syntaxe est ici encore de type EBNF, mais enrichie afin de pouvoir insérer du code lors des «événements».

Insérer un bloc de code proprement dit se fait par la syntaxe: (. ... .).
Le bloc en question sera exécuté «après» le «morceau de règle».
Il est impossible de définir un bloc de code en dehors d'une règle, autrement dit, après le . terminal.

Dans ce bloc, on a accès à divers outils:

• le dernier token trouvé, par la variable t de type Token*, exemple: printf( "%S", t->val) permets d'afficher le nom du dernier token
• le prochain token, par la variable la (LookAhead) de type Token*
• les éventuels paramètres (probablement le truc sur lequel j'ai perdu le plus de temps à comprendre)
• lire la doc pour le reste (je n'ai pas encore tout lu ni même intégré ce que j'ai lu)

L'ajout de paramètre peut se faire de deux façons:

• < ... >
• <. ... .>

J'ai utilisé la 1ère dans mon exemple, mais je pense qu'à l'avenir je me restreindrais à la seconde, par souci d'homogénéité avec la syntaxe (. ... .).

Ce sur quoi j'ai perdu du temps est le «comment déclarer un paramètre». De ce que je comprend, un paramètre doit:

• être déclaré après le nom de la règle (option_name<int &foobar> =)
• être utilisé à chaque référence de la règle (option_name<foobar>)

PRAGMAS:

Je n'ai pas encore joué avec ça, il semble que soit des tokens qui sont exclus du flux.

COMMENTS:

Permets de définir les commentaires du langage, je n'ai pas non plus expérimenté la dessus.
Selon le manuel: COMMENTS FROM TokenExpr TO TokenExpr ["NESTED"].

IGNORE:

Caractères qui seront ignorés par le langage, par défaut c'est le retour de isspace(3).
Selon le manuel: IGNORE '\t' + '\r' + '\n'

nom du langage

Le «nom du langage», ici, argv (oui, je sais, quelle imagination débordante) doit se retrouver en 3 endroits:

• COMPILER argv
• END argv .
• une règle de production doit porter le même nom, ici: argv = identifier { option } .

La règle de production qui est ainsi nommée est, de manière assez logique, celle «de plus haut niveau».

conclusion

Je pense avoir fait le tour de ce que devrais contenir un tutoriel de démarrage rapide, j'espère que mon laïus est assez clair…

J'ai omis volontairement le traitement des erreurs et autres fonctionnalités (liste de symboles par exemple), pour deux raisons:

1. ce texte est déjà assez long comme ça
2. je n'ai pas encore expérimenté ces fonctionnalités ni même complètement lu la doc à ces sujets