ما لغات البرمجة خالية من السياق؟

Question

أو أن تكون أكثر دقة بقليل: ما هي لغات البرمجة التي يتم تعريفها من قبل القواعد الخالية من السياق؟

من ما أجمعه C ++ ليس خاليا من السياق بسبب أشياء مثل وحدات الماكرو والقوالب. أخبرني الأمعاء أن اللغات الوظيفية قد تكون خالية من السياق، لكن ليس لدي أي بيانات صعبة لدعم ذلك.

ممثل إضافي للحصول على أمثلة موجزة :-)

Answer 1

مجموعة البرامج الصحيحة النحوية هي خالية من السياق لجميع اللغات تقريبا.

مجموعة البرامج التي تجميعها ليست خالية من السياق لجميع اللغات تقريبا. على سبيل المثال، إذا كانت مجموعة جميع برامج تجميع جميع البرامج خالية من السياق، فمن خلال التقاطع مع لغة منتظمة (تعرف أيضا باسم Regex)، مجموعة جميع برامج تجميع C التي تطابق

^int main\(void\) { int a+; a+ = a+; return 0; }$

سيكون خاليا من السياق، ولكن هذا هو بوضوح Isomorphic إلى اللغة a ^ kba ^ kba ^ k، وهو معروف ليس أن تكون خالية من السياق.

Answer 2

ما لغات البرمجة خالية من السياق؟ [...

أخبرني الأمعاء أن اللغات الوظيفية خالية من السياق [...]

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

إليك CFG ل إلزامي لغة brainfuck.:

Program → Instr Program | ε
Instr → '+' | '-' | '>' | '<' | ',' | '.' | '[' Program ']'

وهنا CFG ل وظيفي مجمعات التزلج calculus.:

Program → E
E → 'S' E E E
E → 'K' E E
E → 'I'
E → '(' E ')'

هذه cfgs تعترف الكل برامج صالحة للغاتان لأنها بسيطة جدا.

---

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

إذا ب "لغة خالية من السياق" تقصد "... أي جميع البرامج تجميعها"، إذن الجواب هو: بالكاد أي. اللغات التي تناسب هذا الفاتورة بالكاد لديها أي قواعد أو ميزات معقدة، مثل وجود المتغيرات، حساسية من المسبقة، نظام نوع، أو أي شيء آخر سياق الكلام: المعلومات المحددة في مكان واحد وتعتمد عليها في مكان آخر.

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

أمثلة على ميزات النحوية غير الممكن التعبير عن CFG:

• اللغات المسافة البادئة والبييض حساسة مثل بيثون و haskell. تتبع مستويات المسافة البادئة المتداخلة تعسفيا حساسة في السياق وتتطلب عدادات منفصلة لمستوى المسافة البادئة؛ كلاهما عدد المساحات المستخدمة في كل مستوى وعدد المستويات هناك.

  إن السماح لمستوى ثابت فقط من المسافة البادئة باستخدام كمية ثابتة من المساحات ستعمل عن طريق تكرار قواعد المسافة البادئة لكل مستوى، ولكن في الممارسة العملية غير مريح.

• ال C Typedef تحليل مشكلة يقول أن برامج C غامضة خلال التحليل المعجمي لأنه لا يمكن أن تعرف من القواعد وحدها إذا كان هناك شيء معرف منتظم أو اسم مستعار Typedef لنوع موجود.

  المثال هو:

    typedef int my_int;
    my_int x;
  

  في الفاصلة المنقوطة، يجب تحديث بيئة النوع مع إدخال my_int. ولكن إذا كان Lexer قد نظرنا بالفعل إلى my_int، فسوف يكون له LEXED كمعرف بدلا من اسم النوع.

• اللغات المستندة إلى القوالب والمكتبات مثل LISP، C ++، Haskell، Nim، وهلم جرا. نظرا لأن بناء الجملة يتغير كما هو قيد التحليل، فإن حل واحد هو جعل المحلل المحلل في برنامج تعديل الذات. أنظر أيضا "هل C ++ خالية من السياق أو حساس للسياق؟"

• غالبا ما يتم التعبير عن أسبقية المشغل والزملاء مباشرة في CFGS على الرغم من ذلك ممكن. وبعد على سبيل المثال، CFG للحصول على قواعد تعبير صغير حيث ^ يربط أكثر إظهارا من ×، و × الربط أكثر إظهارا من +، قد تبدو وكأنها هذه:

  E → E ^ E
  E → E × E
  E → E + E
  E → (E)
  E → num
  

  هذا CFG هو غامض, ومع ذلك، وغالبا ما يرافقه الجدول الأسبقية / الارتباط قائلا على سبيل المثال أن ^ يرتبط المزائج، × يربط أكثر إظهارا من +، أن ^ هو النقابة اليمنى، وأن × و + يتم التركيز على اليسار.

  يمكن ترميز الأسبقية والزابترية في CFG بطريقة ميكانيكية بحيث لا لبس فيه ولا تنتج فقط أشجار بناء الجملة حيث يتصرف المشغلون بشكل صحيح. مثال على ذلك من أجل القواعد أعلاه:

  E₀ → EA E₁
  EA → E₁ + EA
  EA → ε
  E₁ → EM E₂
  EM → E₂ × EM
  EM → ε
  E₂ → E₃ EP
  EP → ^ E₃ EP
  E₃ → num
  E₃ → (E₀)
  

  لكن جداول CFGS + الأسبقية / الجداول المشتركة لأنها أكثر قابلية للقراءة ولأن أنواع مختلفة من LR المحلل يمكن لمكتبات المولدات إنتاج محلل أكثر كفاءة القضاء على التحول / الحد من النزاعات بدلا من التعامل مع قواعد النحوية التي لا لبس فيها بحجم أكبر.

من الناحية النظرية، جميع المجموعات المحدودة من السلاسل هي لغات منتظمة، وبالتالي فإن جميع البرامج القانونية للحجم المحدود منتظم. نظرا لأن اللغات العادية هي مجموعة فرعية من اللغات المجانية للسياق، فإن جميع برامج الحجم المحتلة خالية من السياق. استمرار الحجة،

على الرغم من أنه يمكن القول بأنه سيكون قيود مقبولا للغة للسماح ببرامج أقل من مليون خط، فليس من العملي وصف لغة البرمجة كقطة منتظمة: سيكون الوصف كبيرا جدا.
- Torben Morgensen أساسيات تصميم مترجم، الفصل. 2.10.2.

الشيء نفسه ينطبق على CFGS. لمعالجة سؤالك الفرعي بشكل مختلف قليلا،

ما لغات البرمجة معرف من قبل القواعد الخالية من السياق؟

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

أمثلة على مواصفات القواعد من البرية:

• BNF لمعيار ML
• bnf مثل ل haskell
• BNF ل SQL.
• YACC Grammar ل PHP

Answer 3

اعتمادا على كيفية فهم السؤال، تتغير الإجابة. لكن Imnsho، الإجابة المناسبة هي أن جميع لغات البرمجة الحديثة في الواقع حساسة للسياق. على سبيل المثال، لا يوجد قواعد حرة سياق يقبل فقط برامج C بتصحيح C.. الأشخاص الذين يشيرون إلى سياق YACC / BISON سياق مجاني ل C يفتقدون النقطة.

Answer 4

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

Answer 5

إذا فهمت سؤالك، فأنت تبحث عن لغات البرمجة التي يمكن وصفها بموجب قواعد النحوية الحرة للسياق (CFG) بحيث يولد CFG جميع البرامج الصحيحة والبرامج الصالحة فقط.

أعتقد أن معظم لغات البرمجة الحديثة (إن لم يكن جميعها) ليست حرة في السياق. على سبيل المثال، بمجرد أن يكون لديك أنواع محددة من قبل المستخدم (شائع جدا باللغات الحديثة)، فإنك حساسة للسياق تلقائيا.

هناك فرق بين التحقق من بناء الجملة والتحقق من صحة الدلالية للبرنامج. فحص بناء الجملة هو خال من السياق، في حين أن التحقق من صحة الدلالية ليس (مرة أخرى، في معظم اللغات).

ومع ذلك، لا يعني ذلك أن مثل هذه اللغة لا يمكن أن توجد. من غير مصنف Lambda Calculus., على سبيل المثال، يمكن وصفها باستخدام قواعد اللغة الحرة السياق، وهي، بالطبع، تورينج كاملة.

Answer 6

معظم لغات البرمجة الحديثة ليست لغات مجانية من السياق. كدليل، إذا قمت بالتحويل إلى جذر CFL الجهاز المقابل، لا يمكن معالجة PDA معالجة String Works {ww | w is a string}. وبعد لذلك تتطلب معظم لغات البرمجة ذلك.

مثال:

int fa; // w
fa=1; // ww as parser treat it like this

Answer 7

VHDL هو حساس للسياق إلى حد ما:

VHDL حساسة للسياق بطريقة متوسطة. النظر في هذا البيان داخل العملية:

jinx := foo(1);

حسنا، اعتمادا على الكائنات المحددة في نطاق العملية (ونطاقاتها المرفوعة)، يمكن أن يكون هذا إما:

• وظيفة الدالة
• فهرسة صفيف
• فهرسة صفيف عاد بواسطة مكالمة وظيفة أقل معلمة

لتحليل هذا بشكل صحيح، يجب أن يحمل المحلل المحلل طاولة رمز هرمي (مع إرفاق النطاقات)، والملف الحالي ليس كافيا. foo يمكن أن تكون وظيفة محددة في الحزمة. لذلك يجب أن يحلل المحلل المحلل أولا الحزم المستوردة بواسطة الملف الذي تحرزه، ومعرفة الرموز المعرفة فيها.

هذا مجرد مثال. نظام VHDL / النوع الفرعي هو فوضى حساسة بالسياق مما يصعب تحليلها.

(ايلي بندرسكي، "تحليل VHDL هو [جدا] الصعب", 2009)

Answer 8

أظن haskell. و مل هي دعم السياق مجانا. انظر الى هذا حلقة الوصل ل haskell.