هذه المقالة يتيمة. ساعد بإضافة وصلة إليها في مقالة متعلقة بها
هذه الصفحة لم تصنف بعد. أضف تصنيفًا لها لكي تظهر في قائمة الصفحات المتعلقة بها.
يرجى إضافة وصلات داخلية للمقالات المتعلّقة بموضوع المقالة.
يرجى مراجعة هذه المقالة وإزالة وسم المقالات غير المراجعة، ووسمها بوسوم الصيانة المناسبة.

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

من ويكيبيديا، الموسوعة الحرة
اذهب إلى التنقل اذهب إلى البحث
N write.svg
هذه مقالة غير مراجعة. ينبغي أن يزال هذا القالب بعد أن يراجعها محرر عدا الذي أنشأها؛ إذا لزم الأمر فيجب أن توسم المقالة بقوالب الصيانة المناسبة. (أبريل 2018)

في نظرية اللغة الرسمية ، تعتبر القواعد الخالية من السياق (CFG) نوعًا معينًا من القواعد الرسمية: مجموعة من قواعد الإنتاج تصف جميع السلاسل الممكنة في لغة رسمية معينة. قواعد الإنتاج هي بدائل بسيطة. على سبيل المثال ، القاعدة

A-->α

يستبدلA مع  αيمكن أن تكون هناك قواعد استبدال متعددة لأي قيمة محددة. فمثلا

A-->α

B-->β

يعني أنه يمكن استبدال A اما بـα اوβ .في القواعد النحوية الخالية من السياق ، تكون جميع القواعد فردية أو فردية أو متعددة. يمكن تطبيق هذه القواعد بغض النظر عن السياق. الجانب الأيسر من قاعدة الإنتاج هو دائمًا رمز غير ملحد. هذا يعني أن الرمز لا يظهر في اللغة الرسمية الناتجة. لذلك في حالتنا ، تحتوي لغتنا على الأحرفα او β وليس A .

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

S-->AA

S-->α

A-->β

إذا بدأنا بالرمز غير منتهي S ، فيمكننا استخدام القاعدةS-->AA لتحويل S إلى AA

يمكننا بعد ذلك تطبيق أحد القاعدتين التاليتين. على سبيل المثال ، إذا طبقنا ذلك A-->βفي الأول A نحن نحصل واذا طبقنا A-->α ثانيا A نحن نحصل على βα نظرًا لأن كلاهما α وβ

هي رموز منتهية .

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

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

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

الخلفية[عدل]

منذ وقت Pāṇini ، على الأقل ، وصف علماء اللغة قواعد القواعد اللغوية من حيث هيكل الكتلة ، ووصف كيف يتم تجميع الجمل بشكل متكرر من عبارات أصغر ، وفي النهاية كلمات فردية أو عناصر كلمة. الخاصية الأساسية لهذه الهياكل كتلة هي أن الوحدات المنطقية أبدا تتداخل. على سبيل المثال ، الجملة: سار جون ، الذي كانت سيارته الزرقاء في المرآب ، إلى متجر البقالة. يمكن تقسيمات منطقية على النحو التالي: (جون ، ((السيارة الزرقاء)) (كان (في المرآب))) (مشى (إلى (محل البقالة))).

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

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

تم إدخال بنية الكتلة إلى لغات برمجة الكمبيوتر بواسطة مشروع Algol (1957-1960) ، والذي ، نتيجة لذلك ، أظهر أيضًا قواعد خالية من السياق لوصف تركيب Algol الناتج. أصبح هذا سمة قياسية في لغات الكمبيوتر ، وأصبح مصطلح القواعد النحوية المستخدمة في الأوصاف الملموسة بلغات الكمبيوتر يعرف باسم Backus – Naur ، بعد أن كان اثنان من أعضاء لجنة تصميم لغة Algol.[2]] الجانب "هيكل كتلة" أن التقاط قواعد اللغة خالية من السياق أمر أساسي جدا لقواعد اللغة التي غالبا ما يتم تحديد قواعد النحو والقواعد النحوية مع القواعد النحوية خالية من السياق ، وخاصة في علوم الكمبيوتر. ثم تعتبر القيود الرسمية التي لم يتم التقاطها من قبل القواعد لتكون جزءا من "دلالات" اللغة.

تعتبر القواعد النحوية الخالية من السياقات بسيطة بما يكفي للسماح ببناء خوارزميات تحليل فعالة ، لتحديد سلسلة وما إذا كان يمكن توليدها من القواعد. محلل Earley هو مثال على مثل هذه الخوارزمية ، في حين أن محللي LR و LL الأكثر استخدامًا هما خوارزميات أبسط لا تتعامل إلا مع مجموعات فرعية أكثر تقييدًا من القواعد النحوية الخالية من السياق .

التعريفات الرسمية[عدل]

يتم تعريف Gالقواعد النحوية الخالية من السياق من خلال 4-انواع:

حيث(G=(V,∑,R,S

1) V مجموعة محدودة. يُطلق على كل عنصر اسم حرف غير مجسم أو متغير. يمثل كل متغير نوعًا مختلفًا للعبارة أو الجملة في الجملة. تسمى المتغيرات أحيانًا بالفئات النحوية. يحدد كل متغير لغة فرعية للغة التي حددها G.

Σ(2 هي مجموعة محدودة من المنهية ، منفصلة عن V ، والتي تشكل المحتوى الفعلي للجملة. مجموعة المحطات هي أبجدية اللغة المحددة بالنحو G.

R(3 هي علاقة محدودة من V إلى  حيث تمثل العلامة النجمية عملية نجمة Kleene. ويطلق على أعضاء R قواعد (أو إعادة كتابتها) من إنتاج القواعد. (كما يرمز له عادة بـ P)

S(4 هو متغير البدء (أو رمز البداية) ، المستخدم لتمثيل الجملة الكاملة (أو البرنامج). يجب أن يكون عنصرا من V.

تدوين قواعد الإنتاج[عدل]

يتم تنظيم قاعدة الإنتاج في R بشكل رياضي كزوج (α,β) تنتمي إلى R, حيثα تنتمي لل V هو غير المنتهية *( βᕮ( ∑ᑌV

هي سلسلة من المتغيرات و / أو المنتهية ؛ بدلاً من استخدام تدوين زوجات مرتبة ، عادةً ما تتم كتابة قواعد الإنتاج باستخدام عامل سهم معα كما في الجانب الأيسر وβ كجانبه الأيمن α-->β  مسموح بها β أن تكون

السلسلة الفارغة ، وفي هذه الحالة يكون من المعتاد أن تشير إلى ε يسمى النموذج α-->ε ε-بالإنتاج

من الشائع إدراج جميع جوانب الجانب الأيمن لنفس الجانب الأيسر على نفس السطر ، باستخدام | (رمز الأنبوب) لفصلها. القواعدα-->β1 ,α-->β2 يمكن بالتالي أن تكتب α-->β1|β2

في هذه الحالة ، يُطلق على β1وβ2 الخيار الأول والثاني على التوالي

تطبيق القاعدة[عدل]

في المتسلسلة *( u,vᕮ(∑ᑌVنقول u مباشرة تنتج v ، مكتوبة كـu-->v اذا ( Ǝ(α,β ينتمي إلى Rمعαᕮ  

*( u1,u2,Vᕮ(∑ᑌV  وبالتالي u=u1αu2 v=u1βu2

، v هو نتيجة لتطبيق القاعدة(α,β) إلى u

مراجع[عدل]

  1. ^ Introduction to Automata Theory, Languages, and Computation, John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Addison Wesley, 2001, p.191
  2. أ ب Hopcroft & Ullman (1979), p. 106.

Categorisation-hierarchy-top2down.svg
هذه الصفحة غير مصنفة:
صنفها حسب الموضوع. جرب المصناف الفوري. دقق تصنيفك قدر الإمكان. (أبريل 2018)