Cicogna: come creare un linguaggio di programmazione in C++

Parte 1: Tokenizzatore

In questa serie, svilupperemo un nuovo linguaggio di scripting e descriveremo il processo passo dopo passo.

È probabile che la prima domanda che viene spontanea in mente a qualsiasi lettore curioso sia: "Abbiamo davvero bisogno di un nuovo linguaggio di programmazione?"

Abbiamo davvero bisogno di un nuovo linguaggio di programmazione?

Per rispondere a questa domanda, mi permetto una piccola digressione.

Immagina di essere un architetto (un vero architetto di mattoni e malta, non di software) e di essere abbastanza sfortunato da nascere in un paese molto burocratico. Hai una grande idea per un centro commerciale nella tua città natale sottosviluppata, quindi crei il progetto e richiedi un permesso di costruzione. Naturalmente, ti respingono immediatamente perché non hai una società registrata. Quindi, registri una società. Per fare ciò, devi depositare del denaro. Quindi, trovi un nome per la tua azienda, che viene rifiutato. Al quinto tentativo, viene accettato e la tua domanda va in fondo all'heap. Alla fine, o ti arrendi o ti rendi conto che nel frattempo qualcun altro ha costruito un centro commerciale.

Ma non siamo veri architetti. Siamo ingegneri del software e abbiamo il privilegio di dare vita alle nostre idee senza permessi o burocrazia. L'unica cosa di cui abbiamo bisogno è tempo libero e la volontà di spenderlo nella programmazione invece che nei sudoku.

Se insisti ancora sul fatto che la motivazione per la programmazione non può essere pura curiosità, lasciami solo menzionare che il primo linguaggio di programmazione che ho progettato è stato sviluppato per necessità, non per semplice curiosità. Tuttavia, questa non dovrebbe essere la prima motivazione per leggere questo blog. Penso che molte idee che incontrerai qui siano abbastanza interessanti e innovative per tenerti interessato anche se in realtà non hai bisogno di creare il tuo linguaggio di programmazione.

Il nostro obiettivo di sviluppare un linguaggio di scripting di piccole dimensioni mi ha ispirato a chiamarlo "Cicogna"; e per fortuna non abbiamo bisogno di convincere nessun burocrate ad approvare il nome.

Svilupperò il linguaggio di programmazione mentre andiamo avanti nella serie, quindi c'è la possibilità che svilupperò anche alcuni bug. Dovrebbero essere risolti mentre ci avviciniamo alla fine della serie.

Il codice sorgente completo per tutto quanto descritto qui è disponibile gratuitamente su GitHub.

Infine, per rispondere alla domanda del titolo di questo paragrafo, no, in realtà non abbiamo bisogno di un nuovo linguaggio di programmazione, ma poiché stiamo cercando di dimostrare come creare un linguaggio di programmazione in C++, ne creeremo uno a scopo dimostrativo .

I piccoli aiutanti di Tokenizer

Non so se altri programmatori affrontano regolarmente lo stesso problema, ma affronto questo problema abbastanza frequentemente:

Ho bisogno di un contenitore chiave-valore che dovrebbe recuperare i valori velocemente, in tempo logaritmico. Tuttavia, una volta inizializzato il contenitore, non voglio aggiungere nuovi valori ad esso. Pertanto, std::map<Key, Value> (o std::unordered_map<Key, Value> ) è eccessivo, poiché consente anche un inserimento rapido.

Sono completamente contrario all'ottimizzazione non necessaria, ma in questo caso sento che molta memoria viene sprecata per niente. Non solo, ma in seguito dovremo implementare un algoritmo di sgranocchiamento massimo su un tale contenitore, e la map non è il miglior contenitore per questo.

La seconda scelta è std::vector<std::pair<Key,Value> > , ordinata dopo gli inserimenti. L'unico problema con questo approccio è la minore leggibilità del codice poiché dobbiamo tenere presente che il vettore è ordinato, quindi ho sviluppato una piccola classe che assicura quel vincolo.

(Tutte le funzioni, le classi, ecc. Sono dichiarate nello spazio dei nomi stork . Ometterò quello spazio dei nomi per leggibilità.)

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

Come puoi vedere, l'implementazione di questa classe è abbastanza semplice. Non volevo implementare tutti i metodi possibili, solo quelli di cui avremo bisogno. Il contenitore sottostante è un vector , quindi può essere inizializzato con un vector precompilato o con initializer_list .

Il tokenizzatore leggerà i caratteri dal flusso di input. In questa fase del progetto, è difficile per me decidere quale sarà il flusso di input, quindi userò invece std::function .

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

Userò le convenzioni note delle funzioni di flusso in stile C, come getc , che restituisce un int invece di char e un numero negativo per segnalare la fine di un file.

Tuttavia, è davvero conveniente leggere un paio di caratteri in anticipo, prima di assumere un tipo di token in un tokenizer. A tal fine, ho implementato uno stream che ci permetterà di non leggere alcuni caratteri.

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

Per risparmiare spazio, ometterò i dettagli di implementazione, che puoi trovare sulla mia pagina GitHub.

Come puoi vedere, push_back_stream viene inizializzato dalla funzione get_character . L'overloaded operator() viene utilizzato per recuperare il carattere successivo e push_back viene utilizzato per restituire il carattere al flusso. line_number e char_number sono metodi pratici utilizzati per i rapporti di errore.

Tieni presente che char_index non è l'indice del carattere nella riga corrente ma nel complesso; in caso contrario, dovremmo conservare tutti i caratteri precedenti in un contenitore per implementare correttamente la funzione push_back .

Token riservati

Il tokenizer è il componente del compilatore di livello più basso. Deve leggere i gettoni di ingresso e di "sputare". Ci sono quattro tipi di token che ci interessano:

• Token riservati
• Identificatori
• Numeri
• stringhe

Non ci interessano i commenti, quindi il tokenizer li "mangerà", senza avvisare nessuno.

Per garantire l'appeal e la popolarità planetaria di questo linguaggio, utilizzeremo la ben nota sintassi C-like. Ha funzionato abbastanza bene per C, C++, JavaScript, Java, C# e Objective-C, quindi deve funzionare anche per Stork. Se hai bisogno di un corso di aggiornamento, puoi consultare uno dei nostri precedenti articoli sulle risorse di apprendimento C/C++.

Ecco l'enumerazione dei token riservati:

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

I membri dell'enumerazione preceduti da "kw_" sono parole chiave. Ho dovuto prefissarli poiché di solito sono le stesse delle parole chiave C++. Quelli senza prefisso sono operatori.

Quasi tutti seguono la convenzione C. Quelli che non lo sono:
- concat e concat_assign ( .. e ..= ), che verranno utilizzati per la concatenazione
- idiv e idiv_assign ( \ e \= ), che verranno utilizzati per la divisione di interi
- kw_var per la dichiarazione delle variabili
- kw_fun per la dichiarazione della funzione
- kw_number per le variabili numeriche
- kw_string per variabili stringa

Aggiungeremo parole chiave aggiuntive, se necessario.

C'è una nuova parola chiave che merita di essere descritta: kw_elif . Sono fermamente convinto che i blocchi di singole affermazioni (senza parentesi graffe) non valgano la pena. Non li uso (e non sento che manchi nulla), tranne in due occasioni:

1. Quando premo accidentalmente un punto e virgola subito dopo un'istruzione for , while o if prima del blocco. Se sono fortunato, restituisce un errore in fase di compilazione, ma a volte risulta in un'istruzione if fittizia e in un blocco che viene sempre eseguito. Fortunatamente, nel corso degli anni, ho imparato dai miei errori, quindi succede molto raramente. Anche il cane di Pavlov ha imparato, alla fine.
2. Quando ho "concatenato" le istruzioni if, quindi ho un blocco if, quindi uno o più blocchi else-if e, facoltativamente, un altro blocco. Tecnicamente, quando scrivo else if , è un blocco else con una sola istruzione, che è quella if-istruzione.

Pertanto, elif può essere utilizzato per eliminare completamente le affermazioni senza braccia. Che lo permettiamo o meno è una decisione che può aspettare per ora.

Esistono due funzioni di supporto che restituiscono token riservati:

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

La funzione get_keyword restituisce una parola chiave opzionale dalla parola passata. Quella "parola" è una sequenza di lettere, cifre e trattini bassi, che iniziano con una lettera o un trattino basso. Restituirà un reserved_token se la parola è una parola chiave. In caso contrario, il tokenizzatore presumerà che si tratti di un identificatore.

La funzione get_operator sta cercando di leggere quanti più caratteri possibile, purché la sequenza sia un operatore valido. Se ne legge di più, cancellerà tutti i caratteri extra che ha letto dopo l'operatore più lungo riconosciuto.

Per l'efficace implementazione di queste due funzioni, abbiamo bisogno di due ricerche tra string_view e 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'implementazione get_keyword è completamente semplice, ma per get_operator , abbiamo bisogno di un comparatore personalizzato che confronterà un dato carattere con gli operatori candidati, prendendo in considerazione solo l'n-esimo carattere.

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

Questo è un normale comparatore lessicale che tiene conto solo del carattere in position idx , ma se la stringa è più corta, la tratta come se avesse un carattere null in position idx , che è minore di qualsiasi altro carattere.

Questa è l'implementazione di get_operator , che dovrebbe rendere più chiara 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; }

Fondamentalmente, all'inizio trattiamo tutti gli operatori come candidati. Quindi, leggiamo carattere per carattere e filtriamo i candidati correnti chiamando equal_range , confrontando solo l'n-esimo carattere. Non abbiamo bisogno di confrontare i caratteri precedenti in quanto sono già confrontati, e non vogliamo confrontare i caratteri che seguono in quanto sono ancora irrilevanti.

Ogni volta che l'intervallo non è vuoto, controlliamo se il primo elemento nell'intervallo non ha più caratteri (se esiste un tale elemento, è sempre all'inizio dell'intervallo mentre la ricerca viene ordinata). In tal caso, abbiamo un operatore legale abbinato. L'operatore di questo tipo più lungo è quello che restituiamo. Non leggeremo tutti i personaggi che alla fine leggeremo.

Tokenizzatore

Poiché i token sono eterogenei, un token è una classe di convenienza che avvolge std::variant diversi tipi di token, vale a dire:

• Token riservato
• Identificatore
• Numero
• Corda
• Fine del fascicolo

 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 è solo una classe con un singolo membro del tipo std::string . È lì per comodità poiché, secondo me, std::variant è più pulito se tutte le sue alternative sono di tipi diversi.

Ora possiamo scrivere il tokenizer. Sarà una funzione che accetterà push_back_stream e restituirà il token successivo.

Il trucco consiste nell'utilizzare rami di codice diversi, in base al tipo di carattere del primo carattere che leggiamo.

• Se leggiamo il carattere di fine file, torneremo dalla funzione.
• Se leggiamo uno spazio bianco, lo salteremo.
• Se leggiamo un carattere alfanumerico (una lettera, una cifra o un trattino basso), leggeremo tutti i caratteri successivi di quel tipo (leggeremo anche i punti se il primo carattere è una cifra). Quindi, se il primo carattere è una cifra, proveremo ad analizzare la sequenza come un numero. In caso contrario, utilizzeremo la funzione get_keyword per verificare se si tratta di una parola chiave o di un identificatore.
• Se leggiamo una virgoletta, la tratteremo come una stringa, senza caratteri di escape da essa.
• Se leggiamo un carattere barra ( / ), verificheremo se il carattere successivo è una barra o un asterisco ( * ), e in tal caso salteremo il commento di riga/blocco.
• In caso contrario, utilizzeremo la funzione get_operator .

Ecco l'implementazione della funzione tokenize. Ometterò i dettagli di implementazione delle funzioni che sta chiamando.

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

Puoi vedere che respinge i caratteri che legge prima di chiamare una funzione di livello inferiore. La riduzione delle prestazioni è quasi inesistente e il codice funzione di livello inferiore è molto più pulito.

Eccezioni

In uno dei suoi sproloqui contro le eccezioni, mio ​​fratello una volta disse:

“Ci sono due tipi di persone: quelle che lanciano eccezioni e quelle che devono prenderle. Sono sempre in quel triste, secondo gruppo.

Sono d'accordo con lo spirito di tale affermazione. Non mi piacciono particolarmente le eccezioni e lanciarle può rendere qualsiasi codice molto più difficile da mantenere e leggere. Quasi sempre.

Ho deciso di fare un'eccezione (un gioco di parole sbagliato) a quella regola. È davvero conveniente lanciare un'eccezione dal compilatore per rilassarsi dalle profondità della compilazione.

Ecco l'implementazione dell'eccezione:

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

Tuttavia, prometto di catturare tutte le eccezioni nel codice di primo livello. Ho anche aggiunto i membri line_number e char_index per la stampa graziosa e la funzione che lo fa:

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

Avvolgendo

Questo conclude la prima parte della nostra serie. Forse non è stato troppo eccitante, ma ora abbiamo un utile tokenizzatore, insieme alla gestione di base degli errori di analisi. Entrambi sono elementi costitutivi cruciali per le cose più interessanti di cui scriverò nei prossimi articoli.

Spero che tu abbia avuto delle buone idee da questo post e, se vuoi esplorare i dettagli, vai alla mia pagina GitHub.

Ulteriori letture sul blog di Toptal Engineering:

• Come avvicinarsi alla scrittura di un interprete da zero