محلل LALR

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

محلل LALR ( محلل الاشتقاق من اليسار إلى اليمين، ذو النظرة الأمامية ) هو نوع من المحللات للغات الحاسوبية. وهو نسخة مبسطة من محلل LR التقليدي .

ابتكر فرانك ديريمر محلل LALR في أطروحته للدكتوراه عام 1969 بعنوان " المترجمات العملية للغات LR(k) " ، [ 1 ] وذلك في سياق معالجته للصعوبات العملية التي كانت تواجه آنذاك في تطبيق محللات LR(1). أظهر ديريمر أن محلل LALR يتمتع بقدرة أكبر على التعرف على اللغة مقارنةً بمحلل LR(0)، مع حاجته إلى نفس عدد الحالات اللازمة للغة التي يمكن التعرف عليها بواسطة كلا المحللين. وهذا ما يجعل محلل LALR بديلاً فعالاً من حيث الذاكرة لمحلل LR(1) بالنسبة للغات التي تُصنف ضمن فئة LALR. كما ثبت وجود لغات LR(1) لا تُصنف ضمن فئة LALR. وعلى الرغم من هذا الضعف، فإن قدرة محلل LALR كافية للعديد من لغات البرمجة الشائعة، [ 2 ] بما في ذلك جافا ، [ 3 ] على الرغم من أن قواعد اللغة المرجعية للعديد من اللغات لا تُصنف ضمن فئة LALR بسبب غموضها . [ 2 ]

لم تُقدّم الرسالة الأصلية أي خوارزمية لبناء محلل نحوي من هذا النوع انطلاقًا من قواعد نحوية رسمية. نُشرت أولى خوارزميات توليد محللات LALR النحوية عام 1973. [ 4 ] وفي عام 1982، نشر ديريمر وتوم بينيلو خوارزمية لتوليد محللات LALR ذات كفاءة عالية في استخدام الذاكرة. [ 5 ] يمكن توليد محللات LALR النحوية تلقائيًا من قواعد نحوية باستخدام مولد محللات LALR مثل Yacc أو GNU Bison . ويمكن تحسين الكود المُولّد تلقائيًا بكود مكتوب يدويًا لتعزيز قدرات المحلل النحوي الناتج.

تاريخ

في عام 1965، اخترع دونالد كنوث محلل LR ( من اليسار إلى اليمين، الاشتقاق الأيمن ) . يستطيع محلل LR التعرف على أي لغة حتمية خالية من السياق في وقت محدود خطيًا. [ 6 ] يتطلب الاشتقاق الأيمن ذاكرة كبيرة جدًا، وكان تطبيق محلل LR غير عملي نظرًا لمحدودية ذاكرة الحواسيب في ذلك الوقت. لمعالجة هذا القصور، اقترح فرانك ديريمر في عام 1969 نسختين مبسطتين من محلل LR، وهما محلل LR ذو النظرة الاستباقية (LALR) [ 1 ] ومحلل LR البسيط (SLR) اللذان يتميزان بمتطلبات ذاكرة أقل بكثير على حساب قدرة أقل على التعرف على اللغة، مع كون محلل LALR هو البديل الأقوى. [ 1 ] في عام 1977، تم ابتكار تحسينات للذاكرة لمحلل LR [ 7 ]، لكنه ظل أقل كفاءة في استخدام الذاكرة من البدائل المبسطة.

في عام 1979، أعلن فرانك ديريمر وتوم بينيلو عن سلسلة من التحسينات لمحلل LALR من شأنها أن تزيد من كفاءة استخدام الذاكرة. [ 8 ] نُشر عملهما في عام 1982. [ 5 ]

ملخص

بشكل عام، يُشير مُحلل LALR إلى مُحلل LALR(1)، تمامًا كما يُشير مُحلل LR إلى مُحلل LR(1). يُشير ( 1 ) إلى التنبؤ المسبق برمز واحد، لحل الاختلافات بين أنماط القواعد أثناء التحليل. وبالمثل، يوجد مُحلل LALR(2) بتنبؤ مسبق برمزين، ومُحللات LALR( k ) بتنبؤ مسبق بـ k رمز، ولكن استخدامها نادر. يعتمد مُحلل LALR على مُحلل LR(0)، لذا يُمكن الإشارة إليه أيضًا بـ LALR(1)  =  LA(1)LR(0) (تنبؤ مسبق برمز واحد، LR(0)) أو بشكل أعم LALR( k )  =  LA( k )LR(0) (تنبؤ مسبق بـ k رمز، LR(0)). في الواقع، هناك عائلة من محللات LA( k )LR( j ) ذات المعلمتين لجميع تركيبات j و k ، والتي يمكن اشتقاقها من محلل LR( j  + k )، [ 9 ] ولكن هذه لا ترى استخدامًا عمليًا. 

كما هو الحال مع أنواع محللات LR الأخرى، يتميز محلل LALR بكفاءة عالية في إيجاد التحليل الصحيح الوحيد من الأسفل إلى الأعلى في مسح واحد من اليسار إلى اليمين على دفق الإدخال، لأنه لا يحتاج إلى استخدام التراجع . وباعتباره محللاً استباقياً بحكم تعريفه، فإنه يستخدم دائماً استباقية، وتُعد LALR(1) الحالة الأكثر شيوعاً.

العلاقة بالمحللات الأخرى

محللات LR

يُعدّ محلل LALR(1) أقل قوة من محلل LR(1)، وأكثر قوة من محلل SLR(1)، على الرغم من استخدامها جميعًا لقواعد الإنتاج نفسها . يتمثل التبسيط الذي يُدخله محلل LALR في دمج القواعد التي لها مجموعات عناصر أساسية متطابقة ، نظرًا لعدم معرفة رموز التنبؤ أثناء عملية بناء الحالة في LR(0). يُقلل هذا من قوة المحلل لأن عدم معرفة رموز التنبؤ قد يُربك المحلل بشأن قاعدة النحو التي يجب اختيارها تاليًا، مما يؤدي إلى تعارضات الاختزال/الاختزال . جميع التعارضات التي تنشأ عند تطبيق محلل LALR(1) على قواعد نحوية LR(1) غير غامضة هي تعارضات اختزال/اختزال. يُجري محلل SLR(1) عملية دمج إضافية، مما يُؤدي إلى تعارضات إضافية.

المثال القياسي لقواعد LR(1) التي لا يمكن تحليلها باستخدام محلل LALR(1)، والتي تُظهر مثل هذا التعارض في الاختزال / الاختزال، هو: [ 10 ] [ 11 ]

 S → a E c → أ ف د → ب ف ج → ب إي د E → e F → e

في عملية إنشاء جدول LALR، سيتم دمج حالتين في حالة واحدة، وسيتبين لاحقًا أن التنبؤات المستقبلية غامضة. الحالة الوحيدة التي تحتوي على تنبؤات مستقبلية هي:

 E → e. {c,d} F → e. {c,d}

يُنشئ محلل LR(1) حالتين مختلفتين (مع استباق غير متعارض)، ولا تُعدّ أيٌّ منهما غامضة. أما في محلل LALR، فتتضمن هذه الحالة إجراءات متعارضة (بالنظر إلى الاستباق c أو d، يتم الاختزال إلى E أو F)، وهو ما يُعرف بـ "تعارض الاختزال/الاختزال"؛ وسيُعلن مُولّد محلل LALR أن القواعد النحوية المذكورة أعلاه غامضة، وسيتم الإبلاغ عن التعارضات.

لحل هذا الغموض، يتم اختيار الخيار E لأنه يسبق الخيار F في القواعد النحوية. مع ذلك، لن يتمكن المحلل النحوي الناتج من التعرف على تسلسل الإدخال الصحيح b e c، لأن التسلسل الغامض e cيُختزل إلى (E → e) c، بدلاً من التسلسل الصحيح (F → e) c، ولكنه b E cغير موجود في القواعد النحوية.

محللات LL

لا يمكن مقارنة محللات LALR( j ) بمحللات LL( k ) : فلكلٍّ من j و k أكبر من صفر، توجد قواعد LALR( j ) ليست قواعد LL( k ) ، والعكس صحيح. في الواقع، من غير الممكن تحديد ما إذا كانت قاعدة LL(1) معينة هي LALR( k ) لأي قيمة لـ j أو k.ك>0{\displaystyle k>0}[ 2 ]​

بحسب وجود الاشتقاقات الفارغة، يمكن أن تكون قواعد LL(1) مساوية لقواعد SLR(1) أو LALR(1). إذا لم تحتوي قواعد LL(1) على أي اشتقاقات فارغة، فهي SLR(1)، وإذا كانت جميع الرموز ذات الاشتقاقات الفارغة لها اشتقاقات غير فارغة، فهي LALR(1). أما إذا وُجدت رموز ذات اشتقاقات فارغة فقط، فقد تكون القواعد LALR(1) أو لا. [ 12 ]

انظر أيضاً

ملحوظات

  1. ↑ يُنطق اختصار "LALR" على النحو التالي : "el-ay-el-arr"
  2. ↑ يُنطق اختصار "LALR(1)" على النحو التالي : "el-ay-el-arr-one"

مراجع

  1. 1 2 3 DeRemer 1969 .
  2. 1 2 3 تحليل LR: النظرية والتطبيق، نايجل ب. تشابمان، ص 86-87
  3. ↑ "إنشاء المحلل اللغوي" . مشروع Eclipse JDT . تم الاطلاع عليه بتاريخ 29 يونيو 2012 .
  4. ↑ أندرسون، ت.؛ إيف، ج.؛ هورنينج، ج. (1973). "محللات LR(1) الفعالة". Acta Informatica (2): 2– 39.
  5. 1 2 ديريمر، فرانك؛ بينيلو، توماس (أكتوبر 1982). "الحساب الفعال لمجموعات التوقع المسبق LALR(1)" (ملف PDF) . معاملات ACM في لغات البرمجة والأنظمة . 4 (4): 615-649 . doi : 10.1145/69622.357187 .
  6. ↑ كنوت، دي إي (يوليو 1965). "حول ترجمة اللغات من اليسار إلى اليمين" . المعلومات والتحكم . 8 (6): 607-639 . doi : 10.1016/S0019-9958(65)90426-2 .
  7. ↑ بيجر، د. (1977)، "طريقة عامة عملية لبناء محللات LR(k)"، مجلة Acta Informatica 7 ، المجلد 7، العدد 3، الصفحات 249-268 ، doi : 10.1007/BF00290336   
  8. ↑ فرانك ديريمر، توماس بينيلو (1979)، "الحساب الفعال لمجموعات التوقع المسبق LALR(1)"، إشعارات سيغبلان - سيغبلان، المجلد 14، العدد 8 ، الصفحات 176-187 
  9. ↑ تقنيات التحليل النحوي: دليل عملي، بقلم ديك غرون وسيريل جيه إتش جاكوبس، "9.7 LALR(1)"، ص 302
  10. ↑ " 7.9 LR(1) ولكن ليس LALR(1) مؤرشف في 4 أغسطس 2010 في Wayback Machine "، CSE 756: تصميم وتنفيذ المترجمات مؤرشف في 23 يوليو 2010 في Wayback Machine ، إيتان غوراري، ربيع 2008
  11. ↑ " لماذا لا تُعتبر هذه القواعد النحوية من نوع LR(1) من نوع LALR(1)؟ "
  12. ↑ ( بيتي 1982 )
  • ديريمر، فرانكلين ل. (1969). مترجمون عمليون للغات LR(k) (ملف PDF) (أطروحة دكتوراه). معهد ماساتشوستس للتكنولوجيا. مؤرشف من الأصل (ملف PDF) بتاريخ 19 أغسطس 2013. تم الاطلاع عليه بتاريخ 13 نوفمبر 2012 .
  • بيتي، جيه سي (1982). "حول العلاقة بين قواعد LL(1) و LR(1)" (ملف PDF) . مجلة ACM . 29 (4 (أكتوبر)): 1007-1022 . doi : 10.1145/322344.322350 .
  • محاكي التحليل اللغوي: يُستخدم هذا المحاكي لإنشاء جداول التحليل اللغوي LALR وحل تمارين الكتاب.
  • JS/CC تطبيق قائم على JavaScript لمولد محلل LALR(1)، والذي يمكن تشغيله في متصفح الويب أو من سطر الأوامر.
  • برنامج تعليمي حول LALR(1) في Wayback Machine (تمت أرشفته في 7 مايو 2021)، وهو برنامج تعليمي يشبه البطاقات التعليمية حول تحليل LALR(1).