Partie 1: Tokenizer
Dans cette série, nous développerons un nouveau langage de script et décrirons ce processus étape par étape.
La première question qui vient spontanément à l'esprit de tout lecteur qui s'interroge est probablement: «Avons-nous vraiment besoin d'un nouveau langage de programmation?»
Avons-nous vraiment besoin d'un nouveau langage de programmation?
Pour répondre à cette question, je me permets une petite digression.
bouteille (cadre web)
Imaginez que vous êtes un architecte (un véritable architecte de brique et de mortier, pas un logiciel), et que vous êtes assez malchanceux pour être né dans un pays très bureaucratique. Vous avez une excellente idée de centre commercial dans votre ville sous-développée, vous créez donc le projet et demandez un permis de construire. Bien sûr, ils vous rejettent immédiatement au motif que vous n'avez pas d'entreprise enregistrée. Donc, vous enregistrez une entreprise. Pour ce faire, vous devez déposer de l'argent. Ensuite, vous trouvez un nom pour votre entreprise, qui est rejeté. Lors de votre cinquième essai, il est accepté et votre application va au bas du tas. En fin de compte, soit vous abandonnez, soit vous réalisez que quelqu'un d'autre a construit un centre commercial entre-temps.
Mais nous ne sommes pas de véritables architectes. Nous sommes ingénieurs logiciels , et nous avons le privilège de donner vie à nos idées sans permis ni bureaucratie. La seule chose dont nous avons besoin est du temps libre et la volonté de le consacrer à la programmation au lieu des puzzles de sudoku.
Si vous insistez encore sur le fait que la motivation pour la programmation ne peut pas être une pure curiosité, laissez-moi simplement 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 garder intéressé 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é à le nommer «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 que nous parcourons la série, il est donc possible que je développe également des bogues. Ils devraient être aplatis à 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 montrer comment créer un langage de programmation en C ++, nous en créerons 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 souhaite pas y ajouter de nouvelles valeurs. Par conséquent, std::map (ou std::unordered_map) est excessif, car il permet également une insertion rapide.
qui a créé le langage de programmation c
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 mettre en œuvre un munch maximal algorithme au-dessus d'un tel conteneur, et map n'est pas le meilleur contenant pour cela.
Le deuxième choix est std::vector, trié après les insertions. Le seul problème avec cette approche est une 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 plus de lisibilité.)
template class lookup { public: using value_type = std::pair; using container_type = std::vector; private: container_type _container; public: using iterator = typename container_type::const_iterator; using const_iterator = iterator; lookup(std::initializer_list 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 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 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 mettre en œuvre 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. À ce stade du projet, il m'est difficile de décider quel sera le flux d'entrée, je vais donc utiliser std::function au lieu.
using get_character = std::function; J'utiliserai les 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 l'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 personnages.
class push_back_stream { private: const get_character& _input; std::stack _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, je vais omettre les détails de mise en œuvre, que vous pouvez trouver sur mon Page GitHub .
Comme vous pouvez le voir, push_back_stream est initialisé à partir de get_character fonction. Le operator() surchargé | 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 globalement; sinon, nous devrions conserver tous les anciens caractères dans un conteneur pour implémenter le push_back fonctionner correctement.
Jetons réservés
Le tokenizer est le composant de compilateur de plus bas niveau. Il doit lire les jetons d'entrée et de «spit-out». Il existe quatre types de jetons 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 fonctionnait assez bien pour C, C ++, JavaScript, Java, C # et Objective-C, donc cela doit également fonctionner pour Stork. Si vous avez besoin d'un cours de recyclage, vous pouvez consulter l'un de nos précédents articles couvrant 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 d'é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. Celles qui ne le sont pas:
- 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 de variable
- 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, au besoin.
Il y a un nouveau mot-clé qui mérite d'être décrit: kw_elif. Je suis fermement convaincu que les blocs à déclaration unique (sans accolades) ne valent pas la peine. Je ne les utilise pas (et je n’ai pas l’impression qu’il ne manque rien), sauf à deux reprises:
les algorithmes sont limités aux applications de calcul vrai ou faux
- Lorsque j'appuie accidentellement sur un point-virgule immédiatement après un
for,whileouifdéclaration avant le blocage. Si j'ai de la chance, cela renvoie une erreur de compilation, mais parfois, il en résulte une instruction if factice et un bloc qui s'exécute toujours. Heureusement, au fil des ans, j'ai appris de mes erreurs, donc cela arrive très rarement. Le chien de Pavlov aussi appris, finalement. - Quand j'ai 'chaîné' des instructions if, 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 unelsebloc avec une seule instruction, qui est cette instruction if.
Par conséquent, elif peut être utilisé pour éliminer complètement les déclarations sans accolades. Que nous l'autorisions ou non, c'est une décision qui peut attendre pour le moment.
Il existe deux fonctions d'assistance qui renvoient des jetons réservés:
std::optional get_keyword(std::string_view word); std::optional get_operator(push_back_stream& stream); La fonction get_keyword renvoie un mot-clé facultatif à 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 lit plus, il ne lira pas tous les caractères supplémentaires qu'il a lus après le plus long opérateur reconnu.
Pour l'implémentation efficace de ces deux fonctions, nous avons besoin de deux recherches entre string_view et reserved_keyword.
obtenir les informations de carte de crédit de quelqu'un
const lookup operator_token_map { {'++', reserved_token::inc}, {'--', reserved_token::dec}, {'+', reserved_token::add}, {'-', reserved_token::sub}, {'..', reserved_token::concat}, /*more exciting operators*/ }; const lookup 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} }; Le get_keyword La mise en œuvre est complètement 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 _idx && l 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 personnage.
C'est l'implémentation de get_operator, qui devrait rendre maximal_munch_operator classe plus claire:
std::optional get_operator(push_back_stream& stream) { auto candidates = std::make_pair( operator_token_map.begin(), operator_token_map.end() ); std::optional ret; size_t match_size = 0; std::stack 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; } En gros, 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 n'est pas 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 retournons. Nous ne lirons pas tous les caractères que nous lirons par la suite.
Tokenizer
Puisque les jetons sont hétérogènes, un jeton est une classe de commodité qui encapsule std::variant différents types de jetons, à savoir:
- Jeton réservé
- Identifier
- Nombre
- Chaîne
- Fin de fichier
class token { private: using token_value = std::variant; 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; }; Le identifier est juste une classe avec un seul membre de std::string type. Il est là pour des raisons 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 renvoyez 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 reviendrons de la fonction.
- Si nous lisons un espace, nous l'ignorerons.
- 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 le
get_keyword fonction 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, sans échapper les caractères échappés.
- Si nous lisons un caractère barre oblique (
/), nous vérifierons si le caractère suivant est une barre oblique ou un astérisque (*), et nous sauterons le commentaire de ligne / bloc dans ce cas. - Sinon, nous utiliserons le
get_operator fonction.
Voici l'implémentation de la fonction tokenize. Je vais omettre 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.
Exceptions
Dans l'une de ses diatribes contre les exceptions, mon frère a dit un jour:
«Il y a deux types de personnes: ceux qui lancent des exceptions et ceux qui doivent les attraper. Je suis toujours dans ce deuxième groupe triste. »
Je suis d'accord avec l'esprit de cette déclaration. Je n'aime pas particulièrement les exceptions, et les lancer peut rendre tout code beaucoup plus difficile à maintenir et à lire. Presque toujours.
comment concevoir pour mobile
J'ai décidé de faire une exception (mauvais jeu de mots) à cette règle. Il est vraiment pratique de lancer une exception depuis le compilateur pour sortir 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é line_number et char_index membres pour une jolie 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 que la gestion des erreurs d’analyse de base. Les deux sont des éléments de base cruciaux pour les choses les plus intéressantes sur lesquelles je vais écrire dans les articles à venir.
J'espère que cet article vous a donné de bonnes idées, et si vous souhaitez explorer les détails, accédez à mon Page GitHub .
Comprendre les bases
Comment écrivez-vous un langage de programmation?
En écrivant la grammaire du langage et le contexte d'exécution dans lequel le code compilé peut être exécuté.
Qu'est-ce qu'un langage de programmation?
Sa grammaire, ses règles de syntaxe et la signification sémantique de la plus petite unité lexicale - un jeton.
Qu'est-ce qu'un tokenizer en C ++?
Tokenizer est un composant qui lit les caractères d'un flux et donne les plus petites unités lexicales, jetons, implémentées en tant qu'objets C ++.
