عرض مصدر التحليل من أعلى إلى أسفل

{{يتيمة|تاريخ=أبريل 2018}}
{{عن|3=التحليل من أعلى إلى أسفل(Top-down parsing)}}

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

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

يمكن النظر إلى التحليل من أعلى إلى أسفل على أنه محاولة للعثور على مشتقات أقصى اليسار من تدفق المدخلات من خلال البحث عن أشجار غير متماثلة باستخدام [[شجرة التحليل]] توسع من أعلى إلى أسفل لقواعد القواعد الرسمية المحددة. يتم استخدام الخيار الشامل لاستيعاب الغموض من خلال توسيع جميع الجوانب اليمنى من القواعد النحوية.
<ref name="AhoSethiUllman 1986">{{استشهاد بكتاب |الأخير1=Aho |الأول1=Alfred V. |مؤلف1-وصلة=Alfred Aho |الأخير2=Sethi |الأول2=Ravi |مؤلف2-وصلة=Ravi Sethi |الأخير3=Ullman |الأول3=Jeffrey D. |مؤلف3-وصلة=Jeffrey Ullman |عنوان=Compilers, principles, techniques, and tools |سنة=1986 |ناشر=Addison-Wesley Pub. Co. |isbn=978-0201100884 |طبعة=Rep. with corrections. |url-access=registration |مسار=https://archive.org/details/compilersprincip00ahoa | مسار أرشيف = https://web.archive.org/web/20200911110338/https://archive.org/details/compilersprincip00ahoa | تاريخ أرشيف = 11 سبتمبر 2020 }}</ref>

لا يتم إنهاء التطبيقات البسيطة للتحليل من أعلى لأسفل لقواعد النحو المتتالية [[شجرة التحليل]]، ويمكن أن يكون للتحليل من أعلى لأسفل مع التراجع تعقيدًا زمنيًا أسيًا فيما يتعلق بطول مدخلاتCFGs الغامضة[[formal grammar]].
<ref name="AhoUllman 1972">{{استشهاد بكتاب |الأخير1=Aho |الأول1=Alfred V. |مؤلف1-وصلة=Alfred Aho |الأخير2=Ullman |الأول2=Jeffrey D. |مؤلف2-وصلة=Jeffrey Ullman |عنوان=The Theory of Parsing, Translation, and Compiling (Volume 1: Parsing.) |سنة=1972 |ناشر=Prentice-Hall |مكان=Englewood Cliffs, NJ |isbn=978-0139145568 |طبعة=Repr. |url-access=registration |مسار=https://archive.org/details/theoryofparsingt00ahoa | مسار أرشيف = https://web.archive.org/web/20191216211812/https://archive.org/details/theoryofparsingt00ahoa | تاريخ أرشيف = 16 ديسمبر 2019 }}</ref>
== تطبيق لغة برمجة ==
يوزع المحول البرمجي [[مصرف (حوسبة)|محول برمجي]] مدخلات من لغة برمجة إلى تمثيل داخلي عن طريق مطابقة الرموز الواردة مع قواعد الإنتاج[[Formal grammar#The syntax of grammars|production rules]]. يتم تعريف قواعد الإنتاج عادة باستخدام نموذج [[صيغة باكوس نور]]. محلل [[المحلل اللغوي LL]] هو نوع من المحلل اللغوي الذي يقوم بإجراء تحليل من أعلى لأسفل عن طريق تطبيق كل قاعدة إنتاج على الرموز الواردة، والعمل من رمز أقصى اليسار الناتج في قاعدة الإنتاج ثم المتابعة إلى قاعدة الإنتاج التالية لكل رمز غير طرفية واجهت. وبهذه الطريقة يبدأ التحليل على يسار جانب النتيجة (الجانب الأيمن) لقاعدة الإنتاج ويقيم النهايات غير الطرفية من اليسار أولاً، وبالتالي، يستمر في خفض شجرة التحليل لكل جديد غير طرفية قبل المتابعة إلى التالي رمز لقاعدة الإنتاج.

على سبيل المثال:
* <math>A \rightarrow aBC</math>
* <math>B \rightarrow c \mid cd</math>
* <math>C \rightarrow df \mid eg</math>

its string will be A=acdf

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

يتطابق <math>A \rightarrow aBC</math>ومحاولة مطابقة <math>B \rightarrow c \mid cd</math> ثم <math>C \rightarrow df \mid eg</math> يتم تجربتة.
كما قد يتوقع المرء، تكون بعض اللغات أكثر غموضا من غيرها[[مغالطات الالتباس]]. بالنسبة إلى لغة غير غامضة تنتج فيها جميع الإنتاجات عن غير طرفية سلاسل مميزة: فالسلسلة التي ينتجها أحد الإنتاج لن تبدأ بنفس الرمز كالسلسلة التي ينتجها إنتاج آخر. قد يتم تحليل لغة غير غامضة بقواعد (LL (1 حيث تشير (1) إلى أن المحلل اللغوي يقرأ أمام رمز مميز في المرة الواحدة. للحصول على لغة غامضة ليتم تحليلها بواسطة محلل LL ، يجب على المحلل أن يبحث أكثر من رمز واحد، على سبيل المثال. (LL (3.

يتمثل الحل المشترك لهذه المشكلة في استخدام محلل [[مجزئ يسار يمين]]، وهو نوع من المحلل اللغوي المختزل[[shift-reduce parser]] ، ويقوم بتحليل من أسفل إلى أعلى [[bottom-up parsing]].
== استيعاب التكرارمن جهة اليسار في التحليل من أعلى لأسفل ==
لا يمكن تحليل قواعد اللغة الرسمية[[formal grammar]] التي تحتوي على التكرار من ناحية اليسار بواسطة محلل [[الترميز التكراري النموذجي]] ما لم يتم تحويلها إلى نموذج متكرر يماثل اليمين. ومع ذلك، فقد أظهرت الأبحاث الحديثة أنه من الممكن استيعاب القواعد ([[قواعد خالية من السياق|CFGs]]) في محلل من أعلى إلى أسفل أكثر تطورا من خلال استخدام تقليص. يصف فروست وحافظ في عام 2006 <ref name="FrostHafiz2006">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.</ref> خوارزمية تقديرية تستوعب القواعد النحوية الغامضة وتقلل توزيعًا مباشرًا متعاظمًا يسارًا متكررًا من خلال فرض قيود على العمق فيما يتعلق بطول الإدخال وموضع الإدخال الحالي.

 تم توسيع هذه الخوارزمية لتشمل خوارزمية تحليل [[تجزئة (لغة)|تجزئة]] كاملة لاستيعاب غير مباشر (بمقارنة سياق محسوب سابقًا مع السياق الحالي) بالإضافة إلى التكرار المباشر في زمن كثير الحدود [[متعددة الحدود]]، ولإنشاء تمثيلات صغيرة الحجم متعددة الحدود للعدد الهائل المحتمل لأشجار التحليل قواعد النحو الغامضة للغاية من قبل فروست وحافظ وكالاهان في عام 2007.
 <ref name="FrostHafizCallaghan 2007">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.</ref>

تم تطبيق الخوارزمية منذ ذلك الحين كمجموعة من أجهزة تحليل المحلل اللغوي parser combinator]]s]]المكتوبة بلغة برمجة هاسكل[[هاسكل (لغة برمجة)]] . يمكن العثور على تفاصيل تنفيذ هذه المجموعة الجديدة من المضاعفات في ورقة
<ref name="FrostHafizCallaghan 2008">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.</ref>
 من قبل المؤلفين، والتي تم تقديمها في PADL'08. يحتوي موقع X-SAIGA [http://www.cs.uwindsor.ca/~hafiz/proHome.html ] على مزيد من المعلومات حول [[خوارزمية|الخوارزميات]] وتفاصيل التنفيذ.
== مدى تعقيد الزمن والمساحة في التحليل من أعلى لأسفل ==
عندما يحاول محلل من أعلى إلى أسفل تحليل مدخلات غامضة[[مغالطات الالتباس]] فيما يتعلق ب CFG غامض، قد يحتاج إلى عدد أسي من الخطوات (فيما يتعلق بطول المدخلات) لتجربة كل بدائل CFG من أجل إنتاج جميع أشجارالتحليل الممكنة، والتي تتطلب في نهاية المطاف مساحة ذاكرة كبيرة جدا. مشكلة التعقيد للوقت في محللات من أعلى لأسفل تم إنشاؤها كمجموعات من الدوال المتكرّرة متبادلة تم حلها بواسطة نورفيغ [[بيتير نورفينغ]] في عام 1991.<ref name=" Norvig 1991">Norvig, P. (1991) “Techniques for automatic memoisation with applications to context-free parsing.” ''Journal - Computational Linguistics'' Volume 17, Issue 1, Pages: 91 - 98.</ref> أسلوبه مشابه لاستخدام [[برمجة ديناميكية|البرمجة الديناميكية]] ومجموعات الحالات في خوارزمية إيرلي[[Earley parser|Earley's algorithm]] في عام (1970)، والجداول في خوارزمية [[خوارزمية CYK]]الخاصة بـ Cocke و Younger و Kasami.

والفكرة الرئيسية هي تخزين نتائج تطبيق محلل <code> p </code> في الموضع <code> j </code> في الذاكرة وإعادة استخدام النتائج كلما ظهرت الحالة نفسها. تستخدم فروست، حافظ وكالاهان
.<ref name="FrostHafizCallaghan 2007" /><ref name="FrostHafizCallaghan 2008" />
أيضًا المذكرات من أجل الامتناع عن إجراء حسابات زائدة عن الحاجة لاستيعاب أي شكل من أشكال CFG في زمن كثير الحدود [[متعددة الحدود]] التي تأخذ زمن ([[تمثيل O الكبرى|Θ]](n<sup>4</sup>) for left-recursive grammars and [[تمثيل O الكبرى|Θ]](n<sup>3</sup>) for non left-recursive grammars) للقواعد النحوية غير المتكررة. كما تتطلب خوارزمية التوزيع من أعلى لأسفل أيضًا مساحة متعددة الحدود لأشكال تحليل غامضة أضافية من خلال «التمثيل الصغير» و «تجميع الغموض المحلي». تمثيلهم المدمج قابل للمقارنة مع تمثيل
 Tomita’s compact للتحليل [[bottom-up parsing]]من أسفل إلى أعلى.
<ref name=" Tomita1985">Tomita, M. (1985) “Efficient Parsing for Natural Language.” ''Kluwer, Boston, MA''.</ref>

باستخدام PEG ، تمثيل آخر من القواعد النحوية، يوفر محللو packrat خوارزمية تحليل أنيقة وقوية. راجع[[Parsing expression grammar]].
== الأمثلة ==
تتضمن بعض المحللون الذين يستخدمون التحليل من أعلى إلى أسفل ما يلي:
* [[Definite clause grammar]] parsers<ref>Pereira, Fernando CN, and David HD Warren. "[http://cgi.di.uoa.gr/~takis/pereira-warren.pdf 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. {{Webarchive|url=https://web.archive.org/web/20170809030402/http://cgi.di.uoa.gr/~takis/pereira-warren.pdf |date=09 أغسطس 2017}}</ref>
* [[الترميز التكراري النموذجي]]
* [[الترميز التكراري النموذجي]]
* [[Earley parser]]
== انظر أيضا ==
* [[تجزئة (لغة)|تجزئة]]
== المراجع ==
{{مراجع}}
== روابط إضافية ==
* [http://www.cs.uwindsor.ca/~hafiz/proHome.html X-SAIGA] - eXecutable SpecificAtIons of GrAmmars

{{Parsers}}
{{شريط بوابات|علم الحاسوب|لسانيات|معلوماتية}}

[[تصنيف:توزيع الخوارزميات]]