التحليل من أعلى إلى أسفل
في البداية، في علم الحاسب، التحليل من أعلى لأسفل هو إستراتيجية إعراب حيث ينظر المرء أولاً إلى أعلى مستوى من شجرة التحليل تجزئة ويعمل أسفل شجرة التحليل باستخدام قواعد إعادة الكتابة لقواعد اللغة الرسمية formal grammar. محلل المحلل اللغوي LL نوع من محلل يستعمل إستراتيجية تحليل من أعلى إلى أسفل. ونتناول فيما يلي مزيدًا من التفاصيل.
إضافةً إلى ذلك، التحليل من أعلى لأسفل هو إستراتيجية لتحليل علاقات البيانات غير المعروفة من خلال فرضية هياكل شجرة التحليل تجزئةالعام ثم التفكير فيما إذا كانت الهياكل الأساسية المعروفة متوافقة مع الفرضية. يحدث في تحليل كل من اللغات الطبيعية لغةولغات الكمبيوترلغة حاسوبية.
من جهة ثانية، يمكن النظر إلى التحليل من أعلى إلى أسفل على أنه محاولة للعثور على مشتقات أقصى اليسار من تدفق المدخلات من خلال البحث عن أشجار غير متماثلة باستخدام شجرة التحليل توسع من أعلى إلى أسفل لقواعد القواعد الرسمية المحددة. يتم استخدام الخيار الشامل لاستيعاب الغموض من خلال توسيع جميع الجوانب اليمنى من القواعد النحوية.
وعلى صعيد آخر، لا يتم إنهاء التطبيقات البسيطة للتحليل من أعلى لأسفل لقواعد النحو المتتالية شجرة التحليل، ويمكن أن يكون للتحليل من أعلى لأسفل مع التراجع تعقيدًا زمنيًا أسيًا فيما يتعلق بطول مدخلاتCFGs الغامضةformal grammar.
its string will be A=acdf
ومن جهة أخرى، عندما يحاول محلل من أعلى إلى أسفل تحليل مدخلات غامضةمغالطات الالتباس فيما يتعلق ب CFG غامض، قد يحتاج إلى عدد أسي من الخطوات (فيما يتعلق بطول المدخلات) لتجربة كل بدائل CFG من أجل إنتاج جميع أشجارالتحليل الممكنة، والتي تتطلب في نهاية المطاف مساحة ذاكرة كبيرة جدا. مشكلة التعقيد للوقت في محللات من أعلى لأسفل تم إنشاؤها كمجموعات من الدوال المتكرّرة متبادلة تم حلها بواسطة نورفيغ بيتير نورفينغ في سنة 1991. أسلوبه مشابه لاستخدام البرمجة الديناميكية ومجموعات الحالات في خوارزمية إيرليEarley's algorithm في عام (1970)، والجداول في خوارزمية خوارزمية CYKالخاصة بـ Cocke و Younger و Kasami.
من جهة ثانية، من قبل المؤلفين، والتي تم تقديمها في PADL'08. يحتوي موقع X-SAIGA على مزيد من المعلومات حول الخوارزميات وتفاصيل التنفيذ.
وفي السياق ذاته، تم توسيع هذه الخوارزمية لتشمل خوارزمية تحليل تجزئة كاملة لاستيعاب غير مباشر (بمقارنة سياق محسوب سابقًا مع السياق الحالي) فضلًا عن التكرار المباشر في زمن كثير الحدود متعددة الحدود، ولإنشاء تمثيلات صغيرة الحجم متعددة الحدود للعدد الهائل المحتمل لأشجار التحليل قواعد النحو الغامضة للغاية من قبل فروست وحافظ وكالاهان في عام 2007.
في هذا الإطار، باستخدام PEG ، تمثيل آخر من القواعد النحوية، يوفر محللو packrat خوارزمية تحليل أنيقة وقوية. راجعParsing expression grammar.
Tomita’s compact للتحليل bottom-up parsingمن أسفل إلى أعلى.
.
وفي السياق ذاته، كذلك المذكرات من أجل الامتناع عن إجراء حسابات زائدة عن الحاجة لاستيعاب أي شكل من أشكال CFG في زمن كثير الحدود متعددة الحدود التي تأخذ زمن (Θ(n4) for left-recursive grammars and Θ(n3) for non left-recursive grammars) للقواعد النحوية غير المتكررة. كما تتطلب خوارزمية التوزيع من أعلى لأسفل كذلك مساحة متعددة الحدود لأشكال تحليل غامضة أضافية من خلال «التمثيل الصغير» و «تجميع الغموض المحلي». تمثيلهم المدمج قابل للمقارنة مع تمثيل
من جانب آخر، يتمثل الحل المشترك لهذه المشكلة في استخدام محلل مجزئ يسار يمين، وهو نوع من المحلل اللغوي المختزلshift-reduce parser ، ويقوم بتحليل من أسفل إلى أعلى bottom-up parsing.
يتطابق ومحاولة مطابقة ثم يتم تجربتة.
مدى تعقيد الزمن والمساحة في التحليل من أعلى لأسفل
من جهة ثانية، تم تطبيق الخوارزمية منذ ذلك الحين كمجموعة من أجهزة تحليل المحلل اللغوي parser combinatorsالمكتوبة بلغة برمجة هاسكلهاسكل (لغة برمجة) . يمكن العثور على تفاصيل تنفيذ هذه المجموعة الجديدة من المضاعفات في ورقة
استيعاب التكرارمن جهة اليسار في التحليل من أعلى لأسفل
وفي هذا الصدد، كما قد يتوقع المرء، تكون بعض اللغات أكثر غموضا من غيرهامغالطات الالتباس. بالنسبة إلى لغة غير غامضة تنتج فيها جميع الإنتاجات عن غير طرفية سلاسل مميزة: فالسلسلة التي ينتجها أحد الإنتاج لن تبدأ بنفس الرمز كالسلسلة التي ينتجها إنتاج آخر. قد يتم تحليل لغة غير غامضة بقواعد (LL (1 حيث تشير (1) إلى أن المحلل اللغوي يقرأ أمام رمز مميز في المرة الواحدة. للحصول على لغة غامضة ليتم تحليلها بواسطة محلل LL ، يجب على المحلل أن يبحث أكثر من رمز واحد، مثلًا. (LL (3.
وفي السياق ذاته، string(كلمة ثابتة تعبير عن نوع البيانات المكونة من سلسلة نصية).
كذلك، والفكرة الرئيسية هي تخزين نتائج تطبيق محلل p في الموضع j في الذاكرة وإعادة استخدام النتائج كلما ظهرت الحالة نفسها. تستعمل فروست، حافظ وكالاهان
إضافةً إلى ذلك، لا يمكن تحليل قواعد اللغة الرسميةformal grammar التي تحتوي على التكرار من ناحية اليسار بواسطة محلل الترميز التكراري النموذجي ما لم يتم تحويلها إلى نموذج متكرر يماثل اليمين. ومع ذلك، فقد أظهرت الأبحاث الحديثة أنه من الممكن استيعاب القواعد (CFGs) في محلل من أعلى إلى أسفل أكثر تطورا من خلال استخدام تقليص. يصف فروست وحافظ في سنة 2006 خوارزمية تقديرية تستوعب القواعد النحوية الغامضة وتقلل توزيعًا مباشرًا متعاظمًا يسارًا متكررًا من خلال فرض قيود على العمق فيما يتعلق بطول الإدخال وموضع الإدخال الحالي.
تطبيق لغة برمجة
من جانب آخر، يوزع المحول البرمجي محول برمجي مدخلات من لغة برمجة إلى تمثيل داخلي عن طريق مطابقة الرموز الواردة مع قواعد الإنتاجproduction rules. يتم تعريف قواعد الإنتاج عادة باستخدام نموذج صيغة باكوس نور. محلل المحلل اللغوي LL هو نوع من المحلل اللغوي الذي يقوم بإجراء تحليل من أعلى لأسفل عن طريق تطبيق كل قاعدة إنتاج على الرموز الواردة، والعمل من رمز أقصى اليسار الناتج في قاعدة الإنتاج ثم المتابعة إلى قاعدة الإنتاج التالية لكل رمز غير طرفية واجهت. وبهذه الطريقة يبدأ التحليل على يسار جانب النتيجة (الجانب الأيمن) لقاعدة الإنتاج ويقيم النهايات غير الطرفية من اليسار أولاً، وبالتالي، يستمر في خفض شجرة التحليل لكل جديد غير طرفية قبل المتابعة إلى التالي رمز لقاعدة الإنتاج.
مثلًا:
الأمثلة
- تتضمن بعض المحللون الذين يستعملون التحليل من أعلى إلى أسفل ما يلي:
- Definite clause grammar parsers
- الترميز التكراري النموذجي
- الترميز التكراري النموذجي
- Earley parser
- انظر كذلك
- تجزئة
- المراجع
- روابط إضافية
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟