لماذا يجب أن تتعلم عن مجزئ يسار يمين

مجزّئ يسار يمين (بالإنجليزية: LR parser) في علوم الحاسب الآلي، هو مجزئ يقرأ الإدخال من اليسار إلى اليمين (كما ستظهر في العرض المرئي)، وتنتج استخلاص أقصى اليمين. مصطلح 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.