Stork : comment créer un langage de programmation en C++

Partie 1 : Générateur de jetons

Dans cette série, nous allons développer un nouveau langage de script et décrire ce processus étape par étape.

La première question qui vient spontanément à l'esprit de tout lecteur qui se pose la question est probablement : « Avons-nous vraiment besoin d'un nouveau langage de programmation ?

A-t-on vraiment besoin d'un nouveau langage de programmation ?

Pour répondre à cette question, je vais me permettre une petite digression.

Imaginez que vous êtes un architecte (un véritable architecte de briques et de mortier, pas un logiciel), et que vous avez la malchance d'être né dans un pays très bureaucratique. Vous avez une idée géniale pour un centre commercial dans votre ville natale sous-développée, alors vous créez le projet et demandez un permis de construire. Bien sûr, ils vous rejettent immédiatement au motif que vous n'avez pas de société enregistrée. Donc, vous enregistrez une entreprise. Pour ce faire, vous devez déposer de l'argent. Ensuite, vous proposez un nom pour votre entreprise, qui est rejeté. À votre cinquième essai, il est accepté et votre candidature va au fond du tas. En fin de compte, soit vous abandonnez, soit vous vous rendez compte que quelqu'un d'autre a construit un centre commercial entre-temps.

Mais nous ne sommes pas de véritables architectes. Nous sommes des ingénieurs en logiciel et nous avons le privilège de donner vie à nos idées sans autorisation ni bureaucratie. La seule chose dont nous avons besoin est du temps libre et la volonté de le consacrer à la programmation plutôt qu'aux puzzles de sudoku.

Si vous insistez toujours sur le fait que la motivation pour programmer ne peut pas être la pure curiosité, permettez-moi de mentionner que le premier langage de programmation que j'ai conçu a été développé par nécessité, et non par simple curiosité. Cependant, cela ne devrait pas être la première motivation pour lire ce blog. Je pense que de nombreuses idées que vous rencontrerez ici sont assez intéressantes et innovantes pour vous intéresser même si vous n'avez pas réellement besoin de créer votre propre langage de programmation.

Notre objectif de développer un langage de script à faible encombrement m'a inspiré à l'appeler "Stork" ; et heureusement, nous n'avons pas besoin de convaincre un bureaucrate d'approuver le nom.

Je vais développer le langage de programmation au fur et à mesure de la série, il est donc possible que je développe également des bogues. Ils devraient être aplanis à l'approche de la fin de la série.

Le code source complet de tout ce qui est décrit ici est disponible gratuitement sur GitHub.

Enfin, pour répondre à la question du titre de ce paragraphe - non, nous n'avons pas réellement besoin d'un nouveau langage de programmation, mais puisque nous essayons de démontrer comment créer un langage de programmation en C++, nous allons en créer un à des fins de démonstration .

Les petits assistants de Tokenizer

Je ne sais pas si d'autres programmeurs sont régulièrement confrontés au même problème, mais je suis confronté à ce problème assez fréquemment :

J'ai besoin d'un conteneur clé-valeur qui devrait récupérer les valeurs rapidement, en temps logarithmique. Cependant, une fois que j'ai initialisé le conteneur, je ne veux pas lui ajouter de nouvelles valeurs. Par conséquent, std::map<Key, Value> (ou std::unordered_map<Key, Value> ) est excessif, car il permet également une insertion rapide.

Je suis complètement contre l'optimisation inutile, mais dans ce cas, j'ai l'impression que beaucoup de mémoire est gaspillée pour rien. Non seulement cela, mais plus tard, nous devrons implémenter un algorithme de munch maximal au-dessus d'un tel conteneur, et map n'est pas le meilleur conteneur pour cela.

Le deuxième choix est std::vector<std::pair<Key,Value> > , trié après les insertions. Le seul problème avec cette approche est la moindre lisibilité du code car nous devons garder à l'esprit que le vecteur est trié, j'ai donc développé une petite classe qui assure cette contrainte.

(Toutes les fonctions, classes, etc. sont déclarées dans l'espace de noms stork . Je vais omettre cet espace de noms pour des raisons de lisibilité.)

 template <typename Key, typename Value> class lookup { public: using value_type = std::pair<Key, Value>; using container_type = std::vector<value_type>; private: container_type _container; public: using iterator = typename container_type::const_iterator; using const_iterator = iterator; lookup(std::initializer_list<value_type> init) : _container(init) { std::sort(_container.begin(), _container.end()); } lookup(container_type container) : _container(std::move(container)) { std::sort(_container.begin(), _container.end()); } const_iterator begin() const { return _container.begin(); } const_iterator end() const { return _container.end(); } template <typename K> const_iterator find(const K& key) const { const_iterator it = std::lower_bound( begin(), end(), key, [](const value_type& p, const K& key) { return p.first < key; } ); return it != end() && it->first == key ? it : end(); } size_t size() const { return _container.size(); } };

Comme vous pouvez le voir, l'implémentation de cette classe est assez simple. Je ne voulais pas implémenter toutes les méthodes possibles, juste celles dont nous aurons besoin. Le conteneur sous-jacent est un vector , il peut donc être initialisé avec un vector pré-rempli ou avec initializer_list .

Le tokenizer lira les caractères du flux d'entrée. A ce stade du projet, il m'est difficile de décider quel sera le flux d'entrée, donc j'utiliserai std::function à la place.

 using get_character = std::function<int()>;

J'utiliserai des conventions bien connues des fonctions de flux de style C, telles que getc , qui renvoie un int au lieu de char ainsi qu'un nombre négatif pour signaler la fin d'un fichier.

Cependant, il est vraiment pratique de lire quelques caractères à l'avance, avant une hypothèse d'un type de jeton dans un tokenizer. Pour cela, j'ai implémenté un flux qui nous permettra de ne pas lire certains caractères.

 class push_back_stream { private: const get_character& _input; std::stack<int> _stack; size_t _line_number; size_t _char_index; public: push_back_stream(const get_character& input); int operator()(); void push_back(int c); size_t line_number() const; size_t char_index() const; };

Pour économiser de l'espace, j'omettrai les détails de mise en œuvre, que vous pouvez trouver sur ma page GitHub.

Comme vous pouvez le voir, push_back_stream est initialisé à partir de la fonction get_character . L' operator() est utilisé pour récupérer le caractère suivant, et push_back est utilisé pour renvoyer le caractère dans le flux. line_number et char_number sont des méthodes pratiques utilisées pour les rapports d'erreurs.

Gardez à l'esprit que char_index n'est pas l'index du caractère dans la ligne courante mais global ; sinon, nous devrions conserver tous les caractères passés dans un conteneur pour implémenter correctement la fonction push_back .

Jetons réservés

Le tokenizer est le composant de compilateur de niveau le plus bas. Il doit lire les jetons d'entrée et de sortie. Il existe quatre types de tokens qui nous intéressent :

• Jetons réservés
• Identifiants
• Nombres
• Cordes

Nous ne sommes pas intéressés par les commentaires, donc le tokenizer va simplement les "manger", sans en avertir personne.

Pour assurer l'attrait et la popularité planétaire de ce langage, nous utiliserons une syntaxe de type C bien connue. Cela a très bien fonctionné pour C, C++, JavaScript, Java, C# et Objective-C, donc cela doit également fonctionner pour Stork. Si vous avez besoin d'un cours de remise à niveau, vous pouvez consulter l'un de nos articles précédents portant sur les ressources d'apprentissage C/C++.

Voici l'énumération des jetons réservés :

 enum struct reserved_token { inc, dec, add, sub, concat, mul, div, idiv, mod, bitwise_not, bitwise_and, bitwise_or, bitwise_xor, shiftl, shiftr, assign, add_assign, sub_assign, concat_assign, mul_assign, div_assign, idiv_assign, mod_assign, and_assign, or_assign, xor_assign, shiftl_assign, shiftr_assign, logical_not, logical_and, logical_or, eq, ne, lt, gt, le, ge, question, colon, comma, semicolon, open_round, close_round, open_curly, close_curly, open_square, close_square, kw_if, kw_else, kw_elif, kw_switch, kw_case, kw_default, kw_for, kw_while, kw_do, kw_break, kw_continue, kw_return, kw_var, kw_fun, kw_void, kw_number, kw_string, };

Les membres de l'énumération précédés de "kw_" sont des mots-clés. J'ai dû les préfixer car ils sont généralement les mêmes que les mots-clés C++. Ceux sans préfixe sont des opérateurs.

Presque tous suivent la convention C. Ceux qui ne le sont pas sont :
- concat et concat_assign ( .. et ..= ), qui seront utilisés pour la concaténation
- idiv et idiv_assign ( \ et \= ), qui seront utilisés pour la division entière
- kw_var pour la déclaration des variables
- kw_fun pour la déclaration de fonction
- kw_number pour les variables numériques
- kw_string pour les variables de chaîne

Nous ajouterons des mots clés supplémentaires, si nécessaire.

Il y a un nouveau mot-clé qui mérite d'être décrit : kw_elif . Je suis fermement convaincu que les blocs à une seule instruction (sans accolades) n'en valent pas la peine. Je ne les utilise pas (et je n'ai pas l'impression qu'il manque quelque chose), sauf à deux reprises :

1. Lorsque j'appuie accidentellement sur un point-virgule immédiatement après une instruction for , while ou if avant le bloc. Si j'ai de la chance, cela renvoie une erreur de compilation, mais parfois, cela se traduit par une instruction if factice et un bloc qui s'exécute toujours. Heureusement, au fil des années, j'ai appris de mes erreurs, donc cela arrive très rarement. Le chien de Pavlov a également appris, finalement.
2. Lorsque j'ai des instructions if "enchaînées", j'ai donc un bloc if, puis un ou plusieurs blocs else-if, et éventuellement un bloc else. Techniquement, quand j'écris else if , c'est un bloc else avec une seule instruction, qui est cette instruction if.

Par conséquent, elif peut être utilisé pour éliminer complètement les instructions sans accolades. Que nous l'autorisions ou non, c'est une décision qui peut attendre pour le moment.

Deux fonctions d'assistance renvoient des jetons réservés :

 std::optional<reserved_token> get_keyword(std::string_view word); std::optional<reserved_token> get_operator(push_back_stream& stream);

La fonction get_keyword renvoie un mot-clé optionnel à partir du mot passé. Ce "mot" est une séquence de lettres, de chiffres et de traits de soulignement, commençant par une lettre ou un trait de soulignement. Il renverra un reserved_token si le mot est un mot-clé. Sinon, le tokenizer supposera qu'il s'agit d'un identifiant.

La fonction get_operator essaie de lire autant de caractères que possible, tant que la séquence est un opérateur valide. S'il en lit plus, il annulera la lecture de tous les caractères supplémentaires qu'il a lus après l'opérateur reconnu le plus long.

Pour la mise en œuvre efficace de ces deux fonctions, nous avons besoin de deux recherches entre string_view et reserved_keyword .

 const lookup<std::string_view, reserved_token> operator_token_map { {"++", reserved_token::inc}, {"--", reserved_token::dec}, {"+", reserved_token::add}, {"-", reserved_token::sub}, {"..", reserved_token::concat}, /*more exciting operators*/ }; const lookup<std::string_view, reserved_token> keyword_token_map { {"if", reserved_token::kw_if}, {"else", reserved_token::kw_else}, {"elif", reserved_token::kw_elif}, {"switch", reserved_token::kw_switch}, {"case", reserved_token::kw_case}, {"default", reserved_token::kw_default}, {"for", reserved_token::kw_for}, {"while", reserved_token::kw_while}, {"do", reserved_token::kw_do}, {"break", reserved_token::kw_break}, {"continue", reserved_token::kw_continue}, {"return", reserved_token::kw_return}, {"var", reserved_token::kw_var}, {"fun", reserved_token::kw_fun}, {"void", reserved_token::kw_void}, {"number", reserved_token::kw_number}, {"string", reserved_token::kw_string} };

L'implémentation get_keyword est tout à fait simple, mais pour get_operator , nous avons besoin d'un comparateur personnalisé qui comparera un caractère donné avec des opérateurs candidats, en ne prenant en compte que le n-ième caractère.

 class maximal_munch_comparator{ private: size_t _idx; public: maximal_munch_comparator(size_t idx) : _idx(idx) { } bool operator()(char l, char r) const { return l < r; } bool operator()( std::pair<std::string_view, reserved_token> l, char r ) const { return l.first.size() <= _idx || l.first[_idx] < r; } bool operator()( char l, std::pair<std::string_view, reserved_token> r ) const { return r.first.size() > _idx && l < r.first[_idx]; } bool operator()( std::pair<std::string_view, reserved_token> l, std::pair<std::string_view, reserved_token> r ) const { return r.first.size() > _idx && ( l.first.size() < _idx || l.first[_idx] < r.first[_idx] ); } };

C'est un comparateur lexical ordinaire qui ne prend en compte que le caractère à la position idx , mais si la chaîne est plus courte, il la traite comme si elle avait un caractère nul à la position idx , qui est inférieur à tout autre caractère.

C'est l'implémentation de get_operator , qui devrait clarifier la classe maximal_munch_operator :

 std::optional<reserved_token> get_operator(push_back_stream& stream) { auto candidates = std::make_pair( operator_token_map.begin(), operator_token_map.end() ); std::optional<reserved_token> ret; size_t match_size = 0; std::stack<int> chars; for (size_t idx = 0; candidates.first != candidates.second; ++idx) { chars.push(stream()); candidates = std::equal_range( candidates.first, candidates.second, char(chars.top()), maximal_munch_comparator(idx) ); if ( candidates.first != candidates.second && candidates.first->first.size() == idx + 1 ) { match_size = idx + 1; ret = candidates.first->second; } } while (chars.size() > match_size) { stream.push_back(chars.top()); chars.pop(); } return ret; }

Fondamentalement, nous traitons tous les opérateurs comme des candidats au début. Ensuite, nous lisons caractère par caractère et filtrons les candidats actuels en appelant equal_range , en comparant uniquement le n-ième caractère. Nous n'avons pas besoin de comparer les caractères précédents car ils sont déjà comparés, et nous ne voulons pas comparer les caractères qui suivent car ils ne sont toujours pas pertinents.

Chaque fois que la plage est non vide, nous vérifions si le premier élément de la plage n'a plus de caractères (si un tel élément existe, il est toujours au début de la plage lorsque la recherche est triée). Dans ce cas, nous avons un opérateur légal correspondant. Le plus long de ces opérateurs est celui que nous renvoyons. Nous allons annuler la lecture de tous les caractères que nous avons éventuellement lus après cela.

Générateur de jetons

Étant donné que les jetons sont hétérogènes, un jeton est une classe pratique qui encapsule std::variant différents types de jetons, à savoir :

• Jeton réservé
• Identifiant
• Nombre
• Chaîne de caractères
• Fin de fichier

 class token { private: using token_value = std::variant<reserved_token, identifier, double, std::string, eof>; token_value _value; size_t _line_number; size_t _char_index; public: token(token_value value, size_t line_number, size_t char_index); bool is_reserved_token() const; bool is_identifier() const; bool is_number() const; bool is_string() const; bool is_eof() const; reserved_token get_reserved_token() const; std::string_view get_identifier() const; double get_number() const; std::string_view get_string() const; size_t get_line_number() const; size_t get_char_index() const; };

L' identifier est juste une classe avec un seul membre du type std::string . Il est là pour plus de commodité car, à mon avis, std::variant est plus propre si toutes ses alternatives sont de types différents.

Maintenant, nous pouvons écrire le tokenizer. Ce sera une fonction qui acceptera push_back_stream et renverra le jeton suivant.

L'astuce consiste à utiliser différentes branches de code, en fonction du type de caractère du premier caractère que nous lisons.

• Si nous lisons le caractère de fin de fichier, nous revenons de la fonction.
• Si nous lisons un espace blanc, nous le sauterons.
• Si nous lisons un caractère alphanumérique (une lettre, un chiffre ou un trait de soulignement), nous lirons tous les caractères successifs de ce type (nous lirons également des points si le premier caractère est un chiffre). Ensuite, si le premier caractère est un chiffre, nous essaierons d'analyser la séquence comme un nombre. Sinon, nous utiliserons la fonction get_keyword pour vérifier s'il s'agit d'un mot-clé ou d'un identifiant.
• Si nous lisons un guillemet, nous le traiterons comme une chaîne, en enlevant les caractères d'échappement.
• Si nous lisons un caractère slash ( / ), nous vérifierons si le caractère suivant est un slash ou un astérisque ( * ), et nous sauterons le commentaire de ligne/bloc dans ce cas.
• Sinon, nous utiliserons la fonction get_operator .

Voici l'implémentation de la fonction tokenize. J'omettrai les détails d'implémentation des fonctions qu'il appelle.

 token tokenize(push_back_stream& stream) { while (true) { size_t line_number = stream.line_number(); size_t char_index = stream.char_index(); int c = stream(); switch (get_character_type(c)) { case character_type::eof: return {eof(), line_number, char_index}; case character_type::space: continue; case character_type::alphanum: stream.push_back(c); return fetch_word(stream); case character_type::punct: switch (c) { case '"': return fetch_string(stream); case '/': { char c1 = stream(); switch(c1) { case '/': skip_line_comment(stream); continue; case '*': skip_block_comment(stream); continue; default: stream.push_back(c1); } } default: stream.push_back(c); return fetch_operator(stream); } break; } } }

Vous pouvez voir qu'il repousse les caractères qu'il lit avant d'appeler une fonction de niveau inférieur. La pénalité de performance est presque inexistante et le code de fonction de niveau inférieur est beaucoup plus propre.

Des exceptions

Dans une de ses diatribes contre les exceptions, mon frère a dit un jour :

« Il y a deux types de personnes : celles qui lancent des exceptions et celles qui doivent les attraper. Je suis toujours dans ce triste deuxième groupe.

Je suis d'accord avec l'esprit de cette déclaration. Je n'aime pas particulièrement les exceptions, et les lancer peut rendre n'importe quel code beaucoup plus difficile à maintenir et à lire. Presque toujours.

J'ai décidé de faire une exception (mauvais jeu de mots) à cette règle. Il est vraiment pratique de lever une exception du compilateur pour se dérouler des profondeurs de la compilation.

Voici l'implémentation de l'exception :

 class error: public std::exception { private: std::string _message; size_t _line_number; size_t _char_index; public: error(std::string message, size_t line_number, size_t char_index) noexcept; const char* what() const noexcept override; size_t line_number() const noexcept; size_t char_index() const noexcept; };

Cependant, je promets d'attraper toutes les exceptions dans le code de niveau supérieur. J'ai même ajouté les membres line_number et char_index pour joli-impression, et la fonction qui le fait :

 void format_error( const error& err, get_character source, std::ostream& output );

Emballer

Cela conclut la première partie de notre série. Ce n'était peut-être pas trop excitant, mais nous avons maintenant un tokenizer utile, ainsi qu'une gestion basique des erreurs d'analyse. Les deux sont des éléments de base cruciaux pour les choses les plus intéressantes sur lesquelles je vais écrire dans les prochains articles.

J'espère que vous avez eu de bonnes idées à partir de cet article, et si vous souhaitez explorer les détails, rendez-vous sur ma page GitHub.

Lectures complémentaires sur le blog Toptal Engineering :

• Comment aborder la rédaction d'un interprète à partir de zéro