في نظرية اللغة الرسمية ، قواعد بلا سياق (CFG) هي نوع من أنواع القواعد الرسمية: مجموعة من قواعد الاشتقاق التي تصف جميع السلاسل الممكنة في لغة رسمية ما لاشتقاق الكلمات, ويمكن تطبيق هذه القواعد بغض النظر عن السياق.
قواعد الاشتقاق هي عمليات تبديل بسيطة, على سبيل المثال، القاعدة التالية: A→α يُستبدل وفقه A مع α. ويمكن أن تكون قواعد استبدال متعددة لأي قيمة ما. على سبيل المثال: A→α|β يعني أنه يمكن استبدال A اما بـα او β. في القواعد النحوية بلا سياق، تكون القواعد إما ذات قيمة مفردة (أي واحدة فقط) أو متعددة. الجانب الأيسر من قاعدة الاشتقاق يكون دائمًا رمزا غير ملحد, أي أنه لا يظهر في كلمات اللغة الرسمية المشتقة. لذلك في المثال المعطى، تحتوي اللغة على الأحرف α او β لكن ليس A .
يمكن أيضًا مُراجعة القواعد (أي تتبع اشتقاقها في الاتجاه التراجعي - اشتقاق تراجعي) للتحقق مما إذا كانت السلسلة صحيحة نحويًا وفقًا للقواعد النحوية المعطاة.
مثال لقواعد لغة بلا سياق, يصف كل السلاسل المكونة من حرفين والتي تحتوي على الأحرف α او β
S → AA
A → α|β
إذا بدأنا بالرمز غير المنتهي S، فيمكننا استخدام القاعدة S → AA لاشتقاق AA من S. يمكننا بعد ذلك تطبيق أحد إمكانيات القاعدة الثانية. فعلى سبيل المثال، إذا طبقنا ذلك A → β في A الأول سنحصل على βA واذا طبقنا بعدها A → α سنحصل عل βα
. α و β هما من الرموز المنتهية, أي التي لا يمكن الاشتقاق منها, وهي القواعد النحوية بلا سياق لا تظهر أبدًا على الجانب الأيسر لقاعدة الاشتقاق.
تُعرف اللغات التي تُنشأ باستخدام قواعد نحوية بلا سياق باسم لغات بلا سياق أو خالية من السياق (CFL). من المهم التمييز بين خصائص اللغة (أي الخصائص الجوهرية) وخصائص قواعد معينة (أي خصائص خارجية).
تُستخدم القواعد النحوية التي بلا سياق في علوم اللغويات لوصف بنية الجمل والكلمات بلغة طبيعية ما، وابتكرها في الواقع العالم اللغوي نعوم تشومسكي لهذا الغرض، لكنها لم ترق إلى مستوى توقعاتها الأصلية. على النقيض من ذلك، في علم الحاسوب، فإن استخدامها في تزايد, فمثلا تُستخدم القواعد النحوية بلا سياق لوصف بنية لغات البرمجة وتستخدم في جزء أساسي من لغة الترميز الموسعة (XML) التي تسمى تعريف نوع المستند.[1]
في اللغويات، يستخدم بعض المؤلفين مصطلح هيكل العبارة النحوي للإشارة إلى القواعد النحوية بلا سياق، إذ تكون قواعد النحو لتراكيب العبارة مختلفة عن قواعد النحو التبعية. في مجال علوم الحاسوب، يعد الترميز الشائع لقواعد النحو بلا سياق هو نموذج Backus – Naur ، أو BNF.
الخلفية
منذ عصر اللغوي السنسكريتي بانيني، بالتقدير، وصف علماء اللغة القواعد اللغوية من حيث هيكلتها، ووصف كيف تُركب الجمل بشكل متكرر من عبارات أصغر، وفي النهاية من كلمات فردية أو عناصر أخرى. الخاصية الأساسية لهذه الهيكلة هي أن الوحدات المنطقية تتداخل. فعلى سبيل المثال الجملة: مشى سامر, الذي كانت سيارته الزرقاء في المرآب، إلى متجر البقالة, يمكن تقسيمهاعلى النحو التالي: (سامر، ((السيارة الزرقاء)) (كانت (في المرآب))) (مشى (إلى (محل البقالة))).
توفر القواعد النحوية التي بلا سياق آلية دقيقة رياضيا لوصف الطرق التي تُركّب وفقها الجمل من كتل صغيرة في بعض اللغات الطبيعية، إذ يمكن تمييز المركبات المختلفة للجملة بطريقة طبيعية. بساطتها يجعلها قابلة للدراسة الرياضية البحت.
لا تعتبر السمات الهامة لبناء الجملة في اللغة الطبيعية, مثل الاتفاقية والمرجع, جزءًا من القواعد النحوية بلا سياق، ولكن البنية الأساسية الخطية للجمل، والطريقة التي تتداخل بها الجمل داخل الجمل الأخرى، والطريقة التي تكون بها قوائم الصفات والأحوال. يبتلع الأسماء والأفعال ، يوصف بالضبط.
تم تطوير شكليات القواعد النحوية الخالية من السياق في منتصف الخمسينيات من قبل ناعوم تشومسكي ، [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
مراجع
- Introduction to Automata Theory, Languages, and Computation, John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Addison Wesley, 2001, p.191
- Hopcroft & Ullman (1979), p. 106.