قواعد خالية من السياق
المحتويات
بدايةً، في نظرية اللغة الرسمية ، قواعد بلا سياق (CFG) هي نوع من أنواع القواعد الرسمية: مجموعة من قواعد الاشتقاق التي تصف جميع السلاسل الممكنة في لغة رسمية ما لاشتقاق الكلمات, ويمكن تطبيق هذه القواعد بغض النظر عن السياق. ونتناول فيما يلي مزيدًا من التفاصيل.
من جانب آخر، قواعد الاشتقاق هي عمليات تبديل بسيطة, مثلًا، القاعدة التالية: A→α يُستبدل وفقه A مع α. ويمكن أن تكون قواعد استبدال متعددة لأي قيمة ما. مثلًا: A→α – β يعني أنه يمكن استبدال A اما بـα او β. في القواعد النحوية بلا سياق، تكون القواعد إما ذات قيمة مفردة (أي واحدة فقط) أو متعددة. الجانب الأيسر من قاعدة الاشتقاق يكون دائمًا رمزا غير ملحد, أي أنه لا يظهر في كلمات اللغة الرسمية المشتقة. لذلك في المثال المعطى، تحتوي اللغة على الأحرف α او β لكن ليس A .
S → AA
من جانب آخر، يمكن كذلك مُراجعة القواعد (أي تتبع اشتقاقها في الاتجاه التراجعي - اشتقاق تراجعي) للتحقق مما إذا كانت السلسلة صحيحة نحويًا بحسب القواعد النحوية المعطاة.
إضافةً إلى ذلك، مثال لقواعد لغة بلا سياق, يصف كل السلاسل المكونة من حرفين والتي تحتوي على الأحرف α او β
A → α – β
من جانب آخر، تُستعمل القواعد النحوية التي بلا سياق في علوم اللغويات لوصف بنية الجمل والكلمات بلغة طبيعية ما، وابتكرها في الواقع العالم اللغوي نعوم تشومسكي لهذا الغرض، لكنها لم ترق إلى مستوى توقعاتها الأصلية. على النقيض من ذلك، في علم الحاسوب، فإن استخدامها في تزايد, فمثلا تُستعمل القواعد النحوية بلا سياق لوصف بنية لغات البرمجة وتستعمل في جزء أساسي من لغة الترميز الموسعة (XML) التي تسمى تعريف نوع المستند.
وفي السياق ذاته، تُعرف اللغات التي تُنشأ باستخدام قواعد نحوية بلا سياق باسم لغات بلا سياق أو خالية من السياق (CFL). من المهم التمييز بين خصائص اللغة (أي الخصائص الجوهرية) وخصائص قواعد معينة (أي خصائص خارجية).
وفي هذا السياق، إذا بدأنا بالرمز غير المنتهي S، فيمكننا استخدام القاعدة S → AA لاشتقاق AA من S. يمكننا لاحقًا تطبيق أحد إمكانيات القاعدة الثانية. فمثلًا، إذا طبقنا ذلك A → β في A الأول سنحصل على βA واذا طبقنا بعدها A → α سنحصل عل βα
وعلى صعيد آخر، في اللغويات، يستعمل بعض المؤلفين مصطلح هيكل العبارة النحوي للإشارة إلى القواعد النحوية بلا سياق، إذ تكون قواعد النحو لتراكيب العبارة مختلفة عن قواعد النحو التبعية. في مجال علوم الحاسوب، يعد الترميز الشائع لقواعد النحو بلا سياق هو نموذج Backus – Naur ، أو BNF.
وفي السياق ذاته، . α و β هما من الرموز المنتهية, أي التي لا يمكن الاشتقاق منها, وهي القواعد النحوية بلا سياق لا تظهر أبدًا على الجانب الأيسر لقاعدة الاشتقاق.
التعريفات الرسمية
وفي السياق ذاته، يتم تعريف Gالقواعد النحوية الخالية من السياق من خلال 4-انواع:
تدوين قواعد الإنتاج
علاوةً على ذلك، يتم تنظيم قاعدة الإنتاج في R بشكل رياضي كزوج (α,β) تنتمي إلى R, حيثα تنتمي لل V هو غير المنتهية *( βᕮ( ∑ᑌV
في هذا الإطار، هي سلسلة من المتغيرات و / أو المنتهية ؛ بدلاً من استخدام تدوين زوجات مرتبة ، عادةً ما تتم كتابة قواعد الإنتاج باستخدام عامل سهم معα كما في الجانب الأيسر وβ كجانبه الأيمن α-->β مسموح بها β أن تكون
وفي هذا الصدد، في هذه الحالة ، يُطلق على β1وβ2 الخيار الأول والثاني على التوالي
إضافةً إلى ذلك، من الشائع إدراج جميع جوانب الجانب الأيمن لنفس الجانب الأيسر على نفس السطر ، باستخدام | (رمز الأنبوب) لفصلها. القواعدα-->β1 ,α-->β2 يمكن بالتالي أن تكتب α-->β1|β2
وعلى صعيد آخر، السلسلة الفارغة ، وفي هذه الحالة يكون من المعتاد أن تشير إلى ε يسمى النموذج α-->ε ε-بالإنتاج
حيث(G=(V,∑,R,S
وعلى صعيد آخر، 1) V مجموعة محدودة. يُطلق على كل عنصر اسم حرف غير مجسم أو متغير. يمثل كل متغير نوعًا مختلفًا للعبارة أو الجملة في الجملة. تسمى المتغيرات أحيانًا بالفئات النحوية. يحدد كل متغير لغة فرعية للغة التي حددها G.
في هذا الإطار، S(4 هو متغير البدء (أو رمز البداية) ، المستعمل لتمثيل الجملة الكاملة (أو البرنامج). يجب أن يكون عنصرا من V.
إضافةً إلى ذلك، Σ(2 هي مجموعة محدودة من المنهية ، منفصلة عن V ، والتي تشكل المحتوى الفعلي للجملة. مجموعة المحطات هي أبجدية اللغة المحددة بالنحو G.
وفي هذا السياق، R(3 هي علاقة محدودة من V إلى حيث تمثل العلامة النجمية عملية نجمة Kleene. ويطلق على أعضاء R قواعد (أو إعادة كتابتها) من إنتاج القواعد. (كما يرمز له عادة بـ P)
*( u1,u2,Vᕮ(∑ᑌV وبالتالي u=u1αu2 v=u1βu2
، v هو نتيجة لتطبيق القاعدة(α,β) إلى u
تطبيق القاعدة
وفي السياق ذاته، في المتسلسلة *( u,vᕮ(∑ᑌVنقول u مباشرة تنتج v ، مكتوبة كـu-->v اذا ( Ǝ(α,β ينتمي إلى Rمعαᕮ
الخلفية
ومن ناحية أخرى، لا تعتبر السمات الهامة لبناء الجملة في اللغة الطبيعية, مثل الاتفاقية والمرجع, جزءًا من القواعد النحوية بلا سياق، ولكن البنية الأساسية الخطية للجمل، والطريقة التي تتداخل بها الجمل داخل الجمل الأخرى، والطريقة التي تكون بها قوائم الصفات والأحوال. يبتلع الأسماء والأفعال ، يوصف بالضبط.
وفي هذا الصدد، تم تطوير شكليات القواعد النحوية الخالية من السياق في منتصف الخمسينيات من قبل ناعوم تشومسكي ، وكذلك تصنيفها كنوع خاص من القواعد الرسمية (والذي أطلق عليه اسم قواعد الجمل - التركيب). ما يُطلق عليه تشومسكي مصطلح "قواعد النحو" ، يُعرف الآن كذلك بقواعد النحو الانتخابي ، حيث يقف قواعد النحو في الدائرة الانتخابية على النقيض من القواعد النحوية الخاصة بالتبعية. في إطار قواعد اللغة التوليدية لشومسكي ، تم وصف بنية اللغات الطبيعية من خلال قواعد خالية من السياق إلى جانب قواعد التحويل.
ومن جهة أخرى، توفر القواعد النحوية التي بلا سياق آلية دقيقة رياضيا لوصف الطرق التي تُركّب وفقها الجمل من كتل صغيرة في بعض اللغات الطبيعية، إذ يمكن تمييز المركبات المختلفة للجملة بطريقة طبيعية. بساطتها يجعلها قابلة للدراسة الرياضية البحت.
إضافةً إلى ذلك، تعتبر القواعد النحوية الخالية من السياقات بسيطة بما يكفي للسماح ببناء خوارزميات تحليل فعالة ، لتحديد سلسلة وما إذا كان يمكن توليدها من القواعد. محلل Earley هو مثال على مثل هذه الخوارزمية ، في حين أن محللي LR و LL الأكثر استخدامًا هما خوارزميات أبسط لا تتعامل إلا مع مجموعات فرعية أكثر تقييدًا من القواعد النحوية الخالية من السياق .
وفي هذا الصدد، منذ عصر اللغوي السنسكريتي بانيني، بالتقدير، وصف علماء اللغة القواعد اللغوية من حيث هيكلتها، ووصف كيف تُركب الجمل بشكل متكرر من عبارات أصغر، وفي النهاية من كلمات فردية أو عناصر أخرى. الخاصية الأساسية لهذه الهيكلة هي أن الوحدات المنطقية تتداخل. فمثلًا الجملة: مشى سامر, الذي كانت سيارته الزرقاء في المرآب، إلى متجر البقالة, يمكن تقسيمهاعلى النحو التالي: (سامر، ((السيارة الزرقاء)) (كانت (في المرآب))) (مشى (إلى (محل البقالة))).
كذلك، تم إدخال بنية الكتلة إلى لغات برمجة الكمبيوتر بواسطة مشروع Algol (1957-1960) ، والذي ، نتيجة لذلك ، أظهر كذلك قواعد خالية من السياق لوصف تركيب Algol الناتج. أصبح هذا سمة قياسية في لغات الكمبيوتر ، وأصبح مصطلح القواعد النحوية المستعملة في الأوصاف الملموسة بلغات الكمبيوتر يعرف باسم Backus – Naur ، بعد أن كان اثنان من أعضاء لجنة تصميم لغة Algol.] الجانب "هيكل كتلة" أن التقاط قواعد اللغة خالية من السياق أمر أساسي جدا لقواعد اللغة التي غالبا ما يتم تحديد قواعد النحو والقواعد النحوية مع القواعد النحوية خالية من السياق ، وخاصة في علوم الكمبيوتر. ثم تعتبر القيود الرسمية التي لم يتم التقاطها من قبل القواعد لتكون جزءا من "دلالات" اللغة.
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟