قواعد نحوية غامضة

📅 آخر تحديث: ٢٤ يوليو ٢٠٢٦
✍️ نُشر في: ٢٤ يوليو ٢٠٢٦
📷 يحتوي على 6 صور
الموسوعة الحرة

في علم الحاسوب ، تُعرَّف القواعد النحوية المبهمة بأنها قواعد نحوية خالية من السياق، حيث يوجد سلسلة نصية يمكن أن يكون لها أكثر من اشتقاق أو شجرة تحليل نحوي من اليسار . [ 1 ] [ 2 ] كل لغة خالية من السياق غير فارغة تقبل قواعد نحوية مبهمة، وذلك بإدخال قاعدة تكرار، على سبيل المثال. تُسمى اللغة التي لا تقبل إلا القواعد النحوية المبهمة لغةً مبهمة بطبيعتها . أما القواعد النحوية الحتمية الخالية من السياق فهي دائمًا غير مبهمة، وتُعد فئة فرعية مهمة من القواعد النحوية غير المبهمة؛ ومع ذلك، توجد قواعد نحوية غير حتمية غير مبهمة.

في لغات برمجة الحاسوب ، غالبًا ما تكون قواعد اللغة المرجعية غامضة، بسبب مشكلات مثل مشكلة جملة else المعلقة . وفي حال وجودها، تُحل هذه الغموضات عادةً بإضافة قواعد الأسبقية أو قواعد تحليل أخرى حساسة للسياق ، بحيث تصبح قواعد اللغة العامة غير غامضة. تستطيع بعض خوارزميات التحليل (مثل خوارزمية إيرلي [ 3 ] أو محللات GLR ) توليد مجموعات من أشجار التحليل (أو "غابات التحليل") من سلاسل نصية غامضة نحويًا . [ 4 ]

أمثلة

لغة تافهة

أبسط مثال على ذلك هو القواعد النحوية الغامضة التالية (مع رمز البداية A) للغة البسيطة التي تتكون فقط من السلسلة الفارغة:

A → A | ε

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

تتميز هذه اللغة أيضاً بقواعد نحوية واضحة لا لبس فيها، تتكون من قاعدة إنتاج واحدة :

A → ε

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

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

خيط أحادي

اللغة المنتظمة للسلاسل الأحادية ذات حرف معين، على سبيل المثال 'a'(التعبير النمطي a*)، لها قواعد نحوية لا لبس فيها:

A → aA | ε

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

A → aA | Aa | ε

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

الجمع والطرح

قواعد اللغة الخالية من السياق

A → A + A | A − A | a

الأمر غامض لأن هناك اشتقاقين من اليسار للسلسلة a + a + a:

    أ→ أ + أ    أ→ أ + أ
    → أ + أ    → A + A + A (يتم استبدال A الأولى بـ A+A. استبدال A الثانية سيؤدي إلى اشتقاق مماثل.)
    → أ + أ + أ    → أ + أ + أ
    → أ + أ + أ    → أ + أ + أ
    → أ + أ + أ    → أ + أ + أ

كمثال آخر، فإن القواعد النحوية غامضة حيث توجد شجرتان تحليليتان للسلسلة a + a − a:

أقصى اليسار jaredwf.svg

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

A → A + a | A − a | a

شيء آخر معلق

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

بشكل ملموس، في العديد من اللغات يمكن كتابة العبارات الشرطية في شكلين صحيحين: شكل if-then، وشكل if-then-else – مما يجعل عبارة else اختيارية في الواقع.

في قواعد نحوية تحتوي على القواعد [ أ ]

العبارة → إذا كان الشرط صحيحًا ، فافعل العبارة | إذا كان الشرط صحيحًا، فافعل العبارة، وإلا فافعل العبارة | ... الحالة → ...

قد تظهر بعض التراكيب العباراتية الغامضة.

إذا كان أ، فإن ب، فإن س، وإلا فإن س٢

يمكن تحليلها على النحو التالي:

إذا كان أ، فابدأ، وإذا كان ب، فابدأ ، وإلا فابدأ s2

أو كما

إذا كان أ، فابدأ؛ إذا كان ب، فابدأ س؛ وإلا فابدأ س٢.

وذلك بحسب ما إذا elseكان مرتبطًا بالأول ifأو الثاني if.

يُحلّ هذا الأمر بطرقٍ مختلفة في اللغات المختلفة. أحيانًا تُعدّل القواعد النحوية لتصبح واضحة لا لبس فيها، كأن يُشترط وجود endifعبارة أو يُجعل الأمر elseإلزاميًا. وفي حالات أخرى، تبقى القواعد النحوية غامضة، ولكن يُحلّ هذا الغموض بجعل قواعد العبارة ككل حساسة للسياق، كأن يُربط عنصرٌ ما elseبأقرب عنصر if. في هذه الحالة الأخيرة، تكون القواعد النحوية واضحة لا لبس فيها، لكن القواعد النحوية غير المرتبطة بالسياق تكون غامضة.

قواعد نحوية واضحة ذات اشتقاقات متعددة

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

على سبيل المثال، القواعد البسيطة

S → A + A أ → ٠ | ١

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

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

و

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

الاشتقاق الأول فقط هو الاشتقاق الأيسر.

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

إن مسألة تحديد ما إذا كانت قواعد نحوية معينة غامضة أم لا هي مسألة غير قابلة للحل، لأنه يمكن إثبات أنها مكافئة لمسألة مطابقة بوست . [ 5 ] على الأقل، توجد أدوات تُنفذ بعض إجراءات شبه القرار للكشف عن غموض القواعد النحوية الخالية من السياق. [ 6 ]

تُحدد كفاءة تحليل القواعد النحوية الخالية من السياق بواسطة الآلة التي تقبلها. تقبل الآلات الحتمية ذات الدفع السفلي القواعد النحوية الخالية من السياق ، ويمكن تحليلها في وقت خطي، على سبيل المثال بواسطة محلل LR . [ 7 ] وهي مجموعة فرعية صارمة من القواعد النحوية الخالية من السياق ، والتي تقبلها الآلات ذات الدفع السفلي ، ويمكن تحليلها في وقت متعدد الحدود، على سبيل المثال بواسطة خوارزمية CYK .

يمكن أن تكون القواعد النحوية الخالية من السياق غير حتمية. على سبيل المثال، لغة المتناظرات الزوجية الطول على أبجدية 0 و1 لها القاعدة النحوية الخالية من السياق غير المبهمة S → 0S0 | 1S1 | ε. لا يمكن تحليل أي سلسلة نصية من هذه اللغة دون قراءة جميع رموزها أولاً، مما يعني أن آلة الدفع لأسفل يجب أن تجرب انتقالات حالة بديلة لاستيعاب الأطوال المختلفة الممكنة لسلسلة نصية شبه محللة. [ 8 ]

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

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

بينما تمتلك بعض اللغات الخالية من السياق (مجموعة السلاسل التي يمكن توليدها بواسطة قواعد نحوية) قواعد نحوية غامضة وغير غامضة، توجد لغات خالية من السياق لا توجد لها قواعد نحوية غير غامضة. تُسمى هذه اللغات باللغات الغامضة بطبيعتها .

لا توجد لغات منتظمة غامضة بطبيعتها. [ 9 ] [ 10 ]

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

اللغة{x|x=أنبمأن′بم أو x=أنبمأنبم′، أين ن،ن′،م،م′≥1}{\displaystyle \{x|x=a^{n}b^{m}a^{n^{\prime }}b^{m}{\text{ or }}x=a^{n}b^{m}a^{n}b^{m^{\prime }},{\text{ where }}n,n',m,m'\geq 1\}}غامض بطبيعته. [ 12 ]

يمكن استخدام مبرهنة أوجدن [ 13 ] لإثبات أن بعض اللغات الخالية من السياق، مثل{أنبمجم|م،ن≥1}∪{أمبمجن|م،ن≥1}{\displaystyle \{a^{n}b^{m}c^{m}|m,n\geq 1\}\cup \{a^{m}b^{m}c^{n}|m,n\geq 1\}}تتسم هذه العبارات بالغموض المتأصل. انظر إلى مبرهنة أوجدن §  الغموض المتأصل للاطلاع على البرهان.

اتحاد{أنبنجمدم|ن،م>0}{\displaystyle \{a^{n}b^{n}c^{m}d^{m}\mid n,m>0\}}مع{أنبمجمدن|ن،م>0}{\displaystyle \{a^{n}b^{m}c^{m}d^{n}\mid n,m>0\}}هو غامض بطبيعته. هذه المجموعة خالية من السياق، لأن اتحاد لغتين خاليتين من السياق يكون دائمًا خاليًا من السياق. لكن هوبكروفت وأولمان (1979) قدما برهانًا على أنه لا توجد قواعد نحوية خالية من السياق لهذه اللغة الاتحادية يمكنها تحليل سلاسل من الشكل بشكل لا لبس فيه.أنبنجندن،(ن>0){\displaystyle a^{n}b^{n}c^{n}d^{n},(n>0)}[ 14 ]​

يمكن الاطلاع على المزيد من الأمثلة، ومراجعة عامة لتقنيات إثبات الغموض المتأصل في اللغات الخالية من السياق، في دراسة باسينو ونيكود (2011). [ 15 ]

انظر أيضاً

الاقتباسات

ملحوظات

  1. ↑ يستخدم المثال التاليصيغة باسكال .

مراجع

  1. ↑ ويليم جيه إم ليفيلت (2008). مقدمة في نظرية اللغات الرسمية والأتمتة . دار نشر جون بنجامينز. رقم ISBN 978-90-272-3250-2.
  2. ↑ هوبكروفت، موتاني وأولمان 2006 ، ص 217.
  3. ↑ سكوت، إليزابيث (1 أبريل 2008). "تحليل نمط SPPF من مُعرِّفات إيرلي" . ملاحظات إلكترونية في علوم الحاسوب النظرية . 203 (2): 53-67 . doi : 10.1016/j.entcs.2008.03.044 .
  4. ↑ توميتا، ماسارو. " خوارزمية تحليل نحوي فعالة تعتمد على السياق المعزز ." اللغويات الحاسوبية 13.1-2 (1987): 31-46.
  5. ^ هوبكروفت، موتواني وأولمان 2006 ، ص. 415، نظرية 9.20.
  6. ↑ أكسلسون، رولاند؛ هيلجانكو، كيجو؛ لانج، مارتن (2008). "تحليل القواعد النحوية الخالية من السياق باستخدام مُحلِّل SAT تزايدي" (ملف PDF) . وقائع الندوة الدولية الخامسة والثلاثين حول الأوتوماتا واللغات والبرمجة (ICALP'08)، ريكيافيك، أيسلندا . سلسلة محاضرات في علوم الحاسوب . المجلد 5126. سبرينغر-فيرلاغ. الصفحات 410-422 . doi : 10.1007/978-3-540-70583-3_34 . ISBN   978-3-540-70582-6.
  7. ↑ كنوت، دي إي (يوليو 1965). "حول ترجمة اللغات من اليسار إلى اليمين". المعلومات والتحكم . 8 (6): 607-639 . doi : 10.1016/S0019-9958(65)90426-2 .
  8. ↑ هوبكروفت، موتاني وأولمان 2006 ، ص 254-256.
  9. ↑ بوك، ر.؛ إيفن، س.؛ غريباخ، س.؛ أوت، ج. (فبراير 1971). "الغموض في الرسوم البيانية والتعبيرات" . معاملات IEEE في الحوسبة . C-20 (2): 149-153 . doi : 10.1109/tc.1971.223204 . ISSN 0018-9340 . S2CID 20676251 .  
  10. ↑ "اللغات الرسمية - هل يمكن جعل التعابير النمطية غير مبهمة؟" . MathOverflow . تم الاسترجاع في 23-02-2023 .
  11. ↑ باريك، روهيت (يناير 1961). أجهزة توليد اللغة . تقرير التقدم الفصلي، مختبر أبحاث الإلكترونيات، معهد ماساتشوستس للتكنولوجيا.
  12. ↑ باريك، روهيت ج. (1966-10-01). "حول اللغات الخالية من السياق" . مجلة ACM . 13 (4): 570-581 . doi : 10.1145/321356.321364 . ISSN 0004-5411 . S2CID 12263468 .  هنا: النظرية 3.
  13. ↑ أوجدن، ويليام (سبتمبر 1968). "نتيجة مفيدة لإثبات الغموض المتأصل" . نظرية الأنظمة الرياضية . 2 (3): 191-194 . doi : 10.1007/bf01694004 . ISSN 0025-5661 . S2CID 13197551 .  
  14. ↑ هوبكروفت وأولمان 1979 ، ص 99-103، القسم 4.7.
  15. ↑ فريدريك باسّينو وسيريل نيكود (16 ديسمبر 2011). "فيليب فلاجو والتوافقية التحليلية: الغموض المتأصل في اللغات الخالية من السياق" (ملف PDF) . مؤرشف (ملف PDF) من الأصل بتاريخ 25 سبتمبر 2022.

للمزيد من القراءة

  • dk.brics.grammar - محلل غموض القواعد النحوية.
  • CFGAnalyzer - أداة لتحليل القواعد النحوية الخالية من السياق فيما يتعلق بشمولية اللغة والغموض والخصائص المماثلة.