توليد بيانات n من قواعد خالية من السياق

Question

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

Answer 1

الدفع منشور المدونة هذا. في الأساس ، تقوم بعشوائية RHS المختارة في كل تطبيق قاعدة.

Answer 2

هناك مقال قديم ولكنه لا يزال مثيرًا للاهتمام هنا يوضح هذا سبب حاجتك إلى بعض القيود الإضافية لتوليد فعال من الجمل العشوائية أكثر مما تفعل لتحليله - إنه يشير أيضًا إلى طريقة بسيطة لتوفير هذه القيود الإضافية وتعطي برنامج مثال كامل (... في Fortran IV ... ولكن ، مهلا ، هو هو أكثر من 40 سنة ...!-).

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

Answer 3

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

لكنني لا أرى الكثير من القيمة في اختبار التحليليين بهذه الطريقة ، على الأقل ليس إذا قبل مولد المحلل الخاص بك الوصف المجاني للسياق مباشرة. يحدث هذا عند استخدام مولد/أداة محلل خالٍ من السياق الكامل مثل GLR (وهو ما نستخدمه في نظام تحويل البرنامج ، DMS) أو محلل إيرلي.

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

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

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