Il y a quelques années, quelqu'un m'a demandé s'il était judicieux de convertir Python en analyseur PEG (ou en grammaire PEG; je ne me souviens pas exactement qui et quand c'était). Puis je l'ai regardé un peu, mais je ne suis pas parvenu à une conclusion, et j'ai donc abandonné ce sujet. J'ai récemment appris plus sur PEG (Parsing Expression Grammars, Parsing Expression Grammar), et maintenant je pense que c'est une alternative intéressante au générateur d'analyseur syntaxique auto-écrit qui a été développé il y a 30 ans lorsque je commençais à peine à travailler sur Python. Je l'ai appelé «pgen», et c'était probablement le premier morceau de code que j'ai écrit pour Python.
Contenu de la série Python PEG Parser La raison pour laquelle je suis actuellement intéressé par l'analyseur PEG est parce que je suis quelque peu ennuyé par les limites de pgen. Il est construit sur sa propre implémentation de LL (1), qui a un certain nombre d'hypothèses. Par exemple, je n'aimais pas les règles de grammaire qui pouvaient générer des lignes vides, je les ai donc interdites. Et ainsi simplifié l'algorithme de création de tables d'analyse. J'ai également inventé ma propre notation grammaticale de type EBNF, que j'aime toujours beaucoup.
Voici quelques problèmes avec pgen qui m'ennuient. Le «1» dans le nom LL (1) implique qu'il n'analyse que le prochain jeton, ce qui limite notre capacité à créer de bonnes règles de grammaire. Par exemple, une instruction Python peut être une expression ou une affectation (ou autre chose, mais elles commencent toutes par un mot clé en surbrillance, comme if ou def ). Je voudrais décrire la syntaxe en utilisant la notation pgen. Notez que ce n'est qu'un exemple simplifié, qui est un sous-ensemble de Python, comme cela se fait habituellement lors de la description de la conception du langage. Ce sera une grammaire de jouets qui sera utile pour une démonstration plus approfondie.
statement: assignment | expr | if_statement expr: expr '+' term | expr '-' term | term term: term '*' atom | term '/' atom | atom atom: NAME | NUMBER | '(' expr ')' assignment: target '=' expr target: NAME if_statement: 'if' expr ':' statement
Quelques mots sur la notation: NAME et NUMBER sont des jetons et sont prédéfinis en dehors de la grammaire. Les chaînes citées de type '+' ou 'if' sont également des jetons. (Remettons à plus tard d'en parler la prochaine fois) Les règles de grammaire commencent par le nom de la règle, suivies de : puis une ou plusieurs alternatives, séparées par | .
Le problème est que si vous décrivez la grammaire de cette façon, pgen ne fonctionnera pas. Cela est dû au fait que certaines règles ( expr et term ) sont laissées récursives, et il n'est pas assez intelligent pour gérer correctement de telles situations. Habituellement, cela est résolu en réécrivant uniquement ces règles, en laissant les autres règles inchangées. Par exemple:
expr: term ('+' term | '-' term)* term: atom ('*' atom | '/' atom)*
Cela révèle plusieurs possibilités d'EBNF dans pgen: vous pouvez imbriquer des alternatives entre parenthèses et créer des répétitions en plaçant * après l'élément. Ainsi, la règle de l'expression expr signifie ici "c'est un terme suivi de zéro ou plusieurs répétitions de la séquence <terme plus ou moins, suivi de terme>". Cette grammaire utilise la même langue que la première version, mais encore une fois, elle ne reflète pas l'intention de conception de la langue. En particulier, cela ne montre pas que les opérateurs sont liés à gauche, ce qui est important lorsque vous essayez de générer du code.
Mais il y a un autre problème gênant dans cet exemple (et en Python aussi). En raison de l'analyse d'un seul jeton, l'analyseur ne peut pas déterminer ce qu'il regarde - le début d'une expression ou d'une affectation. Au tout début du traitement de l'opérateur, l'analyseur doit décider uniquement du premier jeton, quelle alternative il analyse. (Pourquoi? Voici comment fonctionne l'implémentation de l'analyse syntaxique dans pgen) Disons que notre programme est le suivant:
answer = 42
Ce programme est représenté par trois jetons: NAME (avec valeur de answer ), = et NUMBER (avec valeur 42 ). La seule chose que nous savons au tout début de l'analyse est le premier jeton NAME . La règle que nous essayons d'analyser à ce stade est l' statement (le caractère initial de la grammaire). Trois alternatives y sont définies: expr , assignment et if_statement . Nous pouvons immédiatement exclure if_statement , car le jeton précédent n'est pas if . Mais expr et assignment peuvent commencer par le jeton NAME , et pour cette raison, pgen rejette notre grammaire comme ambiguë.
Ce n'est pas tout à fait correct, car techniquement la grammaire elle-même ne l'est pas; Je ne peux pas trouver une formulation plus précise, nous allons donc nous attarder sur celle-ci. Et comment pgen résout-il cela? Il calcule quelque chose appelé un PREMIER ensemble pour chaque règle de grammaire, et s'ils se croisent, il lève une exception.
Alors, ne pouvons-nous pas résoudre ce problème en fournissant à l'analyseur un tampon d'affichage plus grand? Pour notre exemple, un deuxième jeton de prévisualisation est suffisant, car dans cette grammaire, le deuxième jeton d'affectation doit être = . Mais dans un langage plus réaliste comme Python, vous pouvez avoir besoin d'un tampon illimité, car le contenu à gauche du = token = peut être arbitrairement complexe, par exemple:
table[index + 1].name.first = 'Steven'
Dans ce cas, vous devrez analyser dix jetons avant de rencontrer = . Mais je vous assure, il peut y avoir des expressions plus longues. Pour résoudre ce problème dans pgen, nous avons modifié l'analyseur de grammaire pour accepter certaines expressions incorrectes, en ajoutant une vérification supplémentaire dans une passe ultérieure. Il générera une erreur SyntaxError s'il ne peut pas correspondre aux côtés gauche et droit. Pour notre langage de jouet, cela revient à écrire ce qui suit:
statement: assignment_or_expr | if_statement assignment_or_expr: expr ['=' expr]
Les crochets indiquent une partie optionnelle. Et puis lors de la prochaine passe du compilateur (disons, génération de code octet), nous vérifions s'il y a = ou non, et si oui, nous vérifions que le côté gauche correspond à la syntaxe target .
Il existe un problème similaire pour les arguments d'appel de fonction. Nous aimerions écrire quelque chose comme ça (encore une fois, dans une version simplifiée de la syntaxe Python):
call: atom '(' arguments ')' arguments: arg (',' arg) * arg: posarg | kwarg posarg: expr kwarg: NAME '=' expr
Mais l'algorithme d'analyse, qui ne prendrait en compte que le jeton suivant, ne peut pas dire à l'analyseur si NAME au début des arguments est le début de posarg (puisque expr peut commencer par NAME ) ou le début de kwarg . Encore une fois, l'analyseur Python actuel résout ce problème en déterminant:
arg: expr ['=' expr]
puis complète l'alternative dans une passe de compilateur ultérieure. (Nous avons même fait une petite erreur et analysé foo((a) = 1) tout comme foo(a = 1) . Cela n'a été corrigé que dans Python 3.8)
Alors, comment un analyseur PEG résout-il ces problèmes? Utilisation d'un tampon de sauvegarde infini! Son implémentation typique utilise le soi-disant analyseur packrat, qui non seulement charge le programme entier en mémoire avant de l'analyser, mais permet également à l'analyseur d'être restauré à un nombre arbitraire de jetons. Bien que le terme PEG se réfère principalement à la notation grammaticale, les analyseurs générés à partir des grammaires PEG sont généralement des analyseurs à descente récursive et à retour illimité. L'analyseur packrat rend l'ego efficace en se souvenant des règles qui ont déjà été analysées pour des positions spécifiques.
Cela simplifie l'algorithme, mais il y a bien sûr un prix: la mémoire. Il y a trente ans, j'avais une bonne raison d'utiliser LL (1): la mémoire était chère. Il (comme d'autres technologies telles que LALR (1), rendu célèbre par YACC) utilise une machine d'état et une pile pour construire efficacement un arbre d'analyse.
Heureusement, les ordinateurs exécutant CPython ont beaucoup plus de mémoire qu'il y a 30 ans, et le stockage de l'ensemble du fichier en mémoire n'est plus un problème. Par exemple, le plus gros fichier non-test de stdlib que j'ai pu trouver est _pydecimal.py , ce qui prend environ 223 Ko. Dans le monde gigaoctet, ce n'est essentiellement rien, ce qui m'a fait jeter un regard différent sur les analyseurs.
Mais il y a encore une chose dans l'analyseur CPython actuel qui me dérange. Les compilateurs sont des choses complexes et l'implémentation de CPython ne fait pas exception. Bien que le résultat de l'analyseur pgen soit un arbre d'analyse, il n'est pas directement utilisé comme entrée pour le générateur de bytecode: il est d'abord converti en arbre de syntaxe abstraite (AST), et alors seulement cet AST est compilé en bytecode. (En fait, c'est encore plus compliqué là-bas, mais pour l'instant nous n'entrerons pas dans les détails)
Pourquoi ne pas compiler immédiatement à partir d'un arbre d'analyse? C'est exactement comme ça, mais il y a environ 15 ans, nous avons découvert que le compilateur était trop compliqué. Nous avons donc isolé l'AST et la phase de transformation de l'AST de l'arbre d'analyse séparément. Au fur et à mesure de l'évolution de Python, AST est resté plus stable que l'analyse, ce qui a réduit la probabilité d'erreurs dans le compilateur.
AST est également plus facile à travailler avec des bibliothèques tierces qui souhaitent tester le code Python. Il peut être obtenu en utilisant le module ast populaire. Il vous permet également de créer des nœuds à partir de zéro et de modifier ceux qui existent, ainsi que de compiler des pièces en bytecode. Ce dernier a permis la création de toute une industrie d'extensions de langage pour Python. (L'arbre d'analyse est également accessible aux utilisateurs de Python via le module d'analyse, mais travailler avec lui est beaucoup plus difficile; par conséquent, il n'est pas si populaire)
Maintenant, je veux combiner ces choses et voir si nous pouvons créer un nouvel analyseur pour CPython, qui utilise PEG et packrat pour créer l'AST directement pendant l'analyse. Ainsi, il sera possible d'omettre la génération de l'arbre intermédiaire d'analyse, ce qui peut nous faire économiser de la mémoire, même malgré l'utilisation d'un tampon infini pour les jetons. Je suis toujours en cours d'implémentation, mais j'ai déjà un prototype qui peut compiler un sous-ensemble de Python dans AST à environ la même vitesse que l'analyseur CPython actuel. Cependant, il utilise plus de mémoire et il me semble que l'extension du sous-ensemble dans le langage complet ralentira l'analyseur PEG. Mais jusqu'à présent, je n'ai pensé à aucune optimisation, je vais donc continuer à travailler.
Le dernier avantage du passage au PEG est qu'il offre plus de flexibilité pour l'évolution future de la langue. Dans le passé, il a été dit que les contraintes LL (1) dans pgen gardaient la grammaire Python simple. Cela peut très bien être vrai, mais nous avons de nombreux autres processus pour empêcher une croissance linguistique incontrôlée (principalement le processus PEP, qui est aidé par des exigences de compatibilité descendante très strictes et une nouvelle structure de gestion). Je ne suis donc pas inquiet à ce sujet.
Je voudrais en dire beaucoup plus sur PEG et mon implémentation, mais ce sera dans les prochains articles après avoir nettoyé le code.
Licence pour cet article et code cité: CC BY-NC-SA 4.0