Implémentation des fonctionnalités restantes de PEG

Après avoir rassemblé toutes les parties du générateur d'analyseur PEG dans le post précédent, je suis prêt à montrer comment implémenter d'autres choses intéressantes.

Nous considérerons les fonctionnalités suivantes de PEG:

• Éléments nommés: NAME=item (le nom peut être utilisé dans l'action)
• Lookaheads: &item (positif) et !item (négatif)
• Regroupement des éléments entre parenthèses: ( item item ... )
• Éléments facultatifs: [item item ...] et item?
• Articles en double: item* (zéro ou plus) et item+ (un ou plusieurs)

Arguments nommés

Commençons par les éléments nommés. C'est pratique lorsque nous en avons plusieurs dans une alternative pour la même règle, par exemple:

 expr: term '+' term 

Nous pouvons nous référer au deuxième term en ajoutant le numéro 1 au nom de la variable, de sorte que dans l'action, il se présente comme ceci:

 expr: term '+' term { term + term1 } 

Mais tout le monde n'aime pas ça, et personnellement, je préfère écrire quelque chose comme ça:

 expr: left=term '+' right=term { left + right } 

Ceci est facilement pris en charge dans la méta-grammaire en modifiant la règle pour l' item comme suit:

 item: | NAME = atom { NamedItem(name.string, atom) } | atom { atom } atom: | NAME { name.string } | STRING { string.string } 

(Où l' atom n'est qu'un vieil item )

Cela nous oblige à ajouter la définition de la classe grammar.py à grammar.py . C'est l'une de ces classes de données que j'ai mentionnées plus tôt - elle possède également les attributs de name et d' item .

Nous devons également apporter de petites modifications au générateur de code, que je laisserai comme exercice au lecteur (ou vous pouvez consulter mon référentiel :-). Le code généré affectera désormais le résultat de la correspondance de chaque élément à une variable avec le nom spécifié, et non avec le nom obtenu à partir du nom de la règle d'élément. Cela fonctionnera également pour les éléments qui sont des jetons (de la forme NAME ou des littéraux de chaîne tels que ':=' ).

Lookahead

Suivi par lookahead. Vous avez probablement rencontré ce concept dans les expressions régulières. Pendant l'anticipation vers l'avant, l'alternative analysée peut être immédiatement rejetée ou acceptée, sans déplacer le pointeur du tokenizer.

En fait, lookahead peut être utilisé comme un moyen plus élégant d'éliminer la confusion avec les exceptions de l'analyseur, dont j'ai parlé dans un article précédent. Au lieu de permettre aux actions de rejeter une alternative déjà acceptée en renvoyant None, nous pouvons ajouter une instruction avant l' OP d'exclure "}" . L'ancienne règle ressemblait à ceci:

  | OP { None if op.string in ("{", "}") else op.string } 

La nouvelle version ressemble à ceci:

  | !"}" OP { op.string } 

Cela transfère le traitement des accolades de l'action à la grammaire, où il appartient. Nous n'avons pas besoin de vérifier "{" , car cela correspond à une alternative antérieure (en fait, cela est également vrai pour l'ancienne version, mais je l'ai oublié :-).

Nous ajoutons la grammaire des têtes de recherche à la règle pour l' item comme suit:

 item: | NAME = atom { NamedItem(name.string, atom) } | atom { atom } | "&" atom { Lookahead(atom, True) } | "!" atom { Lookahead(atom, False) } 

Encore une fois, nous devons ajouter la classe de données Lookahead à grammar.py (et l'importer dans @subheader !) Et modifier un peu le générateur en ajoutant la méthode d'assistance suivante:

  def lookahead(self, positive, func, *args): mark = self.mark() ok = func(*args) is not None self.reset(mark) return ok == positive 

Dans notre cas, le code généré pour cette alternative ressemble à ceci:

  if (True and self.lookahead(False, self.expect, "}") and (op := self.expect(OP)) ): return op . string 

Comme vous pouvez le voir dans le fragment de grammaire ci-dessus, l'anticipation ne peut pas obtenir de noms corrects. C'est facile à résoudre, mais je n'ai toujours aucune idée de son utilité. De plus, pour les prévisions négatives, la valeur sera toujours None .

Regroupement entre parenthèses

Maintenant, implémentons des groupes avec des crochets. Le meilleur endroit pour les ajouter au métagramme est la règle pour l' atom :

 atom: | NAME { name.string } | STRING { string.string } | "(" alts ")" { self.synthetic_rule(alts) } 

Les deux premières alternatives n'ont pas changé. L'action de la nouvelle alternative utilise un hack (dont l'implémentation reste inexpliquée), qui permet au méta-analyseur d'ajouter de nouvelles règles à la grammaire à la volée. Cette fonction d'assistance (définie dans le méta-analyseur) renvoie le nom du nouvel objet de règle. Il sera composé d'un préfixe fixe suivi d'un nombre, ce qui le rend unique, par exemple, _synthetic_rule_1 .

Vous pouvez demander ce qui se passe si la règle synthétique est finalement supprimée. Je ne sais pas comment éviter cela, mais il ne devrait pas y avoir de problème - dans le pire des cas, il y aura une règle inutilisée dans la grammaire. Et grâce à la mémorisation, la même action ne sera jamais exécutée deux fois pour la même position d'entrée, donc ce n'est pas un problème non plus (mais même si c'était le cas, dans le pire des cas nous aurions une règle morte).

L'utilisation d' alts entre parenthèses signifie que nous pouvons définir une barre verticale comme délimiteur dans un groupe. Par exemple, que notre nouvelle solution d'action ne correspondrait pas accidentellement { , nous pourrions changer la négation en ceci:

  | !("{" | "}") OP { op.string } 

De plus, les groupes peuvent également contenir des actions! Cela n'aiderait pas à résoudre le problème avec les actions, mais dans d'autres situations, cela pourrait être utile. Et comme nous générons de toute façon une règle synthétique, il ne nécessite aucun travail supplémentaire pour l'implémenter (à l'exception de l'implémentation de synthetic_rule :-).

Éléments optionnels

Comme dans l'ancien pgen, j'utilise des crochets pour indiquer un groupe de jetons optionnels. C'est là que cela s'avère utile. Par exemple, une règle de grammaire qui décrit une boucle Python for peut l'utiliser pour indiquer qu'une extension d' else peut exister. Et encore une fois, nous pouvons étendre la grammaire de l' atom comme suit:

 atom: | NAME { name.string } | STRING { string.string } | "(" alts ")" { self.synthetic_rule(alts) } | "[" alts "]" { Maybe(self.synthetic_rule(alts)) } 

Voici Maybe - Maybe une autre classe de données, avec un seul attribut d' item . Nous modifions le générateur de code pour que le résultat de la fonction synthétique n'échoue pas si cette valeur est None . Pour ce faire, vous pouvez ajouter or True dans l'implémentation. Par exemple, pour [term] :

 if (True and ((term := self.term()) or True) ): return term 

Articles en double

Le passage à la répétition est une autre fonction PEG utile (la notation est empruntée aux expressions régulières et est également utilisée dans pgen). Il existe deux formes: l'ajout de * à un atome signifie «zéro ou plusieurs répétitions», tandis que l'ajout de + signifie «une ou plusieurs répétitions». Pour d'autres raisons, j'ai dû réécrire les règles de grammaire pour l' item et l' atom , en ajoutant une règle intermédiaire, que j'ai appelée molecule :

 item: | NAME '=' molecule { NamedItem(name.string, molecule) } | "&" atom { Lookahead(atom) } | "!" atom { Lookahead(atom, False) } | molecule { molecule } molecule: | atom "?" { Maybe(atom) } | atom "*" { Loop(atom, False) } | atom "+" { Loop(atom, True) } | atom { atom } | "[" alts "]" { Maybe(self.synthetic_rule(alts)) } atom: | NAME { name.string } | STRING {string.string } | "(" alts ")" { self.synthetic_rule(alts) } 

Notez que cela introduit une syntaxe alternative pour les éléments optionnels ( atom? ). Cela ne nécessite pas d'efforts d'implémentation supplémentaires, car il s'agit simplement d'une autre façon de créer un nœud Maybe .

La refactorisation de ces règles était nécessaire car je ne souhaite pas rendre certaines situations valables:

• répétitions facultatives (puisque ce n'est qu'une répétition de zéro ou plus);
• répétitions (internes captureraient toutes les correspondances, car PEG utilise toujours un algorithme gourmand)
• valeurs facultatives répétées (ce qui interromprait l'analyse si l'élément facultatif ne correspond pas).

Cependant, ce n'est toujours pas une solution idéale, car vous pouvez écrire quelque chose comme (foo?)* . Il sera nécessaire d'ajouter une vérification à cette situation dans le générateur d'analyseur, mais je le ferai en dehors de l'article.

La classe de données Loop a deux attributs: item et nonempty . Le code généré utilisera la méthode loop() parser helper loop() . Elle est très similaire à la méthode lookahead() présentée précédemment:

  def loop(self, nonempty, func, *args): mark = self.mark() nodes = [] while node := func(*args) is not None: nodes.append(node) if len(nodes) >= nonempty: return nodes self.reset(mark) return None 

Si nonempty est False (dans le sens où la grammaire était * ), cela ne conduira pas à une erreur. Aucune entrée ne sera trouvée et une liste vide sera retournée. Pour que cela se produise, nous implémentons le générateur d'analyseur de sorte que ce is not None ajouté. Une vérification plus douce d'un article précédent retournerait False dans le cas d'une liste vide.

C'est tout pour aujourd'hui! J'allais discuter de l'opérateur «cut» ( ~ ) présent dans TatSu, mais jusqu'à présent je n'ai pas eu la chance de le rencontrer. Je ne suis même pas encore prêt à en discuter - la documentation TatSu ne donne qu'un exemple simple qui m'intéresse un peu. Je ne l'ai pas trouvé dans d'autres générateurs d'analyseurs PEG, donc, peut-être, cette fonctionnalité n'est que TatSu. Peut-être qu'un jour je parlerai de lui. (Pendant ce temps, je l'ai implémenté juste au cas où, on ne sait jamais. :-)

Je pense que le prochain article portera sur mon expérience dans l'écriture d'une grammaire PEG capable d'analyser la grammaire Python. Je vais vous raconter comment s'est déroulé le sprint des développeurs du noyau Python, qui était à Londres cette semaine avec le soutien logistique de Bloomberg et le soutien financier de PSF et d'autres sociétés (par exemple, Dropbox m'a payé l'hôtel et le vol). Un merci spécial à Emily Morhouse et Pablo Galindo Salgado, qui ont beaucoup aidé dans la mise en œuvre des outils et des tests. Ensuite, nous allons écrire des tests de performances, puis nous allons ajouter des actions à cette grammaire afin qu'elle puisse créer des arborescences AST qui peuvent être compilées par le compilateur de code d'octets CPython. Il y a tellement de choses plus intéressantes à venir!

Licence pour cet article et code cité: CC BY-NC-SA 4.0