مستخدم:Smalnassir/ملعب

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

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

اللغة العادية: تحتوي اللغة العادية للأوتار الأحادية لمجهول معين (A) على قواعد غير واضحة: A → aA | ε ولكن تحتوي أيضًا على قواعد غامضة: A → aA | Aa | ε

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

الجمع والطرح: سياق قواعد اللغة الحرة أدناه غامض نظرا لوجود اشتقاقين في أقصى يسار السلسلة: a + a + a: A → A + A | A − A | A * A | id     A → A + A A → A + A     → a + A → A + A + A (يتم استبدال A أولاً بـ A + A. وسيؤدي استبدال الجزء A إلى الحصول على اشتقاق مشابه     → a + A + A → a + A + A     → a + a + A → a + a + A     → a + a + a → a + a + a وكمثال آخر، فإن القواعد النحوية غامضة نظرًا لوجود شجرتي تحليل للحرف a + a - a:

لكن اللغة التي يولدها ليست غامضة بطبيعتها. وما يلي هو قواعد غير مبهمة تولد نفس اللغة: A → A + a | A − a | a

آخر تتبع: المادة الرئيسية: آخر تتبع ومن الأمثلة الشائعة على الغموض في لغات برمجة الكمبيوتر مشكلة آخر تتبع. في العديد من اللغات يكون تعبير شرطي

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

في العديد من اللغات قد يكتب المرء شرطيًا في شكلين صالحين بشكل ملموس: نموذج (إذا-ثم)، ونموذج (إذا-ثم-أيضا) ، مما يجعل هذا الشرط اختياريًا: [ملاحظة 1] في القواعد التي تحتوي على الشروط: Statement → if Condition then Statement |

           if Condition then Statement else Statement |
           ...

Condition → ...

يمكن أن تظهر بعض هياكل عبارات غامضة التعبير 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 بأقرب 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 السابق فقط واحد وهو أقصى اليسار.

التعرف على القواعد النحوية الغامضة: مشكلة القرار حول ما إذا كانت القواعد التعسفية غامضة وغير معقولة للقرار لأنه يمكن أن يثبت أنها مكافئة لمشكلة ما بعد المراسلات. [2] هناك أدوات تقوم بتنفيذ بعض إجراءات شبه القرار لاكتشاف غموض القواعد النحوية الخالية من السياق. [3] يتم تحديد كفاءة تحليل قواعد اللغة الخالية من السياق من قبل إنسان آلي الذي يقبل ذلك. يتم قبول القواعد النحوية المعيارية الخالية من السياق من خلال الأوتوماتكية ذات الدفع القطعي ويمكن تحليلها في وقت خطي بواسطة محلل مجزئ يسار يمين [3]. (LR) هذه مجموعة فرعية من القواعد النحوية الخالية من السياق والتي يتم قبولها بواسطة إنزال آلي ويمكن تحليلها في زمن كثير الحدود بواسطة خوارزمية CYK. ولا يمكن للقواعد النحوية الخالية من الغموض أن تكون غير حتمية. على سبيل المثال لغة palindromes متساوية الطول على الأبجدية من 0 و 1 لديها قواعد S - 0S0 | 1S1 | ε. لا يمكن تحليل سلسلة عشوائية من هذه اللغة بدون قراءة جميع أحرفها أولاً ، مما يعني أنه يجب على الإنسان الآلي الضغط لمحاولة الانتقال إلى حالة بديلة لاستيعاب الأطوال الممكنة المختلفة لسلسلة شبه معلومة. [5] وقد يؤدي ذلك إلى إزالة الغموض في القواعد لإصدار قواعد نحوية خالية من الحتمية وبالتالي السماح بتحليل أكثر كفاءة. تتضمن مولدات المحول البرمجي مثل ياك (YACC)ميزات لحل بعض أنواع الغموض، مثل استخدام الأسبقية وقيود الترابطيات. لغات غامضة بطبيعتها: تم إثبات وجود لغات غامضة بطبيعتها مع نظرية باريخ في عام 1961 التي حررها روهيت باريخ في تقرير بحثي لمعهد MIT. [6]

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

مع

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

See also[edit source] • GLR parser, a type of parser for ambiguous and nondeterministic grammars • Chart parser, another type of parser for ambiguous grammars • Syntactic ambiguity References[edit source] 1. Jump up ^ Tomita, Masaru. "An efficient augmented-context-free parsing algorithm." Computational linguistics 13.1-2 (1987): 31-46. 2. Jump up ^ Hopcroft, John; Motwani, Rajeev; Ullman, Jeffrey (2001). Introduction to automata theory, languages, and computation (2nd ed.). Addison-Wesley. Theorem 9.20, pp. 405–406. ISBN 0-201-44124-1. 3. Jump up ^ Axelsson, Roland; Heljanko, Keijo; Lange, Martin (2008). "Analyzing Context-Free Grammars Using an Incremental SAT Solver". Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP'08), Reykjavik, Iceland. Lecture Notes in Computer Science. 5126. Springer-Verlag. pp. 410–422. doi:10.1007/978-3-540-70583-3_34. (Subscription required (help)). 4. Jump up ^ Knuth, D. E. (July 1965). "On the translation of languages from left to right" (PDF). Information and Control. 8 (6): 607–639. doi:10.1016/S0019-9958(65)90426-2. Retrieved 29 May 2011. 5. Jump up ^ Hopcroft, John; Motwani, Rajeev; Ullman, Jeffrey (2001). Introduction to automata theory, languages, and computation (2nd ed.). Addison-Wesley. pp. 249–253. ISBN 0-201-44124-1. 6. Jump up ^ Parikh, Rohit (January 1961). Language-generating devices. Quarterly Progress Report, Research Laboratory of Electronics, MIT. 7. Jump up ^ p.99-103, Sect.4.7 • Gross, Maurice (September 1964). "Inherent ambiguity of minimal linear grammars". Information and Control. Information and Control. 7 (3): 366–368. doi:10.1016/S0019-9958(64)90422-X. • Michael, Harrison (1978). Introduction to Formal Language Theory. Addison-Wesley. ISBN 0201029553. • Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages, and Computation (1st ed.). Addison-Wesley. • Hopcroft, John; Mowani, Rajeev; Ullman, Jeffrey (2001). Introduction to Automata Theory, Languages and Computation (2nd ed.). Addison Wesley. p. 217. • Brabrand, Claus; Giegerich, Robert; Møller, Anders (March 2010). "Analyzing Ambiguity of Context-Free Grammars". Science of Computer Programming. Elsevier. 75 (3): 176–191. doi:10.1016/j.scico.2009.11.002. Notes[edit source] 1. Jump up ^ The following example uses Pascal syntax External links[edit source] • dk.brics.grammar - a grammar ambiguity analyzer. • CFGAnalyzer - tool for analyzing context-free grammars with respect to language universality, ambiguity, and similar properties.