لماذا لا C++ يكون تحليل مع LR(1) محلل?

Question

كنت أقرأ عن موزعي و محلل مولدات وجدت هذا البيان في ويكيبيديا LR تحليل -الصفحة:

العديد من لغات البرمجة يمكن تحليل باستخدام بعض الاختلاف من LR parser.استثناء واحد هو C++.

لماذا هو كذلك ؟ خاصة ما ملك C++ أسباب ذلك أن يكون من المستحيل تحليل مع LR موزعي?

باستخدام جوجل, لقد وجدت أن ج يمكن أن يكون تماما مع تحليل LR(1) ولكن يتطلب C++ LR(∞).

Answer 1

وهناك موضوع مثير للاهتمام على امدا في نهاية المطاف أن يناقش في قواعد اللغة LALR لC ++ .

وويتضمن وصلة ل رسالة الدكتوراه يتضمن مناقشة توزيع C ++، التي تنص على ما يلي:

<اقتباس فقرة>   

و"C ++ قواعد غامضة،   السياق تعتمد ويحتمل أن تكون   يتطلب lookahead لا نهائية لحل   بعض النقاط الغامضة ".

ووغني عن إعطاء عدد من الأمثلة (انظر الصفحة 147 من قوات الدفاع الشعبي).

والمثال هو:

int(x), y, *const z;

ومعنى

int x;
int y;
int *const z;

وقارن إلى:

int(x), y, new int;

ومعنى

(int(x)), (y), (new int));

و(تعبير مفصولة بفواصل).

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

Answer 2

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

C و C++ كل تسمح البيان التالي:

x * y ;

فقد اثنين من مختلف يوزع:

1. يمكن أن يكون الإعلان من y ، مؤشر إلى نوع x
2. ويمكن أن يكون ضرب من x و y, رمي الجواب.

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

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

وهكذا نقية LR تحليل لا يمكن التعامل مع هذا.ولا يمكن أن أخرى كثيرة متاحة على نطاق واسع محلل مولدات مثل Antlr, JavaCC, YACC ، أو التقليدية البيسون ، أو حتى ربط على غرار موزعي المستخدمة في "نقية" وسيلة.

وهناك الكثير من الحالات الأكثر تعقيدا (توزيع قالب جملة يتطلب التعسفي lookahead ، بينما LALR(ك) يمكن أن نتطلع إلى الأمام في معظم k الرموز) ، ولكن فقط فإنه يأخذ واحد فقط بالدليل لاسقاط نقية LR (أو الآخرين) تحليل.

الأكثر حقيقية C/C++ موزعي التعامل مع هذا المثال عن طريق استخدام بعض نوع من القطعية محلل إضافية الإختراق:أنها تتشابك مع تحليل رمز الجدول جمع...حتى أنه بحلول الوقت "x" هو واجهتها ، محلل يعرف إذا كان x هو نوع أو لا ، وبالتالي يمكن أن اختيار بين اثنين من المحتمل يوزع.ولكن محلل لا ليس هذا السياق مجانا, LR موزعي (نقية منها ، إلخ.) هي (في أحسن الأحوال) السياق مجانا.

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

و إذا كنت الغش بما فيه الكفاية, يمكنك جعل LR موزعي العمل C و C++.دول مجلس التعاون الخليجي الرجال للحظة ، ولكن أعطاه حتى من ناحية مشفرة تحليل أعتقد لأنهم أرادوا أفضل خطأ التشخيص.

هناك نهج آخر ، على الرغم مما جميلة ونظيفة ويوزع C و C++ على ما يرام دون أي رمز الجدول hackery: GLR موزعي.هذه هي كاملة السياق مجانا موزعي (وجود فعال لانهائية lookahead).GLR موزعي تقبل ببساطة سواء يوزع إنتاج مجموعة "الشجرة" (في الواقع موجهة احلقي البياني الذي هو في الغالب مثل شجرة) الذي يمثل غامضة تحليل.بعد تحليل تمرير حل الغموض.

نحن نستخدم هذه التقنية في C و C++ مقدمة لدينا DMS برنامج إعادة الهيكلة Tookit (اعتبارا من يونيو من عام 2017 هذه التعامل الكامل C++17 في مرض التصلب العصبي المتعدد و غنو اللهجات).كانت عملية الملايين من خطوط الكبيرة C و C++ أنظمة كاملة ودقيقة يوزع إنتاج ASTs مع تفاصيل كاملة من التعليمات البرمجية المصدر.(انظر AST C++'ق الأكثر إرباكا تحليل.)

Answer 3

المشكلة لم يعرف مثل هذا ، في حين ينبغي أن تكون مثيرة للاهتمام :

ما هو أصغر مجموعة من التعديلات على C++ اللغة التي سيكون من الضروري جدا أن هذه القواعد الجديدة يمكن أن يكون تماما تحليل من قبل "غير الخالية من السياق" yacc محلل ?(الاستفادة فقط من أحد "الإختراق":على typename/معرف توضيح ، محلل إعلام lexer من كل الرموز المميزة ل typedef/الطبقة/البنية)

أرى بعض منها:

1. Type Type; هو ممنوع.معرف كما أعلن typename لا يمكن أن تصبح غير typename معرف (لاحظ أن struct Type Type لا غموض فيه ولا يمكن أن يكون لا يزال يسمح).

   هناك 3 أنواع من names tokens :

   • types :مدمج من نوع أو بسبب typedef/الطبقة/البنية
   • قالب-وظائف
   • المعرفات :وظائف/أساليب المتغيرات/الكائنات

   النظر في قالب وظائف مختلفة مثل الرموز يحل func< الغموض.إذا func هو قالب-اسم الدالة ثم < يجب أن يكون بداية قالب قائمة المعلمة ، وإلا func هو مؤشر دالة < هو عامل المقارنة.

2. Type a(2); هو كائن مثيل.Type a(); و Type a(int) هي نماذج وظيفة.

3. int (k); ممنوع تماما, يجب أن تكون مكتوبة int k;

4. typedef int func_type(); و typedef int (func_type)(); هي المحرمة.

   وظيفة الرموز المميزة ل typedef يجب أن تكون وظيفة مؤشر typedef : typedef int (*func_ptr_type)();

5. قالب العودية يقتصر على 1024 ، وإلا زيادة الحد الأقصى يمكن أن تكون مرت باعتبارها الخيار برنامج التحويل البرمجي.

6. int a,b,c[9],*d,(*f)(), (*g)()[9], h(char); يمكن أن يكون ممنوعا أيضا ، استبداله int a,b,c[9],*d; int (*f)();

   int (*g)()[9];

   int h(char);

   خط واحد لكل وظيفة النموذج أو وظيفة مؤشر الإعلان.

   جدا يفضل يكون البديل هو تغيير فظيعة مؤشر وظيفة الجملة ،

   int (MyClass::*MethodPtr)(char*);

   يجري resyntaxed مثل:

   int (MyClass::*)(char*) MethodPtr;

   هذا التماسك مع المدلى بها المشغل (int (MyClass::*)(char*))

7. typedef int type, *type_ptr; يمكن أن يكون ممنوعا أيضا :خط واحد لكل الرموز المميزة ل typedef.وبالتالي يصبح

   typedef int type;

   typedef int *type_ptr;

8. sizeof int, sizeof char, sizeof long long و شارك.يمكن أن يعلن في كل ملف المصدر.وهكذا كل مصدر الملف والاستفادة من نوع int يجب أن تبدأ مع

   #type int : signed_integer(4)

   و unsigned_integer(4) سيكون المحرمة خارج #type التوجيه هذا من شأنه أن يكون خطوة كبيرة في الغباء sizeof int غموض موجودة في الكثير من C++ رؤوس

مترجم تنفيذ resyntaxed C++ إذا تواجه C++ المصدر الاستفادة من غموض الجملة ، نقل source.cpp أيضا ambiguous_syntax المجلد ، و من شأنه أن يخلق تلقائيا لا لبس فيه ترجمة source.cpp قبل جمعها.

يرجى إضافة غامضة C++ جمل إذا كنت تعرف بعض!

Answer 4

كما يمكنك أن ترى في بلدي الجواب هنا, C++ يحتوي على الجملة التي لا يمكن deterministically تحليل قبل ليرة لبنانية أو LR parser بسبب نوع القرار مرحلة (عادة بعد تحليل) تغيير ترتيب العمليات, وبالتالي الأساسية شكل AST (عادة من المتوقع أن تقدم أول مرحلة تحليل).

Answer 5

وأعتقد أنك جميلة قريبة من الجواب.

وLR (1) يعني أن تحليل من اليسار إلى اليمين الاحتياجات رمز واحد فقط أن ننظر للأمام للسياق، في حين يعني LR (∞) لانهائي نظرة إلى الأمام. وهذا هو، فإن محلل أن تعرف كل ما هو آت من أجل معرفة أين هو عليه الآن.

Answer 6

وو"typedef و" المشكلة في C ++ يمكن تحليل مع LALR (1) محلل أن يبني جدول الرموز أثناء تحليل (وليس محلل LALR النقي). في "قالب" مشكلة ربما لا يمكن حلها مع هذا الأسلوب. وميزة هذا النوع من LALR (1) محلل هي أن قواعد اللغة (كما هو موضح أدناه) هو (1) قواعد LALR (أي غموض).

/* C Typedef Solution. */

/* Terminal Declarations. */

   <identifier> => lookup();  /* Symbol table lookup. */

/* Rules. */

   Goal        -> [Declaration]... <eof>               +> goal_

   Declaration -> Type... VarList ';'                  +> decl_
               -> typedef Type... TypeVarList ';'      +> typedecl_

   VarList     -> Var /','...     
   TypeVarList -> TypeVar /','...

   Var         -> [Ptr]... Identifier 
   TypeVar     -> [Ptr]... TypeIdentifier                               

   Identifier     -> <identifier>       +> identifier_(1)      
   TypeIdentifier -> <identifier>      =+> typedefidentifier_(1,{typedef})

// The above line will assign {typedef} to the <identifier>,  
// because {typedef} is the second argument of the action typeidentifier_(). 
// This handles the context-sensitive feature of the C++ language.

   Ptr          -> '*'                  +> ptr_

   Type         -> char                 +> type_(1)
                -> int                  +> type_(1)
                -> short                +> type_(1)
                -> unsigned             +> type_(1)
                -> {typedef}            +> type_(1)

/* End Of Grammar. */

ويمكن تحليل المدخلات التالية دون مشكلة:

 typedef int x;
 x * y;

 typedef unsigned int uint, *uintptr;
 uint    a, b, c;
 uintptr p, q, r;

LRSTAR محلل مولد يقرأ تدوين القواعد أعلاه ويولد محلل أن يعالج "typedef و" المشكلة دون غموض في شجرة تحليل أو AST. (الكشف: أنا الرجل الذي خلق LRSTAR).