La grammaire est encore meilleure si vous pouvez ajouter (une) sémantique selon les règles. En particulier, pour l'analyseur Python que je développe, je dois renvoyer le nœud AST de chaque alternative, car je veux m'en tenir à l'implémentation AST actuelle dans CPython.
Contenu de la série Python PEG Parser De nombreuses grammaires utilisent une convention qui vous permet d'ajouter des actions aux règles - généralement un bloc de code entre {accolades}. Plus précisément, ils sont liés à des alternatives. Le code de ce bloc est écrit dans le même langage que le reste du compilateur, par exemple en C, complété par une certaine capacité à se référer aux éléments de l'alternative. Dans le pgen Python d'origine, je n'ai pas ajouté cette fonctionnalité, mais pour un nouveau projet, je voudrais l'implémenter.
Voici comment nous le faisons pour le générateur d'analyseur simplifié que je développe dans le cadre de cette série de publications.
La syntaxe des actions est généralement la suivante:
rule: item item item { action 1 } | item item { action 2 }
Comme cela rend la grammaire plus verbeuse, les générateurs d'analyseurs autorisent généralement des règles multi-lignes, par exemple:
rule: item item item { action 1 } | item item { action 2}
Cela rend l'analyseur un peu plus compliqué, mais il est important pour la lisibilité, donc je soutiendrai un tel enregistrement.
La question éternelle est de savoir quand exécuter ce bloc. Dans Yacc / Bison, cela se fait immédiatement après que l'analyseur a reconnu la règle, car il n'y a pas de restauration dans la liste des jetons. Exécuter chaque action exactement une fois signifie qu'il peut y avoir des effets secondaires globaux (comme la mise à jour de la table des symboles ou une autre structure de données du compilateur).
Dans les analyseurs PEG avec leur retour illimité à la liste des jetons, nous avons plusieurs options:
- N'exécutez aucune action tant que tout n'a pas été analysé. Je ne considérerai pas cela, car je veux créer un droit AST pendant l'analyse.
- Effectue chaque fois que son alternative est reconnue. Leur code doit être idempotent (c'est-à-dire avoir le même effet quel que soit le nombre de fois qu'il a été exécuté). Cela signifie que l'action peut être exécutée, mais son résultat peut finalement être rejeté.
- Mettez le résultat en cache et exécutez l'action uniquement pour la première fois - lorsque son alternative est reconnue dans cette position.
J'ai choisi la troisième option - dans tous les cas, nous mettons en cache le résultat de la méthode en utilisant l'algorithme packrat, afin que nous puissions également mettre en cache les résultats.
Quant au contenu de {curlies}, il utilise traditionnellement du code C avec un accord basé sur $ pour faire référence aux éléments d'une alternative reconnue (par exemple, $1 pour faire référence au premier élément) et l'affectation $$ pour indiquer le résultat de l'action. Cela semble très démodé (j'ai des souvenirs d'utiliser l'affectation de fonction dans Algol-60 pour indiquer la valeur de retour), donc je vais le rendre plus Pythonique: à l'intérieur des crochets, vous devrez mettre une expression, dont le résultat sera le résultat de l'action, et les liens vers les éléments seront noms simples donnant le texte de l'élément. À titre d'exemple, voici une calculatrice simple qui peut additionner et soustraire des nombres:
start: expr NEWLINE { expr } expr: expr '+' term { expr + term } | expr '-' term { expr - term } | term { term } term: NUMBER { float(number.string) }
Exécutons-le sur l'exemple de 100 + 50 - 38 - 70 . Il calculera la réponse, car il reconnaît les parties en calculant ((100 + 50) - 38) - 70 , ce qui bien sûr est 42 .
Un petit détail: dans l'action pour term number variable contient un objet TokenInfo , vous devez donc y utiliser son attribut .string pour obtenir le jeton sous forme de chaîne.
Que faisons-nous lorsqu'une alternative a plusieurs occurrences avec le même nom de règle? Le générateur d'analyseur donne à chaque occurrence un nom unique, en ajoutant 1 , 2 , etc. Pour les occurrences ultérieures au sein de la même alternative. Par exemple:
factor: atom '**' atom { atom ** atom1 } | atom { atom }
La mise en œuvre complète est plutôt ennuyeuse, donc je ne voudrais pas m'y attarder. Je vous invite à regarder dans mon référentiel et à jouer avec le code :
python3.8 -m story5.driver story5/calc.txt -g story5.calc.CalcParser
La visualisation vous permet désormais de vous déplacer d'avant en arrière à l'aide des touches fléchées gauche et droite!
Licence pour cet article et code cité: CC BY-NC-SA 4.0