Maintenant que j'ai esquissé les bases d'un analyseur propriétaire, passons à la génération de ses méthodes à partir de la grammaire, comme je l'ai promis. Je montrerai également comment implémenter un analyseur packrat en utilisant le décorateur @memoize .
Contenu de la série Python PEG Parser La dernière fois, nous avons examiné quelques méthodes d'analyse. Avec certaines restrictions que nous supprimerons un peu plus tard, elles sont faciles à générer automatiquement à partir de la grammaire.
Nous avons besoin de deux choses: quelque chose qui lit la grammaire et construit une structure de données appropriée; et quelque chose qui prend cette structure de données et génère un analyseur. Nous avons également besoin d'autres méthodes d'aide, mais elles ne sont pas intéressantes, je vais donc les omettre.
Donc, nous créons un compilateur de compilateur simple. Je vais simplifier un peu la notation grammaticale dans la mesure où nous n'avons que des règles et des alternatives; c'est en fait suffisant pour la grammaire du jouet que j'ai utilisée dans les parties précédentes:
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
En utilisant la notation complète, nous pouvons décrire la grammaire comme:
grammar: rule+ ENDMARKER rule: NAME ':' alternative ('|' alternative)* NEWLINE alternative: item+ item: NAME | STRING
Il s'agit de notre première méta-grammaire (grammaire pour les grammaires), et notre générateur d'analyseur sera un méta-compilateur (un compilateur est un programme qui traduit des programmes d'une langue à une autre; un méta-compilateur est un compilateur où l'entrée est une grammaire, et la sortie est un analyseur).
Un moyen simple de décrire une méta-grammaire consiste à utiliser uniquement les types de données intégrés: la partie droite de la règle est une liste de listes d'éléments, chacun pouvant être simplement une chaîne. (Soit dit en passant, nous pouvons séparer NAME et STRING en vérifiant si le premier caractère est un guillemet)
Pour les règles, j'utilise la classe Rule simple, et toute la grammaire est une liste de ces objets. Voici la classe Rule , à l'exclusion de __repr__ et __eq__ :
class Rule: def __init__(self, name, alts): self.name = name self.alts = alts
Et voici la classe GrammarParser qui l'utilise:
class GrammarParser(Parser): def grammar(self): pos = self.mark() if rule := self.rule(): rules = [rule] while rule := self.rule(): rules.append(rule) if self.expect(ENDMARKER): return rules
Faites attention à l'utilisation de ENDMARKER . Là, je m'assure qu'il ne reste rien après la dernière règle (et cela peut arriver s'il y a une faute de frappe dans la grammaire). J'ai également indiqué l'endroit où la méthode grammar() renvoie une liste de règles. Tout le reste est très similaire à la classe ToyParser du dernier article, donc je ne m'y attarderai pas. Notez simplement que item() retourne une chaîne, alternative() retourne une liste de chaînes, et la variable alts intérieur de rule() recueille une liste de liste de chaînes. Ensuite, la méthode rule() combine le nom de la règle (chaîne) et le convertit en objet Rule .
Si nous appliquons cet algorithme à notre grammaire du jouet, la méthode grammar() renverra la liste de règles suivante:
[ Rule('statement', [['assignment'], ['expr'], ['if_statement']]), Rule('expr', [['term', "'+'", 'expr'], ['term', "'-'", 'term'], ['term']]), Rule('term', [['atom', "'*'", 'term'], ['atom', "'/'", 'atom'], ['atom']]), Rule('atom', [['NAME'], ['NUMBER'], ["'('", 'expr', "')'"]]), Rule('assignment', [['target', "'='", 'expr']]), Rule('target', [['NAME']]), Rule('if_statement', [["'if'", 'expr', "':'", 'statement']]), ]
Maintenant que nous avons la partie d'analyse de notre méta-compilateur, créons un générateur de code. Ensemble, ils forment un méta-compilateur élémentaire:
def generate_parser_class(rules): print(f"class ToyParser(Parser):") for rule in rules: print() print(f" @memoize") print(f" def {rule.name}(self):") print(f" pos = self.mark()") for alt in rule.alts: items = [] print(f" if (True") for item in alt: if item[0] in ('"', "'"): print(f" and self.expect({item})") else: var = item.lower() if var in items: var += str(len(items)) items.append(var) if item.isupper(): print(" " + f"and ({var} := self.expect({item}))") else: print(f" " + f"and ({var} := self.{item}())") print(f" ):") print(f" " + f"return Node({rule.name!r}, [{', '.join(items)}])") print(f" self.reset(pos)") print(f" return None")
Ce code est assez moche, mais il fonctionne (en quelque sorte), et à l'avenir je le réécrirai quand même.
Certaines lignes à l'intérieur de la for alt in rule.alts peuvent nécessiter une explication: pour chaque élément de l'alternative, nous choisissons l'une des 3 options:
- si l'élément est un littéral de chaîne, par exemple
'+' , nous générons self.expect('+') - si l'élément est entièrement en majuscule, par exemple
NAME , nous générons (name := self.expect(NAME)) - sinon, par exemple, si elle est
expr , nous générons (expr := self.expr())
S'il y a plusieurs éléments avec le même nom dans une variante (par exemple, le term '-' term ), alors nous ajoutons un chiffre à la seconde. Il y a aussi une petite erreur que je corrigerai dans le prochain épisode.
Voici un peu le résultat de son travail (toute la classe serait très ennuyeuse). Ne vous inquiétez pas du code redondant if (True and ... ) qui est nécessaire pour que chaque condition générée puisse commencer par and . Le compilateur d'octets Python optimise cela.
class ToyParser(Parser): @memoize def statement(self): pos = self.mark() if (True and (assignment := self.assignment()) ): return Node('statement', [assignment]) self.reset(pos) if (True and (expr := self.expr()) ): return Node('statement', [expr]) self.reset(pos) if (True and (if_statement := self.if_statement()) ): return Node('statement', [if_statement]) self.reset(pos) return None ...
Faites attention au décorateur @memoize : je l'ai introduit pour passer à un autre sujet: utiliser la mémorisation pour rendre l'analyseur généré assez rapidement.
Voici la fonction memoize() qui implémente ce décorateur:
def memoize(func): def memoize_wrapper(self, *args): pos = self.mark() memo = self.memos.get(pos) if memo is None: memo = self.memos[pos] = {} key = (func, args) if key in memo: res, endpos = memo[key] self.reset(endpos) else: res = func(self, *args) endpos = self.mark() memo[key] = res, endpos return res return memoize_wrapper
Comme dans d'autres décorateurs, il contient une fonction imbriquée qui remplace (ou enveloppe) une fonction décorée, par exemple, la méthode statement() de la classe ToyParser . Étant donné que la fonction encapsulée est une méthode, l'encapsuleur est également une méthode: son premier argument est appelé self et fait référence à l'instance ToyParser pour laquelle la méthode décorée est appelée.
L'encapsuleur met en cache le résultat de l'appel de méthode pour chaque position d'entrée - c'est pourquoi il est appelé l'analyseur packrat! [env. trans. packrat est un «voleur», mais ce terme n'est pas traduit dans les sources en russe.] Cache est un dictionnaire de dictionnaires, qui est stocké dans une instance Parser . La clé du dictionnaire externe est la position dans le flux de données d'entrée; J'ai également ajouté self.memos = {} à Parser .__ init__() pour l'initialiser. Des dictionnaires internes sont ajoutés au besoin; leurs clés consistent en une méthode et ses arguments. (Il n'y a pas d'arguments dans la conception actuelle, mais nous pourrions mémoriser la fonction expect() qui en a une, ce qui est assez trivial)
Le résultat de la méthode d'analyse est présenté sous la forme d'un tuple, car il y a vraiment deux valeurs: le résultat lui-même (pour nos méthodes générées, c'est Node pour la règle de correspondance) et un pointeur vers la position actuelle dans le flux d'entrée, que nous obtenons de self.mark() . Ainsi, nous mettons en cache à la fois la valeur de retour ( res ) et la nouvelle position ( endpos ) dans le dictionnaire interne avec des valeurs mémorisées. Lors des appels ultérieurs à la même méthode d'analyse avec les mêmes arguments dans la même position d'entrée, nous les retirerons du cache. Pour ce faire, déplacez simplement le pointeur sur la position d'entrée à l'aide de self.reset() et regardez dans le cache.
Il est également important de mettre en cache les résultats négatifs - en fait, la plupart des appels seront négatifs. Dans ce cas, la valeur de retour est None et la position d'entrée ne change pas. Vous pouvez ajouter assert pour vérifier cela.
Remarque En Python, il est habituel d'implémenter un cache dans une variable locale dans la fonction memoize() . Dans notre cas, cela ne fonctionnera pas: comme je l'ai découvert à la toute fin du débogage, chaque instance de Parser doit avoir son propre cache. Cependant, vous pouvez vous débarrasser des dictionnaires imbriqués en utilisant ( pos , func , args ) comme clé.
La semaine prochaine, je préparerai du code et des traces pour montrer comment tout cela est réellement assemblé et exécuté lors de l'analyse d'un exemple de programme. Je suis toujours à la recherche d'un meilleur moyen de visualiser la collaboration du tampon de tokenisation, de l'analyseur et du cache. Je pourrai peut-être créer un gif animé en ASCII au lieu d'afficher simplement les listes de trace sous forme de texte.
Licence pour cet article et code cité: CC BY-NC-SA 4.0