مرجع
آخر الزيارات

مجزئ يسار يمين

3٬546 كلمة•0 مشاهدة•🗒️ منذ يوم
باختصار: مجزّئ يسار يمين في علوم الحاسب الآلي، هو مجزئ يقرأ الإدخال من اليسار إلى اليمين (كما ستظهر في العرض المرئي)، وتنتج استخلاص أقصى اليمين. تجد هنا «الطرفية الحالية تم إزالتها من تدفق الإدخال»، «التعارضات في بناء الجداول» و«• مجموعة قواعد CFL» ضمن 39 قسماً.
المحتويات
  1. الطرفية الحالية تم إزالتها من تدفق الإدخال
  2. التعارضات في بناء الجداول
  3. • مجموعة قواعد CFL
  4. [0 E 3]
  5. البنود
  6. + B → • 1
  7. [0 '1' 2]
  8. o an accept: تم قبول السلسلة
  9. [0 E 3 '+' 6 '1' 2]
  10. تجول
  11. [0]
  12. • مخزن مؤقت للمدخلات
  13. E → E • + B
  14. E → E + B •
  15. [0 E 3]
  16. B → 1 •
  17. + B → • 1
  18. + E → • 1
  19. E → E + B •
  20. • Deterministic context-free grammar
  21. الحالة العامة
  22. العمل Action وجدول الأنتقال goto tables
  23. [0 E 3 '+' 6]
  24. قواعد مضافة
  25. بناء الجدول
  26. اختتام مجموعات البند
  27. Further reading
  28. [0 B 4]
  29. مثال البناء
  30. B → 0 •
  31. مجموعات البنود
  32. [0 E 3 '+' 6 B 8]
  33. العدد m هو مكتوب إلى تدفق المخرجات
  34. E → E * B •
  35. B → 1 •
  36. هندسة بناء محللات LR parsers
  37. E → B •
  38. + B → • 1
  39. إجراءات التحليل

على سبيل التعريف، مجزّئ يسار يمين في علوم الحاسب الآلي، هو مجزئ يقرأ الإدخال من اليسار إلى اليمين (كما ستظهر في العرض المرئي)، وتنتج استخلاص أقصى اليمين. مصطلح LR(k) parser يستعمل كذلك؛ حيث K تشير إلى عدد الغير مستهلك "look ahead" رموز المدخلات التي تستعمل في صنع القرارات التحليل. عادة ما تكون K هي 1 والعبارة LR parser عادة ما تستعمل للإشارة إلى هذه الحالة. ونتناول فيما يلي مزيدًا من التفاصيل.

وفي السياق ذاته، القواعد اللغوية لكثير من لغات البرمجة يمكن تحديدها بقواعد هي LR(1) أو ما يقارب ذلك، ولهذا السبب LR parsers غالبا ما تستعمل من قبل برامج المترجم لإجراء تحليل القواعد اللغوية من شفرة المصدرsource code.

من جانب آخر، ويقال أن LR parser لإجراء تحليل من أسفل إلى أعلى لأنه يحاول أستخلاص إنتاجات أعلى مستوى نحوي عن طريق البناء من الأوراق.

من جانب آخر، LR parsers صعب إنتاجها باليد، وعادة ما تنتج بمولد المحلل أو مترجم-مترجمcompiler-compiler. اعتمادا على كيفية إنشاء جدول التحليل، هذه المحللات يمكن أن تسمى محللات LR بسيطة simple LR parsers (SLR)، محللات LR النظر إلى الامام look-ahead LR parsers (LALR), أو محللات LR المقننة canonical LR parsers. محللات LALR لديها قوة أعتراف لغوي بها أكثر من SLR. بينما المحللات LR المقننة canonical LR parsers لديها قوة أعتراف بها أكثر من LALR.

وفي السياق ذاته، LR parsing يمكن تعميمها كلغة سياق حر تعسفية تحلل بدون عقوبة للتشغيل، حتى لقواعد LR(k). هذا لان أغلب لغات البرمجة يمكن التعبير عنها بقواعدLR(k). حيث أن K وثابت صغير (عادة يكون1). علما بأن تحليل القواعد الغير LR(k) هو أمر ضخم أبطأ (المكعب بدلا من التربيعي بالنسبة لطول الإدخال).

ومن ناحية أخرى، LR parser يمكن إنشاءه من قواعد السياق الحر context-free grammar من خلال برنامج يسمى parser generator (مولد المحلل) أو مكتوب بخط اليد من قبل المبرمج. قواعد السياق الحر context-free grammar يصنف كـ LR(k) إذا كان هناك محلل LR(k) له، على النحو الذي يحدده مولد المحلل parser generator.

ومن جهة أخرى، LR parsing يمكن أن تتعامل مع أكبر مجموعة من اللغات من LL parsing، وهي كذلك أفضل في التقرير عن الخطأ، أي أنه يكشف الأخطاء النحوية عندما لاتتفق المدخل مع القواعد في أقرب وقت ممكن. هذا على النقيض مع LL(k) (أو أسوأ من ذلك، محلل LL(*) parser) والتي قد تؤجل الكشف عن الخطأ إلى فرع مختلفة من القواعد بسبب التراجع، مما يؤدى الي صعوبة تحديد موقع الخطأ عبر المفارق في البادئات المشتركة الطويلة.

وفي هذا الصدد، LR parser مبنى على خوارزمية (أو لوغرتمية) التي يقودها جدول محلل parser table، تركيبة البيانات التي تحتوي على قواعد لغة الكمبيوتر التي يتم تحليلها. حتى المصطلح LR parser في الواقع يشير لفئة من المحلل التي يمكن أن تقوم بمعالجة على وجه التقريب أي لغة برمجة، ما دام جدول المحلل متوفر للغة البرمجة. يتم إنشاء جدول المحلل بواسطة برنامج يسمى مولد المحلل parser generator.

ومن جهة أخرى، قواعد السياق الحر الحتمية deterministic context-free language هي لغة يوجد بها بعض قراعد LR(k) كل قواعد LR(k) k > 1 يمكن أن تحول ميكانيكيا إلى قواعد LR(1) لنفس اللغة، في حين أن قواعد LR(0) لنفس اللغة قد لا تكون موجودة، لغات LR(0) هي مجموعة فرعية مناسبة من تلك الحتمية.

الطرفية الحالية تم إزالتها من تدفق الإدخال

الحالة n تدفع إلى المكدس وتصبح الوضع الحالي

تخفيض a reduce rm :

التعارضات في بناء الجداول

علاوةً على ذلك، وثمة مثال صغير للقواعد الغير LR(0) مع تعارض إجراءات الخفض والتحول هو: (1) E → 1 E (2) E → 1

من جهة ثانية، يتم بناء الأوتوكاتيكية في مثل هذه الطريقة مضمونة القطعية. ومع ذلك، عندما تضاف إجراءات الخفض إلى جدول الإجراءات ما يمكن أن يحدث هو أن الخانة نفسها يكون بها إجراء خفض وإجراءات التحول (تعارض إجراءات الخفض والتحول) (a shift-reduce conflict) أو مع إجراءان اثنين للخفض (تعارض إجراءات الخفض والخفض) (a reduce-reduce conflict). ومع ذلك، يمكن أن يتبين أنه عندما يحدث هذا فإن القواعد لا تكون قواعد LR(0).

  • واحدة من مجموعات البند نجدها:
  • مجموعة بند 1
  • E → 1 • E
  • E → 1 •
  • + E → • 1 E

• مجموعة قواعد CFL

وفي هذا السياق، في حين LR parser يقرأ الإدخال من اليسار إلى اليمين لكنه يحتاج إلى إنتاج استخلاص أقصى اليمين، فإنه يستعمل التخفيضات، بدلا من الاشتقاقات لعملية الإدخال. وهذا هو، العمل الخوارزمي (اللوغارتمي) يعمل عن طريق خلق «التخفيض أقصى اليسار» من المدخلات. النتيجة النهائية، عندما تعكس، سيتم اشتقاق أقصى اليمين.

o a shift sn)إزاحة (sn:

وعلى صعيد آخر، 2. نظرا للحالة الراهنة والطرفية الطرفية الحالية في تدفق المدخلات إجراء يتم البحث عنه في جدول الإجراءات. وهناك أربع حالات:

علاوةً على ذلك، 1. المكدس يبدأ من [0]. الحالة الراهنة سوف تكون دائما الحالة التي تقع في أعلى المكدس.

خوارزمية (لوغرتمية) محلل LR parsing تعمل كما يلي:

[0 E 3]

وفي هذا الصدد، الطرفية التالية التي يراها المحلل هي '+' وبحسب جدول الإجراءات يجب أن تذهب فيما بعد إلى الحالة (6):

البنود

  • E → • E + B
  • E → E • + B
  • E → E + • B

من جهة ثانية، بناء جداول التحليل هذه قائم على مفهوم بنود LR(0) (وتسمى ببساطة البنود هنا) التي هي القواعد اللغوية الخاصة مع نقطة مميزة تضاف في مكان ما في الجانب الأيمن. مثلًا القاعدة E → E + B لديها الأربعة بنود المقابلة التالية:

+ B → • 1

  • ولـ '+' الانتقال يذهب إلى:
  • مجموعة البند 6
  • E → E + • B
  • + B → • 0

[0 '1' 2]

وفي هذا الصدد، في الحالة (2) جدول الإجراءات يقول انه بغض النظر عما هو طرفي نراه على تدفق المدخلات، ينبغي أ نخفض مع القاعدة اللغوية 5. إذا كان الجدول صحيح، هذا يعني أن المحلل قد تعرف على الجانب الأيمن من القاعدة 5، والتي في الواقع هي الحالة. في هذه الحالة نكتب 5 إلى تدفق المخرجات، ادفع حالة واحدة من المكدس (حيث الجانب الأيمن من القاعدة لديه رمز واحد)، وادفع على المكدس الحالة من الخلية في جدول الانتقال للحالة 0 و B، أي الحالة 4. ينجم عن ذلك المكدس:

وفي هذا الصدد، حيث الجزء العلوي من المكدس هة الحالة 2. من أجل التفسير نظهر كذلك الرمز (مثلًا '1', B) التي تسببت الانتقال إلى الحالة القادمة، وعلى الرغم من ذلك بالمعنى الدقيق أنها ليست جزءا من المكدس.

o an accept: تم قبول السلسلة

وعلى صعيد آخر، 3. الخطوة 2 يتم تكرارها حتى إما يتم قبول السلسلة أو عمل تقرير للخطأ في قواعد اللغة.

o no action: تم عمل تقرير عن الخطأ في قواعد اللغة

[0 E 3 '+' 6 '1' 2]

كذلك، مثلما جاء في لاسابق '1' وهذه تخفض إلى B لإعطاء المكدس التالي:

تجول

محلل يبدأ مع المكدس تحتوي فقط على الحالة الأولي ('0'):

[0]

وفي هذا السياق، الرمز الأول من سلسلة الإدخال التي يراها المحلل اللغوي هو '1'. من أجل معرفة ما الإجراء القادم هو العمل (shift إزاحة، reduceتخفيض، acceptقبول أو errorخطأ)، تتم فهرسة جدول الإجراءات مع الحالة الحالية (نتذكر أن «الحالة الراهنة» ليست سوى كل ما هو على أعلى المكدس)، والتي في هذه الحالة هو 0، ورمز الإدخال الحالي، وهو '1'. جدول الإجراءات يحدد التحول shift إلى الحالة 2، وهكذا تدفع الحالة 2 فوق المكدس (مرة أخرى، تذكر أن كل معلومات الحالة توجد في المكدس، لذلك «التحول إلى الحالة 2» هو نفس دفع 2 على المكدس). ينجم عن ذلك مكدس

• مخزن مؤقت للمدخلات

وعلى صعيد آخر، • جدول الإجراءات الذي يعطي حكم القواعد لتطبيق المأخوذ من الحالة الراهنة والطرفية الحالية في تدفق المدخلات

• المكدس حيث يتم تخزين قائمة من الأحوال التي كانت عليها

علاوةً على ذلك، • جدول الأنتقال الذي يحدد المكان الذي تنتقل اليه الحالة الجديدة

E → E • + B

مجموعة البند 4

وعلى الغير طرفية B في:

E → E + B •

وعلى صعيد آخر، يمكن للقارئ أن يتحقق من أن هذه النتائج واقعية في جدول العمل والانتقالات التي عرضت من قبل هنا.

إضافةً إلى ذلك، من هذا الجدول ومجموعة البند هذه التي وجدت نبني جداول الإجراءات وجداول الانتقال على النحو التالي:

2. يتم نسخ أعمدة المحطات الطرفية إلى جدول الإجراءات كتحول

من جانب آخر، 3. يتم إضافة عمود إضافي لل'$' (نهاية المدخلات) إلى جداول الإجراءات الذي يحتوي على acc قبول كل مجموعة بند تحتوي على S → E •.

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

1. يتم نسخ أعمدة المحطات الغير طرفية إلى جدول الانتقال goto

من جهة ثانية، 4. إذا كانت مجموعة البند i تحتوي على بند من النموذج A → w • and A → w هي القاعدة m مع m > 0 ثم الصف للحالة i في جدول الإجراءات يتم تعبئتة تماما مع إجراء الخفض rm.

من جهة ثانية، مجموعات البند الأخيرة هذه لا يوجد رموز لها خلف لذا لا يوجد مجموعات بنود جديدة تضاف وانتهينا. والأوتوكاتيكية المحدودة، مع مجموعات البند كما توجد أدناه.

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

ملاحظة حول LR(0) مقارنة بتحليل SLR و LALR

بناء جداول الإجراءات action tables والانتقالات goto tables

[0 E 3]

بناء جداول التحليل LR(0)

إضافةً إلى ذلك، وأخيرا، نقرأ '$' من تدفق الإدخال وهذا يعني أنه بحسب جدول الإجراءات (الحالة الحالية هو 3) المحلل يقبل سلسلة الإدخال. أعداد القواعد التي سوف تتم كتابتها إلى تدفق الإخراج سوف تكون [5, 3, 5, 2] الذي هو في الواقع الاشتقاق أقصى اليمينrightmost derivation من السلســـلة "1 + 1" في الاتجاه المعاكس.

B → 1 •

  • وعلى الغير طرفية E في:
  • مجموعة بند 3
  • S → E •
  • E → E • * B

+ B → • 1

وفي السياق ذاته، ابتداء من حالة البدء (S0) نحن الآن سوف نحدد جميع الحالات التي يمكن الوصول إليها من هذه الحالة. التحولات المحتملة لمجموعة البند يمكن إيجادها من خلال النظر في الرموز (المحطات الطرفية والغير طرفية) نجد بعد النقاط تماماً ; وفي حالة مجموعة البند 0 هذه هي المحطات الطرفية '0' و'1' وB وE المحطة الغير طرفية.للعثور على مجموعة البند التي يؤدى اليها الرمز x نتبع الإجراء التالي:

وفي هذا السياق، 1. نأخذ المجموعة، S، من كافة البنود في مجموعة البند الحالي حيث توجد نقطة أمام بعض الرموز X.

  • 2. لكل بند في S، انقل نقطة على يمين X.
  • 3. إغلاق المجموعة الناتجة من البنود.
  • لطرفية '0' هذه النتائج في:
  • مجموعة بند 1

وفي السياق ذاته، حرف "+" الكبير أمام بند يدل على البنود التي تمت إضافتها للإغلاق (وينبغي عدم الخلط بينها وبين مشغل رمز رياضي '+' وهو محطة طرفية). البنود الأصلية بدون علامة "+ تسمى النواة لمجموعة البند.

+ E → • 1

في هذا الإطار، وثمة مثال صغير القواعد الغير LR(0) مع تعارض إجراءات الخفض والخفض، هو: (1) E → A 1 (2) E → B 2 (3) A → 1 (4) B → 1

  • في هذه الحالة نحصل على مجموعة البند التالية:
  • مجموعة بند 1
  • A → 1 •

من جهة ثانية، هناك تعارض إجراءات الخفض والتحول في مجموعة هذا البند لأن في الخلية في جدول الإجراءات لمجموعة البند هذه والطرفية '1' سوف يكون هناك على حد سواء إجراء التحول إلى الحالة (1) وإجراء خفض للمادة 2.

E → E + B •

وفي السياق ذاته، قواعد الشكل الذي ε →A لديها فقط بند واحد A → •. البند E → E • + B، مثلًا، يشير إلى أن المحلل تعرف على السلسلة المقابلة لـE على تدفق المدخلات ويتوقع الآن أن تقرأ '+' متبوعة بسلسلة أخرى المقابلة لـ B

• Deterministic context-free grammar

• LL parser

• Simple LR, Look-Ahead LR, Canonical LR and Generalized LR

الحالة العامة

المحلل هو آلة الحال وهو يتألف من:

العمل Action وجدول الأنتقال goto tables

وعلى صعيد آخر، جدولين التحليل LR(0) parsing لهذه القاعدة تبدو على النحو التالي:

  • • shift, التي تكتب 'sn' وتشير إلى أن الحالة القادمة هي n
  • • reduce، التي تكتب 'rm' وتشير إلى أنه ينبغي إجراء تخفيض في القاعدة النحوية m
  • • accept، والتي تكتب 'acc' وتشير إلى أن المحلل يقبل السلسلة في تدفق الإدخال.

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

ومن جهة أخرى، تتم فهرسة جدول الإجراءات من جانب حالة المحلل ومحطة طرفية (بما في ذلك طرفية خاصة $ التي تشير إلى نهاية تدفق المدخلات) وتحتوي على ثلاثة أنواع من الأعمال:

[0 E 3 '+' 6]

وفي هذا الصدد، الطرفية التالية هي الآن '1' وهذا يعني أن علينا إجراء التحول shift والانتقال إلى الحالة 2 :

وفي هذا السياق، لاحظ أن الناتج مكدس يمكن أن يفسرعلى أنه تاريخ حالة محدودة أوتوماتيكيا التي قرأت E الغير طرفية يليها '+' الطرفية. يتم تعريف جدول الانتقال لهذه الألية عن طريق إجراءات التحول shift actions في جدول الإجراءات والانتقالات في جدول الانتقالات.

قواعد مضافة

ومن جهة أخرى، قبل أن نبدأ في تحديد الانتقال بين مختلف الحالات، القواعد دائما مزاد عليها بقواعد إضافية (0) S → E

وفي هذا السياق، مثلًا سوف نتخذ نفس القاعدة كما في السابق ونزيد عليها: (0) S → E (1) E → E * B (2) E → E + B (3) E → B (4) B → 0 (5) B → 1

كذلك، ولهذه القواعد المضافة سوف نحدد مجموعات البند والتحولات بينها.

وفي هذا الصدد، حيث S انه هو رمز بداية جديدة وE هو رمز البداية القديم. المحلل سوف يستعمل هذه القاعدة للتخفيض بالضبط متى يتم قبول سلسلة الإدخال.

بناء الجدول

من جانب آخر، العثور على مجموعات البند التي يمكن الوصول اليها والتحولات بينها

في هذا الإطار، الخطوة الأولى في بناء الجداول تتكون من تحديد المراحل الانتقالية بين مجموعات البند المغلقة. وسيتم تحديد هذه التحولات كما لو أننا نظر إلى في أوتوكاتيكية محدودة التي يمكن أن تقرأ الطرفيات واللا طرفيات. حالة البداية لهذه الأوتوكاتيكية دائما اختتام البند الأول من المادة المضافة S → • E

  • مجموعة البند 0
  • S → • E
  • + E → • E * B
  • + E → • E + B
  • + E → • B
  • + B → • 0

اختتام مجموعات البند

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

Further reading

وفي هذا السياق، Chapman, Nigel P., LR Parsing: Theory and Practice, مطبعة جامعة كامبريدج، 1987. ISBN 0-521-30413-X

وفي السياق ذاته، Chapman, Nigel P., LR Parsing: Theory and Practice, Cambridge University Press, 1987.

إضافةً إلى ذلك، "Compiler Construction: Principles and Practice" by Kenneth C. Louden.

ومن جهة أخرى، Pager, D., A Practical General Method for Constructing LR(k) Parsers. Acta Informatica 7, 249 - 268 (1977)

[0 B 4]

وعلى صعيد آخر، مع ذلك، في الحالة 4 جدول الإجراءات يقول إنه يجب علينا القيام بتخفيض للمادة 3. حتى نكتب 3 إلى تدفق الإخراج، ادفع حالة واحدة من المكدس، وابحث عن الحالة الجديدة في جدول الانتقال للحالة 0 وE، وهي الحالة 3. الناتج المكدس:

مثال البناء

ومن ناحية أخرى، انتبه ان الحالة العامة التي يجب أن تكون في المكدس هي (رقم، رمز، رقم).

1 + 1

وتحليل المدخلات التالية:

كذلك، لتفسير كيف يعمل، سوف نستعمل القواعد التالية الصغيرة التي تبدأ بالرمز E : (1) E → E * B (2) E → E + B (3) E → B (4) B → 0 (5) B → 1

B → 0 •

وللطرفية '1' في:

مجموعة بند 2

مجموعات البنود

من جهة ثانية، إذا كان هناك بند من النموذج A → v • Bw في مجموعة بند وفي القواعد هناك قاعدة B → w' حينها البند B → • w' ينبغي كذلك أن يكون في مجموعة البند.

وفي هذا السياق، بند مع نقطة قبل محطة غير طرفية، مثل E → E + • B، يشير إلى أن المحلل يتوقع أن تحليل B اللا طرفية لاحقًا. لضمان ان مجموعة البند تتضمن كافة القواعد الممكنة حيث المحلل قد يكون في وسط التحليل، يجب أن تشمل جميع البنود التي تصف كيف B نفسها سيتم تحليلها. وهذا يعني أنه إذا كانت هناك قواعد مثل B → 1 و B → 0 حينها مجموعة البند يجب أن يتضمن كذلك البنود B → 1 و B → 0. وبصفة عامة هذا يمكن أن يصاغ هذه على النحو التالي:

تمديد مجموعة البند عن طريق التوسع في اللا طرفيات

ومن ناحية أخرى، عادة ليس من الممكن وصف حالة المحلل ذا البند الواحد لأنه قد لا يعرف مقدما أية قاعدة سوف يستعملها للتخفيض. مثلًا إذا كان هناك كذلك قاعدة E → E * B إذاً البنود E → E • + B و E → E • * B سوف تطبق على حد سواء بعد قراءة سلسلة مقابلة لـ E. ولذلك فإننا سوف نوصف حالة المحلل بمجموعة بنود، في هذه الحالة المجموعة { E → E • + B, E → E • * B }

[0 E 3 '+' 6 B 8]

ومن ناحية أخرى، لاحظ مرة أخرى أن المكدس يتوافق مع قائمة الحالات الأوتوكاتيكية المحدودة التي قرأت E الغير طرفية، تليها '+' وثم B الغير طرفية. في الحالة 8 نقوم دائما بخفض للمادة 2. لاحظ أن أعلى 3 حالات على مكدس تتوافق مع الرموز الثلاثة في الجانب الأيمن من المادة 2.

العدد m هو مكتوب إلى تدفق المخرجات

كذلك، لكل رمز في الجانب الأيمن من القاعدة m يتم إزالة حالة من المكدس (أي إذا كان الجانب الأيمن من القاعدة m تتكون من 3 رموز، 3 حالات فوقية يتم إزالتها من المكدس)

في هذا الإطار، إعطاء الحالة التي كانت فوقية في المكدس والجانب الايسر من القاعدة m يتم البحث عن حالة جديدة في جدول الأنتقال وتحقق الحالة الجديدة الحالية بدفعها داخل المكدس.

E → E * B •

من جهة ثانية، بالنسبة لمجموعة بند 6 يجب النظر في الطرفية '0' و'1' والمحطة الغير طرفية B سبق، مجموعات البند الناتجة عن المحطات الطرفية متساوية إلى مجموعات البند التي وجدت بالفعل 1 و 2. للمحطة الغير طرفية B الانتقال يذهب إلى:

مجموعة البند 8

B → 1 •

انظر كذلك

كذلك، المثالين المذكورين أعلاه يمكن حلهما عن طريق السماح للمحلل باستخدام محلل المجموعة التالية (انظر محلل اللغة LL LL parser) من المحطة الغير طرفية A لتقرر استخدام واحدة من القواعد مثل قواعد الخفض؛ انها سوف تستعمل فقط القاعدة A → w للتخفيض إذا كان الرمز التالي على تدفق الإدخال هي المجموعة التالية لـ A هذه النتائج في الحل تسمى محلل LR البسيط Simple LR parsers.

وفي هذا السياق، هناك تعارض إجراءات الخفض والخفض في مجموعة البند هذه لأن في الخلايا في جدول الإجراءات لمجموعة البند هذه سوف يكون هناك إجراءان خفض للمادة 3 وواحد للمادة 4.

هندسة بناء محللات LR parsers

الشكل رقم 1. هندسة بناء محلل الجدول من أسفل إلى أعلى.

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

وفي هذا الصدد، من الناحية النظرية، LR Parser هو برنامج تكراري الذي يمكن أن يثبت صحته بحساب مباشر، ويمكن تنفيذه بشكل أكثر كفاءة (في الوقت المحدد) كمحلل تكراري تصاعدي recursive ascent parser، مجموعة من الوظائف المتبادلة المتكررة لكل قاعدة، تشبه كثيراً المحلل التكراري التنازلي recursive descent parser تقليدي، ومع ذلك، LR Parser يتم تقديمه وتنفيذه كآلات تخزين مكدسة مستندة على جدول، حيث مكدس الاستدعاءات call stack لمصدر البرنامج التكراري يقوم بالتلاعب بشكل صريح.

E → B •

  • مجموعة البند 5
  • E → E * • B
  • + B → • 0

وفي السياق ذاته، لاحظ أن الإغلاق لا يضيف بنود جديدة في جميع الحالات. نواصل هذه العملية حتى لا نجد مجموعات بند جديد. لمجموعات البند 1 و 2 و 4 لن تكون هناك انتقالات حين لا توجد النقطة أمام أي رمز. بالنسبة لمجموعة البند 3 نرى أن لنقطة أمام الطرفيات'*' و'+. لـ '*' الانتقال يذهب إلى:

+ B → • 1

مجموعة البند 7

ومن جهة أخرى، لمجموعة البند 5 يجب النظر في المحطات الطرفية '0' و'1' والمحطة الغير طرفية B للمحطات الطرفية، نرى أن الناتج المجموعات المغلقة تساويى البنود التي وجدت بالفعل 1 و 2 على التوالي. بالنسبة للمحطة الغير طرفية B الانتقال يذهب إلى:

إجراءات التحليل

علاوةً على ذلك، StateInput StreamOutput StreamStackNext Action 0 1+1$ [0] Shift 2 2 +1$ [0,2] Reduce 5 4 +1$ 5 [0,4] Reduce 3 3 +1$ 5,3 [0,3] Shift 6 6 1$ 5,3 [0,3,6] Shift 2 2 $ 5,3 [0,3,6,2] Reduce 5 8 $ 5,3,5 [0,3,6,8] Reduce 2 3 $ 5,3,5,2 [0,3] Accept

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

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.