حقائق ورؤى حول قواعد خالية من السياق

في نظرية اللغة الرسمية ، قواعد بلا سياق (CFG) هي نوع من أنواع القواعد الرسمية: مجموعة من قواعد الاشتقاق التي تصف جميع السلاسل الممكنة في لغة رسمية ما لاشتقاق الكلمات, ويمكن تطبيق هذه القواعد بغض النظر عن السياق.

قواعد الاشتقاق هي عمليات تبديل بسيطة, على سبيل المثال، القاعدة التالية: A→α يُستبدل وفقه A مع α. ويمكن أن تكون قواعد استبدال متعددة لأي قيمة ما. على سبيل المثال: A→α|β يعني أنه يمكن استبدال A اما بـα او β. في القواعد النحوية بلا سياق، تكون القواعد إما ذات قيمة مفردة (أي واحدة فقط) أو متعددة. الجانب الأيسر من قاعدة الاشتقاق يكون دائمًا رمزا غير ملحد, أي أنه لا يظهر في كلمات اللغة الرسمية المشتقة. لذلك في المثال المعطى، تحتوي اللغة على الأحرف α او β لكن ليس A .

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

مثال لقواعد لغة بلا سياق, يصف كل السلاسل المكونة من حرفين والتي تحتوي على الأحرف α او β

S → AA

A → α|β

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

. α و β هما من الرموز المنتهية, أي التي لا يمكن الاشتقاق منها, وهي القواعد النحوية بلا سياق لا تظهر أبدًا على الجانب الأيسر لقاعدة الاشتقاق.

تُعرف اللغات التي تُنشأ باستخدام قواعد نحوية بلا سياق باسم لغات بلا سياق أو خالية من السياق (CFL). من المهم التمييز بين خصائص اللغة (أي الخصائص الجوهرية) وخصائص قواعد معينة (أي خصائص خارجية).

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

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