Inspiré uniquement par une compréhension partielle du PEG, j'ai décidé d'essayer de le mettre en œuvre. Le résultat n'est peut-être pas le meilleur parmi les analyseurs PEG à usage général - il y en a déjà beaucoup (par exemple, TatSu est écrit en Python et génère du code Python) - mais c'est un bon moyen de comprendre PEG. À l'avenir, je veux le remplacer par l'implémentation actuelle de l'analyseur en CPython.
Contenu de la série Python PEG Parser Dans cette section, je jette les bases de la compréhension du travail de l'analyseur, en utilisant un exemple d'une implémentation simple auto-écrite de la grammaire du jouet d'un article précédent.
(Au fait, à titre expérimental, je ne place pas de liens dans mon texte. Si vous ne comprenez pas quelque chose, vous pouvez simplement le rechercher sur Google. :-)
En règle générale, un PEG utilise un analyseur de descente récursif avec un tampon illimité pour revenir. Voici une grammaire de jouet d'un article précédent:
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
L'analyseur super abstrait de la descente récursive pour ce langage définira sa fonction pour chaque règle dans laquelle les alternatives seront comprises. Par exemple, pour l' statement , nous aurions cette fonction:
def statement(): if assignment(): return True if expr(): return True if if_statement(): return True return False
Bien sûr, c'est un exemple trop simpliste: il omet des détails importants, par exemple, ce qui est appliqué à l'entrée de cette fonction et quel sera le résultat de son exécution.
Commençons par les arguments. Les analyseurs classiques utilisent un tokenizer séparé, qui divise l'entrée (fichier texte ou ligne) en une série de tokens, tels que des mots clés, des identifiants (noms), des nombres et des opérateurs. Les analyseurs PEG (comme d'autres analyseurs modernes comme ANTLR) combinent souvent la tokenisation et l'analyse, mais pour mon projet, j'ai décidé de laisser un tokenizer séparé.
La tokenisation Python est assez compliquée, donc je ne veux pas l'implémenter sur les règles PEG. Par exemple, vous devez suivre l'indentation (cela nécessite une pile à l'intérieur du tokenizer); Le traitement des sauts de ligne en Python est également intéressant (ils sont significatifs, à l'exception de ceux placés entre crochets correspondants). De nombreux types de chaînes provoquent également une certaine complexité. En bref, je n'ai rien à redire sur le tokenizer Python existant, donc je veux le laisser tel quel. Soit dit en passant, CPython a deux jetons: celui interne, qui est utilisé par l'analyseur, il est écrit en C, et celui de la bibliothèque standard, qui est une copie exacte implémentée en Python pur. Cela sera utile dans mon projet.
Un tokenizer classique possède généralement une interface simple composée d'une seule fonction get_token() . À chaque fois, il renvoie le jeton suivant de la séquence d'entrée, analysant un groupe de caractères. Le module tokenize de CPython ne fait pas exception: son API principale est un générateur qui émet un jeton à la fois. Chaque jeton est un objet de type TypeInfo , qui a plusieurs champs, dont le plus important est le type de jeton (par exemple, NAME , NUMBER , STRING ) et sa valeur de chaîne est l'ensemble de caractères qui le compose (par exemple, abc , 42 ou "Hello, world" ). Il existe également des champs supplémentaires. Par exemple, pour l'index de jeton dans le flux d'entrée, ce qui est utile dans les messages d'erreur.
Un type spécial de jeton est ENDMARKER , qui indique que la fin du fichier d'entrée a été atteinte. Le générateur tombera si vous l'ignorez et essayez d'obtenir le prochain jeton.
Mais j'étais distrait. Comment réalisons-nous des retours illimités? Pour faire reculer la liste des jetons, vous devez pouvoir vous souvenir de la position dans le code source et réanalyser à partir de ce point. L'API tokenizer ne nous permet pas de déplacer son pointeur, mais vous pouvez capturer le flux de jetons dans un tableau et le lire à partir de là, ce que nous ferons. Vous pouvez également répéter cela avec itertools.tee() , mais cela est probablement moins efficace dans notre cas, si vous regardez les avertissements dans la documentation.
Je suppose que vous pouvez tout d'abord tokeniser toutes les entrées de la liste, puis les utiliser comme entrées pour l'analyseur. Mais s'il y avait un jeton non valide à la fin du fichier (par exemple, une ligne avec un guillemet de fermeture manquant) et qu'il y avait également une erreur de syntaxe dans le fichier, vous recevrez d'abord un message d'erreur du tokenizer. Je pense que cela est mauvais pour l'utilisateur, car une erreur de syntaxe peut être la principale cause d'une ligne invalide. J'ai donc des exigences légèrement différentes pour le tokenizer, en particulier, il devrait être implémenté comme une liste paresseuse.
L'API principale est très simple. L'objet Tokenizer encapsule un tableau de jetons et sa position dans ce tableau. Il a trois méthodes principales:
get_token() renvoie le prochain jeton, en déplaçant le pointeur (ou lit le prochain jeton de la source, si nous sommes à la fin du tampon de jeton);mark() renvoie la position actuelle dans le tampon;reset(pos) définit la position dans le tampon (l'argument doit être obtenu à partir de mark() ).
Nous avons ajouté une fonction d'assistance peek_token() , qui renvoie le jeton suivant sans déplacer la position dans le tampon.
Voici à quoi ressemble la base de la classe Tokenizer :
class Tokenizer: def __init__(self, tokengen): """Call with tokenize.generate_tokens(...).""" self.tokengen = tokengen self.tokens = [] self.pos = 0 def mark(self): return self.pos def reset(self, pos): self.pos = pos def get_token(self): token = self.peek_token() self.pos += 1 return token def peek_token(self): if self.pos == len(self.tokens): self.tokens.append(next(self.tokengen)) return self.tokens[self.pos]
Ici, quelque chose est omis pour des raisons de simplicité (par exemple, les noms des méthodes et des variables d'instance doivent commencer par un trait de soulignement), mais ce n'est qu'un prototype de l'API Tokenizer .
L'analyseur doit également devenir une classe pour que statement() , expr() , etc. pourrait être mis en œuvre comme méthodes. Le tokenizer deviendra une variable d'instance, mais je ne veux pas que les méthodes de l'analyseur appellent directement get_token() - à la place, nous implémentons la méthode wait() dans la classe Parser , qui peut réussir ou échouer comme la méthode de l'analyseur. L'argument de la fonction wait() est le jeton attendu: soit une chaîne (par exemple, + ) ou un type de jeton (par exemple, NAME ). Le type de la valeur de retour n'est pas encore important, j'y reviendrai après avoir discuté du résultat du travail de l'analyseur.
Laissez les fonctions de règle de grammaire renvoyer uniquement True ou False . C'est bon pour l'informatique théorique (là, l'analyseur répond à la question «Est- ce une chaîne valide dans la langue?»), Mais pas pour nous. Notre tâche est de créer un AST. Réécrivons donc ce code afin que chaque méthode d'analyse renvoie un objet Node en cas de succès ou None en cas d'échec.
La classe Node peut être très simple:
class Node: def __init__(self, type, children): self.type = type self.children = children
Ici, type détermine le type du nœud AST (par exemple, add ou if ), et les descendants sont une liste de nœuds et de jetons (instances TokenInfo ). Cela suffit pour que le compilateur génère du code ou effectue d'autres analyses, telles que le linting ou la vérification de type statique. Bien qu'à l'avenir, j'aimerais changer la façon dont AST est présenté.
Pour tenir dans ce schéma, la méthode expect() doit renvoyer un objet TokenInfo en cas de succès et None en cas d'échec. Pour pouvoir revenir aux jetons précédents, j'encapsule les appels aux méthodes mark() et reset() du tokenizer (ici l'API ne change pas). Voici ce qui s'est passé:
class Parser: def __init__(self, tokenizer): self.tokenizer = tokenizer def mark(self): return self.tokenizer.mark() def reset(self, pos): self.tokenizer.reset(pos) def expect(self, arg): token = self.tokenizer.peek_token() if token.type == arg or token.string == arg: return self.tokenizer.get_token() return None
Encore une fois: j'ai omis certains détails, mais cela fonctionne déjà.
Maintenant, je dois introduire une exigence importante pour les méthodes d'analyse syntaxique. Chacun doit retourner Node , en plaçant le tokenizer après le dernier token de la règle de grammaire qu'il a reconnu; soit None et laissez la position du tokenizer inchangée. Si la méthode de l'analyseur lit plusieurs jetons puis tombe, elle doit restaurer la position du tokenizer. Pour ce faire, mark() et reset() sont prévus. Notez que expect() obéit également à cette règle.
Voici donc un croquis de l'analyseur réel. Ici, j'utilise l'opérateur morse de Python 3.8 ( := ):
class ToyParser(Parser): def statement(self): if a := self.assignment(): return a if e := self.expr(): return e if i := self.if_statement(): return i return None def expr(self): if t := self.term(): pos = self.mark() if op := self.expect("+"): if e := self.expr(): return Node("add", [t, e]) self.reset(pos) if op := self.expect("-"): if e := self.expr(): return Node("sub", [t, e]) self.reset(pos) return t return None def term(self):
J'ai omis la mise en œuvre de certaines méthodes afin que le lecteur ait l'occasion de s'exercer lui-même. C'est vraiment mieux que de simplement lire comment un tel analyseur est implémenté. Au final, nous générerons automatiquement ce code à partir de la grammaire. Les constantes telles que NAME et NUMBER sont importées du module de token de la bibliothèque standard. Cela nous lie davantage à l'implémentation actuelle du tokenizer Python. Si nous voulons créer un analyseur PEG généralisé, nous devons trouver des moyens d'éviter cela.
Notez également que je suis un peu trompé. La méthode expr doit être laissée récursive, mais j'ai rendu le parseur droit récursif car le parseur récursif de descente ne fonctionne pas avec les règles de grammaire récursive gauche. Cela peut être corrigé, mais c'est toujours le sujet de certaines recherches scientifiques, et je voudrais en parler séparément. Gardez à l'esprit que cette implémentation n'est pas 100% cohérente avec notre grammaire simplifiée.
Les éléments clés que je veux que vous compreniez jusqu'à présent:
- Les règles de grammaire correspondent aux méthodes d'analyse syntaxique et lorsqu'une règle de grammaire se réfère à une autre, elle appelle une méthode d'une autre règle.
- Lorsqu'une séquence de jetons peut être interprétée différemment, les méthodes d'analyseur correspondantes sont invoquées les unes après les autres.
- Lorsqu'une règle de grammaire fait référence à un jeton, la méthode appelle la fonction
expect() . - Si l'analyseur reconnaît avec succès sa règle de grammaire à la position actuelle, il renvoie le nœud AST correspondant; s'il ne peut pas reconnaître sa règle de grammaire, il renvoie
None . - Les méthodes d'analyseur doivent réinitialiser explicitement la position du tokenizer lorsqu'elles arrêtent l'analyse après avoir utilisé un ou plusieurs jetons (directement ou indirectement, en invoquant une autre méthode d'analyse réussie). Cela s'applique non seulement lorsque l'une des options est rejetée afin de passer à la suivante, mais également lorsque l'analyse est rejetée dans son ensemble.
Si toutes les méthodes d'analyse obéissent à ces règles, il n'est pas nécessaire d'envelopper chacune dans les appels mark() et reset() . Cela peut être prouvé par induction.
De plus, il est tentant d'essayer de se débarrasser des appels explicites à mark() et reset() à l'aide du gestionnaire de contexte et de l'instruction with , mais cela ne fonctionnera pas: vous ne devriez pas appeler reset() cas de succès! Comme autre correction, vous pouvez essayer d'utiliser des exceptions pour le flux de contrôle afin que le gestionnaire de contexte sache si le tokenizer doit être réinitialisé (je pense que TatSu fait quelque chose de similaire). Par exemple, quelque chose comme ceci:
def statement(self): with self.alt(): return self.assignment() with self.alt(): return self.expr() with self.alt(): return self.if_statement() raise ParsingFailure
En particulier, une petite échelle d' if dans atom() pour reconnaître une expression entre crochets peut s'écrire:
with self.alt(): self.expect("(") e = self.expr() self.expect(")") return e
Mais il me semble trop "magique" - lors de la lecture d'un tel code, vous devez vous rappeler que chaque méthode d'analyse (y compris wait() ) peut lever une exception. Et que cette exception est interceptée et ignorée par le gestionnaire de contexte dans l'instruction with . C'est plutôt inhabituel, bien que réalisable (en retournant True depuis __exit__ ). Cependant, mon objectif ultime est de générer du code en C, pas en Python, et en C il n'y a pas with instruction with pour changer le flux de contrôle.
Quoi qu'il en soit, voici quelques sujets pour les parties suivantes:
- génération de méthodes d'analyseur à partir de la grammaire;
- packrat-parsing (mémorisation);
- Fonctionnalités EBNF telles que
(x | y) , [xy ...] , x* , x+ ; - traçage (pour déboguer un analyseur ou une grammaire);
- Fonctionnalités PEG telles que l'anticipation et la coupe;
- comment gérer les règles récursives gauches;
- Génération de code C
Licence pour cet article et code cité: CC BY-NC-SA 4.0