التحليل من أعلى إلى أسفل

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

استيعاب التكرارمن جهة اليسار في التحليل من أعلى لأسفل

لا يمكن تحليل قواعد اللغة الرسميةformal grammar التي تحتوي على التكرار من ناحية اليسار  بواسطة محلل الترميز التكراري النموذجي  ما لم يتم تحويلها إلى نموذج متكرر يماثل اليمين. ومع ذلك ، فقد أظهرت الأبحاث الحديثة أنه من الممكن استيعاب القواعد (CFGs) في محلل من أعلى إلى أسفل أكثر تطورا من خلال استخدام تقليص. يصف فروست وحافظ في عام 2006  خوارزمية تقديرية تستوعب القواعد النحوية الغامضة وتقلل توزيعًا مباشرًا متعاظمًا يسارًا متكررًا من خلال فرض قيود على العمق فيما يتعلق بطول الإدخال وموضع الإدخال الحالي.
تم توسيع هذه الخوارزمية لتشمل خوارزمية تحليل تجزئة كاملة لاستيعاب غير مباشر (بمقارنة سياق محسوب سابقًا مع السياق الحالي) بالإضافة إلى التكرار المباشر في زمن كثير الحدود متعددة الحدود ، ولإنشاء تمثيلات صغيرة الحجم متعددة الحدود للعدد الهائل المحتمل لأشجار التحليل قواعد النحو الغامضة للغاية من قبل فروست وحافظ وكالاهان في عام 2007.
تم تطبيق الخوارزمية منذ ذلك الحين كمجموعة من أجهزة تحليل المحلل اللغوي parser combinator]]s]]المكتوبة بلغة برمجة هاسكلهاسكل (لغة برمجة) . يمكن العثور على تفاصيل تنفيذ هذه المجموعة الجديدة من المضاعفات في ورقة
من قبل المؤلفين ، والتي تم تقديمها في PADL'08. يحتوي موقع X-SAIGA  على مزيد من المعلومات حول الخوارزميات وتفاصيل التنفيذ.

مدى تعقيد الزمن والمساحة في التحليل من أعلى لأسفل

عندما يحاول محلل من أعلى إلى أسفل تحليل مدخلات غامضةمغالطات الالتباس  فيما يتعلق ب CFG غامض ، قد يحتاج إلى عدد أسي من الخطوات (فيما يتعلق بطول المدخلات) لتجربة كل بدائل CFG من أجل إنتاج جميع أشجارالتحليل الممكنة ، والتي تتطلب في نهاية المطاف مساحة ذاكرةكبيرة جدا. مشكلة التعقيد للوقت في محللات من أعلى لأسفل تم إنشاؤها كمجموعات من الدوال المتكرّرة متبادلة تم حلها بواسطة نورفيغ بيتير نورفينغ في عام 1991.  أسلوبه مشابه لاستخدام البرمجة الديناميكية ومجموعات الحالات في خوارزمية إيرليEarley's algorithm  في عام (1970) ، والجداول في خوارزمية  خوارزمية CYKالخاصة بـ Cocke و Younger و Kasami.
والفكرة الرئيسية هي تخزين نتائج تطبيق محلل  p   في الموضع  j  في الذاكرة وإعادة استخدام النتائج كلما ظهرت الحالة نفسها. تستخدم فروست ، حافظ و كالاهان
.
أيضًا المذكرات من أجل الامتناع عن إجراء حسابات زائدة عن الحاجة لاستيعاب أي شكل من أشكال CFG في زمن كثير الحدود  متعددة الحدود  التي تأخذ زمن (Θ(n⁴) for left-recursive grammars and Θ(n³) for non left-recursive grammars) للقواعد النحوية غير المتكررة. كما تتطلب خوارزمية التوزيع من أعلى لأسفل أيضًا مساحة متعددة الحدود لأشكال تحليل غامضة أضافية من خلال "التمثيل الصغير" و "تجميع الغموض المحلي". تمثيلهم المدمج قابل للمقارنة مع تمثيل 
Tomita’s compact للتحليل bottom-up parsingمن أسفل إلى أعلى.
باستخدام PEG ، تمثيل آخر من القواعد النحوية ، يوفر محللو packrat خوارزمية تحليل أنيقة وقوية. راجعParsing expression grammar.