Stork: C++ ile Programlama Dili Nasıl Yapılır?

Bölüm 1: Simgeleştirici

Bu seride yeni bir betik dili geliştireceğiz ve bu süreci adım adım anlatacağız.

Merak eden herhangi bir okuyucunun kendiliğinden aklına gelen ilk soru muhtemelen şudur: “Gerçekten yeni bir programlama diline ihtiyacımız var mı?”

Gerçekten Yeni Bir Programlama Diline İhtiyacımız Var mı?

Bu soruyu cevaplamak için kendime küçük bir arasöz vereceğim.

Bir mimar olduğunuzu (bir yazılım değil, gerçek bir tuğla-harç mimarı) ve çok bürokratik bir ülkede doğmak için yeterince şanssız olduğunuzu hayal edin. Az gelişmiş memleketinizde bir alışveriş merkezi için harika bir fikriniz var, bu yüzden projeyi oluşturuyor ve yapı ruhsatı için başvuruyorsunuz. Tabii ki, kayıtlı bir şirketiniz olmadığı gerekçesiyle sizi hemen reddediyorlar. Yani bir şirket kaydettiniz. Bunu yapmak için bir miktar para yatırmanız gerekir. Ardından, şirketiniz için reddedilen bir isim bulursunuz. Beşinci denemenizde, kabul edilir ve başvurunuz yığının dibine gider. Sonuçta ya vazgeçersiniz ya da bu arada başkasının AVM yaptığını fark edersiniz.

Ama biz gerçek mimarlar değiliz. Biz yazılım mühendisleriyiz ve fikirlerimizi hiçbir izin veya bürokrasi olmadan hayata geçirme ayrıcalığına sahibiz. İhtiyacımız olan tek şey boş zaman ve onu sudoku bulmacaları yerine programlamaya harcama isteği.

Hala programlama motivasyonunun salt merak olamayacağında ısrar ediyorsanız, ilk tasarladığım programlama dilinin sadece meraktan değil, zorunluluktan kaynaklandığını belirteyim. Ancak, bu blogu okumak için ilk motivasyon bu olmamalı. Burada karşılaşacağınız birçok fikir, aslında kendi programlama dilinizi oluşturmanız gerekmese bile ilginizi çekecek kadar ilginç ve yenilikçi.

Az yer kaplayan bir betik dili geliştirme hedefimiz, ona “Stork” adını vermem için bana ilham verdi; ve neyse ki, adı onaylaması için herhangi bir bürokratı ikna etmemize gerek yok.

Seri boyunca ilerlerken programlama dilini geliştireceğim, bu yüzden benim de bazı hatalar geliştirme ihtimalim var. Serinin sonuna yaklaştığımızda ütülenmeleri gerekir.

Burada açıklanan her şeyin tam kaynak kodu GitHub'da ücretsiz olarak mevcuttur.

Son olarak, bu paragrafın başlığındaki soruyu yanıtlamak için—hayır, aslında yeni bir programlama diline ihtiyacımız yok, ancak C++'da nasıl bir programlama dili yapılacağını göstermeye çalıştığımız için, tanıtım amaçlı bir tane oluşturacağız. .

Tokenizer'ın Küçük Yardımcıları

Diğer programcıların aynı sorunla düzenli olarak karşılaşıp karşılaşmadığını bilmiyorum, ancak bu sorunla oldukça sık karşılaşıyorum:

Değerleri logaritmik zamanda hızlı bir şekilde alması gereken bir anahtar/değer kabına ihtiyacım var. Ancak, kabı başlattığımda, ona yeni değerler eklemek istemiyorum. Bu nedenle, std::map<Key, Value> (veya std::unordered_map<Key, Value> ) hızlı eklemeye de izin verdiği için aşırıya kaçar.

Gereksiz optimizasyona tamamen karşıyım, ancak bu durumda, hiçbir şey için çok fazla hafıza boşa harcanmış gibi hissediyorum. Sadece bu değil, daha sonra böyle bir kapsayıcının üzerine bir maksimum munch algoritması uygulamamız gerekecek ve map bunun için en iyi kapsayıcı değil.

İkinci seçenek, eklemelerden sonra sıralanan std::vector<std::pair<Key,Value> > şeklindedir. Bu yaklaşımla ilgili tek sorun, vektörün sıralandığını akılda tutmamız gerektiğinden daha az kod okunabilirliğidir, bu yüzden bu kısıtlamayı sağlayan küçük bir sınıf geliştirdim.

(Tüm işlevler, sınıflar vb. stork ad alanında bildirilmiştir. Okunabilirlik için bu ad alanını atlayacağım.)

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

Gördüğünüz gibi, bu sınıfın uygulaması oldukça basittir. Tüm olası yöntemleri uygulamak istemedim, sadece ihtiyacımız olanları. Temeldeki kapsayıcı bir vector , bu nedenle önceden doldurulmuş bir vector veya initializer_list ile initializer_list .

Belirteç, giriş akışındaki karakterleri okuyacaktır. Projenin bu aşamasında, girdi akışının ne olacağına karar vermek benim için zor, bu yüzden onun yerine std::function kullanacağım.

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

Bir dosyanın sonunu bildirmek için char yerine int ve negatif bir sayı döndüren getc gibi C-tarzı akış işlevlerinden iyi bilinen kuralları kullanacağım.

Ancak, bir belirteçte belirteç türü varsayımından önce birkaç karakteri önceden okumak gerçekten uygundur. Bu amaçla, bazı karakterleri okumamamıza izin verecek bir akış uyguladım.

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

Yer kazanmak için GitHub sayfamda bulabileceğiniz uygulama ayrıntılarını atlayacağım.

Gördüğünüz gibi, push_back_stream get_character işlevinden başlatıldı. Aşırı yüklenmiş operator() sonraki karakteri almak için kullanılır ve push_back , karakteri akışa geri döndürmek için kullanılır. line_number ve char_number , hata raporları için kullanılan kolaylık yöntemleridir.

char_index mevcut satırdaki karakterin dizini değil, genel olduğunu unutmayın; aksi takdirde, push_back işlevini doğru şekilde uygulamak için tüm geçmiş karakterleri bir kapta tutmamız gerekir.

Ayrılmış Jetonlar

Belirteç, en düşük seviyeli derleyici bileşenidir. Girdiyi ve “tükürme” belirteçlerini okuması gerekir. Bizi ilgilendiren dört tür jeton vardır:

• Ayrılmış jetonlar
• tanımlayıcılar
• sayılar
• Teller

Yorumlarla ilgilenmiyoruz, bu nedenle belirteç, kimseye haber vermeden onları "yiyecek".

Bu dilin çekiciliğini ve gezegensel popülerliğini sağlamak için iyi bilinen C-benzeri sözdizimini kullanacağız. C, C++, JavaScript, Java, C# ve Objective-C için oldukça iyi çalıştı, bu nedenle Stork için de çalışması gerekiyor. Bir tazeleme kursuna ihtiyacınız varsa, C/C++ öğrenme kaynaklarını kapsayan önceki makalelerimizden birine başvurabilirsiniz.

İşte ayrılmış belirteçler numaralandırması:

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

Ön eki “kw_” olan numaralandırma üyeleri anahtar kelimelerdir. Genellikle C++ anahtar sözcükleri ile aynı oldukları için bunları öneklemek zorunda kaldım. Ön eki olmayanlar operatörlerdir.

Hemen hemen hepsi C konvansiyonunu takip ediyor. Olmayanlar ise:
- birleştirme için kullanılacak olan concat ve concat_assign ( .. ve ..= )
- tamsayı bölme için kullanılacak idiv ve idiv_assign ( \ ve \= )
- değişken bildirimi için kw_var
- fonksiyon bildirimi için kw_fun
- sayı değişkenleri için kw_number
- dize değişkenleri için kw_string

Gerektiğinde ek anahtar kelimeler ekleyeceğiz.

Tanımlamaya değer yeni bir anahtar kelime var: kw_elif . Tek ifade bloklarının (kıvrımlı parantezler olmadan) buna değmeyeceğine kesin olarak inanıyorum. Onları kullanmıyorum (ve hiçbir şeyin eksik olduğunu hissetmiyorum), iki durum dışında:

1. Bloktan önce for , while veya if ifadesinden hemen sonra yanlışlıkla noktalı virgüle bastığımda. Şanslıysam, bir derleme zamanı hatası verir, ancak bazen, kukla bir if-ifadesi ve her zaman çalışan bir blok ile sonuçlanır. Neyse ki, yıllar içinde hatalarımdan ders çıkardım, bu yüzden çok nadiren oluyor. Sonunda Pavlov'un köpeği de öğrendi.
2. if-ifadelerini "zincirleme" yaptığımda, yani bir if-block'um, ardından bir veya daha fazla else-if-block'um ve isteğe bağlı olarak bir else bloğum olur. Teknik olarak, else if yazdığımda, bu sadece tek bir ifade içeren bir else bloğudur, bu if ifadesidir.

Bu nedenle, elif , parantezsiz ifadeleri tamamen ortadan kaldırmak için kullanılabilir. Buna izin verip vermememiz şimdilik bekleyebilecek bir karar.

Ayrılmış belirteçleri döndüren iki yardımcı işlev vardır:

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

get_keyword işlevi, geçirilen kelimeden isteğe bağlı bir anahtar kelime döndürür. Bu "kelime", bir harf veya alt çizgi ile başlayan bir harf, rakam ve alt çizgi dizisidir. Kelime bir anahtar kelimeyse, bir reserved_token döndürür. Aksi takdirde, belirteç, bunun bir tanımlayıcı olduğunu varsayacaktır.

get_operator işlevi, dizi geçerli bir operatör olduğu sürece mümkün olduğunca çok karakter okumaya çalışıyor. Daha fazlasını okursa, tanınan en uzun operatörden sonra okuduğu tüm ekstra karakterleri okumayacaktır.

Bu iki işlevin etkili bir şekilde uygulanması için string_view ve reserved_keyword arasında iki aramaya ihtiyacımız var.

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

get_keyword uygulaması tamamen basittir, ancak get_operator için, yalnızca n'inci karakteri hesaba katarak belirli bir karakteri aday operatörlerle karşılaştıracak özel bir karşılaştırıcıya ihtiyacımız var.

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

Bu, yalnızca idx konumundaki karakteri hesaba katan sıradan bir sözcüksel karşılaştırıcıdır, ancak dize daha kısaysa, onu diğer herhangi bir karakterden daha küçük olan idx konumunda boş bir karaktere sahipmiş gibi değerlendirir.

Bu, maximal_munch_operator sınıfını daha net hale getirmesi gereken get_operator uygulamasının uygulamasıdır:

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

Temel olarak, tüm operatörleri başlangıçta aday olarak ele alıyoruz. Ardından, karakter karakter okuruz ve yalnızca n'inci karakteri karşılaştırarak equal_range çağırarak mevcut adayları filtreleriz. Zaten karşılaştırıldıkları için önceki karakterleri karşılaştırmamıza gerek yok ve takip eden karakterleri hala alakasız oldukları için karşılaştırmak istemiyoruz.

Aralık boş olmadığında, aralıktaki ilk öğenin başka karaktere sahip olup olmadığını kontrol ederiz (böyle bir öğe varsa, arama sıralanırken her zaman aralığın başındadır). Bu durumda, eşleşen bir yasal operatörümüz var. Bu tür en uzun operatör, döndürdüğümüz operatördür. Ondan sonra sonunda okuduğumuz tüm karakterleri okuyacağız.

belirteç

Belirteçler heterojen olduğundan, belirteç, std::variant farklı belirteç türlerini saran bir kolaylık sınıfıdır, yani:

• ayrılmış jeton
• tanımlayıcı
• Numara
• Sicim
• Dosyanın sonu

 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 , yalnızca std::string türünün tek bir üyesine sahip bir sınıftır. Bence kolaylık sağlamak için var, çünkü tüm alternatifleri farklı türlerdeyse std::variant daha temiz.

Şimdi belirteci yazabiliriz. push_back_stream kabul edecek ve bir sonraki belirteci döndürecek bir işlev olacaktır.

İşin püf noktası, okuduğumuz ilk karakterin karakter türüne göre farklı kod dalları kullanmaktır.

• Dosya sonu karakterini okursak fonksiyondan döneriz.
• Bir boşluk okursak, onu atlarız.
• Bir alfasayısal karakter (harf, rakam veya alt çizgi) okursak, o türden ardışık tüm karakterleri okuruz (ilk karakter bir rakamsa noktaları da okuruz). Daha sonra ilk karakter bir rakam ise diziyi sayı olarak ayrıştırmaya çalışacağız. Aksi takdirde, anahtar kelime mi yoksa tanımlayıcı mı olduğunu kontrol etmek için get_keyword işlevini kullanırız.
• Bir tırnak işaretini okursak, onu kaçan karakterlerden kaçmayan bir dize olarak ele alırız.
• Bir eğik çizgi karakteri ( / ) okursak, bir sonraki karakterin eğik çizgi mi yoksa yıldız işareti mi ( * ) olup olmadığını kontrol edeceğiz ve bu durumda satır/blok yorumunu atlayacağız.
• Aksi takdirde get_operator fonksiyonunu kullanacağız.

İşte belirteç işlevi uygulaması. Çağırdığı işlevlerin uygulama ayrıntılarını atlayacağım.

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

Alt düzey bir işlev çağırmadan önce okuduğu karakterleri geri ittiğini görebilirsiniz. Performans cezası neredeyse yok ve alt düzey işlev kodu çok daha temiz.

istisnalar

İstisnalara karşı nutuklarından birinde kardeşim bir keresinde şöyle demişti:

“İki tür insan vardır: istisnalar atanlar ve onları yakalaması gerekenler. Ben her zaman o üzgün ikinci gruptayım.”

Bu ifadenin ruhuna katılıyorum. İstisnaları özellikle sevmiyorum ve onları atmak, herhangi bir kodun bakımını ve okunmasını çok daha zorlaştırabilir. Neredeyse her zaman.

Bu kurala bir istisna (kötü kelime oyunu) yapmaya karar verdim. Derlemenin derinliklerinden kurtulmak için derleyiciden bir istisna atmak gerçekten uygundur.

İşte istisna uygulaması:

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

Ancak, üst düzey koddaki tüm istisnaları yakalayacağıma söz veriyorum. Güzel baskı için line_number ve char_index üyelerini ve bunu yapan işlevi bile ekledim:

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

Toplama

Böylece serimizin ilk bölümü tamamlanmış oldu. Belki çok heyecan verici değildi, ancak artık temel ayrıştırma hatası işleme ile birlikte yararlı bir belirteçimiz var. Her ikisi de, gelecek makalelerde hakkında yazacağım daha ilginç şeyler için çok önemli yapı taşlarıdır.

Umarım bu gönderiden iyi fikirler edinmişsinizdir ve ayrıntıları keşfetmek istiyorsanız GitHub sayfama gidin.

Toptal Mühendislik Blogunda Daha Fazla Okuma:

• Sıfırdan Tercüman Yazmaya Nasıl Yaklaşılır?