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

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

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

يمكن النظر إلى التحليل من أعلى إلى أسفل على أنه محاولة للعثور على مشتقات أقصى اليسار من تدفق المدخلات من خلال البحث عن أشجار غير متماثلة باستخدام شجرة التحليل توسع من أعلى إلى أسفل لقواعد القواعد الرسمية المحددة. يتم استخدام الخيار الشامل لاستيعاب الغموض من خلال توسيع جميع الجوانب اليمنى من القواعد النحوية. ^[1]

لا يتم إنهاء التطبيقات البسيطة للتحليل من أعلى لأسفل لقواعد النحو المتتالية شجرة التحليل، ويمكن أن يكون للتحليل من أعلى لأسفل مع التراجع تعقيدًا زمنيًا أسيًا فيما يتعلق بطول مدخلاتCFGs الغامضةformal grammar. ^[2]

تطبيق لغة برمجة

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

على سبيل المثال:

$A \to a B C$
$B \to c ∣ c d$
$C \to d f ∣ e g$

its string will be A=acdf

string(كلمة ثابتة تعبير عن نوع البيانات المكونة من سلسلة نصية).

يتطابق $A \to a B C$ ومحاولة مطابقة $B \to c ∣ c d$ ثم $C \to d f ∣ e g$ يتم تجربتة. كما قد يتوقع المرء، تكون بعض اللغات أكثر غموضا من غيرهامغالطات الالتباس. بالنسبة إلى لغة غير غامضة تنتج فيها جميع الإنتاجات عن غير طرفية سلاسل مميزة: فالسلسلة التي ينتجها أحد الإنتاج لن تبدأ بنفس الرمز كالسلسلة التي ينتجها إنتاج آخر. قد يتم تحليل لغة غير غامضة بقواعد (LL (1 حيث تشير (1) إلى أن المحلل اللغوي يقرأ أمام رمز مميز في المرة الواحدة. للحصول على لغة غامضة ليتم تحليلها بواسطة محلل LL ، يجب على المحلل أن يبحث أكثر من رمز واحد، على سبيل المثال. (LL (3.

يتمثل الحل المشترك لهذه المشكلة في استخدام محلل مجزئ يسار يمين، وهو نوع من المحلل اللغوي المختزلshift-reduce parser ، ويقوم بتحليل من أسفل إلى أعلى bottom-up parsing.

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

لا يمكن تحليل قواعد اللغة الرسميةformal grammar التي تحتوي على التكرار من ناحية اليسار بواسطة محلل الترميز التكراري النموذجي ما لم يتم تحويلها إلى نموذج متكرر يماثل اليمين. ومع ذلك، فقد أظهرت الأبحاث الحديثة أنه من الممكن استيعاب القواعد (CFGs) في محلل من أعلى إلى أسفل أكثر تطورا من خلال استخدام تقليص. يصف فروست وحافظ في عام 2006 ^[3] خوارزمية تقديرية تستوعب القواعد النحوية الغامضة وتقلل توزيعًا مباشرًا متعاظمًا يسارًا متكررًا من خلال فرض قيود على العمق فيما يتعلق بطول الإدخال وموضع الإدخال الحالي.

تم توسيع هذه الخوارزمية لتشمل خوارزمية تحليل تجزئة كاملة لاستيعاب غير مباشر (بمقارنة سياق محسوب سابقًا مع السياق الحالي) بالإضافة إلى التكرار المباشر في زمن كثير الحدود متعددة الحدود، ولإنشاء تمثيلات صغيرة الحجم متعددة الحدود للعدد الهائل المحتمل لأشجار التحليل قواعد النحو الغامضة للغاية من قبل فروست وحافظ وكالاهان في عام 2007.
^[4]

تم تطبيق الخوارزمية منذ ذلك الحين كمجموعة من أجهزة تحليل المحلل اللغوي parser combinator]]s]]المكتوبة بلغة برمجة هاسكلهاسكل (لغة برمجة) . يمكن العثور على تفاصيل تنفيذ هذه المجموعة الجديدة من المضاعفات في ورقة ^[5]

من قبل المؤلفين، والتي تم تقديمها في PADL'08. يحتوي موقع X-SAIGA [1] على مزيد من المعلومات حول الخوارزميات وتفاصيل التنفيذ.

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

عندما يحاول محلل من أعلى إلى أسفل تحليل مدخلات غامضةمغالطات الالتباس فيما يتعلق ب CFG غامض، قد يحتاج إلى عدد أسي من الخطوات (فيما يتعلق بطول المدخلات) لتجربة كل بدائل CFG من أجل إنتاج جميع أشجارالتحليل الممكنة، والتي تتطلب في نهاية المطاف مساحة ذاكرة كبيرة جدا. مشكلة التعقيد للوقت في محللات من أعلى لأسفل تم إنشاؤها كمجموعات من الدوال المتكرّرة متبادلة تم حلها بواسطة نورفيغ بيتير نورفينغ في عام 1991.^[6] أسلوبه مشابه لاستخدام البرمجة الديناميكية ومجموعات الحالات في خوارزمية إيرليEarley's algorithm في عام (1970)، والجداول في خوارزمية خوارزمية CYKالخاصة بـ Cocke و Younger و Kasami.

والفكرة الرئيسية هي تخزين نتائج تطبيق محلل p في الموضع j في الذاكرة وإعادة استخدام النتائج كلما ظهرت الحالة نفسها. تستخدم فروست، حافظ وكالاهان .^[4]^[5] أيضًا المذكرات من أجل الامتناع عن إجراء حسابات زائدة عن الحاجة لاستيعاب أي شكل من أشكال CFG في زمن كثير الحدود متعددة الحدود التي تأخذ زمن (Θ(n⁴) for left-recursive grammars and Θ(n³) for non left-recursive grammars) للقواعد النحوية غير المتكررة. كما تتطلب خوارزمية التوزيع من أعلى لأسفل أيضًا مساحة متعددة الحدود لأشكال تحليل غامضة أضافية من خلال «التمثيل الصغير» و «تجميع الغموض المحلي». تمثيلهم المدمج قابل للمقارنة مع تمثيل

Tomita’s compact للتحليل bottom-up parsingمن أسفل إلى أعلى.

^[7]

باستخدام PEG ، تمثيل آخر من القواعد النحوية، يوفر محللو packrat خوارزمية تحليل أنيقة وقوية. راجعParsing expression grammar.

الأمثلة

تتضمن بعض المحللون الذين يستخدمون التحليل من أعلى إلى أسفل ما يلي:

انظر أيضا

تجزئة

المراجع

^ Aho، Alfred V.؛ Sethi، Ravi؛ Ullman، Jeffrey D. (1986). Compilers, principles, techniques, and tools (ط. Rep. with corrections.). Addison-Wesley Pub. Co. ISBN:978-0201100884. مؤرشف من الأصل في 2020-09-11.
^ Aho، Alfred V.؛ Ullman، Jeffrey D. (1972). The Theory of Parsing, Translation, and Compiling (Volume 1: Parsing.) (ط. Repr.). Englewood Cliffs, NJ: Prentice-Hall. ISBN:978-0139145568. مؤرشف من الأصل في 2019-12-16.
^ Frost, R. and Hafiz, R. (2006) " A New Top-Down Parsing Algorithm to Accommodate Ambiguity and Left Recursion in Polynomial Time." ACM SIGPLAN Notices, Volume 41 Issue 5, Pages: 46 - 54.
^ ^أ ^ب Frost, R., Hafiz, R. and Callaghan, P. (2007) " Modular and Efficient Top-Down Parsing for Ambiguous Left-Recursive Grammars ." 10th International Workshop on Parsing Technologies (IWPT), ACL-SIGPARSE , Pages: 109 - 120, June 2007, Prague.
^ ^أ ^ب Frost, R., Hafiz, R. and Callaghan, P. (2008) " Parser Combinators for Ambiguous Left-Recursive Grammars." 10th International Symposium on Practical Aspects of Declarative Languages (PADL), ACM-SIGPLAN , Volume 4902/2008, Pages: 167-181, January 2008, San Francisco.
^ Norvig, P. (1991) “Techniques for automatic memoisation with applications to context-free parsing.” Journal - Computational Linguistics Volume 17, Issue 1, Pages: 91 - 98.
^ Tomita, M. (1985) “Efficient Parsing for Natural Language.” Kluwer, Boston, MA.
^ Pereira, Fernando CN, and David HD Warren. "Definite clause grammars for language analysis—a survey of the formalism and a comparison with augmented transition networks." Artificial intelligence 13.3 (1980): 231-278. نسخة محفوظة 09 أغسطس 2017 على موقع واي باك مشين.

روابط إضافية

X-SAIGA - eXecutable SpecificAtIons of GrAmmars

قالب:Parsers

[AhoSethiUllman_1986-1] Aho، Alfred V.؛ Sethi، Ravi؛ Ullman، Jeffrey D. (1986). Compilers, principles, techniques, and tools (ط. Rep. with corrections.). Addison-Wesley Pub. Co. ISBN:978-0201100884. مؤرشف من الأصل في 2020-09-11.

[AhoUllman_1972-2] Aho، Alfred V.؛ Ullman، Jeffrey D. (1972). The Theory of Parsing, Translation, and Compiling (Volume 1: Parsing.) (ط. Repr.). Englewood Cliffs, NJ: Prentice-Hall. ISBN:978-0139145568. مؤرشف من الأصل في 2019-12-16.

[FrostHafiz2006-3] Frost, R. and Hafiz, R. (2006) " A New Top-Down Parsing Algorithm to Accommodate Ambiguity and Left Recursion in Polynomial Time." ACM SIGPLAN Notices, Volume 41 Issue 5, Pages: 46 - 54.

[FrostHafizCallaghan_2007-4] أ ^ب Frost, R., Hafiz, R. and Callaghan, P. (2007) " Modular and Efficient Top-Down Parsing for Ambiguous Left-Recursive Grammars ." 10th International Workshop on Parsing Technologies (IWPT), ACL-SIGPARSE , Pages: 109 - 120, June 2007, Prague.

[FrostHafizCallaghan_2008-5] أ ^ب Frost, R., Hafiz, R. and Callaghan, P. (2008) " Parser Combinators for Ambiguous Left-Recursive Grammars." 10th International Symposium on Practical Aspects of Declarative Languages (PADL), ACM-SIGPLAN , Volume 4902/2008, Pages: 167-181, January 2008, San Francisco.

[Norvig_1991-6] Norvig, P. (1991) “Techniques for automatic memoisation with applications to context-free parsing.” Journal - Computational Linguistics Volume 17, Issue 1, Pages: 91 - 98.

[Tomita1985-7] Tomita, M. (1985) “Efficient Parsing for Natural Language.” Kluwer, Boston, MA.

[8] Pereira, Fernando CN, and David HD Warren. "Definite clause grammars for language analysis—a survey of the formalism and a comparison with augmented transition networks." Artificial intelligence 13.3 (1980): 231-278. نسخة محفوظة 09 أغسطس 2017 على موقع واي باك مشين.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]