Stork: Cum se creează un limbaj de programare în C++

Partea 1: Tokenizer

În această serie, vom dezvolta un nou limbaj de scripting și vom descrie acest proces pas cu pas.

Prima întrebare care vine spontan în mintea oricărui cititor care se întrebă este probabil: „Avem cu adevărat nevoie de un nou limbaj de programare?”

Avem cu adevărat nevoie de un nou limbaj de programare?

Pentru a răspunde la această întrebare, îmi voi permite o mică digresiune.

Imaginați-vă că sunteți arhitect (un adevărat arhitect de cărămidă și mortar, nu unul de software) și că aveți ghinionul să vă născut într-o țară foarte birocratică. Aveți o idee grozavă pentru un centru comercial în orașul natal subdezvoltat, așa că creați proiectul și aplicați pentru o autorizație de construire. Desigur, te resping imediat pe motiv că nu ai o firmă înregistrată. Deci, înregistrați o companie. Pentru a face asta, trebuie să depui niște bani. Apoi, vii cu un nume pentru compania ta, care este respins. La a cincea încercare, este acceptată, iar cererea dvs. ajunge la partea de jos a gheamului. În cele din urmă, fie renunți, fie realizezi că altcineva și-a construit un mall între timp.

Dar nu suntem arhitecți adevărați. Suntem ingineri software și avem privilegiul de a ne aduce ideile la viață fără permise sau birocrație. Singurul lucru de care avem nevoie este timpul liber și dorința de a-l petrece programării în loc de puzzle-uri sudoku.

Dacă tot insistați că motivația pentru programare nu poate fi pură curiozitate, permiteți-mi doar să menționez că primul limbaj de programare pe care l-am conceput a fost dezvoltat ca urmare a necesității, nu a simplă curiozitate. Cu toate acestea, aceasta nu ar trebui să fie prima motivație pentru a citi acest blog. Cred că multe idei pe care le veți întâlni aici sunt destul de interesante și inovatoare pentru a vă menține interesat, chiar dacă nu aveți nevoie de fapt să vă creați propriul limbaj de programare.

Scopul nostru de a dezvolta un limbaj de scripting cu amprentă mică m-a inspirat să-l numesc „Stork”; și, din fericire, nu trebuie să convingem niciun birocrat să aprobe numele.

Voi dezvolta limbajul de programare pe măsură ce parcurgem seria, așa că există posibilitatea ca și eu să dezvolt unele erori. Ele ar trebui să fie eliminate pe măsură ce ne apropiem de sfârșitul seriei.

Codul sursă complet pentru tot ceea ce este descris aici este disponibil gratuit pe GitHub.

În cele din urmă, pentru a răspunde la întrebarea din titlul acestui paragraf - nu, de fapt nu avem nevoie de un nou limbaj de programare, dar din moment ce încercăm să demonstrăm cum să facem un limbaj de programare în C++, vom crea unul în scopuri demonstrative. .

Micii ajutatori ai lui Tokenizer

Nu știu dacă alți programatori se confruntă cu aceeași problemă în mod regulat, dar mă confrunt cu această problemă destul de frecvent:

Am nevoie de un container cheie-valoare care ar trebui să recupereze valorile rapid, în timp logaritmic. Cu toate acestea, odată ce inițialez containerul, nu vreau să-i adaug noi valori. Prin urmare, std::map<Key, Value> (sau std::unordered_map<Key, Value> ) este exagerat, deoarece permite și inserarea rapidă.

Sunt complet împotriva optimizării inutile, dar în acest caz, simt că se irosește multă memorie pentru nimic. Nu numai asta, dar mai târziu, va trebui să implementăm un algoritm de munch maxim pe deasupra unui astfel de container, iar map nu este cel mai bun container pentru asta.

A doua alegere este std::vector<std::pair<Key,Value> > , sortată după inserări. Singura problemă cu această abordare este lizibilitatea codului mai mică, deoarece trebuie să ținem cont de faptul că vectorul este sortat, așa că am dezvoltat o clasă mică care asigură această constrângere.

(Toate funcțiile, clasele etc. sunt declarate în spațiul de nume stork . Voi omite acel spațiu de nume pentru lizibilitate.)

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

După cum puteți vedea, implementarea acestei clase este destul de simplă. Nu am vrut să implementez toate metodele posibile, doar cele de care vom avea nevoie. Containerul de bază este un vector , deci poate fi inițializat cu un vector pre-populat sau cu initializer_list .

Tokenizatorul va citi caractere din fluxul de intrare. În această etapă a proiectului, îmi este greu să decid care va fi fluxul de intrare, așa că voi folosi în schimb std::function .

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

Voi folosi convenții binecunoscute din funcțiile de flux în stil C, cum ar fi getc , care returnează un int în loc de char , precum și un număr negativ pentru a semnala sfârșitul unui fișier.

Cu toate acestea, este foarte convenabil să citiți câteva caractere în avans, înainte de a presupune un tip de token într-un tokenizer. În acest scop, am implementat un flux care ne va permite să necitim unele personaje.

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

Pentru a economisi spațiu, voi omite detaliile de implementare, pe care le puteți găsi pe pagina mea GitHub.

După cum puteți vedea, push_back_stream este inițializat din funcția get_character . operator() este folosit pentru a prelua următorul caracter, iar push_back este folosit pentru a returna caracterul înapoi în flux. line_number și char_number sunt metode convenabile utilizate pentru rapoartele de eroare.

Rețineți că char_index nu este indexul caracterului din linia curentă, ci în general; altfel, ar trebui să păstrăm toate caracterele trecute într-un container pentru a implementa corect funcția push_back .

Jetoane rezervate

Tokenizer-ul este componenta compilatorului de cel mai jos nivel. Trebuie să citească jetoanele de intrare și „scuipat”. Există patru tipuri de jetoane care ne interesează:

• Jetoane rezervate
• Identificatori
• Numerele
• Siruri de caractere

Nu ne interesează comentariile, așa că tokenizatorul le va „mânca”, fără a anunța pe nimeni.

Pentru a asigura atractivitatea și popularitatea planetară a acestui limbaj, vom folosi binecunoscuta sintaxă asemănătoare C. A funcționat destul de bine pentru C, C++, JavaScript, Java, C# și Objective-C, așa că trebuie să funcționeze și pentru Stork. În cazul în care aveți nevoie de un curs de perfecționare, puteți consulta unul dintre articolele noastre anterioare care acoperă resursele de învățare C/C++.

Iată enumerarea jetoanelor rezervate:

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

Membrii de enumerare prefixați cu „kw_” sunt cuvinte cheie. A trebuit să le prefixez, deoarece sunt de obicei aceleași cu cuvintele cheie C++. Cei fără prefix sunt operatori.

Aproape toate urmează convenția C. Cei care nu sunt:
- concat și concat_assign ( .. și ..= ), care vor fi folosite pentru concatenare
- idiv și idiv_assign ( \ și \= ), care vor fi folosite pentru împărțirea întregilor
- kw_var pentru declararea variabilelor
- kw_fun pentru declararea funcției
- kw_number pentru variabilele numerice
- kw_string pentru variabile șir

Vom adăuga cuvinte cheie suplimentare, după cum este necesar.

Există un cuvânt cheie nou care merită descris: kw_elif . Sunt ferm convins că blocurile cu o singură declarație (fără bretele) nu merită. Nu le folosesc (și nu simt că lipsește ceva), decât în ​​două ocazii:

1. Când am apăsat accidental punct și virgulă imediat după o declarație for , while , sau if înainte de bloc. Dacă sunt norocos, returnează o eroare de timp de compilare, dar uneori, rezultă o instrucțiune if și un bloc care se execută întotdeauna. Din fericire, de-a lungul anilor, am învățat din greșelile mele, așa că se întâmplă foarte rar. Câinele lui Pavlov a învățat și el, până la urmă.
2. Când am „înlănțuit” instrucțiuni if, deci am un if-bloc, apoi unul sau mai multe else-if-blocks și, opțional, un else-bloc. Din punct de vedere tehnic, când scriu else if , acesta este un bloc else cu o singură declarație, care este acea if-instruction.

Prin urmare, elif poate fi folosit pentru a elimina complet declarațiile fără bretele. Dacă permitem sau nu este o decizie care poate aștepta deocamdată.

Există două funcții de ajutor care returnează jetoane rezervate:

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

Funcția get_keyword returnează un cuvânt cheie opțional din cuvântul transmis. Acel „cuvânt” este o succesiune de litere, cifre și liniuțe de subliniere, începând cu o literă sau un caracter de subliniere. Va returna un reserved_token dacă cuvântul este un cuvânt cheie. În caz contrar, tokenizer-ul va presupune că este un identificator.

Funcția get_operator încearcă să citească cât mai multe caractere posibil, atâta timp cât secvența este un operator valid. Dacă citește mai mult, va anula toate caracterele suplimentare pe care le-a citit după cel mai lung operator recunoscut.

Pentru implementarea eficientă a acestor două funcții, avem nevoie de două căutări între string_view și 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} };

Implementarea get_keyword este complet simplă, dar pentru get_operator , avem nevoie de un comparator personalizat care va compara un anumit caracter cu operatorii candidați, luând în considerare doar al n-lea caracter.

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

Acesta este un comparator lexical obișnuit care ia în considerare doar caracterul de la poziția idx , dar dacă șirul este mai scurt, îl tratează ca și cum ar avea un caracter nul la poziția idx , care este mai mic decât orice alt caracter.

Aceasta este implementarea lui get_operator , care ar trebui să clarifice clasa 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; }

Practic, tratăm toți operatorii ca candidați la început. Apoi, citim caracter cu caracter și filtram candidații actuali apelând equal_range , comparând doar al n-lea caracter. Nu trebuie să comparăm caracterele precedente, deoarece acestea sunt deja comparate și nu vrem să comparăm caracterele care urmează, deoarece acestea sunt încă irelevante.

Ori de câte ori intervalul nu este gol, verificăm dacă primul element din interval nu mai are caractere (dacă un astfel de element există, acesta este întotdeauna la începutul intervalului pe măsură ce căutarea este sortată). În acest caz, avem un operator legal potrivit. Cel mai lung astfel de operator este cel pe care îl întoarcem. Vom neciti toate personajele pe care le-am citit în cele din urmă după aceea.

Tokenizer

Deoarece token-urile sunt eterogene, un token este o clasă de comoditate care include std::variant diferite tipuri de jetoane, și anume:

• Jeton rezervat
• Identificator
• Număr
• Şir
• Sfârșitul fișierului

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

identifier este doar o clasă cu un singur membru al tipului std::string . Este acolo pentru comoditate, deoarece, în opinia mea, std::variant este mai curat dacă toate alternativele sale sunt de tipuri diferite.

Acum, putem scrie tokenizer-ul. Va fi o funcție care va accepta push_back_stream și va returna următorul token.

Trucul este să folosiți diferite ramuri de cod, în funcție de tipul de caracter al primului caracter pe care îl citim.

• Dacă citim caracterul de sfârșit de fișier, vom reveni din funcție.
• Dacă citim un spațiu alb, îl vom sări peste el.
• Dacă citim un caracter alfanumeric (o literă, o cifră sau un caracter de subliniere), vom citi toate caracterele succesive de acel tip (vom citi și puncte dacă primul caracter este o cifră). Apoi, dacă primul caracter este o cifră, vom încerca să analizăm secvența ca număr. În caz contrar, vom folosi funcția get_keyword pentru a verifica dacă este un cuvânt cheie sau un identificator.
• Dacă citim un ghilimele, îl vom trata ca pe un șir, fără caractere escape din el.
• Dacă citim un caracter oblic ( / ), vom verifica dacă următorul caracter este o bară oblică sau un asterisc ( * ), iar în acest caz vom sări peste comentariul rând/bloc.
• În caz contrar, vom folosi funcția get_operator .

Iată implementarea funcției tokenize. Voi omite detaliile de implementare ale funcțiilor pe care le apelează.

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

Puteți vedea că respinge caracterele pe care le citește înainte de a apela o funcție de nivel inferior. Penalizarea de performanță este aproape inexistentă, iar codul funcției de nivel inferior este mult mai curat.

Excepții

Într-una dintre dezvăluirile sale împotriva excepțiilor, fratele meu a spus odată:

„Există două feluri de oameni: cei care fac excepții și cei care trebuie să-i prindă. Eu sunt mereu în acel al doilea grup trist.”

Sunt de acord cu spiritul acestei afirmații. Nu-mi plac în mod deosebit excepțiile, iar aruncarea lor poate face orice cod mult mai greu de întreținut și citit. Aproape intotdeauna.

Am hotărât să fac o excepție de la această regulă. Este foarte convenabil să aruncați o excepție de la compilator pentru a vă relaxa din profunzimile compilației.

Iată implementarea excepției:

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

Cu toate acestea, promit să prind toate excepțiile în codul de nivel superior. Am adăugat chiar și membri line_number și char_index pentru imprimare destul de, și funcția care o face:

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

Încheierea

Așa se încheie prima parte a seriei noastre. Poate că nu a fost prea interesant, dar acum avem un tokenizer util, împreună cu gestionarea de bază a erorilor de analiză. Ambele sunt blocuri esențiale pentru lucrurile mai interesante despre care voi scrie în articolele următoare.

Sper că ați primit câteva idei bune din această postare și, dacă doriți să explorați detaliile, accesați pagina mea GitHub.

Citiți suplimentare pe blogul Toptal Engineering:

• Cum să abordați scrierea unui interpret de la zero