books learn about ambiguous rules
If you do not find what you're looking for, you can use more accurate words.
التعرف على القواعد الغامضة (Info)
إن مشكلة قرار ما إذا كانت القواعد غامضة هي معضلة غير قابلة للقرار، لأنه يمكن إظهار أنها مكافئة لمشكلة ما بعد التطابق. على الأقل، هناك أدوات تنفيذ بعض إجراءات شبيهة بالقرار للكشف عن غموض القواعد الخالية من السياق.
يتم تحديد كفاءة تحليل قواعد اللغة الخالية من السياق من قبل الأوتوميتا التي تقبل ذلك. القواعد الحتمية الخالية من السياق يتم قبولها بواسطة الأوتوميتا ذات الدفع القطعي ويمكن تحليلها في وقت خطي، على سبيل المثال بواسطة محلل يسار يمين. هذه مجموعة فرعية من القواعد الخالية من السياق والتي يتم قبولها بواسطة أوتوميتا الدفع السفلي ويمكن تحليلها في زمن كثير الحدود، على سبيل المثال بواسطة خوارزمية CYK. لا يمكن للقواعد الخالية من الغموض أن تكون غير حتمية.
على سبيل المثال، لغة palindromes المتساوية الطول مع أرقام 0 و 1 لديها قاعدة خالية من السياق غير غامضة
S -> 0S0 | 1S1 | ε
لا يمكن تحليل سلسلة عشوائية من هذه اللغة بدون قراءة جميع أحرفها أولاً، مما يعني أن أوتوميتا الدفع السفلي يجب عليه محاولة انتقالات لحالات بديلة لإستيعاب الأطوال الممكنة المختلفة لسلسلة شبه معلومة. ومع ذلك، قد يؤدي إزالة الغموض في القواعد إلى إصدار قواعد نحوية خالية من الحتمية وبالتالي السماح بتحليل أكثر كفاءة. تتضمن مولدات المحول البرمجي مثل (ياك) ميزات لحل بعض أنواع الغموض، مثل استخدام الأسبقية وقيود الترابط.
