Journal quick start pour coco/R

Posté par  . Licence CC By‑SA.
10
16
juil.
2020

Sommaire

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
  • # oubli

    Posté par  . Évalué à 4.

    Zut, j'ai oublié de préciser quelques détails au sujet des fichiers .frame fournis par l'upstream:

    • ils sont écrit dans du C++ pré-2011 (et ça warn dur, même si j'ai patché les miens pour résoudre ce problème), qui n'utilise pas std::auto_ptr
    • clang --analyze détecte un bug
    • de même, au moins une variable n'est jamais utilisée
    • pas mal de padding qui peut être réduit dans le code généré
    • le copyright utilise des fins de lignes de type CR/LF, «à la Windows», un petit coup de dos2unix sur les fichiers .frame résout le problème à la source

    Concernant mes patchs perso:

    correctif du bug (je pense que c'est le seul patch vraiment important):

    diff --git a/coco-cpp-20120102/Scanner.frame b/coco-cpp-20120102/Scanner.frame
    index 35c4dc7..cc42ec6 100644
    --- a/coco-cpp-20120102/Scanner.frame
    +++ b/coco-cpp-20120102/Scanner.frame
    @@ -339,7 +339,7 @@ wchar_t* coco_string_create(const wchar_t *value, size_t startIndex, size_t leng
    
        if (value) { len = length; }
        data = new wchar_t[len + 1];
    -   wcsncpy(data, &(value[startIndex]), len);
    +   if (value) { wcsncpy(data, &(value[startIndex]), len); };
        data[len] = 0;
    
        return data;

    Mon log actuel (je pousserais sûrement upstream (dommage qu'ils aient pas importé l'historique quand même) quand j'aurai un peu plus de connaissance sur le code de base):

    fbdf15a fixed using nullptr as non-null param (found with clang analyzer)
    d96c82a removed unused charSetSize
    627b6de fix weak-vtable
    662fe62 fixed remaining implicit conversions warnings
    8ee6cab fixed most implict sign conversions
    dd097f8 fixed most shortens 64 to 32 warnings
    43fb34f fix extra-semi
    548b34a no longer use 0 as nullptr
    d50ecea slightly reduce padding
    1a76de4 generated code no longer use reserved macros
    6cd6446 no more shadown vars
    12b8daa no longer generate code with old-style cast
    b1ccb79 NULL -> nullptr
    68aa815 dos2unix
    5fb038c initial commit
    
    • [^] # Re: oubli

      Posté par  (site web personnel) . Évalué à 4.

      Je serais curieux de voir si les erreurs sont correctement gérés. La dernière fois que j'avais regardé ce genre d'outil, j'ai fini par tout faire à la main, car faire un reporting propre d'erreur était ultra lourdingue.

      Les auteurs d'outils type lex/yacc avaient l'air d'être plus intéressé par la vitesse de parse, ce dont tout le monde se fout, que d'avoir des messages d'erreurs par défaut utile, alors que c'est utilisé tout le temps.

      "La première sécurité est la liberté"

      • [^] # Re: oubli

        Posté par  . Évalué à 3.

        franchement c'est honnête je trouve:

        echo foo bar | ./cmdline
        -- line 1 col 5: EOF expected
        

        bon, c'est surtout que mon fichier de règles ici est bien trop trivial hein. Avec des règles plus complexes et surtout plus complètes c'est mieux.

        Il aurait suffit que je change la production argv en argv = identifier { option } '\n' pour avoir:

        printf "foo bar\n" | ./a.out       
        -- line 1 col 5: "\n" expected
        

        J'ai vu des messages d'erreurs plus sympas lors de mes essais (qui sont sur un «langage» plus évolué), et ce, alors même que j'ai éludé la question de la gestion des erreurs.

    • [^] # Re: oubli

      Posté par  (Mastodon) . Évalué à 3.

      Ce n'est pas un bug, ton patch ne sert à rien. new renvoie toujours un pointeur non nul, sinon il envoie une exception. Donc il est inutile de vérifier que le pointeur est non-nul, il l'est sinon tu ne serais plus à cette ligne là.

      • [^] # Re: oubli

        Posté par  . Évalué à 2.

        Exact, j'avais oublié.

  • # Merci !

    Posté par  . Évalué à 2.

    Salut,

    Merci d'avoir fait tout cet effort de rédaction !

    Ça peut mettre des idées à compulser, mais pas ce soir, la nuit porte conseil.

    Forcément du C++ ou c'est plus ouvert cette contrainte ?

    Matricule 23415

    • [^] # Re: Merci !

      Posté par  . Évalué à 2. Dernière modification le 16 juillet 2020 à 21:51.

      Il y a 3 langages supportés, et vu le code je pense qu'il ne devrais pas être trop difficile de porter la bête pour un autre langage si la syntaxe dérive du C et que l'orienté objet est supporté.

      Pour du python par contre, ça risque d'être plus chiant, mais je suis pas expert.

      Et pour l'effort de rédaction, je vais juste profiter de mon propre journal pour virer mes notes locales, ça a mis du propre et ça m'a permis de régler un bug dans l'exemple du coup j'y gagne aussi :)

      Par contre j'adorerais avoir un contre exemple de la même syntaxe avec d'autres outils.

  • # Condensé de glossaire

    Posté par  . Évalué à 8.

    Sommaire

    Voici un extrait de mes notes sur le sujet. L’original est en anglais, je traduis sans vérifier la terminologie exacte en français. Je laisse quelques concepts en anglais en tant que différentes pistes à explorer avec un moteur de recherche.

    Parsing, token, alphabet, terminaux

    Parsing, première approximation : c’est de l’analyse syntaxique. Comment y procéder ? À l’aide d’une grammaire, structurer une succession linéaire de symboles — linéaire : le prochain symbole dépend d’une façon ou d’une autre des symboles qui l’ont précédés.

    Token : on nomme tokens ce que les linguistes appellent phrases. En combinant la structure obtenue après le parsing avec les tokens, on peut définir une sémantique. Exemple : 3 + 4 × 5 est un token dont on pourrait structurer comme 3 + (4 × 5) pour lui attribuer la sémantique 23.

    Un alphabet est un fonds où l’on peut puiser des symboles qui engendreront un langage. Celui-ci comportera deux catégories de symboles : ceux qui sont ‘visibles’ ou ‘palpables‘ participent à la construction de phrases (e.g. ‘freem’, ‘;’), ceux qui constituent des ‘méta-données’ ne peuvent pas apparaître dans une phrase (e.g. les notions de ‘phrase’ ou de ‘nom commun’).

    Les symboles palpables sont appelés symboles terminaux. Les méta-données sont appelés symboles non-terminaux.

    Grammaires, productions

    Generative grammar : est ainsi appelée une grammaire qui définit comment faire des substitutions de symboles. Ainsi, écrire Y → X signifie « X pourrait remplacer Y » . Une procédure systématique d’applications de règles du genre Y → X est dite “generative process”.

    Les règles sont appelées “production rules”, les différentes étapes “production steps”.

    On peut construire différents types de grammaires et les regrouper selon les types de productions qu’elles permettent. Un regroupement de ce genre qui est très connu est la “Chomsky hierarchy” où on trouve une catégorie de grammaires dite “context-free” (CF).

    Pour écrire les règles de production d’une grammaire CF, il existe une palanquée de notations. Exemples: Backus-Naur Form (BNF), notation de van Wijngaarden, Extended BNF (EBNF), …

    Parsing, redux

    L’objectif du parsing d’une chaîne de caractères est de détailler les étapes qui mènent à la chaîne en partant d’une grammaire. On ne peut pas se baser seulement sur la grammaire : au moment où celle-ci a été écrite, une sémantique lui a été attachée ; les règles de production dont elle comporte possèdent elles aussi une sémantique. Ce dont on a besoin alors, c’est de trouver quelles règles ont participé à la construction de la chaîne et comment elles ont été impliquées.

    La succession des règles de production forme un arbre (ou des arbres) qui est appelé “parse tree”. Parser revient à appliquer ces règles, parfois en prenant des décisions intermédiaires quand il y a plusieurs symboles candidats à la prochaine substitution.

    Parser generators

    On peut automatiser le processus qui, à partir d’un symbole donné, passe au prochain et, le cas échéant, lève les ambiguïtés. Un programme capable d’accomplir pareil processus est nommé “parser generator”. Ses entrées : la grammaire (toujours), les symboles terminaux (parfois) ; ses sorties : un parseur.

    Ce processus de passage de symbole en symbole peut se faire de haut-en-bas ou de bas-en-haut.

    Notion de direction

    La génération de parseurs peut être “non-directional” : on consulte la chaîne cible symbole après symbole afin de construire l’arbre (parse tree) au fur et à mesure. La méthode d’Unger y va de haut-en-ba tandis que la méthode CYK (ou CYK) y va de bas-en-haut — appellation faite d’après Cocke, Younger, et Kasami.

    La génération peut aussi être “directional” : on procède de symbole en symbole, de gauche à droite (c’est ça la direction). Deux techniques prévalent pour cette méthode : “predictions/matches” quand on va de haut-en-bas, “shifts/reductions” de bas-en-haut.

    Notion de déterminisme

    Un automate qui génère des parseurs directionnels possède les caractéristiques suivantes.

    • Il est d’abord muni des symboles qui restent à parser.
    • Il est également muni d’instructions qui lui permettront de se débloquer dans tous les cas possibles.
    • Au cas où il est confronté à une ambiguïté, il a besoin de « tricher » et consulter un nombre k de symboles à venir sans les consommer. Cette technique de triche est appelée look-ahead. La méthode est appelée X(k).

    Il n’existe qu’une seule méthode déterministe allant de haut-en-bas : LL. Première lettre L : “Left-to-right”. deuxième L : la méthode identifie “the Leftmost production”. L’appellation générale de X(k) devient alors LL(k). Parfois, on inverse la chaîne à parser avant d’appliquer LL. Dans ce cas, on fait spécifiquement du RR(k).

    Les méthodes déterministes allant de bas-en-haut font légion. La plus connue est LR(k) avec L : “Left-to-right” ; R : identifier “the Rightmost production”.

    Quand on fait l’inversion comme au point précédent, on obtient RL(k).

    Bibliothèques de génération de parseurs

    Dans les langages de programmation dotés de types algébriques de données, la définition d’une grammaire est juste une définition de type. Cette simplicité mène à une prolifération de bibliothèques du genre parser generator, chaque se démarquant sur un point particulier.

    TatTempo, le retour !

    Regarde de ce côté pour un exemple d’utilisation d’une de ces bibliothèques ; chaque option

    • comporte une valeur par défaut ;
    • peut être parsée en version longue (--foo) ou courte (-f) ;
    • sera documentée après que le programme aura été invoqué via programme --help.

    Et c’est compilé :)

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.