القواعد الغامضة

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

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

أمثلة

لغة عادية

أبسط مثال هو القواعد الغامضة التالية للغة عادية، والتي تتكون من السلسلة الفارغة فقط:

A → A | ε

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

A → A

تحتوي هذه اللغة أيضًا على قواعد غير غامضة تتكون من قاعدة إنتاج واحدة:

A → ε

مما يعني أن الإنتاج الفريد يمكن أن ينتج السلسلة الفارغة فقط، والتي هي السلسلة الفريدة في اللغة.

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

سلسلة أحادية

اللغة العادية لسلسلة أحادية لرمز معين، نضع "a" (التعبير العادي *a ) ، تحتوي على قاعدة غير غامضة:

A → aA | ε

ولكن لديها أيضًا قاعدة غامضة:

A → aA | Aa | ε

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

الجمع والطرح

القاعدة الخالية السياق التالية:

A → A + A | A − A | A * A | id

غامضة، لوجود اشتقاقين من أقصى اليسار لسلسلة a + a + a.

ما يلي هو قواعد غير غامضة تولد نفس اللغة:

A → A + a | A − a | a

else المعلقة

ومن الأمثلة الشائعة على الغموض في لغات برمجة الكمبيوتر مشكلة else المعلقة. في العديد من اللغات، تكون else في عبارة (If – then (–else اختياريًا، مما ينتج عنه شروط متداخلة لها طرق متعددة للاعتراف بها من حيث قواعد اللغة الخالية من السياق.

في العديد من اللغات، قد يكتب المرء شرطاً في شكلين صالحين: نموذج if-then ، ونموذج if-then-else ، مما يجعل شرطًا else اختياريًا:

في قاعدة تحتوي القواعد التالية:

... | Statement → if Condition then Statement | if Condition then Statement else Statement 

بعض هياكل العبارات غامضة يمكن أن تظهر. كالتعبير التالي:

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. في هذه الحالة الأخيرة، فإن القواعد لا غموض فيها، لكن قواعد اللغة الخالية من السياق غامضة.

مثال للعداد

S → A + A A → 0 | 1

هذه القاعدة غير غامضة للغة { 0+0, 0+1, 1+0, 1+1 }. في حين أن كل واحدة من هذه السلاسل الأربع لها اشتقاق واحد فقط في أقصى اليسار، إلا أن لها مشتقين مختلفين، على سبيل المثال:

S ⇒ A + A ⇒ 0 + A ⇒ 0 + 0

و

S ⇒ A + A ⇒ A + 0 ⇒ 0 + 0 

فقط أول قاعدة هي التي من أقصى اليسار.

التعرف على القواعد الغامضة

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

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

على سبيل المثال، لغة palindromes المتساوية الطول مع أرقام 0 و 1 لديها قاعدة خالية من السياق غير غامضة

S -> 0S0 | 1S1 | ε

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

اللغات الغامضة بطبيعتها

تم إثبات وجود لغات غامضة بطبيعتها مع نظرية باريخ في عام 1961 من قبل روهيت باريخ في تقرير بحثي لمعهد ماساتشوستس للتكنولوجيا.

في حين أن بعض اللغات الخالية من السياق (مجموعة السلاسل التي يمكن أن تولدها قواعد اللغة) لها غموض و وضوح على حد سواء، توجد لغات خالية من السياق لا يمكن أن توجد فيها قواعد واضحة خالية من السياق.