Storch: Wie man eine Programmiersprache in C++ erstellt

Teil 1: Tokenisierer

In dieser Serie werden wir eine neue Skriptsprache entwickeln und diesen Prozess Schritt für Schritt beschreiben.

Die erste Frage, die jedem staunenden Leser spontan in den Sinn kommt, dürfte lauten: „Brauchen wir wirklich eine neue Programmiersprache?“

Brauchen wir wirklich eine neue Programmiersprache?

Zur Beantwortung dieser Frage erlaube ich mir einen kleinen Exkurs.

Stellen Sie sich vor, Sie sind ein Architekt (ein echter Ziegel-und-Mörtel-Architekt, kein Software-Architekt) und Sie haben das Pech, in einem sehr bürokratischen Land geboren zu sein. Sie haben eine großartige Idee für ein Einkaufszentrum in Ihrer unterentwickelten Heimatstadt, also erstellen Sie das Projekt und beantragen eine Baugenehmigung. Natürlich lehnen sie dich sofort mit der Begründung ab, dass du kein eingetragenes Unternehmen hast. Sie registrieren also ein Unternehmen. Dazu müssen Sie etwas Geld einzahlen. Dann fällt Ihnen ein Name für Ihr Unternehmen ein, der abgelehnt wird. Beim fünften Versuch wird es akzeptiert und Ihre Bewerbung landet ganz unten. Am Ende gibt man entweder auf oder stellt fest, dass jemand anderes in der Zwischenzeit ein Einkaufszentrum gebaut hat.

Aber wir sind keine echten Architekten. Wir sind Software-Ingenieure und haben das Privileg, unsere Ideen ohne Genehmigungen oder Bürokratie zum Leben zu erwecken. Das Einzige, was wir brauchen, ist Freizeit und der Wille, diese statt Sudoku-Rätseln ins Programmieren zu investieren.

Wenn Sie immer noch darauf bestehen, dass die Motivation zum Programmieren nicht reine Neugier sein kann, lassen Sie mich nur erwähnen, dass die erste Programmiersprache, die ich entworfen habe, aus Notwendigkeit und nicht aus reiner Neugier entwickelt wurde. Das soll aber nicht die erste Motivation sein, diesen Blog zu lesen. Ich denke, dass viele Ideen, denen Sie hier begegnen werden, ziemlich interessant und innovativ sind, um Ihr Interesse aufrechtzuerhalten, auch wenn Sie eigentlich keine eigene Programmiersprache erstellen müssen.

Unser Ziel, eine Skriptsprache mit kleinem Fußabdruck zu entwickeln, hat mich dazu inspiriert, sie „Storch“ zu nennen; und zum Glück müssen wir keinen Bürokraten davon überzeugen, den Namen zu genehmigen.

Ich werde die Programmiersprache entwickeln, während wir die Serie durchlaufen, also besteht die Möglichkeit, dass ich auch einige Fehler entwickle. Sie sollten ausgebügelt werden, wenn wir uns dem Ende der Serie nähern.

Der vollständige Quellcode für alles, was hier beschrieben wird, ist auf GitHub frei verfügbar.

Um abschließend die Frage aus dem Titel dieses Abschnitts zu beantworten: Nein, wir brauchen eigentlich keine neue Programmiersprache, aber da wir versuchen zu demonstrieren, wie man eine Programmiersprache in C++ erstellt, werden wir eine zu Demonstrationszwecken erstellen .

Die kleinen Helfer des Tokenizers

Ich weiß nicht, ob andere Programmierer regelmäßig mit demselben Problem konfrontiert sind, aber ich habe dieses Problem ziemlich häufig:

Ich brauche einen Schlüssel-Wert-Container, der Werte schnell in logarithmischer Zeit abrufen sollte. Nachdem ich den Container jedoch initialisiert habe, möchte ich ihm keine neuen Werte hinzufügen. Daher ist std::map<Key, Value> (oder std::unordered_map<Key, Value> ) übertrieben, da es auch ein schnelles Einfügen ermöglicht.

Ich bin absolut gegen unnötige Optimierung, aber in diesem Fall habe ich das Gefühl, dass viel Speicher für nichts verschwendet wird. Darüber hinaus müssen wir später einen Maximal-Munch-Algorithmus auf einem solchen Container implementieren, und map ist nicht der beste Container dafür.

Die zweite Wahl ist std::vector<std::pair<Key,Value> > , sortiert nach Einfügungen. Das einzige Problem bei diesem Ansatz ist die geringere Lesbarkeit des Codes, da wir bedenken müssen, dass der Vektor sortiert ist, also habe ich eine kleine Klasse entwickelt, die diese Einschränkung gewährleistet.

(Alle Funktionen, Klassen usw. werden im Namensraum stork deklariert. Ich werde diesen Namensraum aus Gründen der Lesbarkeit weglassen.)

 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(); } };

Wie Sie sehen können, ist die Implementierung dieser Klasse recht einfach. Ich wollte nicht alle möglichen Methoden implementieren, sondern nur die, die wir brauchen werden. Der zugrunde liegende Container ist ein vector , sodass er mit einem vorab ausgefüllten vector oder mit initializer_list kann.

Der Tokenizer liest Zeichen aus dem Eingabestrom. In dieser Phase des Projekts ist es schwer für mich zu entscheiden, was der Eingabestream sein wird, also werde ich stattdessen std::function verwenden.

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

Ich werde bekannte Konventionen von Stream-Funktionen im C-Stil verwenden, wie z. B. getc , das ein int anstelle von char sowie eine negative Zahl zurückgibt, um das Ende einer Datei zu signalisieren.

Es ist jedoch sehr praktisch, ein paar Zeichen im Voraus zu lesen, bevor ein Token-Typ in einem Tokenizer angenommen wird. Zu diesem Zweck habe ich einen Stream implementiert, der es uns ermöglicht, einige Zeichen ungelesen zu lassen.

 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; };

Um Platz zu sparen, werde ich die Implementierungsdetails weglassen, die Sie auf meiner GitHub-Seite finden können.

Wie Sie sehen können, wird push_back_stream von der Funktion get_character initialisiert. Der überladene operator() wird verwendet, um das nächste Zeichen abzurufen, und push_back wird verwendet, um das Zeichen wieder an den Stream zurückzugeben. line_number und char_number sind bequeme Methoden, die für Fehlerberichte verwendet werden.

Denken Sie daran, dass char_index nicht der Index des Zeichens in der aktuellen Zeile ist, sondern insgesamt; Andernfalls müssten wir alle vergangenen Zeichen in einem Container aufbewahren, um die push_back Funktion korrekt zu implementieren.

Reservierte Token

Der Tokenizer ist die Compiler-Komponente der untersten Ebene. Es muss die Eingabe- und „Ausspucken“-Tokens lesen. Es gibt vier Arten von Token, die für uns interessant sind:

• Reservierte Token
• Identifikatoren
• Zahlen
• Saiten

Wir sind nicht an Kommentaren interessiert, also „frisst“ der Tokenizer sie einfach, ohne jemanden zu benachrichtigen.

Um Attraktivität und weltweite Popularität dieser Sprache sicherzustellen, werden wir bekannte C-ähnliche Syntax verwenden. Es funktionierte ziemlich gut für C, C++, JavaScript, Java, C# und Objective-C, also muss es auch für Stork funktionieren. Falls Sie einen Auffrischungskurs benötigen, können Sie einen unserer vorherigen Artikel zu C/C++-Lernressourcen konsultieren.

Hier ist die Aufzählung der reservierten Token:

 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, };

Aufzählungsmitglieder mit dem Präfix „kw_“ sind Schlüsselwörter. Ich musste ihnen ein Präfix voranstellen, da sie normalerweise mit C++-Schlüsselwörtern identisch sind. Diejenigen ohne Präfix sind Operatoren.

Fast alle folgen der C-Konvention. Diejenigen, die das nicht tun, sind:
- concat und concat_assign ( .. und ..= ), die für die Verkettung verwendet werden
- idiv und idiv_assign ( \ und \= ), die für die ganzzahlige Division verwendet werden
- kw_var für Variablendeklaration
- kw_fun für Funktionsdeklaration
- kw_number für Zahlenvariablen
- kw_string für String-Variablen

Bei Bedarf fügen wir weitere Keywords hinzu.

Es gibt ein neues Schlüsselwort, das es wert ist, beschrieben zu werden: kw_elif . Ich bin der festen Überzeugung, dass Blöcke mit einer einzigen Anweisung (ohne geschweifte Klammern) es nicht wert sind. Ich benutze sie nicht (und ich habe nicht das Gefühl, dass etwas fehlt), außer bei zwei Gelegenheiten:

1. Wenn ich versehentlich direkt nach einer for , while oder if -Anweisung vor dem Block ein Semikolon drücke. Wenn ich Glück habe, gibt es einen Kompilierzeitfehler zurück, aber manchmal führt es zu einer Dummy-if-Anweisung und einem Block, der immer ausgeführt wird. Glücklicherweise habe ich im Laufe der Jahre aus meinen Fehlern gelernt, daher passiert es sehr selten. Auch Pawlows Hund lernte schließlich.
2. Wenn ich If-Anweisungen „verkettet“ habe, habe ich also einen If-Block, dann einen oder mehrere Else-If-Blöcke und optional einen Else-Block. Wenn ich else if schreibe, ist das technisch gesehen ein else -Block mit nur einer Anweisung, nämlich dieser if-Anweisung.

Daher kann elif verwendet werden, um klammerlose Anweisungen vollständig zu eliminieren. Ob wir es zulassen oder nicht, ist eine Entscheidung, die jetzt warten kann.

Es gibt zwei Hilfsfunktionen, die reservierte Token zurückgeben:

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

Die Funktion get_keyword gibt ein optionales Schlüsselwort aus dem übergebenen Wort zurück. Dieses „Wort“ ist eine Folge von Buchstaben, Ziffern und Unterstrichen, beginnend mit einem Buchstaben oder einem Unterstrich. Es wird ein reserved_token wenn das Wort ein Schlüsselwort ist. Andernfalls geht der Tokenizer davon aus, dass es sich um eine Kennung handelt.

Die Funktion get_operator versucht so viele Zeichen wie möglich zu lesen, solange die Sequenz ein gültiger Operator ist. Wenn es mehr liest, werden alle zusätzlichen Zeichen, die es nach dem längsten erkannten Operator gelesen hat, ungelesen.

Für die effektive Implementierung dieser beiden Funktionen benötigen wir zwei Lookups zwischen string_view und 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} };

Die Implementierung von get_keyword ist völlig unkompliziert, aber für get_operator benötigen wir einen benutzerdefinierten Komparator, der ein bestimmtes Zeichen mit Kandidatenoperatoren vergleicht, wobei nur das n-te Zeichen berücksichtigt wird.

 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] ); } };

Das ist ein gewöhnlicher lexikalischer Komparator, der nur das Zeichen an Position idx , aber wenn die Zeichenfolge kürzer ist, behandelt er sie so, als hätte sie ein Nullzeichen an Position idx , das kleiner ist als jedes andere Zeichen.

Dies ist die Implementierung von get_operator , die die Klasse maximal_munch_operator klarer machen sollte:

 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; }

Grundsätzlich behandeln wir zu Beginn alle Operatoren als Kandidaten. Dann lesen wir Zeichen für Zeichen und filtern aktuelle Kandidaten, indem wir equal_range aufrufen und nur das n-te Zeichen vergleichen. Wir müssen die vorangehenden Zeichen nicht vergleichen, da sie bereits verglichen wurden, und wir möchten die folgenden Zeichen nicht vergleichen, da sie noch irrelevant sind.

Immer wenn der Bereich nicht leer ist, prüfen wir, ob das erste Element im Bereich keine Zeichen mehr enthält (falls ein solches Element vorhanden ist, befindet es sich beim Sortieren der Suche immer am Anfang des Bereichs). In diesem Fall haben wir einen passenden legalen Operator. Der längste derartige Operator ist einer, den wir zurückgeben. Wir werden alle Charaktere, die wir schließlich lesen, unlesen lassen.

Tokenisierer

Da Token heterogen sind, ist ein Token eine praktische Klasse, die std::variant verschiedene Token-Typen umschließt, nämlich:

• Reserviertes Token
• Kennung
• Anzahl
• Schnur
• Ende der Datei

 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; };

Der identifier ist nur eine Klasse mit einem einzigen Mitglied vom Typ std::string . Es dient der Bequemlichkeit, da std::variant meiner Meinung nach sauberer ist, wenn alle seine Alternativen unterschiedliche Typen sind.

Jetzt können wir den Tokenizer schreiben. Es wird eine Funktion sein, die push_back_stream akzeptiert und das nächste Token zurückgibt.

Der Trick besteht darin, verschiedene Codezweige zu verwenden, basierend auf dem Zeichentyp des ersten Zeichens, das wir lesen.

• Wenn wir das Dateiendezeichen lesen, kehren wir von der Funktion zurück.
• Wenn wir ein Leerzeichen lesen, überspringen wir es.
• Wenn wir ein alphanumerisches Zeichen (einen Buchstaben, eine Ziffer oder einen Unterstrich) lesen, lesen wir alle nachfolgenden Zeichen dieses Typs (wir lesen auch Punkte, wenn das erste Zeichen eine Ziffer ist). Wenn das erste Zeichen eine Ziffer ist, versuchen wir dann, die Sequenz als Zahl zu analysieren. Andernfalls verwenden wir die get_keyword Funktion, um zu prüfen, ob es sich um ein Schlüsselwort oder eine Kennung handelt.
• Wenn wir ein Anführungszeichen lesen, behandeln wir es als Zeichenfolge, wobei die Escapezeichen daraus entfernt werden.
• Wenn wir einen Schrägstrich ( / ) lesen, prüfen wir, ob das nächste Zeichen ein Schrägstrich oder ein Sternchen ( * ) ist, und überspringen in diesem Fall den Zeilen-/Blockkommentar.
• Andernfalls verwenden wir die get_operator Funktion.

Hier ist die Implementierung der Tokenisierungsfunktion. Ich werde die Implementierungsdetails der aufgerufenen Funktionen weglassen.

 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; } } }

Sie können sehen, dass es gelesene Zeichen zurückschiebt, bevor es eine untergeordnete Funktion aufruft. Die Leistungseinbuße ist fast nicht vorhanden und der Funktionscode auf niedrigerer Ebene ist viel sauberer.

Ausnahmen

In einem seiner Tiraden gegen Ausnahmen sagte mein Bruder einmal:

„Es gibt zwei Arten von Menschen: diejenigen, die Ausnahmen auslösen, und diejenigen, die sie abfangen müssen. Ich bin immer in dieser traurigen zweiten Gruppe.“

Ich stimme dem Geist dieser Aussage zu. Ich mag Ausnahmen nicht besonders, und wenn ich sie auslöse, kann jeder Code viel schwerer zu warten und zu lesen sein. Fast immer.

Ich beschloss, eine Ausnahme (schlechtes Wortspiel beabsichtigt) von dieser Regel zu machen. Es ist wirklich bequem, eine Ausnahme vom Compiler auszulösen, um sich von den Tiefen der Kompilierung zu erholen.

Hier ist die Ausnahmeimplementierung:

 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; };

Ich verspreche jedoch, alle Ausnahmen im Code der obersten Ebene abzufangen. Ich habe sogar line_number und char_index -Mitglieder für den hübschen Druck hinzugefügt, und die Funktion, die das macht:

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

Einpacken

Damit endet der erste Teil unserer Serie. Vielleicht war es nicht allzu aufregend, aber wir haben jetzt einen nützlichen Tokenizer zusammen mit einer grundlegenden Behandlung von Parsing-Fehlern. Beides sind entscheidende Bausteine ​​für die interessanteren Dinge, über die ich in den kommenden Artikeln schreiben werde.

Ich hoffe, dass Sie einige gute Ideen aus diesem Beitrag gewonnen haben, und wenn Sie die Details erkunden möchten, besuchen Sie meine GitHub-Seite.

Weiterführende Literatur im Toptal Engineering Blog:

• Wie man einen Dolmetscher von Grund auf neu schreibt