Bocian: jak zrobić język programowania w C++

Część 1: Tokenizer

W tej serii opracujemy nowy język skryptowy i krok po kroku opiszemy ten proces.

Pierwsze pytanie, które spontanicznie przychodzi do głowy każdemu zastanawiającemu się czytelnikowi, prawdopodobnie brzmi: „Czy naprawdę potrzebujemy nowego języka programowania?”

Czy naprawdę potrzebujemy nowego języka programowania?

Aby odpowiedzieć na to pytanie, pozwolę sobie na małą dygresję.

Wyobraź sobie, że jesteś architektem (prawdziwym architektem z cegły i zaprawy, a nie programistą) i masz pecha, by urodzić się w bardzo zbiurokratyzowanym kraju. Masz świetny pomysł na galerię handlową w swoim słabo rozwiniętym rodzinnym mieście, więc tworzysz projekt i ubiegasz się o pozwolenie na budowę. Oczywiście natychmiast odrzucają Cię, ponieważ nie masz zarejestrowanej firmy. Więc rejestrujesz firmę. Aby to zrobić, musisz wpłacić trochę pieniędzy. Następnie wymyślasz nazwę swojej firmy, która jest odrzucana. Przy piątej próbie zostaje zaakceptowana, a Twoja aplikacja trafia na sam dół stosu. Ostatecznie albo się poddajesz, albo zdajesz sobie sprawę, że ktoś inny zbudował w międzyczasie centrum handlowe.

Ale nie jesteśmy prawdziwymi architektami. Jesteśmy inżynierami oprogramowania i mamy przywilej wcielania naszych pomysłów w życie bez zezwoleń i biurokracji. Jedyne czego potrzebujemy to wolny czas i chęć poświęcenia go na programowanie zamiast łamigłówek sudoku.

Jeśli nadal upierasz się, że motywacją do programowania nie może być czysta ciekawość, wspomnę tylko, że pierwszy język programowania, który zaprojektowałem, powstał z konieczności, a nie z ciekawości. Jednak nie to powinno być pierwszą motywacją do przeczytania tego bloga. Myślę, że wiele pomysłów, które tu napotkasz, jest dość interesujących i innowacyjnych, aby Cię zainteresować, nawet jeśli nie musisz tworzyć własnego języka programowania.

Nasz cel, jakim było opracowanie niewielkiego języka skryptowego, zainspirował mnie do nazwania go „Bocianem”; i na szczęście nie musimy przekonywać żadnego biurokraty do zatwierdzenia tej nazwy.

Zamierzam rozwijać język programowania w miarę przechodzenia przez serię, więc istnieje możliwość, że rozwinę również kilka błędów. Należy je dopracować, gdy zbliżamy się do końca serii.

Pełny kod źródłowy wszystkiego, co tutaj opisano, jest bezpłatnie dostępny na GitHub.

Na koniec, aby odpowiedzieć na pytanie z tytułu tego akapitu — nie, właściwie nie potrzebujemy nowego języka programowania, ale ponieważ próbujemy zademonstrować, jak stworzyć język programowania w C++, stworzymy go w celach demonstracyjnych .

Mali pomocnicy Tokenizera

Nie wiem, czy inni programiści regularnie borykają się z tym samym problemem, ale z tym problemem spotykam się dość często:

Potrzebuję kontenera klucz-wartość, który powinien szybko pobierać wartości w czasie logarytmicznym. Jednak po zainicjowaniu kontenera nie chcę dodawać do niego nowych wartości. Dlatego std::map<Key, Value> (lub std::unordered_map<Key, Value> ) jest przesadą, ponieważ umożliwia również szybkie wstawianie.

Jestem całkowicie przeciwny niepotrzebnej optymalizacji, ale w tym przypadku czuję, że dużo pamięci jest marnowane na nic. Nie tylko to, ale później będziemy musieli zaimplementować algorytm maksymalnego chrupania na takim pojemniku, a map nie jest do tego najlepszym pojemnikiem.

Drugim wyborem jest std::vector<std::pair<Key,Value> > , posortowane po wstawieniu. Jedynym problemem związanym z tym podejściem jest mniejsza czytelność kodu, ponieważ musimy pamiętać, że wektor jest posortowany, więc opracowałem małą klasę, która zapewnia to ograniczenie.

(Wszystkie funkcje, klasy itp. są zadeklarowane w przestrzeni nazw stork . Pominę tę przestrzeń nazw dla czytelności.)

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

Jak widać, implementacja tej klasy jest dość prosta. Nie chciałem wdrażać wszystkich możliwych metod, tylko te, które będą nam potrzebne. Podstawowym kontenerem jest vector , więc można go zainicjować za pomocą wstępnie wypełnionego vector lub za pomocą initializer_list .

Tokenizer odczyta znaki ze strumienia wejściowego. Na tym etapie projektu trudno mi zdecydować, jaki będzie strumień wejściowy, więc zamiast tego std::function .

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

Użyję dobrze znanych konwencji z funkcji strumieniowych w stylu C, takich jak getc , które zwracają int zamiast char , a także liczbę ujemną sygnalizującą koniec pliku.

Jednak naprawdę wygodnie jest przeczytać kilka znaków wcześniej, przed założeniem typu tokena w tokenizerze. W tym celu zaimplementowałem strumień, który umożliwi nam nieprzeczytanie niektórych znaków.

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

Aby zaoszczędzić miejsce, pominę szczegóły implementacji, które znajdziecie na mojej stronie GitHub.

Jak widać, push_back_stream jest inicjowany z funkcji get_character . Przeciążony operator() służy do pobierania następnego znaku, a push_back służy do zwracania znaku z powrotem do strumienia. line_number i char_number to wygodne metody używane do raportowania błędów.

Należy pamiętać, że char_index nie jest indeksem znaku w bieżącej linii, ale ogólnie; w przeciwnym razie musielibyśmy przechowywać wszystkie przeszłe znaki w jakimś kontenerze, aby poprawnie zaimplementować funkcję push_back .

Zarezerwowane tokeny

Tokenizer jest składnikiem kompilatora najniższego poziomu. Musi odczytywać tokeny wejściowe i „wypluć”. Interesują nas cztery rodzaje tokenów:

• Zarezerwowane tokeny
• Identyfikatory
• Liczby
• Smyczki

Nie interesują nas komentarze, więc tokenizer po prostu je „zje”, nie powiadamiając nikogo.

Aby zapewnić atrakcyjność i globalną popularność tego języka, użyjemy dobrze znanej składni podobnej do C. Działało całkiem dobrze w C, C++, JavaScript, Java, C# i Objective-C, więc musi działać również w Stork. Jeśli potrzebujesz kursu przypominającego, możesz zapoznać się z jednym z naszych poprzednich artykułów dotyczących zasobów edukacyjnych C/C++.

Oto wyliczenie zarezerwowanych tokenów:

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

Elementy wyliczenia z przedrostkiem „kw_” są słowami kluczowymi. Musiałem je poprzedzić, ponieważ zwykle są takie same, jak słowa kluczowe C++. Te bez prefiksu to operatory.

Prawie wszystkie z nich są zgodne z konwencją C. Te, które nie są:
- concat i concat_assign ( .. i ..= ), które zostaną użyte do konkatenacji
- idiv i idiv_assign ( \ i \= ), które będą używane do dzielenia liczb całkowitych
- kw_var dla deklaracji zmiennej
- kw_fun dla deklaracji funkcji
- kw_number dla zmiennych liczbowych
- kw_string dla zmiennych łańcuchowych

W razie potrzeby dodamy dodatkowe słowa kluczowe.

Jest jedno nowe słowo kluczowe, które zasługuje na opisanie: kw_elif . Jestem głęboko przekonany, że bloki jednowyrazowe (bez nawiasów klamrowych) nie są tego warte. Nie używam ich (i nie czuję, żeby czegoś brakowało), z wyjątkiem dwóch okazji:

1. Kiedy przypadkowo nacisnę średnik zaraz po instrukcji for , while lub if przed blokiem. Jeśli mam szczęście, zwraca błąd czasu kompilacji, ale czasami powoduje to fikcyjną instrukcję if i blok, który zawsze się wykonuje. Na szczęście przez lata uczyłem się na błędach, więc zdarza się to bardzo rzadko. Pies Pawłowa też się w końcu nauczył.
2. Kiedy mam „połączone” instrukcje if, mam blok if, a następnie jeden lub więcej bloków else-if i opcjonalnie blok else. Technicznie rzecz biorąc, kiedy piszę else if , jest to blok else z tylko jedną instrukcją, czyli instrukcją if.

Dlatego elif może być używany do całkowitego wyeliminowania stwierdzeń bez nawiasów klamrowych. To, czy pozwolimy na to, czy nie, to decyzja, która może poczekać na teraz.

Istnieją dwie funkcje pomocnicze, które zwracają zarezerwowane tokeny:

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

Funkcja get_keyword zwraca opcjonalne słowo kluczowe z przekazanego słowa. To „słowo” to sekwencja liter, cyfr i podkreśleń, zaczynająca się od litery lub podkreślenia. Zwróci reserved_token , jeśli słowo jest słowem kluczowym. W przeciwnym razie tokenizer przyjmie, że jest to identyfikator.

Funkcja get_operator próbuje odczytać jak najwięcej znaków, o ile sekwencja jest prawidłowym operatorem. Jeśli czyta więcej, odczyta wszystkie dodatkowe znaki, które przeczytał po najdłuższym rozpoznanym operatorze.

Aby efektywnie zaimplementować te dwie funkcje, potrzebujemy dwóch wyszukiwań między 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} };

Implementacja get_keyword jest całkowicie prosta, ale dla get_operator potrzebujemy niestandardowego komparatora, który porówna dany znak z operatorami kandydującymi, biorąc pod uwagę tylko n-ty znak.

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

To zwykły leksykalny komparator, który bierze pod uwagę tylko znak na pozycji idx , ale jeśli łańcuch jest krótszy, traktuje go tak, jakby miał znak null na pozycji idx , który jest mniejszy niż jakikolwiek inny znak.

Oto implementacja get_operator , która powinna sprawić, że klasa maximal_munch_operator bardziej przejrzysta:

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

W zasadzie wszystkich operatorów traktujemy na początku jak kandydatów. Następnie czytamy znak po znaku i filtrujemy obecnych kandydatów, wywołując equal_range , porównując tylko n-ty znak. Nie musimy porównywać poprzedzających znaków, ponieważ są już porównywane, i nie chcemy porównywać kolejnych znaków, ponieważ nadal są nieistotne.

Za każdym razem, gdy zakres nie jest pusty, sprawdzamy, czy pierwszy element w zakresie nie ma więcej znaków (jeśli taki element istnieje, zawsze znajduje się na początku zakresu, ponieważ wyszukiwanie jest sortowane). W takim przypadku mamy dopasowany operator prawny. Najdłuższy taki operator to taki, do którego zwracamy. Odczytamy wszystkie znaki, które w końcu przeczytamy.

Tokenizer

Ponieważ tokeny są heterogeniczne, token jest klasą wygodną, ​​która otacza std::variant różne typy tokenów, a mianowicie:

• Zarezerwowany token
• Identyfikator
• Numer
• Strunowy
• Koniec pliku

 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 jest po prostu klasą z pojedynczym elementem typu std::string . Jest tam dla wygody, ponieważ moim zdaniem std::variant jest czystszy, jeśli wszystkie jego alternatywy są różnych typów.

Teraz możemy napisać tokenizer. Będzie to jedna funkcja, która zaakceptuje push_back_stream i zwróci kolejny token.

Sztuczka polega na użyciu różnych gałęzi kodu, w zależności od typu znaku pierwszego odczytanego znaku.

• Jeśli odczytamy znak końca pliku, wrócimy z funkcji.
• Jeśli odczytamy spację, pominiemy ją.
• Jeśli odczytamy znak alfanumeryczny (litera, cyfra lub podkreślenie), to odczytamy wszystkie kolejne znaki tego typu (czytamy też kropki, jeśli pierwszy znak jest cyfrą). Następnie, jeśli pierwszy znak jest cyfrą, spróbujemy przeanalizować sekwencję jako liczbę. W przeciwnym razie użyjemy funkcji get_keyword , aby sprawdzić, czy jest to słowo kluczowe, czy identyfikator.
• Jeśli odczytamy cudzysłów, potraktujemy go jako ciąg, usuwając z niego znaki ucieczki.
• Jeśli odczytamy znak ukośnika ( / ), sprawdzimy, czy następny znak to ukośnik, czy gwiazdka ( * ) i w takim przypadku pominiemy komentarz linii/bloku.
• W przeciwnym razie użyjemy funkcji get_operator .

Oto implementacja funkcji tokenizacji. Pominę szczegóły implementacji funkcji, które wywołuje.

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

Możesz zobaczyć, że odpycha znaki, które czyta, zanim wywoła funkcję niższego poziomu. Spadek wydajności prawie nie istnieje, a kod funkcji niższego poziomu jest znacznie czystszy.

Wyjątki

W jednej ze swoich tyrad przeciwko wyjątkom mój brat powiedział kiedyś:

„Są dwa rodzaje ludzi: ci, którzy rzucają wyjątki i ci, którzy muszą je łapać. Zawsze jestem w tej smutnej, drugiej grupie”.

Zgadzam się z duchem tego stwierdzenia. Nieszczególnie lubię wyjątki, a ich rzucanie może znacznie utrudnić utrzymanie i odczytywanie dowolnego kodu. Prawie zawsze.

Postanowiłem zrobić wyjątek (zła gra słów) od tej reguły. Naprawdę wygodnie jest wyrzucić wyjątek z kompilatora, aby uwolnić się od głębi kompilacji.

Oto implementacja wyjątku:

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

Obiecuję jednak wyłapać wszystkie wyjątki w kodzie najwyższego poziomu. Dodałem nawet elementy line_number i char_index do ładnego drukowania oraz funkcję, która to robi:

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

Zawijanie

Na tym kończy się pierwsza część naszej serii. Być może nie było to zbyt ekscytujące, ale teraz mamy użyteczny tokenizer wraz z podstawową obsługą błędów parsowania. Oba są kluczowymi elementami budulcowymi dla ciekawszych rzeczy, o których zamierzam napisać w kolejnych artykułach.

Mam nadzieję, że w tym poście znalazłeś kilka dobrych pomysłów, a jeśli chcesz poznać szczegóły, wejdź na moją stronę GitHub.

Dalsza lektura na blogu Toptal Engineering:

• Jak podejść do pisania tłumacza od podstaw