ستورك: كيف تصنع لغة برمجة في C ++

الجزء 1: الرمز المميز

في هذه السلسلة ، سنطور لغة برمجة نصية جديدة ونصف هذه العملية خطوة بخطوة.

من المرجح أن يكون السؤال الأول الذي يتبادر إلى ذهن أي قارئ يتساءل بشكل عفوي هو: "هل نحتاج حقًا إلى لغة برمجة جديدة؟"

هل نحتاج حقًا إلى لغة برمجة جديدة؟

للإجابة على هذا السؤال ، سأسمح لنفسي باستطراد بسيط.

تخيل أنك مهندس معماري (مهندس معماري حقيقي ، وليس مهندس برمجيات) ، وأنت غير محظوظ بما يكفي لأنك ولدت في بلد بيروقراطي للغاية. لديك فكرة رائعة عن مركز تسوق في مسقط رأسك المتخلفة ، لذلك تقوم بإنشاء المشروع والتقدم بطلب للحصول على تصريح بناء. بالطبع ، يرفضونك على الفور على أساس أنه ليس لديك شركة مسجلة. لذلك ، تقوم بتسجيل شركة. للقيام بذلك ، تحتاج إلى إيداع بعض المال. بعد ذلك ، توصلت إلى اسم لشركتك ، والذي تم رفضه. في محاولتك الخامسة ، تم قبوله ، وينتقل طلبك إلى أسفل الكومة. في النهاية ، إما أن تستسلم أو تدرك أن شخصًا آخر قد بنى مركزًا للتسوق في هذه الأثناء.

لكننا لسنا معماريين حقيقيين. نحن مهندسون برمجيات ، ولدينا امتياز إحياء أفكارنا دون تصاريح أو بيروقراطية. الشيء الوحيد الذي نحتاجه هو وقت الفراغ والإرادة لإنفاقه على البرمجة بدلاً من ألغاز سودوكو.

إذا كنت لا تزال تصر على أن الدافع وراء البرمجة لا يمكن أن يكون مجرد فضول ، دعني أذكر فقط أن لغة البرمجة الأولى التي صممتها قد تم تطويرها نتيجة الضرورة ، وليس مجرد الفضول. ومع ذلك ، لا ينبغي أن يكون هذا هو الدافع الأول لقراءة هذه المدونة. أعتقد أن العديد من الأفكار التي ستواجهها هنا مثيرة للاهتمام ومبتكرة إلى حد ما لإبقائك مهتمًا حتى لو لم تكن بحاجة فعليًا إلى إنشاء لغة البرمجة الخاصة بك.

ألهمني هدفنا المتمثل في تطوير لغة برمجة نصية صغيرة الحجم لتسميتها "ستورك" ؛ ولحسن الحظ ، لسنا بحاجة إلى إقناع أي بيروقراطي بالموافقة على الاسم.

سأقوم بتطوير لغة البرمجة أثناء استعراضنا للسلسلة ، لذلك هناك احتمال أن أطور بعض الأخطاء أيضًا. يجب تسويتها مع اقتراب نهاية السلسلة.

شفرة المصدر الكاملة لكل ما هو موصوف هنا متاحة مجانًا على GitHub.

أخيرًا ، للإجابة على السؤال من عنوان هذه الفقرة - لا ، لسنا في الواقع بحاجة إلى لغة برمجة جديدة ، ولكن نظرًا لأننا نحاول توضيح كيفية إنشاء لغة برمجة في C ++ ، فسنقوم بإنشاء لغة لأغراض العرض التوضيحي .

مساعدو الرمز الصغير

لا أعرف ما إذا كان المبرمجون الآخرون يواجهون نفس المشكلة بشكل منتظم ، لكنني أواجه هذه المشكلة كثيرًا:

أحتاج إلى حاوية ذات قيمة رئيسية يجب أن تسترد القيم بسرعة ، في الوقت اللوغاريتمي. ومع ذلك ، بمجرد أن أقوم بتهيئة الحاوية ، لا أريد إضافة قيم جديدة إليها. لذلك ، فإن std::map<Key, Value> (أو std::unordered_map<Key, Value> ) مبالغة ، لأنها تتيح الإدراج السريع أيضًا.

أنا أعارض تمامًا التحسين غير الضروري ، لكن في هذه الحالة ، أشعر أن الكثير من الذاكرة تضيع على لا شيء. ليس هذا فقط ، ولكن لاحقًا ، سنحتاج إلى تنفيذ خوارزمية مضغ قصوى أعلى مثل هذه الحاوية ، map ليست هي الحاوية الأفضل لذلك.

الخيار الثاني هو std::vector<std::pair<Key,Value> > ، مرتبة بعد الإدخالات. المشكلة الوحيدة في هذا النهج هي قابلية قراءة الكود الأقل لأننا بحاجة إلى أن نضع في اعتبارنا أن المتجه مصنف ، لذلك قمت بتطوير فئة صغيرة تؤكد هذا القيد.

(يتم الإعلان عن جميع الوظائف والفئات وما إلى ذلك في مساحة اسم stork . سأحذف مساحة الاسم هذه لسهولة القراءة.)

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

كما ترى ، فإن تنفيذ هذا الفصل بسيط للغاية. لم أرغب في تنفيذ كل الطرق الممكنة ، فقط تلك التي سنحتاجها. الحاوية الأساسية عبارة عن vector ، لذا يمكن تهيئتها باستخدام vector مملوء مسبقًا ، أو باستخدام قائمة initializer_list .

سوف يقرأ الرمز المميز الأحرف من دفق الإدخال. في هذه المرحلة من المشروع ، يصعب علي تحديد تدفق الإدخال ، لذلك std::function بدلاً من ذلك.

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

سأستخدم اصطلاحات معروفة من وظائف دفق نمط C ، مثل getc ، والتي تُرجع int بدلاً من char بالإضافة إلى رقم سالب للإشارة إلى نهاية الملف.

ومع ذلك ، فمن الملائم حقًا قراءة حرفين مقدمًا ، قبل افتراض نوع الرمز المميز في الرمز المميز. تحقيقا لهذه الغاية ، قمت بتنفيذ دفق يسمح لنا بإلغاء قراءة بعض الأحرف.

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

لتوفير مساحة ، سأحذف تفاصيل التنفيذ ، والتي يمكنك العثور عليها في صفحة GitHub الخاصة بي.

كما ترى ، يتم تهيئة push_back_stream من وظيفة get_character . يتم استخدام operator() لاسترداد الحرف التالي ، ويتم استخدام push_back لإعادة الحرف مرة أخرى إلى التدفق. line_number و char_number هما طريقتان ملائمتان تستخدمان لتقارير الأخطاء.

ضع في اعتبارك أن char_index ليس فهرس الحرف في السطر الحالي ولكن بشكل عام ؛ وإلا ، فسيتعين علينا الاحتفاظ بجميع الأحرف السابقة في بعض الحاويات لتنفيذ وظيفة push_back بشكل صحيح.

الرموز المحجوزة

الرمز المميز هو مكون المترجم ذو المستوى الأدنى. يجب أن يقرأ الإدخال و "البصق" الرموز المميزة. هناك أربعة أنواع من الرموز التي تهمنا:

• الرموز المحجوزة
• معرفات
• أعداد
• سلاسل

لسنا مهتمين بالتعليقات ، لذا فإن رمز الرمز "يأكل" منهم فقط ، دون إخطار أي شخص.

لضمان جاذبية هذه اللغة وشعبية كوكب الأرض ، سنستخدم صيغة C-like معروفة. لقد عملت بشكل جيد مع C و C ++ و JavaScript و Java و C # و Objective-C ، لذلك يجب أن تعمل مع Stork أيضًا. إذا كنت بحاجة إلى دورة تنشيطية ، يمكنك الرجوع إلى إحدى مقالاتنا السابقة التي تغطي موارد تعلم C / C ++.

هنا تعداد الرموز المحجوزة:

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

أعضاء التعداد المسبوق بـ "kw_" هي كلمات رئيسية. اضطررت إلى إضافة بادئة إليها لأنها عادةً ما تكون مماثلة للكلمات الرئيسية في C ++. العوامل التي ليس لها بادئة هي عوامل.

جميعهم تقريبًا يتبعون اتفاقية C. أولئك الذين ليسوا هم:
- concat و concat_assign ( .. و ..= ) ، والتي ستُستخدم للتسلسل
- idiv و idiv_assign ( \ and \= ) ، وسيتم استخدامهما لقسمة عدد صحيح
- kw_var عن المتغير
- kw_fun لإعلان الوظيفة
- kw_number للمتغيرات العددية
- kw_string لمتغيرات السلسلة

سنضيف كلمات رئيسية إضافية ، حسب الحاجة.

هناك كلمة رئيسية جديدة تستحق الوصف: kw_elif . أنا من أشد المؤمنين بأن الكتل ذات البيان الواحد (بدون الأقواس المتعرجة) لا تستحق العناء. أنا لا أستخدمها (ولا أشعر أن هناك شيئًا مفقودًا) ، إلا في مناسبتين:

1. عندما أصبت بالخطأ بالفاصلة المنقوطة مباشرة بعد عبارة for أو while أو if قبل الكتلة. إذا كنت محظوظًا ، فسيتم إرجاع خطأ وقت التجميع ، ولكن في بعض الأحيان ينتج عنه عبارة if وهمية وكتلة يتم تنفيذها دائمًا. لحسن الحظ ، على مر السنين ، تعلمت من أخطائي ، لذلك نادرًا ما يحدث ذلك. تعلم كلب بافلوف أيضًا في النهاية.
2. عندما أكون قد "ربطت" عبارات if ، لذلك لدي كتلة if ، ثم واحد أو أكثر من block-if-block ، واختياريًا ، block-block. من الناحية الفنية ، عندما أكتب else if ، فهذه كتلة else تحتوي على عبارة واحدة فقط ، وهي عبارة if.

لذلك ، يمكن استخدام elif لإزالة العبارات غير المقواة تمامًا. سواء سمحنا به أم لا ، فهو قرار يمكن أن ينتظر الآن.

هناك وظيفتان مساعدتان تقومان بإرجاع الرموز المميزة المحجوزة:

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

ترجع الدالة get_keyword كلمة أساسية اختيارية من الكلمة التي تم تمريرها. هذه "الكلمة" عبارة عن سلسلة من الأحرف والأرقام والشرطات السفلية ، تبدأ بحرف أو شرطة سفلية. سيعود reserved_token إذا كانت الكلمة كلمة أساسية. خلاف ذلك ، سيفترض الرمز المميز أنه معرّف.

تحاول وظيفة get_operator قراءة أكبر عدد ممكن من الأحرف ، طالما أن التسلسل عامل صالح. إذا قرأت المزيد ، فلن تقرأ كل الأحرف الإضافية التي قرأتها بعد أطول عامل تم التعرف عليه.

من أجل التنفيذ الفعال لهاتين الوظيفتين ، نحتاج إلى عمليتي بحث بين string_view و 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} };

يعد تنفيذ get_keyword تمامًا ، ولكن بالنسبة لـ get_operator ، نحتاج إلى مقارنة مخصصة تقارن حرفًا معينًا مع عوامل التشغيل المرشحة ، مع مراعاة الحرف n فقط.

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

هذا مقارن معجمي عادي يأخذ في الاعتبار فقط الحرف الموجود في idx الموضع ، ولكن إذا كانت السلسلة أقصر ، فإنها تعاملها كما لو كانت تحتوي على حرف فارغ في idx الموضع ، وهو أقل من أي حرف آخر.

هذا هو تنفيذ get_operator ، والذي من شأنه أن يجعل فئة 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; }

في الأساس ، نتعامل مع جميع المشغلين كمرشحين في البداية. بعد ذلك ، نقرأ حرفًا حرفًا ونقوم بتصفية المرشحين الحاليين عن طريق استدعاء equal_range ، ومقارنة الحرف n فقط. لا نحتاج إلى مقارنة الأحرف السابقة كما تمت مقارنتها بالفعل ، ولا نريد مقارنة الأحرف التالية لأنها لا تزال غير ذات صلة.

عندما يكون النطاق غير فارغ ، نتحقق مما إذا كان العنصر الأول في النطاق لا يحتوي على المزيد من الأحرف (إذا كان هذا العنصر موجودًا ، فسيكون دائمًا في بداية النطاق حيث يتم فرز البحث). في هذه الحالة ، لدينا عامل قانوني مطابق. أطول عامل من هذا القبيل هو الذي نعود إليه. سنقوم بإلغاء قراءة جميع الأحرف التي قرأناها في النهاية بعد ذلك.

رمزية

نظرًا لأن الرموز المميزة غير متجانسة ، فإن الرمز المميز هو فئة ملائمة تلتف بـ std::variant أنواع الرموز المختلفة ، وهي:

• رمز محجوز
• المعرف
• رقم
• سلسلة
• نهاية الملف

 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 هو مجرد فئة بها عضو واحد من نوع std::string . إنه متاح للراحة لأنه ، في رأيي ، يكون std::variant أنظف إذا كانت جميع بدائلها أنواعًا مختلفة.

الآن ، يمكننا كتابة الرمز المميز. ستكون إحدى الوظائف التي تقبل push_back_stream وإرجاع الرمز المميز التالي.

الحيلة هي استخدام فروع كود مختلفة ، بناءً على نوع حرف الحرف الأول الذي نقرأه.

• إذا قرأنا حرف نهاية الملف ، فسنرجع من الوظيفة.
• إذا قرأنا مسافة بيضاء ، فسوف نتخطى ذلك.
• إذا قرأنا حرفًا أبجديًا رقميًا (حرف أو رقم أو شرطة سفلية) ، فسنقرأ جميع الأحرف المتتالية من هذا النوع (سنقرأ أيضًا النقاط إذا كان الحرف الأول رقمًا). بعد ذلك ، إذا كان الحرف الأول عبارة عن رقم ، فسنحاول تحليل التسلسل كرقم. خلافًا لذلك ، سنستخدم وظيفة get_keyword للتحقق مما إذا كانت كلمة رئيسية أو معرّفًا.
• إذا قرأنا علامة اقتباس ، فسنعاملها كسلسلة ، ولا تتخطى الأحرف الهاربة منها.
• إذا قرأنا حرف الشرطة المائلة ( / ) ، فسوف نتحقق مما إذا كان الحرف التالي هو شرطة مائلة أم علامة نجمية ( * ) ، وسنتخطى تعليق السطر / الكتلة في هذه الحالة.
• خلاف ذلك ، سوف نستخدم وظيفة get_operator .

هنا هو تنفيذ وظيفة الرمز المميز. سأحذف تفاصيل تنفيذ الوظائف التي تستدعيها.

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

يمكنك أن ترى أنه يدفع الأحرف التي تقرأها للخلف قبل أن تستدعي وظيفة ذات مستوى أدنى. عقوبة الأداء غير موجودة تقريبًا ، ورمز وظيفة المستوى الأدنى أكثر نظافة.

استثناءات

قال أخي ذات مرة في أحد صيحاته الصاخبة ضد الاستثناءات:

هناك نوعان من الناس: أولئك الذين يرمون استثناءات وأولئك الذين يتعين عليهم القبض عليهم. أنا دائما في تلك المجموعة الثانية الحزينة ".

أنا أتفق مع روح هذا البيان. لا أحب الاستثناءات بشكل خاص ، ورميها يمكن أن يجعل صيانة أي كود أكثر صعوبة وقراءته. تقريبا دائما.

قررت إجراء استثناء (قصد من التورية السيئة) لهذه القاعدة. من المريح حقًا طرح استثناء من المترجم للاسترخاء من أعماق الترجمة.

هنا هو تنفيذ الاستثناء:

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

ومع ذلك ، أعدك بالتقاط جميع الاستثناءات في كود المستوى الأعلى. حتى أنني أضفت أعضاء line_number و char_index للطباعة الجميلة ، والوظيفة التي تقوم بذلك:

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

تغليف

بهذا يختتم الجزء الأول من سلسلتنا. ربما لم يكن الأمر مثيرًا للغاية ، ولكن لدينا الآن رمز مميز مفيد ، إلى جانب معالجة أخطاء التحليل الأساسية. كلاهما لبنات بناء أساسية للأشياء الأكثر إثارة التي سأكتب عنها في المقالات القادمة.

آمل أن تكون قد حصلت على بعض الأفكار الجيدة من هذا المنشور ، وإذا كنت ترغب في استكشاف التفاصيل ، فانتقل إلى صفحة GitHub الخاصة بي.

مزيد من القراءة على مدونة Toptal Engineering:

• كيفية الاقتراب من كتابة المترجم الفوري من الصفر