أصبحت الآلات الافتراضية للغات البرمجة واسعة الانتشار في العقود الأخيرة. لقد مر الكثير من الوقت منذ تقديم Java Virtual Machine في النصف الثاني من التسعينات ، ومن الآمن أن نقول أن مفسري كود البايت ليسوا المستقبل ، ولكن الحاضر.

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

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

الجزء الأول ، تمهيدي (حالي)
الجزء الثاني ، التحسين
الجزء الثالث التطبيقي

الخلفية

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

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

يعرض الأول منهم خمسة آلات (آلات) افتراضية صغيرة صغيرة (تصل إلى مئات خطوط C) ، يكشف كل منها عن جانب معين من تطوير مثل هؤلاء المترجمين.

أين ذهبت رموز البايت في لغات البرمجة؟

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

ترجع شعبية مجموعات التعليمات الافتراضية كتمثيل وسيط للكود إلى ثلاثة أسباب:

1. يتم نقل برامج Bytecode بسهولة إلى منصات جديدة.
2. يعد مفسرو Bytecode أسرع من المترجمين الشفويين لشجرة بنية التعليمات البرمجية.
3. يمكنك تطوير آلة افتراضية بسيطة في بضع ساعات فقط.

دعونا نصنع بعض الأجهزة الافتراضية البسيطة C ونستخدم هذه الأمثلة لإبراز الجوانب التقنية الرئيسية لتطبيق الأجهزة الافتراضية.

تتوفر رموز عينة كاملة على GitHub . يمكن تجميع الأمثلة مع دول مجلس التعاون الخليجي الجديدة نسبيًا:

gcc interpreter-basic-switch.c -o interpreter ./interpreter 

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

أسهل مترجم الشفرة في العالم

كما قلت ، من السهل جدًا عمل مترجم فوري. التعليقات مباشرة خلف القائمة ، لكن لنبدأ مباشرة بالرمز:

 struct { uint8_t *ip; uint64_t accumulator; } vm; typedef enum { /* increment the register */ OP_INC, /* decrement the register */ OP_DEC, /* stop execution */ OP_DONE } opcode; typedef enum interpret_result { SUCCESS, ERROR_UNKNOWN_OPCODE, } interpret_result; void vm_reset(void) { puts("Reset vm state"); vm = (typeof(vm)) { NULL }; } interpret_result vm_interpret(uint8_t *bytecode) { vm_reset(); puts("Start interpreting"); vm.ip = bytecode; for (;;) { uint8_t instruction = *vm.ip++; switch (instruction) { case OP_INC: { vm.accumulator++; break; } case OP_DEC: { vm.accumulator--; break; } case OP_DONE: { return SUCCESS; } default: return ERROR_UNKNOWN_OPCODE; } } return SUCCESS; } 

يوجد أقل من مائة سطر ، ولكن يتم تمثيل جميع السمات المميزة للجهاز الظاهري. يحتوي الجهاز على سجل واحد ( vm.accumulator ) ، وثلاث عمليات (زيادة التسجيل ، vm.accumulator التسجيل وإكمال تنفيذ البرنامج) ومؤشر للتعليمات الحالية ( vm.ip ).

يتم ترميز كل عملية (eng. code code أو opcode ) ببايت واحد ، ويتم تنفيذ الجدولة باستخدام switch المعتاد في وظيفة vm_interpret . تحتوي الفروع في switch على منطق العمليات ، أي أنها تغير حالة السجل أو تكمل تنفيذ البرنامج.

يتم نقل العمليات إلى وظيفة vm_interpret في شكل صفيف من وحدات البايت - رمز بايت (Eng Bytecode ) - ويتم تنفيذها بالتسلسل حتى تتم مواجهة عملية OP_DONE الجهاز الظاهري ( OP_DONE ) OP_DONE .

أحد الجوانب الرئيسية للجهاز الظاهري هو دلالات ، أي مجموعة العمليات الممكنة عليه. في هذه الحالة ، هناك عمليتان فقط ، وتغيران قيمة السجل الواحد.

يقترح بعض الباحثين ( تقنيات التجريد والتحسين للجهاز الظاهري ، 2009) تقسيم الأجهزة الافتراضية إلى أجهزة عالية المستوى ومنخفضة المستوى وفقًا لقرب دلالات الجهاز الظاهري من دلالات الجهاز المادي الذي سيتم تنفيذ الرمز الثانوي عليه.

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

والعكس صحيح: إن عمليات الأجهزة الظاهرية عالية المستوى تعكس عن كثب دلالات لغة البرمجة المتخصصة التي تم تجميعها في كود ثانوي. لذا اعمل ، على سبيل المثال ، SQLite و Gawk والعديد من الإصدارات من Prolog.

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

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

وسيطات تعليمات Bytecode

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

سنقوم بتوسيع المثال عن طريق تقديم تعليمات (OP_ADDI ، OP_SUBI) تأخذ حجة في شكل بايت بعد كود التشغيل مباشرة:

 struct { uint8_t *ip; uint64_t accumulator; } vm; typedef enum { /* increment the register */ OP_INC, /* decrement the register */ OP_DEC, /* add the immediate argument to the register */ OP_ADDI, /* subtract the immediate argument from the register */ OP_SUBI, /* stop execution */ OP_DONE } opcode; typedef enum interpret_result { SUCCESS, ERROR_UNKNOWN_OPCODE, } interpret_result; void vm_reset(void) { puts("Reset vm state"); vm = (typeof(vm)) { NULL }; } interpret_result vm_interpret(uint8_t *bytecode) { vm_reset(); puts("Start interpreting"); vm.ip = bytecode; for (;;) { uint8_t instruction = *vm.ip++; switch (instruction) { case OP_INC: { vm.accumulator++; break; } case OP_DEC: { vm.accumulator--; break; } case OP_ADDI: { /* get the argument */ uint8_t arg = *vm.ip++; vm.accumulator += arg; break; } case OP_SUBI: { /* get the argument */ uint8_t arg = *vm.ip++; vm.accumulator -= arg; break; } case OP_DONE: { return SUCCESS; } default: return ERROR_UNKNOWN_OPCODE; } } return SUCCESS; } 

تعليمات جديدة (انظر وظيفة vm_interpret ) قراءة حجة من رمز البايت وإضافتها إلى التسجيل / طرحها من التسجيل.

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

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

آلة المكدس

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

ببساطة ، ليس لدينا طريقة لتقييم التعبيرات المعقدة. لحل هذه المشكلة ، هناك حاجة إلى آلة مكدسة ، أي آلة افتراضية مع مكدس متكامل:

 #define STACK_MAX 256 struct { uint8_t *ip; /* Fixed-size stack */ uint64_t stack[STACK_MAX]; uint64_t *stack_top; /* A single register containing the result */ uint64_t result; } vm; typedef enum { /* push the immediate argument onto the stack */ OP_PUSHI, /* pop 2 values from the stack, add and push the result onto the stack */ OP_ADD, /* pop 2 values from the stack, subtract and push the result onto the stack */ OP_SUB, /* pop 2 values from the stack, divide and push the result onto the stack */ OP_DIV, /* pop 2 values from the stack, multiply and push the result onto the stack */ OP_MUL, /* pop the top of the stack and set it as execution result */ OP_POP_RES, /* stop execution */ OP_DONE, } opcode; typedef enum interpret_result { SUCCESS, ERROR_DIVISION_BY_ZERO, ERROR_UNKNOWN_OPCODE, } interpret_result; void vm_reset(void) { puts("Reset vm state"); vm = (typeof(vm)) { NULL }; vm.stack_top = vm.stack; } void vm_stack_push(uint64_t value) { *vm.stack_top = value; vm.stack_top++; } uint64_t vm_stack_pop(void) { vm.stack_top--; return *vm.stack_top; } interpret_result vm_interpret(uint8_t *bytecode) { vm_reset(); puts("Start interpreting"); vm.ip = bytecode; for (;;) { uint8_t instruction = *vm.ip++; switch (instruction) { case OP_PUSHI: { /* get the argument, push it onto stack */ uint8_t arg = *vm.ip++; vm_stack_push(arg); break; } case OP_ADD: { /* Pop 2 values, add 'em, push the result back to the stack */ uint64_t arg_right = vm_stack_pop(); uint64_t arg_left = vm_stack_pop(); uint64_t res = arg_left + arg_right; vm_stack_push(res); break; } case OP_SUB: { /* Pop 2 values, subtract 'em, push the result back to the stack */ uint64_t arg_right = vm_stack_pop(); uint64_t arg_left = vm_stack_pop(); uint64_t res = arg_left - arg_right; vm_stack_push(res); break; } case OP_DIV: { /* Pop 2 values, divide 'em, push the result back to the stack */ uint64_t arg_right = vm_stack_pop(); /* Don't forget to handle the div by zero error */ if (arg_right == 0) return ERROR_DIVISION_BY_ZERO; uint64_t arg_left = vm_stack_pop(); uint64_t res = arg_left / arg_right; vm_stack_push(res); break; } case OP_MUL: { /* Pop 2 values, multiply 'em, push the result back to the stack */ uint64_t arg_right = vm_stack_pop(); uint64_t arg_left = vm_stack_pop(); uint64_t res = arg_left * arg_right; vm_stack_push(res); break; } case OP_POP_RES: { /* Pop the top of the stack, set it as a result value */ uint64_t res = vm_stack_pop(); vm.result = res; break; } case OP_DONE: { return SUCCESS; } default: return ERROR_UNKNOWN_OPCODE; } } return SUCCESS; } 

في هذا المثال ، هناك بالفعل المزيد من العمليات ، وكلها تقريبًا تعمل فقط مع المكدس. يدفع OP_PUSHI حجته الفورية إلى المكدس. يتم إبراز التعليمات OP_ADD و OP_SUB و OP_DIV و OP_MUL من مجموعة من القيم وحساب النتيجة ودفعها مرة أخرى إلى المكدس. OP_POP_RES يزيل القيمة من المكدس ويضعها في سجل النتائج ، مخصص لنتائج الجهاز الظاهري.

بالنسبة لعملية القسمة (OP_DIV) ، يتم اكتشاف خطأ القسمة على صفر ، والذي يوقف الجهاز الظاهري.

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

آلة تسجيل

نظرًا لبساطتها ، يتم استخدام الأجهزة الافتراضية المكدسة على نطاق واسع بين مطوري لغات البرمجة ؛ نفس JVMs و Python VMs يستخدمونها بالضبط.

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

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

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

 #define REGISTER_NUM 16 struct { uint16_t *ip; /* Register array */ uint64_t reg[REGISTER_NUM]; /* A single register containing the result */ uint64_t result; } vm; typedef enum { /* Load an immediate value into r0 */ OP_LOADI, /* Add values in r0,r1 registers and put them into r2 */ OP_ADD, /* Subtract values in r0,r1 registers and put them into r2 */ OP_SUB, /* Divide values in r0,r1 registers and put them into r2 */ OP_DIV, /* Multiply values in r0,r1 registers and put them into r2 */ OP_MUL, /* Move a value from r0 register into the result register */ OP_MOV_RES, /* stop execution */ OP_DONE, } opcode; typedef enum interpret_result { SUCCESS, ERROR_DIVISION_BY_ZERO, ERROR_UNKNOWN_OPCODE, } interpret_result; void vm_reset(void) { puts("Reset vm state"); vm = (typeof(vm)) { NULL }; } void decode(uint16_t instruction, uint8_t *op, uint8_t *reg0, uint8_t *reg1, uint8_t *reg2, uint8_t *imm) { *op = (instruction & 0xF000) >> 12; *reg0 = (instruction & 0x0F00) >> 8; *reg1 = (instruction & 0x00F0) >> 4; *reg2 = (instruction & 0x000F); *imm = (instruction & 0x00FF); } interpret_result vm_interpret(uint16_t *bytecode) { vm_reset(); puts("Start interpreting"); vm.ip = bytecode; uint8_t op, r0, r1, r2, immediate; for (;;) { /* fetch the instruction */ uint16_t instruction = *vm.ip++; /* decode it */ decode(instruction, &op, &r0, &r1, &r2, &immediate); /* dispatch */ switch (op) { case OP_LOADI: { vm.reg[r0] = immediate; break; } case OP_ADD: { vm.reg[r2] = vm.reg[r0] + vm.reg[r1]; break; } case OP_SUB: { vm.reg[r2] = vm.reg[r0] - vm.reg[r1]; break; } case OP_DIV: { /* Don't forget to handle the div by zero error */ if (vm.reg[r1] == 0) return ERROR_DIVISION_BY_ZERO; vm.reg[r2] = vm.reg[r0] / vm.reg[r1]; break; } case OP_MUL: { vm.reg[r2] = vm.reg[r0] * vm.reg[r1]; break; } case OP_MOV_RES: { vm.result = vm.reg[r0]; break; } case OP_DONE: { return SUCCESS; } default: return ERROR_UNKNOWN_OPCODE; } } return SUCCESS; } 

يوضح المثال آلة تسجيل مع 16 تسجيل. تشغل التعليمات 16 بتة لكل منها ويتم تشفيرها بثلاث طرق:

1. 4 بت لكل كود تشغيل + 4 بت لكل اسم تسجيل + 8 بت لكل وسيطة.
2. 4 بت لكل كود تشغيل + ثلاث مرات 4 بت لكل اسم تسجيل.
3. 4 بت لكل كود تشغيل + 4 بت لكل اسم تسجيل مفرد + 8 بت غير مستخدم.

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

هناك حاجة إلى النوع الأول من الترميز (4 + 4 + 8) لتحميل البيانات في السجلات باستخدام عملية OP_LOADI. يتم استخدام النوع الثاني (4 + 4 + 4 + 4) للعمليات الحسابية ، والتي يجب أن تعرف أين تأخذ زوجًا من الحجج وأين تضاف نتيجة الحساب. وأخيرًا ، يتم استخدام النموذج الأخير (4 + 4 + 8 بت غير ضروري) للحصول على تعليمات مع سجل واحد كحجة ، في حالتنا هو OP_MOV_RES.

لتشفير التعليمات وفك تشفيرها ، نحتاج الآن إلى منطق خاص (وظيفة decode ). من ناحية أخرى ، يصبح منطق التعليمات ، بفضل الإشارة الصريحة إلى موقع الحجج ، أسهل - تختفي العمليات مع المكدس.

الملامح الرئيسية: في الرمز الفرعي لآلات التسجيل ، هناك عدد أقل من التعليمات ، التعليمات الفردية أوسع ، والتجميع في مثل هذا الرمز الفرعي أكثر صعوبة - يجب على المترجم أن يقرر كيفية استخدام السجلات المتاحة.

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

مكدس وتسجيل الآلات والمقارنة

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

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

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

الجدل حول أي هندسة أفضل لم ينته بعد. إذا كنا نتحدث عن جامعي جافا ، فإن Dalvik VM bytecode ، الذي كان يعمل حتى وقت قريب على كل جهاز Android ، تم تسجيله ؛ لكن العنوان احتفظت JVM بمجموعة من التعليمات. تستخدم آلة Lua الظاهرية آلة تسجيل ، لكن Python VM لا تزال قابلة للتكديس. وهكذا دواليك.

Bytecode في مترجمين التعبير العادي

أخيرًا ، لإلهاء أنفسنا عن الأجهزة الافتراضية منخفضة المستوى ، دعنا نلقي نظرة على مترجم متخصص يتحقق من السلاسل لمطابقة التعبير العادي:

 typedef enum { /* match a single char to an immediate argument from the string and advance ip and cp, or * abort*/ OP_CHAR, /* jump to and match either left expression or the right one, abort if nothing matches*/ OP_OR, /* do an absolute jump to an offset in the immediate argument */ OP_JUMP, /* stop execution and report a successful match */ OP_MATCH, } opcode; typedef enum match_result { MATCH_OK, MATCH_FAIL, MATCH_ERROR, } match_result; match_result vm_match_recur(uint8_t *bytecode, uint8_t *ip, char *sp) { for (;;) { uint8_t instruction = *ip++; switch (instruction) { case OP_CHAR:{ char cur_c = *sp; char arg_c = (char)*ip ; /* no match? FAILed to match */ if (arg_c != cur_c) return MATCH_FAIL; /* advance both current instruction and character pointers */ ip++; sp++; continue; } case OP_JUMP:{ /* read the offset and jump to the instruction */ uint8_t offset = *ip; ip = bytecode + offset; continue; } case OP_OR:{ /* get both branch offsets */ uint8_t left_offset = *ip++; uint8_t right_offset = *ip; /* check if following the first offset get a match */ uint8_t *left_ip = bytecode + left_offset; if (vm_match_recur(bytecode, left_ip, sp) == MATCH_OK) return MATCH_OK; /* no match? Check the second branch */ ip = bytecode + right_offset; continue; } case OP_MATCH:{ /* success */ return MATCH_OK; } } return MATCH_ERROR; } } match_result vm_match(uint8_t *bytecode, char *str) { printf("Start matching a string: %s\n", str); return vm_match_recur(bytecode, bytecode, str); } 

التعليمات الرئيسية هي OP_CHAR. تأخذ حجتها الفورية وتقارنها بالحرف الحالي في السلسلة ( char *sp ). في حالة مصادفة الأحرف المتوقعة والحالية في السطر ، يحدث الانتقال إلى التعليمات التالية والحرف التالي.

تفهم الآلة أيضًا عملية القفز (OP_JUMP) ، التي تأخذ وسيطة فورية واحدة. الوسيطة تعني الإزاحة المطلقة في الرمز الثانوي ، من أين تستمر الحساب.

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

والمثير للدهشة أن أربعة شفرات opcodes وسبعين سطرًا من الكود تكفي للتعبير عن التعبيرات العادية مثل "abc" و "a؟ Bc" و "(ab | bc) d" و "a * bc". لا يحتوي هذا الجهاز الظاهري حتى على حالة صريحة ، نظرًا لأن كل ما تحتاجه - يشير إلى بداية دفق التعليمات والإرشادات الحالية والشخصية الحالية - يتم تمريره كحجج للدالة العودية.

إذا كنت مهتمًا بتفاصيل عمل محركات التعبير العادي ، فيمكنك أولاً قراءة سلسلة من المقالات التي كتبها روس كوكس ، مؤلف محرك التعبير العادي من Google RE2 .

الملخص

دعونا نلخص.

بالنسبة إلى لغات البرمجة للأغراض العامة ، كقاعدة عامة ، يتم استخدام بنيتين: المكدس والتسجيل.

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

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

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

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

توصيات عملية:

1. إذا كنت بحاجة إلى تنفيذ أي رمز ثانوي والقيام بذلك في فترة زمنية معقولة ، فحاول العمل باستخدام الإرشادات الأقرب إلى مهمتك ؛ كلما ارتفع المستوى الدلالي ، كان ذلك أفضل. سيؤدي ذلك إلى تقليل تكاليف الجدولة وتبسيط إنشاء التعليمات البرمجية.
2. إذا كنت بحاجة إلى مزيد من المرونة والمعاني غير المتجانسة ، فيجب عليك على الأقل محاولة إبراز القاسم المشترك في الرمز الثانوي بحيث تكون التعليمات الناتجة على مستوى متوسط ​​مشروط.
3. إذا كان من الضروري في المستقبل حساب أي تعبيرات ، وإنشاء آلة مكدسة ، فإن ذلك سيقلل من الصداع عند تجميع كود البايت.
4. إذا لم تكن التعبيرات متوقعة ، فقم بإنشاء آلة تسجيل بسيطة ، والتي ستتجنب تكلفة المكدس وتبسط التعليمات نفسها.

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