لماذا يكون التحليل من أسفل إلى أعلى أكثر شيوعًا من التحليل من أعلى إلى أسفل؟

Question

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

لماذا إذن ، يتم تحليل التحليل أكثر شيوعًا من التحليل من أعلى إلى أسفل (أي النسب العودية)؟

Answer 1

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

ويميل المحللون من أسفل إلى أعلى إلى أن يكون فعالًا جدًا. لذلك ، بمجرد أن تدفع سعر القليل من الآلات المعقدة ، من الأسهل كتابة Grammers و Parsers أداء جيد.

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

Answer 2

ينبع من بضعة أشياء مختلفة.

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

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

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

لهذا السبب يستخدم العديد من مجمعي الإنتاج Lexers و Parsers المكتوب يدويًا.

Answer 3

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

يصبح اختلاف الأداء مكبدًا مع زيادة تعقيد القواعد.

Answer 4

للإضافة إلى إجابات أخرى ، من المهم أن ندرك أنه إلى جانب الكفاءة ، يمكن أن يقبل المحللون من أسفل إلى أعلى أكثر بكثير القواعد من محلات السنين العودية. من أعلى إلى أسفل-سواء كانت التنبؤية أو لا يمكن أن يكون لها رمز Lookahead واحد وفشل فقط إذا كان الرمز المميز الحالي وأيًا يتبع ذلك على الفور يمكن اشتقاق الرمز المميز باستخدام قاعدتين مختلفتين. بالطبع ، يمكنك تنفيذ المحلل المحلل للحصول على المزيد من Lookaheads (على سبيل المثال LL (3)) ، ولكن إلى أي مدى أنت على استعداد لدفعه قبل أن يصبح معقدًا مثل محلل من أسفل إلى أعلى؟ من ناحية أخرى ، من ناحية أخرى ، الحفاظ على قائمة من أسفل إلى أعلى (LALR) firsts و follows ويمكن أن يتعامل مع الحالات التي لا يستطيع فيها محللون من أعلى إلى أسفل.

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

Answer 5

لديّ تخمينان ، على الرغم من أنني أشك في أن إما يشرح ذلك تمامًا:

1. يمكن أن يكون التحليل من أعلى إلى أسفل بطيئًا. قد يتطلب محللون المتكررون وقتًا أسيًا لإكمال وظائفهم. هذا من شأنه أن يضع قيودًا شديدة على قابلية التوسع في برنامج التحويل البرمجي الذي يستخدم محللًا من أعلى إلى أسفل.

2. أدوات أفضل. إذا تمكنت من التعبير عن اللغة في متغيرات EBNF ، فمن المحتمل أنه يمكنك lex/yacc في طريقك بعد مجموعة كبيرة من الكود الممل. لا يبدو أن هناك العديد من الأدوات للمساعدة في أتمتة مهمة تجميع محلل من أعلى إلى أسفل. ودعونا نواجه الأمر ، فإن طحن رمز المحللون ليس هو الجزء الممتع من اللعب مع اللغات.

Answer 6

لم أر أبداً مقارنة حقيقية بين محلل النقل من أعلى إلى أسفل وإحالة التحول:

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

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

لذا ، كيف نتحدث بصراحة عن شيء لم نفعله أبدًا: مقارنة بصرامة النهجين؟