القواعد الغامضة
المحتويات
قبل الخوض في التفاصيل، في علم الكمبيوتر ، القواعد الغامضة عبارة عن قواعد خالية من السياق ، والتي توجد بها سلسلة (مجموعة من الكلمات) يمكن أن تحتوي على أكثر من إشتقاق من أقصى اليسار أو شجرة تحليل، في حين أن القواعد التي لا لبس فيها عبارة عن غرامر خالية من السياق يكون لكل سلسلة صحيحة اشتقاق فريد من أقصى اليسار أو شجرة تحليل فريدة. الكثير من اللغات تعترف بكل من القواعد النحوية الغامضة و الخالية من الغموض، في حين أن بعض اللغات تعترف فقط بالقواعد النحوية الغامضة. أي لغة غير فارغة تعترف بقواعد غامضة من خلال أخذ قواعد خالية من الغموض وإدخال قاعدة مكررة أو مرادف (اللغة الوحيدة بدون قواعد غامضة هي اللغة الفارغة). تسمى اللغة التي تعترف فقط بالقواعد الغامضة لغة غامضة بطبيعتها ، وهناك لغات عديدة خالية من السياق غامضة بطبيعتها. دائمًا ما تكون القواعد الحتمية الخالية من السياق غامضة، وهي فئة فرعية مهمة من القواعد الغامضة، على أية حال، هناك قواعد غير حتمية غير غامضة. ونتناول فيما يلي مزيدًا من التفاصيل.
وفي هذا الصدد، بالنسبة للغات برمجة الكمبيوتر ، غالبًا ما تكون القواعد المرجعية غامضة، نظرًا لوجود مشكلات مثل مشكلة else المعلقة. إذا وجدت، يتم حل هذه الغموض بشكل عام عن طريق إضافة قواعد الأسبقية أو قواعد تحليل أخرى حساسة للسياق ، لذا فإن عبارة القواعد بشكل عام لا غموض فيها. تسمى مجموعة أشجار التحليل اللغوية لجملة غامضة غابة التحليل.
أمثلة
لغة عادية
وفي هذا الصدد، أبسط مثال هو القواعد الغامضة التالية للغة عادية، والتي تتكون من السلسلة الفارغة فقط:
اللغات الغامضة بطبيعتها
ومن ناحية أخرى، في حين أن بعض اللغات الخالية من السياق (مجموعة السلاسل التي يمكن أن تولدها قواعد اللغة) لها غموض و وضوح على حد سواء، توجد لغات خالية من السياق لا يمكن أن توجد فيها قواعد واضحة خالية من السياق.
ومن ناحية أخرى، تم إثبات وجود لغات غامضة بطبيعتها مع نظرية باريخ في سنة 1961 من قبل روهيت باريخ في تقرير بحثي لمعهد ماساتشوستس للتكنولوجيا.
سلسلة أحادية
وفي السياق ذاته، اللغة العادية لسلسلة أحادية لرمز معين، نضع "a" (التعبير العادي *a ) ، تحتوي على قاعدة غير غامضة:
A → A – ε
إضافةً إلى ذلك، مما يعني أن الإنتاج يمكن أن يكون إما نفسه مرة أخرى، أو سلسلة فارغة. وبالتالي، تحتوي السلسلة الفارغة على مشتقات أقصى اليسار طول 1 ، 2 ، 3 ، أو بأي طول، اعتمادًا على عدد المرات التي يتم فيها استخدام القاعدة
A → A
إضافةً إلى ذلك، تحتوي هذه اللغة كذلك على قواعد غير غامضة تتكون من قاعدة إنتاج واحدة:
A → aA – Aa – ε
علاوةً على ذلك، وهذه تتوافق مع إنتاج شجرة ترابطية لليمين (لقواعد غير غامضة) أو السماح لكل من الارتباط لليسار ولليمين. وهذا مفصل بالأسفل.
S -> 0S0 | 1S1 | ε
من جانب آخر، لا يمكن تحليل سلسلة عشوائية من هذه اللغة بدون قراءة جميع أحرفها أولاً، مما يعني أن أوتوميتا الدفع السفلي يجب عليه محاولة انتقالات لحالات بديلة لإستيعاب الأطوال الممكنة المختلفة لسلسلة شبه معلومة. ومع ذلك، قد يؤدي إزالة الغموض في القواعد إلى إصدار قواعد نحوية خالية من الحتمية وبالتالي السماح بتحليل أكثر كفاءة. تتضمن مولدات المحول البرمجي مثل (ياك) ميزات لحل بعض أنواع الغموض، مثل استخدام الأسبقية وقيود الترابط.
A → aA – ε
ولكن لديها كذلك قاعدة غامضة:
A → ε
كذلك، مما يعني أن الإنتاج الفريد يمكن أن ينتج السلسلة الفارغة فقط، والتي هي السلسلة الفريدة في اللغة.
وفي هذا الصدد، بنفس الطريقة، يمكن جعل أي قواعد لغوية غير فارغة غامضة عن طريق إضافة تكرار.
و
S ⇒ A + A ⇒ A + 0 ⇒ 0 + 0
فقط أول قاعدة هي التي من أقصى اليسار.
الجمع والطرح
- القاعدة الخالية السياق التالية:
- A → A + A – A − A – A * A – id
- غامضة، لوجود اشتقاقين من أقصى اليسار لسلسلة a + a + a.
- ما يلي هو قواعد غير غامضة تولد نفس اللغة:
- A → A + a – A − a – a
else المعلقة
- بعض هياكل العبارات غامضة يمكن أن تظهر. كالتعبير التالي:
- if a then if b then s else s2
- يمكن أن يتم تحليلها، كـ:
- if a then begin if b then s end else s2
- أو كـ:
- if a then begin if b then s else s2 end
- اعتماداً على ما إذا كانت else ترتبط مع أول if أو ثاني if.
علاوةً على ذلك، يتم حلها بطرق مختلفة وبلغات مختلفة. في بعض الأحيان يتم تعديل القواعد بحيث تكون غير غامضة، مثل أن تكون endif مطلوبة أو جعل else إلزامية. في حالات أخرى، يتم ترك قواعد اللغة غامضة، ولكن يتم حل الغموض عن طريق جعل العبارة العامة لحالة القواعد ككل حساسة للسياق، مثل ربط else بأقرب if. في هذه الحالة الأخيرة، فإن القواعد لا غموض فيها، لكن قواعد اللغة الخالية من السياق غامضة.
في هذا الإطار، ومن الأمثلة الشائعة على الغموض في لغات برمجة الكمبيوتر مشكلة else المعلقة. في الكثير من اللغات، تكون else في عبارة (If – then (–else اختياريًا، مما ينتج عنه شروط متداخلة لها طرق متعددة للاعتراف بها من حيث قواعد اللغة الخالية من السياق.
في هذا الإطار، في الكثير من اللغات، قد يكتب المرء شرطاً في شكلين صالحين: نموذج if-then ، ونموذج if-then-else ، مما يجعل شرطًا else اختياريًا:
في قاعدة تحتوي القواعد التالية:
إضافةً إلى ذلك، ... – Statement → if Condition then Statement – if Condition then Statement else Statement
التعرف على القواعد الغامضة
وفي هذا الصدد، إن مشكلة قرار ما إذا كانت القواعد غامضة هي معضلة غير قابلة للقرار، لأنه يمكن إظهار أنها مكافئة لمشكلة ما بعد التطابق. على الأقل، هناك أدوات تنفيذ بعض إجراءات شبيهة بالقرار للكشف عن غموض القواعد الخالية من السياق.
وفي هذا الصدد، يتم تحديد كفاءة تحليل قواعد اللغة الخالية من السياق من قبل الأوتوميتا التي تقبل ذلك. القواعد الحتمية الخالية من السياق يتم قبولها بواسطة الأوتوميتا ذات الدفع القطعي ويمكن تحليلها في وقت خطي، مثلًا بواسطة محلل يسار يمين. هذه مجموعة فرعية من القواعد الخالية من السياق والتي يتم قبولها بواسطة أوتوميتا الدفع السفلي ويمكن تحليلها في زمن كثير الحدود، مثلًا بواسطة خوارزمية CYK. لا يمكن للقواعد الخالية من الغموض أن تكون غير حتمية.
علاوةً على ذلك، مثلًا، لغة palindromes المتساوية الطول مع أرقام 0 و 1 لديها قاعدة خالية من السياق غير غامضة
مثال للعداد
S ⇒ A + A ⇒ 0 + A ⇒ 0 + 0
S → A + A A → 0 – 1
من جهة ثانية، هذه القاعدة غير غامضة للغة { 0+0, 0+1, 1+0, 1+1 }. في حين أن كل واحدة من هذه السلاسل الأربع لها اشتقاق واحد فقط في أقصى اليسار، إلا أن لها مشتقين مختلفين، مثلًا:
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟