La grammaire de CoCKTaiL
Dans mon dernier article, j'ai donné quelques exemples et expliqué la motivation derrière CoCKTaiL, un langage de types pour le CCK de Drupal. J'avais promis de décrire la grammaire sur laquelle je travaille et de dire quelques mots sur les outils que j'utilise.
Je dois commencer par préciser qu'il s'agit vraiment d'un travail en cours; ce que vous voyez ici ne doit donc pas être considéré comme une spécification, ni comme une quelconque promesse de la forme finale des choses à venir. Il s'agit plutôt d'une invitation à vous joindre à la fête et à aider à donner vie à cet outil. Tous les commentaires, suggestions et coups de main pour le développement, les tests et la documentation sont les bienvenus. En particulier, si vous avez des idées sur la façon dont la grammaire elle-même pourrait être modifiée pour la rendre plus simple, ou meilleure de quelque autre façon, j'aimerais beaucoup avoir votre avis.
Sans plus tarder, voici donc la grammaire (à l'heure actuelle) de CoCKTaiL. Ce qui suit est la sortie du générateur d'analyseurs syntaxiques lemon, relativement nouveau, dont nous reparlerons un peu plus loin. Note : les numéros au début de chaque ligne ne font pas partie de la sortie; ils ont été ajoutés pour pouvoir renvoyer à des lignes précises dans la discussion qui suit.
1 // Reprint of input file "CoCKTaiL.y".
2 // Symbols:
3 // 0 $ 13 RPAREN 26 groupname
4 // 1 TYPE 14 KEYSTRING 27 fieldtype
5 // 2 LBRACE 15 TRUE 28 fieldname
6 // 3 RBRACE 16 FALSE 29 attr
7 // 4 ENCAPSED_STRING 17 DOTDOT 30 attrname
8 // 5 GROUP 18 error 31 attrvalue
9 // 6 FIELD 19 typedef 32 rhsvalue
10 // 7 IDENTIFIER 20 typename 33 boolean
11 // 8 SEMICOLON 21 field_or_group 34 range
12 // 9 STRING 22 attributes 35 array
13 // 10 INTEGER 23 groups_or_fields 36 arrayentries
14 // 11 ARR 24 group_def 37 arrayentry
15 // 12 LPAREN 25 field_def 38 arraykey
16 typedef ::= TYPE typename LBRACE field_or_group RBRACE.
17 typename ::= ENCAPSED_STRING.
18 field_or_group ::= attributes groups_or_fields.
19 groups_or_fields ::=.
20 groups_or_fields ::= groups_or_fields group_def.
21 groups_or_fields ::= groups_or_fields field_def.
22 group_def ::= GROUP groupname LBRACE field_or_group RBRACE.
23 groupname ::= ENCAPSED_STRING.
24 field_def ::= FIELD fieldtype fieldname LBRACE attributes RBRACE.
25 fieldtype ::= IDENTIFIER.
26 fieldname ::= ENCAPSED_STRING.
27 attributes ::=.
28 attributes ::= attributes attr.
29 attr ::= attrname attrvalue SEMICOLON.
30 attrname ::= IDENTIFIER.
31 attrvalue ::= rhsvalue.
32 rhsvalue ::= STRING.
33 rhsvalue ::= IDENTIFIER.
34 rhsvalue ::= ENCAPSED_STRING.
35 rhsvalue ::= INTEGER.
36 rhsvalue ::= boolean.
37 rhsvalue ::= range.
38 rhsvalue ::= array.
39 array ::= ARR LPAREN arrayentries RPAREN.
40 arrayentries ::=.
41 arrayentries ::= arrayentry arrayentries.
42 arrayentry ::= arraykey rhsvalue SEMICOLON.
43 arraykey ::= KEYSTRING.
44 boolean ::= TRUE.
45 boolean ::= FALSE.
46 range ::= INTEGER DOTDOT INTEGER.
La première partie définit les symboles de la grammaire. Par convention, les symboles en MAJUSCULES sont des symboles terminaux, tandis que les symboles en minuscules sont des non-terminaux. Les symboles terminaux sont reconnus et transmis à l'analyseur syntaxique par un analyseur lexical (aussi appelé lexer, scanner ou tokenizer).
La deuxième partie définit la grammaire proprement dite, sous forme d'une suite de règles ou productions. Chaque règle se termine par un point. Une règle signifie qu'une suite de symboles d'entrée correspondant au membre de droite (RHS) peut être remplacée par (c.-à-d. réduite en) le membre de gauche (LHS) de la règle. Si une suite de telles réductions appliquées à une entrée aboutit au symbole de départ (typedef), alors l'entrée est « acceptée » comme expression valide de la grammaire.
Par exemple, les lignes 27 et 28 définissent attributes comme étant soit vide (ligne 27), soit attributes suivi d'un attribut. Il s'agit d'une définition récursive, mais puisqu'on peut sortir de la récursion en prenant le premier choix pour attributes, on voit que ces deux lignes définissent attributes comme une liste de symboles d'attribut.
Outils
J'ai déjà mentionné le générateur d'analyseurs syntaxiques Lemon, le plus récent d'une vénérable lignée d'outils logiciels dont YACC (yet another compiler-compiler) est probablement l'ancêtre le plus célèbre, et GNU/Bison et AntLR les représentants actuels les plus utilisés.
Lemon a été écrit (en C, pour générer du code en langage C) par Richard Hipp, que vous connaissez peut-être comme l'auteur de SQLite, le moteur SQL embarqué utilisé par Trac, pour ne nommer qu'un projet parmi bien d'autres. Lemon a servi à écrire l'analyseur SQL de SQLite.
Bon, tout cela ne serait qu'intéressant si l'histoire s'arrêtait là, car après tout, nous voulons écrire en PHP pour générer du PHP, n'est-ce pas? Heureusement, Greg Beaver a porté lemon en PHP et l'a publié sous forme de paquet PEAR : PHP_ParserGenerator. Pour que notre bonheur soit complet, il a aussi écrit un générateur d'analyseurs lexicaux pour compléter la suite d'outils nécessaires. Encore une fois, il est offert sous forme de paquet PEAR : PHP_LexerGenerator.
Utiliser phplemon et plex pour générer un analyseur CoCKTaiL
Étape 1 : Téléchargez et installez PHP_ParserGenerator et PHP_LexerGenerator.
Étape 2 : Configurez l'environnement. J'ai ajouté quelques lignes à ma spécification PATH pour ajouter les répertoires où se trouvent phplemon et plex au chemin de recherche des exécutables de mon interpréteur de commandes. Ensuite, phplemon parser.y lance le générateur d'analyseurs PHP lemon en ligne de commande sur le fichier d'entrée parser.y, ce qui produit les fichiers de sortie parser.out et parser.php. De même, plex lexer.plex construit l'analyseur lexical et produit lexer.php.
Étape 3 : Écrivez l'analyseur syntaxique. Il s'agit d'écrire la spécification de la grammaire de l'analyseur. J'ai développé l'analyseur de façon itérative, en partant d'une grammaire triviale et en ajoutant les fonctionnalités une à une. Le fichier d'entrée de l'analyseur (CoCKTaiL.y dans mon cas) comprend plusieurs sections, dont la grammaire proprement dite. En plus de spécifier les productions comme je l'ai expliqué plus haut, on peut ajouter une action à chaque production. Il s'agit d'un bout de code que l'analyseur exécute lorsqu'une production « correspond » (c.-à-d. est réduite). Ces bouts de code ont accès au contexte de l'analyseur pour la pile d'entrée, ce qui peut servir à générer le code approprié. Pour revenir à notre exemple ci-dessus, si nous avons réduit un symbole attributes, nous pouvons rassembler la liste des attributs et la conserver pour usage ultérieur.
J'ai commencé avec des actions vides, ce qui gardait l'accent sur la grammaire et rendait l'analyseur plus propre. Cette approche permet aussi de construire facilement plusieurs applications à partir de la même grammaire. Un analyseur aux actions vides est un validateur; ajouter des actions qui génèrent le code PHP approprié nous permet de construire un générateur de types CCK.
Étape 4 : Construisez l'analyseur lexical. En fait, la construction de l'analyseur syntaxique et celle de l'analyseur lexical vont un peu de pair si vous voulez faire des tests avec de vraies données. Le point à retenir, c'est que c'est le générateur d'analyseurs syntaxiques qui définit les symboles; c'est donc lui qui doit servir à générer les noms symboliques qu'utilise l'analyseur lexical. La version « C » de Lemon peut générer un fichier d'en-tête C contenant les symboles terminaux; j'ai dû les extraire à la main du fichier PHP généré, pour construire un fichier de classe définissant les symboles, que l'analyseur lexical pouvait ensuite utiliser.
En réalité, la grammaire est assez simple pour qu'on puisse construire un analyseur lexical à la main. Cependant, plex est très simple à utiliser, et l'analyseur lexical qui en résulte est probablement plus rapide et moins bogué qu'un analyseur fait maison. Comme la spécification est plutôt en mouvement en ce moment, la flexibilité est un grand atout.
Spécifier un analyseur lexical revient à écrire des expressions régulières qui définissent les symboles terminaux. Les choses se compliquent légèrement du fait que l'analyseur lexical fonctionne en réalité par états : il peut analyser les symboles différemment selon l'état dans lequel il se trouve; les transitions entre états sont définies en précisant vers quels états passer lorsque certaines suites de symboles sont lues. Notre analyseur lexical actuel est assez simple. Cela pourrait changer, si cela peut aider à simplifier la grammaire d'entrée. (En général, les choses sont plus simples pour les humains si l'on peut compter sur le contexte pour masquer des détails autrement disgracieux. Cela signifie toutefois que l'analyseur lexical doit tenir compte du contexte : il le fait en réalisant des états différents pour des contextes différents.)
À venir
Dans mon prochain article, je présenterai le code complet d'un validateur et d'un générateur de types CCK, qui analysera un fichier d'entrée CoCKTaiL pour produire du PHP pouvant être importé par CCK. Tous les commentaires, suggestions et coups de main pour le développement et les tests sont les bienvenus.