اللغات الخالية من السياق والآلات الضاغطة

تولد القواعد النحوية الخالية من السياق لغات ذات بنية متداخلة ومتكررة، وتتعرف الآلات الضاغطة (pushdown automata) على هذه اللغات تحديدًا عن طريق تعزيز التحكم المحدود بمكدس غير محدود.

Definition

اللغة الخالية من السياق هي لغة يتم إنشاؤها بواسطة قواعد نحوية تعيد كتابة رمز غير طرفي واحد بشكل مستقل عن السياق، ويتم التعرف عليها بواسطة آلة ضاغطة، وهي آلة محدودة مزودة بمكدس يوفر ذاكرة من نوع "آخر ما يدخل أول ما يخرج" (last-in, first-out) بعمق غير محدود.

Scope

يغطي هذا الموضوع القواعد النحوية الخالية من السياق والاشتقاقات، وأشجار التحليل والغموض، وتكافؤ القواعد النحوية الخالية من السياق مع الآلات الضاغطة، والأشكال المعيارية مثل شكل تشومسكي المعياري (Chomsky normal form)، ومبرهنة الضخ للغات الخالية من السياق، وخصائص الإغلاق والقرار التي تميز هذه الفئة عن اللغات المنتظمة.

Core questions

• ما أنواع الأنماط المتداخلة أو المتكررة التي تتطلب مكدسًا بدلاً من الذاكرة المحدودة؟
• لماذا تتكافئ القواعد النحوية الخالية من السياق والآلات الضاغطة في القوة؟
• متى تكون القاعدة النحوية غامضة، ولماذا يهم الغموض في التحليل؟
• ما هي مشاكل القرار للغات الخالية من السياق التي يمكن حلها، وما هي التي لا يمكن حلها؟

Key theories

تكافؤ القواعد النحوية والآلات

تكون اللغة خالية من السياق إذا وفقط إذا تم قبولها بواسطة آلة ضاغطة ما، لذا فإن منظور القواعد النحوية التوليدية ومنظور آلة المكدس يصفان نفس الفئة من اللغات.

شكل تشومسكي المعياري

يمكن إعادة كتابة كل قاعدة نحوية خالية من السياق بحيث تنتج كل قاعدة إما رمزين غير طرفيين أو رمزًا طرفيًا واحدًا، وهو شكل معياري يشكل أساس خوارزميات التحليل والبراهين الاستقرائية حول هذه الفئة.

مبرهنة الضخ للغات الخالية من السياق

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

Clinical relevance

تحدد القواعد النحوية الخالية من السياق بناء (syntax) كل لغة برمجة تقريبًا والعديد من تنسيقات البيانات، وتحول خوارزميات التحليل من نمط الآلة الضاغطة هذه القواعد النحوية إلى محللات تركيبية في قلب المترجمات والمفسرات، مما يجعل هذا الموضوع الأساس النظري لمعالجة لغات البرمجة.

History

قدم تشومسكي القواعد النحوية الخالية من السياق في أواخر الخمسينيات كجزء من تسلسله الهرمي، وقد استخدمها باكوس وناور بشكل مستقل لتحديد بناء لغة البرمجة ALGOL. تم تطوير التكافؤ مع الآلات الضاغطة والنظرية الهيكلية للفئة خلال الستينيات.

Key figures

• Noam Chomsky
• John Backus
• Seymour Ginsburg
• Sheila Greibach

Seminal works

• sipser2013
• hopcroft2006

Frequently asked questions

لماذا يتطلب تحليل لغة برمجة مكدسًا؟

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

ماذا يعني أن تكون القاعدة النحوية غامضة؟

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