Cette semaine, nous rendons le générateur d'analyseur «indépendant», c'est-à-dire qu'il générera son propre analyseur.
Contenu de la série Python PEG Parser Donc, nous avons déjà un générateur d'analyseur, dont une partie est un analyseur de grammaire. Nous pourrions l'appeler un méta-analyseur. Le méta-analyseur fonctionne de manière similaire à celui généré: GrammarParser hérite de l' Parser et utilise le même mécanisme mark() / reset() / hope() . Cependant, tout était écrit à la main. Mais est-ce vrai?
Lors de la conception d'un compilateur, il est habituel que le compilateur soit écrit dans le langage qu'il compile. Je me souviens avec amour que le compilateur Pascal que j'ai utilisé lorsque j'ai appris à programmer était écrit en Pascal lui-même, GCC est écrit en C et le compilateur Rust est écrit en Rust.
Comment faire Au tout début, implémentez un compilateur pour un sous-ensemble ou une version antérieure d'une langue dans une autre langue. (Permettez-moi de vous rappeler que le compilateur Pascal d'origine a été écrit en FORTRAN!) Ensuite, le nouveau compilateur est écrit dans le langage cible et compilé à l'aide du compilateur de démarrage implémenté au tout début. Dès que le nouveau compilateur commence à fonctionner suffisamment bien, le compilateur d'amorçage est supprimé et chaque version ultérieure du langage ou du compilateur est limitée à ce qui peut être compilé à l'aide de la version précédente du compilateur.
Faisons-le pour notre méta analyseur. Nous allons écrire une grammaire pour les grammaires (méta-grammaire) puis générer un nouveau méta-analyseur à partir de cela. Heureusement, j'ai planifié ce mouvement dès le début, donc ce sera assez simple. Les actions que nous avons ajoutées dans l'épisode précédent sont un élément important car nous n'avons pas besoin de changer le générateur, nous devons donc créer une structure de données compatible.
Voici une version simplifiée du métagramme sans actions:
start: rules ENDMARKER rules: rule rules | rule rule: NAME ":" alts NEWLINE alts: alt "|" alts | alt alt: items items: item items | item item: NAME | STRING
Je vais vous montrer comment ajouter une action de bas en haut. Rappelez-vous de la partie 3 qu'il existe des objets Rule qui ont les alts name et alts . Initialement, alts n'était qu'une liste de listes de lignes (une liste externe pour les alternatives et une liste interne pour chaque élément de l'alternative), mais pour implémenter des actions, je l'ai changé de sorte que les alternatives soient représentées par des objets Alt avec des items et action attributs d' action . Les éléments sont toujours représentés comme de simples chaînes. Pour l' item nous obtenons:
item: NAME { name.string } | STRING { string.string }
Cela nécessite une petite explication: lorsque l'analyseur traite le jeton, il renvoie un objet TokenInfo qui a le type , la string et d'autres attributs. Nous ne voulons pas que le générateur traite les objets TokenInfo , donc les actions ici extraient la chaîne du jeton. Notez que pour tous les jetons en majuscules, tels que NAME , l'analyseur généré utilise la version de chaîne (ici name ) comme nom de la variable.
Les items doivent renvoyer une liste de chaînes:
items: item items { [item] + items } | item { [item] }
Ici, j'utilise des règles récursives à droite, donc nous ne dépendons pas du traitement de la récursion à gauche, ajouté dans la partie 5. (Pourquoi pas? Il est toujours bon de garder les choses aussi simples que possible, et cette grammaire ne bénéficiera pas grandement d'un changement sous la récursion à gauche). item répertorié, mais les items ne le sont pas récursivement, car il s'agit déjà d'une liste.
Règle alt pour créer un objet Alt :
alt: items { Alt(items) }
Je vais omettre les actions pour les rules et start , car elles sont définies de cette façon.
Cependant, il y a deux questions ouvertes. Tout d'abord, comment trouver la définition des classes Rule et Alt ? Pour ce faire, nous devons ajouter plusieurs instructions d' import au code généré. Le moyen le plus simple serait de passer le drapeau au générateur, qui dit "c'est une méta-grammaire", et de laisser le générateur insérer une import supplémentaire au début du programme généré. Mais maintenant que nous avons les actions, de nombreux autres analyseurs voudront également personnaliser leur importation, alors pourquoi ne pas voir si nous pouvons implémenter une approche plus générale.
Il existe de nombreuses façons de le mettre en œuvre. Un mécanisme simple et général consiste à ajouter une section «définitions de variables» en haut de la grammaire et à permettre au générateur d'utiliser ces variables pour contrôler divers aspects du code généré. J'ai décidé d'utiliser le symbole @ pour commencer à définir la variable, suivi du nom de la variable ( NAME ) et de la valeur ( STRING ). Par exemple, nous pouvons mettre le bloc de code suivant en haut de la méta-grammaire:
@subheader "from grammar import Rule, Alt"
Le générateur d'analyseur imprimera la valeur de la variable de sous-en- subheader après l'importation standard, qui est ajoutée par défaut (par exemple, pour importer la memoize ). Si vous souhaitez plusieurs éléments d' import , vous pouvez utiliser une chaîne avec des guillemets triples, par exemple,
@subheader """ from token import OP from grammar import Rule, Alt """
Ceci est facile à ajouter à la méta-grammaire: nous allons casser la règle de start comme suit:
start: metas rules ENDMARKER | rules ENDMARKER metas: meta metas | meta meta: "@" NAME STRING NEWLINE
(Je ne me souviens pas pourquoi je l'ai appelé "méta", mais j'ai choisi ce nom quand j'ai écrit le code, et je m'en tiendrai. :-)
Nous devons l'ajouter au métaparser de bootstrap. Maintenant que la grammaire n'est pas seulement une liste de règles, ajoutons un objet de grammaire avec les attributs metas et rules . Nous pouvons définir les actions suivantes:
start: metas rules ENDMARKER { Grammar(rules, metas) } | rules ENDMARKER { Grammar(rules, []) } metas: meta metas { [meta] + metas } | meta { [meta] } meta: "@" NAME STRING { (name.string, eval(string.string)) }
(Notez que la meta retourne un tuple; et aussi qu'il utilise eval() pour traiter les guillemets de chaîne.)
Je n'ai pas mentionné la mise en place d'actions dans les règles pour alt ! La raison en est qu'ils sortent un peu en désordre. Mais cela n'a aucun sens de reporter plus loin, alors voici:
alt: items action { Alt(items, action) } | items { Alt(items, None) } action: "{" stuffs "}" { stuffs } stuffs: stuff stuffs { stuff + " " + stuffs } | stuff { stuff } stuff: "{" stuffs "}" { "{" + stuffs + "}" } | NAME { name.string } | NUMBER { number.string } | STRING { string.string } | OP { None if op.string in ("{", "}") else op.string }
La saleté dans la définition est causée par mon désir de rendre le code Python arbitraire valide entre des crochets d'action bouclés, y compris imbriqués dans un autre accolades bouclés. À cette fin, nous utilisons un jeton OP spécial qui génère notre tokenizer pour toutes les ponctuations reconnues par Python (renvoyant un seul jeton de type OP pour les opérateurs à plusieurs caractères tels que <= ou ** ). Les seuls autres jetons pouvant apparaître dans les expressions Python sont les noms, les nombres et les chaînes. Ainsi, le code entre les accolades extérieures de l'action, semble-t-il, peut être exprimé par des répétitions de NAME | NUMBER | STRING | OP NAME | NUMBER | STRING | OP NAME | NUMBER | STRING | OP .
Hélas, cela ne fonctionnera pas car l' OP correspond également aux accolades, et puisque l'analyseur PEG est toujours gourmand, cela capturera le crochet de fermeture et nous ne verrons jamais la fin de l'action. Par conséquent, nous ajoutons un petit ajustement, permettant à l'action de renvoyer une erreur de choix alternatif, renvoyant None. Je ne sais pas si c'est un phénomène standard dans d'autres analyseurs PEG - je l'ai trouvé sur place quand j'ai dû résoudre le problème de reconnaissance de la parenthèse fermante (même sans paires imbriquées). Cela semble bien fonctionner et je pense que cela correspond à la philosophie globale de l'analyse PEG. Cela peut être considéré comme une forme spéciale de prospective (dont je parlerai ci-dessous).
En utilisant ce petit hack, nous pouvons faire la comparaison sur l' OP tomber sur une accolade bouclée. Ensuite, une comparaison des stuff et de l' action sera possible.
Avec ces choses, une méta-grammaire peut être analysée par un métaparser de bootstrap, et le générateur peut la transformer en un nouveau méta-analyseur qui peut s'analyser. Et, chose importante, le nouveau méta-analyseur peut toujours analyser la même méta-grammaire. Si nous compilons la méta grammaire avec le nouveau compilateur de méta, le résultat est le même: cela prouve que le méta analyseur généré fonctionne correctement.
Voici la méta grammaire de l'action complète. Il peut s'analyser, car il sait combiner de longues lignes:
@subheader """ from grammar import Grammar, Rule, Alt from token import OP """ start: metas rules ENDMARKER { Grammar(rules, metas) } | rules ENDMARKER { Grammar(rules, []) } metas: meta metas { [meta] + metas } | meta { [meta] } meta: "@" NAME STRING NEWLINE { (name.string, eval(string.string)) } rules: rule rules { [rule] + rules } | rule { [rule] } rule: NAME ":" alts NEWLINE { Rule(name.string, alts) } alts: alt "|" alts { [alt] + alts } | alt { [alt] } alt: items action { Alt(items, action) } | items { Alt(items, None) } items: item items { [item] + items } | item { [item] } item: NAME { name.string } | STRING { string.string } action: "{" stuffs "}" { stuffs } stuffs: stuff stuffs { stuff + " " + stuffs } | stuff { stuff } stuff: "{" stuffs "}" { "{" + stuffs + "}" } | NAME { name.string } | NUMBER { number.string } | STRING { string.string } | OP { None if op.string in ("{", "}") else op.string }
Maintenant que nous avons une méta-grammaire fonctionnelle, nous sommes presque prêts à apporter quelques améliorations.
Mais vous devez d'abord réfléchir un peu: des lignes vides! Il s'avère que le module de jeton tokenize crée des jetons supplémentaires pour suivre les tokenize ligne insignifiants (jeton NL ) et les commentaires (jeton COMMENT ). Au lieu de les inclure dans la grammaire (je l'ai essayé, il n'y a pas beaucoup de plaisir!), Il y a un morceau de code très simple que nous pouvons ajouter à notre classe tokenizer pour les filtrer. Voici la méthode peek_token améliorée:
def peek_token(self): if self.pos == len(self.tokens): while True: token = next(self.tokengen) if token.type in (NL, COMMENT): continue break self.tokens.append(token) self.report() return self.tokens[self.pos]
Cela supprime complètement les jetons NL et COMMENT , donc nous n'avons plus besoin de nous en préoccuper dans la grammaire.
Enfin, améliorons la méta-grammaire! Ils seront purement cosmétiques: je n'aime pas quand je suis obligé d'écrire toutes les alternatives sur une seule ligne. La méta grammaire que j'ai montrée ci-dessus ne s'analyse pas réellement à cause de telles choses:
start: metas rules ENDMARKER { Grammar(rules, metas) } | rules ENDMARKER { Grammar(rules, []) }
Cela est dû au fait que le tokenizer crée un token NEWLINE à la fin de la première ligne, et à ce moment le méta-analyseur considérera que c'est la fin de la règle. De plus, cette NEWLINE sera suivie du jeton INDENT , car la ligne suivante est en retrait. Jusqu'au début de la prochaine règle, un jeton DEDENT sera également présent.
Voici comment le gérer. Pour comprendre le comportement du module tokenize , nous pouvons regarder la séquence de jetons générés pour les blocs en retrait en exécutant le module tokenize tant que script et en lui passant du texte:
$ python -m tokenize foo bar baz dah dum ^D
Nous voyons que cela produit la séquence de jetons suivante (j'ai un peu simplifié la sortie du code ci-dessus):
NAME 'foo' NAME 'bar' NEWLINE INDENT NAME 'baz' NEWLINE NAME 'dah' NEWLINE DEDENT NAME 'dum' NEWLINE
Ainsi, un groupe sélectionné de chaînes est indiqué par les DEDENT et DEDENT . Maintenant, nous pouvons réécrire la rule méta-grammaire pour la rule comme suit:
rule: NAME ":" alts NEWLINE INDENT more_alts DEDENT { Rule(name.string, alts + more_alts) } | NAME ":" alts NEWLINE { Rule(name.string, alts) } | NAME ":" NEWLINE INDENT more_alts DEDENT { Rule(name.string, more_alts) } more_alts: "|" alts NEWLINE more_alts { alts + more_alts } | "|" alts NEWLINE { alts }
(Je décompose les actions en lignes pour qu'elles se lisent normalement dans une étroite colonne de texte. Ceci est possible car le tokenizer ignore les sauts de ligne à l'intérieur des accolades correspondantes.)
La beauté de ceci est que nous n'avons même pas besoin de changer le générateur: la structure de données créée par cette méta-grammaire améliorée est la même qu'auparavant. Faites également attention à la troisième option pour la rule : cela nous permet d'écrire:
start: | metas rules ENDMARKER { Grammar(rules, metas) } | rules ENDMARKER { Grammar(rules, []) }
que certains peuvent trouver plus propre que la version que j'ai montrée plus tôt. Les deux formes sont faciles à résoudre, nous n'avons donc pas besoin de discuter de style.
Dans le prochain article, je montrerai comment j'ai implémenté diverses fonctions PEG, telles que des éléments facultatifs, des répétitions et des info-bulles. (Pour être honnête, j'avais prévu d'en parler dans cet article, mais il est déjà trop volumineux. Je vais donc le diviser en deux parties.)
Licence pour cet article et code cité: CC BY-NC-SA 4.0