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

📅 آخر تحديث: ٢ أغسطس ٢٠٢٦
✍️ نُشر في: ٢ أغسطس ٢٠٢٦
📷 يحتوي على 3 صور
الموسوعة الحرة

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

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

يمكن اعتبار التحليل من أعلى إلى أسفل محاولةً لإيجاد الاشتقاقات اليسارية لتدفق المدخلات من خلال البحث عن أشجار التحليل باستخدام توسيع من أعلى إلى أسفل لقواعد النحو الرسمية المعطاة . ويُستخدم الاختيار الشامل لمعالجة الغموض عن طريق توسيع جميع الجوانب اليمنى البديلة لقواعد النحو. [ 2 ]

لا تنتهي التطبيقات البسيطة للتحليل من أعلى إلى أسفل بالنسبة للقواعد النحوية ذات الاستدعاء الذاتي الأيسر ، وقد يكون للتحليل من أعلى إلى أسفل مع التراجع تعقيد زمني أُسّي بالنسبة لطول المدخلات في حالة القواعد النحوية الخالية من السياق الغامضة . [ 3 ] ومع ذلك، فقد تم إنشاء محللات من أعلى إلى أسفل أكثر تطوراً بواسطة فروست وحافظ وكالاغان، [ 4 ] [ 5 ] والتي تستوعب الغموض والاستدعاء الذاتي الأيسر في وقت متعدد الحدود ، والتي تولد تمثيلات ذات حجم متعدد الحدود لعدد أشجار التحليل الذي قد يكون أُسّياً.

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

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

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

  • أ→أبج{\displaystyle A\rightarrow ABC}
  • ب→ج|جد{\displaystyle B\rightarrow c\mid cd}
  • ج→دو|هـز{\displaystyle C\rightarrow df\mid eg}

مما ينتج عنه السلسلة A = acdf

سيتناسبأ→أبج{\displaystyle A\rightarrow ABC}وحاول أن تتطابقب→ج|جد{\displaystyle B\rightarrow c\mid cd}ثم.ج→دو|هـز{\displaystyle C\rightarrow df\mid eg}سيتم تجربة ذلك. وكما هو متوقع، فإن بعض اللغات أكثر غموضًا من غيرها. بالنسبة للغة غير الغامضة، حيث تُنتج جميع قواعد الإنتاج لرمز غير طرفي سلاسل نصية مختلفة، فإن السلسلة الناتجة عن قاعدة إنتاج معينة لن تبدأ بنفس الرمز الذي تبدأ به السلسلة الناتجة عن قاعدة إنتاج أخرى. يمكن تحليل اللغة غير الغامضة باستخدام قواعد LL(1)، حيث يشير الرقم (1) إلى أن المحلل يقرأ رمزًا واحدًا في كل مرة. أما بالنسبة للغة الغامضة، فيجب على المحلل أن يقرأ أكثر من رمز واحد، مثل LL(3).

الحل الشائع لهذه المشكلة هو استخدام محلل LR ، وهو نوع من محلل الإزاحة والاختزال ، ويقوم بالتحليل من الأسفل إلى الأعلى .

استيعاب الاستدعاء الذاتي الأيسر في التحليل من أعلى إلى أسفل

لا يمكن تحليل القواعد النحوية الرسمية التي تحتوي على استدعاء ذاتي يساري بواسطة محلل نحوي تنازلي بسيط إلا إذا تم تحويلها إلى شكل استدعاء ذاتي يميني مكافئ ضعيفًا. ومع ذلك، تُظهر الأبحاث الحديثة أنه من الممكن استيعاب القواعد النحوية الاستدعائية اليسارية (إلى جانب جميع الأشكال الأخرى للقواعد النحوية الحرة للسياق العامة ) في محلل نحوي تنازلي أكثر تطورًا باستخدام الاختصار. في عام 2006، وصف فروست وحافظ خوارزمية للتعرف على القواعد النحوية الغامضة ، تحدّ من تزايد حجم التحليل التكراري المباشر من اليسار، وذلك بفرض قيود على عمق المدخلات بناءً على طول المدخلات وموقعها الحالي. [ 6 ] وفي عام 2007 ، قام فروست وحافظ وكالاغان بتوسيع هذه الخوارزمية لتصبح خوارزمية تحليل كاملة ، تستوعب التحليل التكراري غير المباشر (عن طريق مقارنة السياق المحسوب مسبقًا بالسياق الحالي) والتحليل التكراري المباشر من اليسار في وقت متعدد الحدود ، كما تُنتج تمثيلات مضغوطة متعددة الحدود لعدد أشجار التحليل المحتمل، والذي قد يصل إلى عدد أُسّي، للقواعد النحوية شديدة الغموض. [ 4 ] ومنذ ذلك الحين، تم تطبيق الخوارزمية كمجموعة من مُركِّبات التحليل المكتوب بلغة البرمجة هاسكل . ويمكن الاطلاع على تفاصيل تطبيق هذه المجموعة الجديدة من المُركِّبات في ورقة بحثية [ 5 ] للمؤلفين، والتي عُرضت في مؤتمر PADL'08. يحتوي موقع X-SAIGA على المزيد من المعلومات حول الخوارزميات وتفاصيل التنفيذ.

بالإضافة إلى ذلك، يمكن استخدام مكدس ذي بنية بيانية، إلى جانب التقليص المذكور سابقًا، لاستيعاب الاستدعاء الذاتي الأيسر عن طريق "دمج" المكدسات ذات البادئات المشتركة ومنع الاستدعاء الذاتي اللانهائي، مما يقلل عدد ومحتويات كل مكدس، وبالتالي يقلل من تعقيد الوقت والمساحة للمحلل. يؤدي هذا إلى خوارزمية تُعرف باسم تحليل LL المعمم ، حيث يتم استخدام مكدس ذي بنية بيانية عامة، وتقليص الاستدعاء الذاتي الأيسر، ومحلل LL(k) لتحليل سلاسل الإدخال بالنسبة إلى قواعد نحوية حرة معينة. [ 7 ] [ 8 ]

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

عندما يحاول محلل من أعلى إلى أسفل تحليل مدخل غامض بالنسبة لقواعد نحوية خالية من السياق غامضة، فقد يحتاج إلى عدد هائل من الخطوات (مقارنةً بطول المدخل) لتجربة جميع بدائل القواعد النحوية الخالية من السياق لإنتاج جميع أشجار التحليل الممكنة، الأمر الذي يتطلب في النهاية مساحة ذاكرة هائلة. وقد حلّ نورفيج مشكلة التعقيد الزمني الهائل في المحللات من أعلى إلى أسفل، المصممة كمجموعات من الدوال المتكررة، عام ١٩٩١. [ ٩ ] تشبه تقنيته استخدام البرمجة الديناميكية ومجموعات الحالات في خوارزمية إيرلي (١٩٧٠)، والجداول في خوارزمية CYK لكوك ويونغر وكاسامي.

تتمثل الفكرة الأساسية في تخزين نتائج تطبيق المحلل اللغوي pفي موضع محدد jفي ذاكرة مؤقتة، وإعادة استخدام هذه النتائج كلما تكرر الموقف نفسه. كما يستخدم فروست وحافظ وكالاغان [ 4 ] [ 5 ] التخزين المؤقت لتجنب العمليات الحسابية الزائدة، وذلك لاستيعاب أي شكل من أشكال قواعد اللغة الخالية من السياق في وقت متعدد الحدود ( Θ (n⁴ ) للقواعد النحوية اليسارية المتكررة، و Θ (n³ ) للقواعد النحوية غير اليسارية المتكررة). تتطلب خوارزمية التحليل من أعلى إلى أسفل مساحة متعددة الحدود لأشجار التحليل اللغوي الغامضة التي قد تكون أسية، وذلك من خلال "التمثيل المضغوط" و"تجميع الغموض المحلي". يُقارن تمثيلهم المضغوط بالتمثيل المضغوط لتوميتا للتحليل من أسفل إلى أعلى . [ 10 ]

باستخدام PEG، وهو تمثيل آخر للقواعد النحوية، توفر محللات Packrat خوارزمية تحليل نحوي أنيقة وقوية. انظر تحليل قواعد التعبير النحوي .

أمثلة

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

انظر أيضاً

مراجع

  1. ↑ ديك غرون؛ سيريل جيه إتش جاكوبس (29 أكتوبر 2007). تقنيات التحليل النحوي: دليل عملي . سبرينغر ساينس آند بيزنس ميديا. ISBN 978-0-387-68954-8.
  2. ↑ أهو، ألفريد ف .؛ سيثي، رافي ؛ أولمان، جيفري د. (1986). المترجمات، المبادئ، التقنيات، والأدوات (طبعة مع تصحيحات ). شركة أديسون-ويسلي للنشر. ISBN  978-0201100884.
  3. ↑ أهو، ألفريد ف .؛ أولمان، جيفري د. (1972). نظرية التحليل النحوي والترجمة والترجمة (المجلد 1: التحليل النحوي). (طبعة مُعاد طباعتها). إنجلوود كليفس، نيوجيرسي: برنتيس هول. ISBN  978-0139145568.
  4. 1 2 3 فروست، ر.، حافظ، ر.، وكالاغان، ب. (2007) " تحليل نحوي معياري وفعال من أعلى إلى أسفل للقواعد النحوية اليسارية الغامضة ". ورشة العمل الدولية العاشرة حول تقنيات التحليل النحوي (IWPT)، ACL-SIGPARSE ، الصفحات: 109-120، يونيو 2007، براغ. مؤرشف من الأصل في 12 نوفمبر 2018.
  5. 1 2 3 Frost, R., Hafiz, R. and Callaghan, P. (2008) " مُركِّبات المُحلِّل النحوي للقواعد النحوية اليسارية الغامضة ." الندوة الدولية العاشرة حول الجوانب العملية للغات التصريحية (PADL)، ACM-SIGPLAN ، المجلد 4902/2008، الصفحات: 167-181، يناير 2008، سان فرانسيسكو.
  6. ↑ فروست، ر. وحافظ، ر. (2006) " خوارزمية تحليل نحوي جديدة من أعلى إلى أسفل لمعالجة الغموض والتكرار الأيسر في وقت متعدد الحدود ." إشعارات ACM SIGPLAN ، المجلد 41، العدد 5، الصفحات: 46-54. doi : 10.1145/1149982.1149988
  7. ↑ سكوت، إليزابيث؛ جونستون، أدريان. "تحليل GLL" (ملف PDF) . dotat.at . جامعة لندن .
  8. ↑ سكوت، إليزابيث؛ جونستون، أدريان. "هيكلة خوارزمية تحليل GLL لتحسين الأداء" (ملف PDF) . dotat.at . جامعة لندن .
  9. ↑ نورفيج، ب. (1991) " تقنيات التخزين المؤقت التلقائي مع تطبيقات على التحليل النحوي الخالي من السياق ". مجلة اللغويات الحاسوبية ، المجلد 17، العدد 1، الصفحات: 91 - 98.
  10. ↑ توميتا، م. (1985) " التحليل النحوي الفعال للغة الطبيعية ". كلوير، بوسطن، ماساتشوستس .
  11. ↑ بيريرا، فرناندو سي إن، وديفيد إتش دي وارين. " قواعد الجملة المحددة لتحليل اللغة - مسح للشكلية ومقارنة مع شبكات الانتقال المعززة ." الذكاء الاصطناعي 13.3 (1980): 231-278.
  • X-SAIGA - مواصفات تنفيذية للقواعد