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:
- 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.
- ce journal s'adresse aux gens qui ont des notions de C++ et connaissent la notation BNF
- la plupart des liens sont en http
- 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€).
- 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
etScanner.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 typeToken*
, exemple:printf( "%S", t->val)
permets d'afficher le nom du dernier token - le prochain token, par la variable
la
(LookAhead) de typeToken*
- 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:
- ce texte est déjà assez long comme ça
- je n'ai pas encore expérimenté ces fonctionnalités ni même complètement lu la doc à ces sujets
# oubli
Posté par freem . Évalué à 4.
Zut, j'ai oublié de préciser quelques détails au sujet des fichiers
.frame
fournis par l'upstream:clang --analyze
détecte un bugdos2unix
sur les fichiers.frame
résout le problème à la sourceConcernant mes patchs perso:
correctif du bug (je pense que c'est le seul patch vraiment important):
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):
[^] # Re: oubli
Posté par Nicolas Boulay (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 freem . Évalué à 3.
franchement c'est honnête je trouve:
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: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 rewind (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 freem . Évalué à 2.
Exact, j'avais oublié.
# Merci !
Posté par _kaos_ . É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 freem . É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 gipoisson . É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 comme3 + (4 × 5)
pour lui attribuer la sémantique23
.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 genreY → 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.
k
de symboles à venir sans les consommer. Cette technique de triche est appelée look-ahead. La méthode est appeléeX(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 alorsLL(k)
. Parfois, on inverse la chaîne à parser avant d’appliquer LL. Dans ce cas, on fait spécifiquement duRR(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
--foo
) ou courte (-f
) ;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.