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

مجزئ يسار يمين في علوم الحاسب الآلي، هو مجزئ يقرأ الإدخال من اليسار إلى اليمين (كما ستظهر في العرض المرئي)، وتنتج استخلاص أقصى اليمين. مصطلح LR(k) parser يستخدم أيضاً ؛ حيث K تشير إلى عدد الغير مستهلك "look ahead" رموز المدخلات التي تستخدم في صنع القرارات التحليل. عادة ما تكون K هي 1 والعبارة LR parser عادة ما تستخدم للإشارة إلى هذه الحالة.
القواعد اللغوية لكثير من لغات البرمجة يمكن تحديدها بقواعد هي LR(1) أو ما يقارب ذلك،، ولهذا السبب LR parsers غالبا ما تستخدم من قبل برامج المترجم لإجراء تحليل القواعد اللغوية من شفرة المصدرsource code.
LR parser يمكن إنشاءه من قواعد السياق الحر context-free grammar من خلال برنامج يسمى parser generator (مولد المحلل) أو مكتوب بخط اليد من قبل المبرمج. قواعد السياق الحر context-free grammar يصنف كـ LR(k) إذا كان هناك محلل LR(k) له، على النحو الذي يحدده مولد المحلل parser generator.
ويقال أن LR parser لإجراء تحليل من أسفل إلى أعلى لأنه يحاول أستخلاص إنتاجات أعلى مستوى نحوي عن طريق البناء من الأوراق.
قواعد السياق الحر الحتمية deterministic context-free language هي لغة يوجد بها بعض قراعد LR(k) كل قواعد LR(k) k > 1 يمكن أن تحول ميكانيكيا إلى قواعد LR(1) لنفس اللغة، في حين أن قواعد LR(0) لنفس اللغة قد لا تكون موجودة، لغات LR(0) هي مجموعة فرعية مناسبة من تلك الحتمية.
LR parser مبنى على خوارزمية (أو لوغرتمية) التي يقودها جدول محلل parser table، تركيبة البيانات التي تحتوي على قواعد لغة الكمبيوتر التي يتم تحليلها. حتى المصطلح LR parser في الواقع يشير لفئة من المحلل التي يمكن أن تقوم بمعالجة تقريباً أي لغة برمجة، ما دام جدول المحلل متوفر للغة البرمجة. يتم إنشاء جدول المحلل بواسطة برنامج يسمى مولد المحلل parser generator.
LR parsing يمكن تعميمها كلغة سياق حر تعسفية تحلل بدون عقوبة للتشغيل، حتى لقواعد LR(k). هذا لان معظم لغات البرمجة يمكن التعبير عنها بقواعدLR(k). حيث أن K وثابت صغير (عادة يكون1). علما بأن تحليل القواعد الغير LR(k) هو أمر ضخم أبطأ (المكعب بدلا من التربيعي بالنسبة لطول الإدخال).
LR parsing يمكن أن تتعامل مع أكبر مجموعة من اللغات من LL parsing، وهي أيضا أفضل في التقرير عن الخطأ، أي أنه يكشف الأخطاء النحوية عندما لاتتفق المدخل مع القواعد في أقرب وقت ممكن. هذا على النقيض مع LL(k) (أو أسوأ من ذلك، محلل LL(*) 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 parsers

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

مثال البناء

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

تجول

محلل يبدأ مع المكدس تحتوي فقط على الحالة الأولي ('0') :
[0]
الرمز الأول من سلسلة الإدخال التي يراها المحلل اللغوي هو '1'. من أجل معرفة ما الإجراء القادم هو العمل (shift إزاحة، reduceتخفيض, acceptقبول أو errorخطأ)، تتم فهرسة جدول الإجراءات مع الحالة الحالية (نتذكر أن "الحالة الراهنة" ليست سوى كل ما هو على أعلى المكدس)، والتي في هذه الحالة هو 0، ورمز الإدخال الحالي، وهو '1'. جدول الإجراءات يحدد التحول shift إلى الحالة 2، وهكذا تدفع الحالة 2 فوق المكدس (مرة أخرى، تذكر أن كل معلومات الحالة توجد في المكدس، لذلك "التحول إلى الحالة 2" هو نفس دفع 2 على المكدس). ينجم عن ذلك مكدس
[0 '1' 2]
حيث الجزء العلوي من المكدس هة الحالة 2. من أجل التفسير نظهر أيضا الرمز (على سبيل المثال '1', B) التي تسببت الانتقال إلى الحالة القادمة، وعلى الرغم من ذلك بالمعنى الدقيق أنها ليست جزءا من المكدس.
في الحالة (2) جدول الإجراءات يقول انه بغض النظر عما هو طرفي نراه على تدفق المدخلات، ينبغي أ نخفض مع القاعدة اللغوية 5. إذا كان الجدول صحيح، هذا يعني أن المحلل قد تعرف على الجانب الأيمن من القاعدة 5، والتي في الواقع هي الحالة. في هذه الحالة نكتب 5 إلى تدفق المخرجات، ادفع حالة واحدة من المكدس (حيث الجانب الأيمن من القاعدة لديه رمز واحد)، وادفع على المكدس الحالة من الخلية في جدول الانتقال للحالة 0 و B، أي الحالة 4. ينجم عن ذلك المكدس:
[0 B 4]
مع ذلك، في الحالة 4 جدول الإجراءات يقول إنه يجب علينا القيام بتخفيض للمادة 3. حتى نكتب 3 إلى تدفق الإخراج، ادفع حالة واحدة من المكدس، وابحث عن الحالة الجديدة في جدول الانتقال للحالة 0 وE، وهي الحالة 3. الناتج المكدس :
[0 E 3]
الطرفية التالية التي يراها المحلل هي '+' ووفقا لجدول الإجراءات يجب أن تذهب بعد ذلك إلى الحالة (6) :
[0 E 3 '+' 6]
لاحظ أن الناتج مكدس يمكن أن يفسرعلى أنه تاريخ حالة محدودة أوتوماتيكيا التي قرأت E الغير طرفية يليها '+' الطرفية. يتم تعريف جدول الانتقال لهذه الألية عن طريق إجراءات التحول shift actions في جدول الإجراءات والانتقالات في جدول الانتقالات.
الطرفية التالية هي الآن '1' وهذا يعني أن علينا إجراء التحول shift والانتقال إلى الحالة 2 :
[0 E 3 '+' 6 '1' 2]
مثلما جاء في لاسابق '1' وهذه تخفض إلى B لإعطاء المكدس التالي :
[0 E 3 '+' 6 B 8]
لاحظ مرة أخرى أن المكدس يتوافق مع قائمة الحالات الأوتوكاتيكية المحدودة التي قرأت E الغير طرفية، تليها '+' وثم B الغير طرفية. في الحالة 8 نقوم دائما بخفض للمادة 2. لاحظ أن أعلى 3 حالات على مكدس تتوافق مع الرموز الثلاثة في الجانب الأيمن من المادة 2.
[0 E 3]
وأخيرا، نقرأ '$' من تدفق الإدخال وهذا يعني أنه وفقا لجدول الإجراءات (الحالة الحالية هو 3) المحلل يقبل سلسلة الإدخال. أعداد القواعد التي سوف تتم كتابتها إلى تدفق الإخراج سوف تكون [5, 3, 5, 2] الذي هو في الواقع الاشتقاق أقصى اليمينrightmost derivation من السلســـلة "1 + 1" في الاتجاه المعاكس.

البنود

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

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

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

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

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

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

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

قواعد مضافة

قبل أن نبدأ في تحديد الانتقال بين مختلف الحالات، القواعد دائما مزاد عليها بقواعد إضافية (0) S → E
حيث S انه هو رمز بداية جديدة وE هو رمز البداية القديم. المحلل سوف يستخدم هذه القاعدة للتخفيض بالضبط متى يتم قبول سلسلة الإدخال.
على سبيل المثال سوف نتخذ نفس القاعدة كما في السابق ونزيد عليها : (0) S → E (1) E → E * B (2) E → E + B (3) E → B (4) B → 0 (5) B → 1 
ولهذه القواعد المضافة سوف نحدد مجموعات البند والتحولات بينها.

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

من هذا الجدول ومجموعة البند هذه التي وجدت نبني جداول الإجراءات وجداول الانتقال على النحو التالي :
1. يتم نسخ أعمدة المحطات الغير طرفية إلى جدول الانتقال goto
2. يتم نسخ أعمدة المحطات الطرفية إلى جدول الإجراءات كتحول
3. يتم إضافة عمود إضافي لل'$' (نهاية المدخلات) إلى جداول الإجراءات الذي يحتوي على acc قبول كل مجموعة بند تحتوي على S → E •.
4. إذا كانت مجموعة البند i تحتوي على بند من النموذج A → w • and A → w هي القاعدة m مع m > 0 ثم الصف للحالة i في جدول الإجراءات يتم تعبئتة تماما مع إجراء الخفض rm.
يمكن للقارئ أن يتحقق من أن هذه النتائج واقعية في جدول العمل والانتقالات التي عرضت من قبل هنا.

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

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

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

يتم بناء الأوتوكاتيكية في مثل هذه الطريقة مضمونة القطعية. ومع ذلك، عندما تضاف إجراءات الخفض إلى جدول الإجراءات ما يمكن أن يحدث هو أن الخانة نفسها يكون بها إجراء خفض وإجراءات التحول (تعارض إجراءات الخفض والتحول) (a shift-reduce conflict) أو مع إجراءان اثنين للخفض (تعارض إجراءات الخفض والخفض) (a reduce-reduce conflict). ومع ذلك، يمكن أن يتبين أنه عندما يحدث هذا فإن القواعد لا تكون قواعد LR(0).
وثمة مثال صغير للقواعد الغير LR(0) مع تعارض إجراءات الخفض والتحول هو : (1) E → 1 E (2) E → 1
واحدة من مجموعات البند نجدها :
مجموعة بند 1
E → 1 • E 
E → 1 • 
+ E → • 1 E 
+ E → • 1
هناك تعارض إجراءات الخفض والتحول في مجموعة هذا البند لأن في الخلية في جدول الإجراءات لمجموعة البند هذه والطرفية '1' سوف يكون هناك على حد سواء إجراء التحول إلى الحالة (1) وإجراء خفض للمادة 2.
وثمة مثال صغير القواعد الغير LR(0) مع تعارض إجراءات الخفض والخفض، هو : (1) E → A 1 (2) E → B 2 (3) A → 1 (4) B → 1
في هذه الحالة نحصل على مجموعة البند التالية:
مجموعة بند 1
A → 1 • 
B → 1 •
هناك تعارض إجراءات الخفض والخفض في مجموعة البند هذه لأن في الخلايا في جدول الإجراءات لمجموعة البند هذه سوف يكون هناك إجراءان خفض للمادة 3 وواحد للمادة 4.
المثالين المذكورين أعلاه يمكن حلهما عن طريق السماح للمحلل باستخدام محلل المجموعة التالية (انظر محلل اللغة LL LL parser) من المحطة الغير طرفية A لتقرر استخدام واحدة من القواعد مثل قواعد الخفض ؛ انها سوف تستخدم فقط القاعدة A → w للتخفيض إذا كان الرمز التالي على تدفق الإدخال هي المجموعة التالية لـ A هذه النتائج في الحل تسمى محلل LR البسيط Simple LR parsers.