La Technologie

Stork, Partie 2: Création d'un analyseur d'expression

Dans cette partie de notre série, nous aborderons l'un des composants les plus délicats (du moins à mon avis) du scripting d'un moteur de langage, qui est un élément essentiel de tout langage de programmation: l'analyseur d'expression.

Une question qu’un lecteur pourrait se poser - et à juste titre - est la suivante: pourquoi n’utilisons-nous pas simplement des outils ou bibliothèques sophistiqués, déjà à notre disposition?

Pourquoi n’utilisons-nous pas Lex, YACC, Bison, Boost Spirit ou au moins des expressions régulières?

Tout au long de notre relation, ma femme a remarqué un de mes traits que je ne peux nier: chaque fois que je suis confronté à une question difficile, je fais une liste. Si vous y réfléchissez, c'est parfaitement logique - j'utilise la quantité pour compenser le manque de qualité de ma réponse.

Je vais faire la même chose maintenant.

Je souhaite utiliser le C ++ standard. Dans ce cas, ce sera C ++ 17. Je pense que le langage est assez riche en soi, et je lutte contre l'envie d'ajouter autre chose que la bibliothèque standard dans le mix.
Lorsque j'ai développé mon premier langage de script, je n’ai utilisé aucun outil sophistiqué. J'étais sous pression et dans un délai serré, mais je ne savais pas comment utiliser Lex, YACC ou quelque chose de similaire. Par conséquent, j'ai décidé de tout développer manuellement.
Plus tard, j'ai trouvé un blog par un développeur de langage de programmation expérimenté, qui déconseillait d'utiliser l'un de ces outils. Il a dit que ces outils résolvent la partie la plus facile du développement du langage, donc dans tous les cas, vous vous retrouvez avec les choses difficiles. Je ne trouve pas ce blog pour le moment, comme il y a longtemps, quand Internet et moi étions jeunes.
En même temps, il y avait un mème qui disait: «Vous avez un problème que vous décidez de résoudre en utilisant des expressions régulières. Maintenant, vous avez deux problèmes.
Je ne connais pas Lex, YACC, Bison ou quelque chose de similaire. Je connais Boost Spirit, et c'est une bibliothèque pratique et étonnante, mais je préfère toujours avoir un meilleur contrôle sur l'analyseur.
J'aime faire ces composants manuellement. En fait, je pourrais simplement donner cette réponse et supprimer complètement cette liste.

Le code complet est disponible sur mon Page GitHub .

Itérateur de jetons

Il y a quelques changements dans le code de Partie 1 .

Ce sont pour la plupart des correctifs simples et de petits changements, mais un ajout important au code d'analyse existant est la classe token_iterator. Cela nous permet d'évaluer le jeton actuel sans le supprimer du flux, ce qui est vraiment pratique.

class tokens_iterator { private: push_back_stream& _stream; token _current; public: tokens_iterator(push_back_stream& stream); const token& operator*() const; const token* operator->() const; tokens_iterator& operator++(); explicit operator bool() const; };

Il est initialisé avec push_back_stream, puis il peut être déréférencé et incrémenté. Il peut être vérifié avec un cast booléen explicite, qui sera évalué à false lorsque le jeton actuel est égal à eof.

Langue typée statiquement ou dynamiquement?

Il y a une décision que je dois prendre dans cette partie: ce langage sera-t-il typé statiquement ou dynamiquement?

À typé statiquement language est un langage qui vérifie les types de ses variables au moment de la compilation.

À typé dynamiquement langage, par contre, ne le vérifie pas lors de la compilation (s’il existe une compilation, ce qui n’est pas obligatoire pour un langage typé dynamiquement) mais lors de l’exécution. Par conséquent, des erreurs potentielles peuvent vivre dans le code jusqu'à ce qu'elles soient touchées.

C'est un avantage évident des langages typés statiquement. Tout le monde aime attraper ses erreurs le plus tôt possible. Je me suis toujours demandé quel était le plus gros avantage des langages à typage dynamique, et la réponse m'a frappé ces dernières semaines: C'est beaucoup plus facile à développer!

Le langage précédent que j'ai développé était typé dynamiquement. J'étais plus ou moins satisfait du résultat et l'écriture de l'analyseur d'expression n'était pas trop difficile. En gros, vous n’avez pas à vérifier les types de variables et vous vous fiez aux erreurs d’exécution, que vous codez presque spontanément.

Par exemple, si vous devez écrire le binaire + et que vous voulez le faire pour les nombres, il vous suffit d'évaluer les deux côtés de cet opérateur comme des nombres dans le runtime. Si l'un des côtés ne peut pas évaluer le nombre, vous lancez simplement une exception. J'ai même implémenté la surcharge d'opérateurs en vérifiant les informations de type d'exécution des variables dans une expression, et les opérateurs faisaient partie de ces informations d'exécution.

Dans le premier langage que j'ai développé (c'est mon troisième), j'ai fait une vérification de type au moment de la compilation, mais je n'en avais pas pleinement profité. L'évaluation de l'expression dépendait toujours des informations de type d'exécution.

Maintenant, j'ai décidé de développer un langage à typage statique, et cela s'est avéré être une tâche beaucoup plus difficile que prévu. Cependant, comme je ne prévois pas de le compiler en binaire ou en tout type de code d'assemblage émulé, certains types d'informations existeront implicitement dans le code compilé.

Les types

Types: nombres, chaînes, fonctions, tableaux

Au strict minimum des types que nous devons prendre en charge, nous commencerons par ce qui suit:

Nombres
Cordes
Les fonctions
Tableaux

Bien que nous puissions les ajouter à l'avenir, nous ne prendrons pas en charge les structures (ou classes, enregistrements, tuples, etc.) au début. Cependant, nous garderons à l'esprit que nous pourrons les ajouter plus tard, afin de ne pas sceller notre destin avec des décisions difficiles à changer.

Tout d'abord, je voulais définir le type comme une chaîne, qui suivra une convention. Chaque identifiant conserverait cette chaîne par valeur au moment de la compilation, et nous devrons parfois l'analyser. Par exemple, si nous encodons le type de tableau de nombres comme «[nombre]», alors nous devrons couper le premier et le dernier caractère afin d'obtenir un type interne, qui est «nombre» dans ce cas. C’est une très mauvaise idée si vous y réfléchissez.

Ensuite, j'ai essayé de l'implémenter en tant que classe. Cette classe aurait toutes les informations sur le type. Chaque identifiant conserverait un pointeur partagé vers cette classe. Au final, j'ai pensé avoir le registre de tous les types utilisé lors de la compilation, donc chaque identifiant aurait le pointeur brut sur son type.

J'ai aimé cette idée, alors nous nous sommes retrouvés avec ce qui suit:

using type = std::variant; using type_handle = const type*;

Les types simples sont membres de l'énumération:

enum struct simple_type { nothing, number, string, };

Membre d'énumération nothing est ici comme un espace réservé pour void, que je ne peux pas utiliser car il s'agit d'un mot clé en C ++.

Les types de tableaux sont représentés avec la structure ayant le seul membre de type_handle.

struct array_type { type_handle inner_type_id; };

De toute évidence, la longueur du tableau ne fait pas partie de array_type, donc les tableaux grandiront dynamiquement. Cela signifie que nous finirons par std::deque ou quelque chose de similaire, mais nous y reviendrons plus tard.

Un type de fonction est composé de son type de retour, du type de chacun de ses paramètres et du fait que chacun de ces paramètres soit passé par valeur ou par référence.

struct function_type { struct param { type_handle type_id; bool by_ref; }; type_handle return_type_id; std::vector param_type_id; };

Maintenant, nous pouvons définir la classe qui conservera ces types.

class type_registry { private: struct types_less{ bool operator()(const type& t1, const type& t2) const; }; std::set _types; static type void_type; static type number_type; static type string_type; public: type_registry(); type_handle get_handle(const type& t); static type_handle get_void_handle() { return &void_type; } static type_handle get_number_handle() { return &number_type; } static type_handle get_string_handle() { return &string_type; } };

Les types sont conservés dans std::set, car ce conteneur est stable, ce qui signifie que les pointeurs vers ses membres sont valides même après l'insertion de nouveaux types. Il y a la fonction get_handle, qui enregistre le type passé et y renvoie le pointeur. Si le type est déjà enregistré, il renverra le pointeur vers le type existant. Il existe également des fonctions pratiques pour obtenir des types primitifs.

Comme pour la conversion implicite entre les types, les nombres seront convertibles en chaînes. Cela ne devrait pas être dangereux, car une conversion inverse n’est pas possible et l’opérateur de concaténation de chaînes est distinctif de celui d’addition de nombres. Même si cette conversion est supprimée dans les étapes ultérieures du développement de ce langage, elle servira bien d'exercice à ce stade. Pour cela, j'ai dû modifier l'analyseur numérique, car il analysait toujours . sous forme de point décimal. Il peut s'agir du premier caractère de l'opérateur de concaténation ...

Contexte du compilateur

Lors de la compilation, différentes fonctions du compilateur doivent obtenir des informations sur le code compilé jusqu'à présent. Nous conserverons ces informations dans une classe compiler_context. Puisque nous sommes sur le point d'implémenter l'analyse des expressions, nous devrons récupérer des informations sur les identificateurs que nous rencontrons.

Pendant l'exécution, nous conserverons les variables dans deux conteneurs différents. L'un d'entre eux sera le conteneur de variables globales et un autre sera la pile. La pile grandira au fur et à mesure que nous appelons des fonctions et entrons dans des portées. Il diminuera à mesure que nous reviendrons des fonctions et quitterons les portées. Lorsque nous appelons une fonction, nous pousserons les paramètres de fonction, puis la fonction s'exécutera. Sa valeur de retour sera poussée vers le haut de la pile lors de sa sortie. Par conséquent, pour chaque fonction, la pile ressemblera à ceci:

La fonction conservera l'index absolu de la variable de retour, et chaque variable ou paramètre sera trouvé par rapport à cet index.

Pour l'instant, nous traiterons les fonctions comme des identifiants globaux constants.

C'est la classe qui sert d'informations d'identification:

class identifier_info { private: type_handle _type_id; size_t _index; bool _is_global; bool _is_constant; public: identifier_info(type_handle type_id, size_t index, bool is_global, bool is_constant); type_handle type_id() const; size_t index() const; bool is_global() const; bool is_constant() const; };

Pour les variables locales et les paramètres de fonction, fonction index renvoie l'index par rapport à la valeur de retour. Il renvoie l'index global absolu en cas d'identificateurs globaux.

Nous aurons trois recherches d'identifiant différentes dans compile_context:

Recherche d'identifiant global, qui compile_context tenir par valeur, car c'est la même chose tout au long de la compilation.
Recherche d'identifiant local, sous forme de unique_ptr, qui sera nullptr dans la portée globale et sera initialisé dans n'importe quelle fonction. Chaque fois que nous entrons dans la portée, le nouveau contexte local sera initialisé avec l'ancien comme parent. Lorsque nous quitterons la portée, il sera remplacé par son parent.
Recherche d'identifiant de fonction, qui sera le pointeur brut. Ce sera nullptr dans la portée globale, et la même valeur que la portée locale la plus externe dans n'importe quelle fonction.

class compiler_context { private: global_identifier_lookup _globals; function_identifier_lookup* _params; std::unique_ptr _locals; type_registry _types; public: compiler_context(); type_handle get_handle(const type& t); const identifier_info* find(const std::string& name) const; const identifier_info* create_identifier(std::string name, type_handle type_id, bool is_constant); const identifier_info* create_param(std::string name, type_handle type_id); void enter_scope(); void enter_function(); bool leave_scope(); };

Arbre d'expression

Lorsque les jetons d'expression sont analysés, ils sont convertis en une arborescence d'expression. Semblable à tous les arbres, celui-ci se compose également de nœuds.

Il existe deux types de nœuds différents:

Les nœuds feuilles, qui peuvent être:
a) Identifiants
b) Numéros
c) Cordes
Nœuds internes, qui représentent une opération sur leurs nœuds enfants. Il garde ses enfants avec unique_ptr.

Pour chaque nœud, il y a des informations sur son type et s'il renvoie ou non une lvalue (une valeur qui peut apparaître sur le côté gauche de l'opérateur =).

Lorsqu'un nœud interne est créé, il essaiera de convertir les types de retour de ses enfants en types qu'il attend. Les conversions implicites suivantes sont autorisées:

lvalue à non-lvalue
Tout pour void
number à string

Si la conversion n'est pas autorisée, une erreur sémantique sera générée.

Voici la définition de la classe, sans quelques fonctions d'assistance et détails d'implémentation:

enum struct node_operation { ... }; using node_value = std::variant; struct node { private: node_value _value; std::vector _children; type_handle _type_id; bool _lvalue; public: node( compiler_context& context, node_value value, std::vector children ); const node_value& get_value() const; const std::vector& get_children() const; type_handle get_type_id() const; bool is_lvalue() const; void check_conversion(type_handle type_id, bool lvalue); };

La fonctionnalité des méthodes est explicite, à l'exception de la fonction check_conversion. Il vérifiera si le type est convertible en type_id et booléen lvalue en obéissant aux règles de conversion de type et lèvera une exception si ce n'est pas le cas.

Si un nœud est initialisé avec std::string, ou double, son type sera string ou number, respectivement, et ce ne sera pas une lvalue. S'il est initialisé avec un identifiant, il assumera le type de cet identifiant et sera une lvalue si l'identifiant n'est pas constant.

S'il est initialisé, cependant, avec une opération de nœud, son type dépendra de l'opération, et parfois du type de ses enfants. Écrivons les types d’expressions dans le tableau. J'utiliserai & suffixe pour désigner une lvalue. Dans les cas où plusieurs expressions ont le même traitement, j'écrirai des expressions supplémentaires entre crochets.

Opérations unaires

Opération	Type d'opération	x type
++ x (--x)	nombre&	nombre&
x ++ (x--)	nombre	nombre&
+ x (-x ~ x! x)	nombre	nombre

Opérations binaires

Opération	Type d'opération	x type	et tapez
x + y (x-y x * y x / y x y x% y x & y x \| y x ^ y x<>y x && y x \|\| y)	nombre	nombre	nombre
x == y (x! = y xy x = y)	nombre	nombre ou chaîne	identique à x
x..y	chaîne	chaîne	chaîne
x = y	identique à x	la valeur de quoi que ce soit	identique à x, sans lvalue
x + = y (x- = y x * = y x / = y x = y x% = y x & = y x \| = y x ^ = y x<>= y)	nombre&	nombre&	nombre
x .. = y	chaîne&	chaîne&	chaîne
x, y	même que y	néant	n'importe quoi
x [y]	type d'élément de x	type de tableau	nombre

Opérations ternaires

Opération	Type d'opération	x type	et tapez	type z
X y Z	même que y	nombre	n'importe quoi	même que y

Appel de fonction

En ce qui concerne l'appel de fonction, les choses se compliquent un peu. Si la fonction a N arguments, l'opération d'appel de fonction a N + 1 enfants, où le premier enfant est la fonction elle-même et le reste des enfants correspond aux arguments de la fonction.

Cependant, nous n'autoriserons pas le passage implicite d'arguments par référence. Nous demanderons à l'appelant de les préfixer avec le & signe. Pour l'instant, ce ne sera pas un opérateur supplémentaire mais la façon dont l'appel de fonction est analysé. Si nous n’analysons pas l’esperluette, lorsque l’argument est attendu, nous supprimerons la valeur de cet argument en ajoutant une fausse opération unaire que nous appelons node_operation::param. Cette opération a le même type que son enfant, mais ce n'est pas une lvalue.

Ensuite, lorsque nous construisons le nœud avec cette opération d'appel, si nous avons un argument qui est lvalue mais qui n'est pas attendu par la fonction, nous générerons une erreur, car cela signifie que l'appelant a tapé l'esperluette accidentellement. De manière assez surprenante, ce &, s'il était traité comme un opérateur, aurait la moindre priorité, car il n'a pas de signification sémantiquement s'il est analysé à l'intérieur de l'expression. Nous pouvons le changer plus tard.

Analyseur d'expression

Dans l'une de ses affirmations sur le potentiel des programmeurs, le célèbre philosophe informatique Edsger Dijkstra a dit un jour:

«Il est pratiquement impossible d'enseigner une bonne programmation à des étudiants qui ont déjà été familiarisés avec BASIC. En tant que programmeurs potentiels, ils sont mutilés mentalement au-delà de tout espoir de régénération.

Donc, pour tous ceux qui n’ont pas été exposés au BASIC - soyez reconnaissants, car vous avez échappé à la «mutilation mentale».

Le reste d'entre nous, programmeurs mutilés, rappelons-nous l'époque où nous codions en BASIC. Il y avait un opérateur , qui a été utilisé pour la division intégrale. Dans un langage où vous n’avez pas de types séparés pour les nombres à virgule flottante et intégrale, c’est assez pratique, alors j’ai ajouté le même opérateur à Stork. J'ai également ajouté l'opérateur =, qui, comme vous l'avez deviné, effectuera une division intégrale puis assignera.

Je pense que de tels opérateurs seraient appréciés par les programmeurs JavaScript, par exemple. Je ne veux même pas imaginer ce que Dijkstra dirait à leur sujet s'il vivait assez longtemps pour voir la popularité croissante de JS.

En parlant de cela, l'un des plus gros problèmes que j'ai avec JavaScript est la divergence des expressions suivantes:

'1' - “1” évalue à 0
'1' * “1” évalue à 1
'1' / “1” évalue à 1
'1' + “1” évalue à “11”

Le duo hip-hop croate 'Tram 11', du nom d'un tramway qui relie les quartiers périphériques de Zagreb, avait une chanson qui se traduit à peu près par: 'Un et un ne sont pas deux, mais 11.' Il est sorti à la fin des années 90, donc ce n'était pas une référence à JavaScript, mais il illustre assez bien l'écart.

Pour éviter ces écarts, j'ai interdit la conversion implicite de chaîne en nombre, et j'ai ajouté .. opérateur pour la concaténation (et ..= pour la concaténation avec affectation). Je ne me souviens pas d’où j’ai eu l’idée de cet opérateur. Ce n'est pas de BASIC ou PHP, et je ne rechercherai pas l'expression «concaténation Python» parce que googler quoi que ce soit à propos de Python me fait froid dans le dos. J'ai une phobie des serpents, et en combinant cela avec la «concaténation» - non, merci! Peut-être plus tard, avec un navigateur textuel archaïque, sans art ASCII.

Mais revenons au sujet de cette section - notre analyseur d'expressions. Nous utiliserons une adaptation de «Shunting-yard Algorithm».

C'est l'algorithme qui vient à l'esprit de tout programmeur, même moyen, après avoir réfléchi au problème pendant environ 10 minutes. Il peut être utilisé pour évaluer une expression d'infixe ou la transformer à l'inverse Notation polonaise , ce que nous ne ferons pas.

L'idée de l'algorithme est de lire les opérandes et les opérateurs de gauche à droite. Lorsque nous lisons un opérande, nous le poussons dans la pile d'opérandes. Lorsque nous lisons un opérateur, nous ne pouvons pas l’évaluer immédiatement, car nous ne savons pas si l’opérateur suivant aura une meilleure priorité que celui-ci. Par conséquent, nous le poussons vers la pile d'opérateurs.

Cependant, nous vérifions d'abord si l'opérateur en haut de la pile a une meilleure priorité que celui que nous venons de lire. Dans ce cas, nous évaluons l'opérateur depuis le haut de la pile avec des opérandes sur la pile d'opérandes. Nous poussons le résultat dans la pile d'opérandes. Nous le conservons jusqu'à ce que nous lisions tout, puis évaluons tous les opérateurs à gauche de la pile d'opérateurs avec les opérandes sur la pile d'opérandes, repoussant les résultats sur la pile d'opérandes jusqu'à ce que nous soyons laissés sans opérateur et avec un seul opérande, qui est le résultat.

Lorsque deux opérateurs ont la même priorité, nous prendrons celui de gauche au cas où ces opérateurs seraient associatifs à gauche; sinon, nous prenons la bonne. Deux opérateurs de même priorité ne peuvent pas avoir d'associativité différente.

L'algorithme d'origine traite également les parenthèses, mais nous le ferons de manière récursive à la place, car l'algorithme sera plus propre de cette façon.

Edsger Dijkstra a nommé l'algorithme ' Cour de manœuvre »Parce que cela ressemble à l'exploitation d'une gare de triage ferroviaire.

Cependant, l'algorithme de shunting-yard original ne vérifie presque pas les erreurs, il est donc tout à fait possible qu'une expression invalide soit analysée comme étant correcte. Par conséquent, j'ai ajouté la variable booléenne qui vérifie si nous attendons un opérateur ou un opérande. Si nous attendons des opérandes, nous pouvons également analyser les opérateurs de préfixes unaires. De cette façon, aucune expression invalide ne peut passer sous le radar et la vérification de la syntaxe de l'expression est terminée.

Emballer

Quand j'ai commencé à coder pour cette partie de la série, j'avais prévu d'écrire sur le générateur d'expression. Je voulais construire une expression qui puisse être évaluée. Cependant, cela s'est avéré beaucoup trop compliqué pour un article de blog, j'ai donc décidé de le diviser en deux. Dans cette partie, nous avons terminé l'analyse des expressions et j'écrirai sur la construction d'objets d'expression dans le prochain article.

Si je me souviens bien, il y a une quinzaine d'années, il m'a fallu un week-end pour écrire la première version de ma langue maternelle, ce qui me fait me demander ce qui n'a pas fonctionné cette fois.

Dans un effort pour nier que je vieillis et que je suis moins spirituel, je blâmerai mon fils de deux ans d’être trop exigeant pendant mon temps libre.

Comme dans la partie 1, vous pouvez lire, télécharger ou même compiler le code à partir de ma page GitHub .