محلل LR

في علوم الحاسوب ، تُعدّ محللات LR نوعًا من المحللات التصاعدية التي تُحلل اللغات الحتمية الخالية من السياق في زمن خطي. ^{[ 1 ]} توجد عدة أنواع من محللات LR: محللات SLR ، ومحللات LALR ، ومحللات LR(1) الكلاسيكية ، ومحللات LR(1) الدنيا ، ومحللات LR المعممة (محللات GLR). يمكن توليد محللات LR بواسطة مولد محللات من قواعد نحوية رسمية تُحدد بنية اللغة المراد تحليلها. وهي تُستخدم على نطاق واسع في معالجة لغات الحاسوب .

يقرأ محلل LR (من اليسار إلى اليمين، مع عكس الاشتقاق الأيمن) النص المدخل من اليسار إلى اليمين دون الرجوع للخلف (وهذا ينطبق على معظم المحللات)، وينتج اشتقاقًا أيمنًا معكوسًا: فهو يُجري تحليلًا من الأسفل إلى الأعلى - وليس تحليل LL من الأعلى إلى الأسفل أو تحليلًا مخصصًا. غالبًا ما يتبع اسم "LR" مُحدد رقمي، كما في "LR(1)" أو أحيانًا "LR( k )". لتجنب التراجع أو التخمين، يُسمح لمحلل LR بالاطلاع على k من رموز الإدخال المُسبقة قبل تحديد كيفية تحليل الرموز السابقة. عادةً ما تكون قيمة k هي 1 ولا تُذكر. غالبًا ما يسبق اسم "LR" مُحددات أخرى، كما في "SLR" و"LALR". اقترح كنوت استخدام رمز "LR( k )" للقواعد النحوية ليرمز إلى "قابل للترجمة من اليسار إلى اليمين بحد k ". ^[¹^]

تُعدّ محللات LR حتمية؛ فهي تُنتج تحليلًا صحيحًا واحدًا دون تخمين أو تراجع، في زمن خطي. وهذا مثالي للغات الحاسوب، لكن محللات LR غير مناسبة للغات البشرية التي تحتاج إلى أساليب أكثر مرونة ولكنها أبطأ حتمًا. بعض الأساليب التي يمكنها تحليل لغات خالية من السياق (مثل Cocke–Younger–Kasami و Earley و GLR ) يكون أداؤها في أسوأ الحالات O( n³ ⁾ . أما الأساليب الأخرى التي تتراجع أو تُنتج تحليلات متعددة فقد تستغرق زمنًا أُسّيًا عند سوء التخمين. ^{[ 2 ]}

تشترك جميع محللات الإزاحة والاختزال ، بما فيها محللات الأسبقية ، في الخصائص المذكورة أعلاه لـ L و R و k . ولكن اصطلاحًا، يشير مصطلح LR إلى شكل التحليل الذي ابتكره دونالد كنوث ، ويستثني أساليب الأسبقية الأقل قوة (مثل محلل أسبقية المعامل ). ^[¹^] تستطيع محللات LR التعامل مع نطاق أوسع من اللغات والقواعد النحوية مقارنةً بمحللات الأسبقية أو تحليل LL من أعلى إلى أسفل . ^[³^] يعود ذلك إلى أن محلل LR ينتظر حتى يرى مثالًا كاملًا لنمط نحوي معين قبل أن يلتزم بما وجده. أما محلل LL، فيتعين عليه أن يقرر أو يخمن ما يراه في وقت أبكر بكثير، عندما يكون قد رأى فقط رمز الإدخال الأيسر من ذلك النمط.

ملخص

تعريف قواعد LR(k)

بينما $\operatorname {LR} (k)$ تُستخدم القواعد النحوية بشكل أساسي في التحليل النحوي ، والتعريف التالي لـ $\operatorname {LR} (k)$ تستخدم القواعد النحوية بدلاً من ذلك المنظور المزدوج: منظور البدء برمز البداية $S$ وتطبيق قواعد الإنتاج النحوية بشكل متكرر لإنتاج سلسلة من الصيغ الجملية . ونعني بالجملة صيغة جملية خالية من أي رموز غير طرفية .

الصيغة الجملية الصحيحة هي أي صيغة جملية يمكن الحصول عليها بالبدء برمز البداية $S$ وتطبيق قواعد الإنتاج بشكل متكرر على الرموز غير الطرفية الموجودة في أقصى اليمين فقط. يستخدم إطار عمل LR بأكمله أشكال الجمل اليمنى فقط.

تعريف $\operatorname {LR} (k)$ أصبح الآن مختصراً: قواعد نحوية خالية من السياق $G$ يُطلق عليه اسم $\operatorname {LR} (k)$ إذا كان لكل زوج من اشتقاقات الصيغ الجملية اليمنى التي تتطابق مع النمط التالي، فيمكننا أن نستنتج أن ${\color {blue}\alpha }={\color {green}\alpha '}$ و ${\color {red}B}={\color {green}B'}$ : ${\begin{matrix}S&{\overset {*}{\underset {G}{\implies }}}&{\color {blue}\alpha }{\color {red}B}{\color {blue}c_{1}c_{2}\dotsb c_{k}}{\color {purple}\gamma }&{\underset {G}{\implies }}&{\color {blue}\alpha \beta c_{1}c_{2}\dotsb c_{k}}\color {purple}\gamma \\S&{\overset {*}{\underset {G}{\implies }}}&{\color {green}\alpha 'B'}{\color {blue}c_{1}c_{2}\dotsb c_{k}}\color {magenta}\gamma '&{\underset {G}{\implies }}&{\color {blue}\alpha \beta c_{1}c_{2}\dotsb c_{k}}\color {magenta}\gamma '\end{matrix}}$

مزيد من المصطلحات والمناقشات

البادئة ${\color {blue}\alpha }$ يُطلق عليه اسم البادئة القابلة للتطبيق ، السلسلة الفرعية ${\color {blue}\beta }$ يُطلق عليه اسم المقبض ، والخيط ${\color {blue}c_{1}c_{2}\dotsb c_{k}}$ يُطلق عليه اسم " النظر المسبق ". لاحظ أنه من تعريف "صيغة الجملة الصحيحة"، لدينا أن ${\color {blue}c_{1},c_{2},\dotsc ,c_{k}}$ ، $\color {purple}\gamma$ و $\color {magenta}\gamma '$ جميعها رموز نهائية. لاحظ أن التحليل يتكون من تطبيق قواعد الإنتاج بشكل عكسي ، وهو ما يُسمى بالاختزال . علاوة على ذلك، سيزور المحلل الرموز في سلسلة الإدخال من اليسار إلى اليمين، وهو عكس الاشتقاقات المذكورة أعلاه. الفكرة الأساسية وراء $\operatorname {LR} (k)$ إذن، الخاصية هي أن السياق الوحيد المطلوب للتقليل ${\color {blue}\beta }$ ل ${\color {red}B}$ (أ) البادئة الصالحة بأكملها ${\color {blue}\alpha }$ (ii) المقبض ${\color {blue}\beta }$ نفسها (ثالثاً) و $k$ رموز إضافية للتنبؤ. والجدير بالذكر أنه لا يهم ما إذا ${\color {purple}\gamma }={\color {magenta}\gamma '}$ أو لا.

سواء كان CFG أم لا $\operatorname {LR} (k)$ مقابل مبلغ ثابت $k$ قابل للتقرير . ما إذا كان هناك أي $k$ والتي تتضمن مجموعة أدوات CFG $G$ يكون $\operatorname {LR} (k)$ لا يمكن حسم الأمر. عملياً، $k=1$ يتم اختيارها. أي لغة حتمية خالية من السياق تقبل $\operatorname {LR} (1)$ القواعد النحوية، ولكن هذا ليس صغيرًا ولا فريدًا بشكل عام، وكل من هذه القواعد النحوية سيؤدي إلى شجرة تحليل مختلفة لنفس السلسلة.

شجرة تحليل من الأسفل إلى الأعلى، على سبيل المثال A * 2 + 1

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

في الخطوة السادسة من عملية التحليل، تم تحليل "A * 2" فقط، ولكن بشكل غير كامل. لا يوجد سوى الزاوية السفلية اليسرى المظللة من شجرة التحليل. لم يتم العثور على أي من عقد شجرة التحليل المرقمة من 7 فما فوق. العقد 3 و4 و6 هي جذور أشجار فرعية معزولة للمتغير A، والمعامل *، والرقم 2، على التوالي. يتم الاحتفاظ بهذه العقد الجذرية الثلاث مؤقتًا في مكدس التحليل. الجزء المتبقي غير المُحلل من دفق الإدخال هو "+ 1".

تغيير الإجراءات وتقليلها

كما هو الحال مع محللات الإزاحة والاختزال الأخرى، يعمل محلل LR من خلال القيام بمجموعة من خطوات الإزاحة وخطوات الاختزال.

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

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

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

يُعزى جزء كبير من كفاءة محلل LR إلى كونه حتميًا. ولتجنب التخمين، غالبًا ما ينظر محلل LR إلى الرمز التالي الذي تم مسحه ضوئيًا (باتجاه اليمين) قبل اتخاذ قرار بشأن كيفية التعامل مع الرموز التي تم مسحها ضوئيًا سابقًا. يعمل الماسح المعجمي على رمز واحد أو أكثر قبل المحلل. تُمثل الرموز التي يتم النظر إليها مسبقًا "السياق الأيمن" لقرار التحليل. ^{[ 4 ]}

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

على غرار محللات الإزاحة والاختزال الأخرى، ينتظر محلل LR بشكل كسول حتى يفحص ويحلل جميع أجزاء بنية معينة قبل تحديد ماهية البنية المدمجة. ثم يتصرف المحلل فورًا على التركيبة دون مزيد من الانتظار. في مثال شجرة التحليل، تُختزل العبارة A إلى Value ثم إلى Products في الخطوات من 1 إلى 3 بمجرد رؤية lookahead *، بدلاً من الانتظار لاحقًا لتنظيم تلك الأجزاء من شجرة التحليل. وتستند قرارات كيفية التعامل مع A فقط إلى ما رآه المحلل والماسح الضوئي بالفعل، دون النظر إلى العناصر التي تظهر لاحقًا على اليمين.

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

خطوات التحليل من الأسفل إلى الأعلى، على سبيل المثال A * 2 + 1

خطوة	تحليل المكدس	غير محلل	تحويل/تقليل
0	فارغ	أ * ٢ + ١	يحول
1	بطاقة تعريف	* 2 + 1	القيمة → المعرف
2	قيمة	* 2 + 1	المنتجات ← القيمة
3	منتجات	* 2 + 1	يحول
4	منتجات *	2 + 1	يحول
5	المنتجات * عدد صحيح	+ 1	القيمة → عدد صحيح
6	المنتجات * القيمة	+ 1	المنتجات ← المنتجات * القيمة
7	منتجات	+ 1	المجموع ← المنتجات
8	المجاميع	+ 1	يحول
9	المجموع +	1	يحول
10	المجموع + عدد صحيح	نهاية الصفحة	القيمة → عدد صحيح
11	المجموع + القيمة	نهاية الصفحة	المنتجات ← القيمة
12	المجموع + المنتجات	نهاية الصفحة	المجاميع → المجاميع + النواتج
13	المجاميع	نهاية الصفحة	يقبل

الخطوة السادسة تطبق قاعدة نحوية ذات أجزاء متعددة:

المنتجات ← المنتجات * القيمة

يتطابق هذا مع الجزء العلوي من المكدس الذي يحتوي على العبارات المُحللة "... المنتجات * القيمة". تستبدل خطوة الاختزال هذه النسخة من الجانب الأيمن للقاعدة، "المنتجات * القيمة"، برمز الجانب الأيسر للقاعدة، وهو هنا رمز أكبر للمنتجات. إذا أنشأ المحلل اللغوي أشجار تحليل كاملة، فسيتم دمج الأشجار الثلاث للمنتجات الداخلية، و*، والقيمة، بجذر شجرة جديد للمنتجات. وإلا، فسيتم إخراج التفاصيل الدلالية من المنتجات الداخلية والقيمة إلى مرحلة لاحقة من مراحل المُصرّف ، أو دمجها وحفظها في رمز المنتجات الجديد. ^{[ 5 ]}

خطوات تحليل LR على سبيل المثال A * 2 + 1

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

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

خطوة	تحليل _حالة المكدس [ _حالة الرمز ]*	انظر إلى الأمام	غير ممسوح ضوئياً	إجراء المحلل اللغوي	قاعدة نحوية	الولاية التالية
0	₀	بطاقة تعريف	* 2 + 1	يحول		9
1	₀ id ₉	*	2 + 1	يقلل	القيمة → المعرف	7
2	القيمة₀₇	*	2 + 1	يقلل	المنتجات ← القيمة	4
3	₀ منتجات₄	*	2 + 1	يحول		5
4	_٠ منتجات_٤ *_٥	عدد صحيح	+ 1	يحول		8
5	₀ منتجات₄ ₅ int* ₈	+	1	يقلل	القيمة → عدد صحيح	6
6	_٠ منتجات_٤ *_٥ القيمة_٦	+	1	يقلل	المنتجات ← المنتجات * القيمة	4
7	₀ منتجات₄	+	1	يقلل	المجموع ← المنتجات	1
8	₀ مجموع₁	+	1	يحول		2
9	مجموع_{0 هو}₁ +₂	عدد صحيح	نهاية الصفحة	يحول		8
10	₀ مجموع₁ +₂ عدد صحيح ₈	نهاية الصفحة		يقلل	القيمة → عدد صحيح	7
11	مجموع_{0 =}₁ +₂ =₇	نهاية الصفحة		يقلل	المنتجات ← القيمة	3
12	₀ مجموع₁ +₂ نواتج₃	نهاية الصفحة		يقلل	المجاميع → المجاميع + النواتج	1
13	₀ مجموع₁	نهاية الصفحة		يقبل

في الخطوة الأولية 0، يتم تقسيم تيار الإدخال "A * 2 + 1" إلى

قسم فارغ في مكدس التحليل،
تم مسح النص "A" كرمز تعريف ، و
النص المتبقي غير الممسوح ضوئياً "* 2 + 1".

يبدأ مكدس التحليل بالاحتفاظ بالحالة الأولية 0 فقط. عندما ترى الحالة 0 معرف التطلع ، فإنها تعرف كيفية نقل هذا المعرف إلى المكدس، ومسح رمز الإدخال التالي * ، والتقدم إلى الحالة 9.

في الخطوة الرابعة، يتم حاليًا تقسيم تدفق الإدخال الكلي "A * 2 + 1" إلى

القسم المُحلل "A *" مع عبارتين متراكبتين هما Products و * ،
تم مسح النص "2" كرمز عدد صحيح ، و
النص المتبقي غير الممسوح ضوئياً " + 1".

الحالات المقابلة للعبارات المكدسة هي 0 و4 و5. الحالة الحالية، الموجودة في أقصى اليمين على المكدس، هي الحالة 5. عندما ترى الحالة 5 العدد الصحيح المتوقع ، فإنها تعرف أن تنقل هذا العدد الصحيح إلى المكدس كعبارة خاصة بها، وتفحص رمز الإدخال التالي + ، وتتقدم إلى الحالة 8.

في الخطوة 12، تم استهلاك كامل تدفق الإدخال ولكن لم يتم تنظيمه بالكامل. الحالة الحالية هي 3. عندما ترى الحالة 3 إشارة التوقع eof ، فإنها تعرف كيفية تطبيق قاعدة النحو المكتملة.

المجاميع → المجاميع + النواتج

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

قواعد المثال أ * ٢ + ١

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

إن قواعد اللغة المستخدمة هنا هي مجموعة فرعية صغيرة من لغة جافا أو لغة سي :

r0: الهدف → مجموع نهاية الملف

r1: المجاميع → المجاميع + النواتج

r2: المجاميع → النواتج

r3: المنتجات → المنتجات * القيمة

r4: المنتجات ← القيمة

r5: القيمة → عدد صحيح

r6: القيمة → المعرف

الرموز الطرفية للقواعد النحوية هي رموز متعددة الأحرف أو "رموز مميزة" يعثر عليها الماسح المعجمي في دفق الإدخال . تشمل هذه الرموز + و * و int لأي ثابت عددي صحيح ، و id لأي اسم مُعرِّف، و eof لنهاية ملف الإدخال. لا تُعير القواعد النحوية اهتمامًا لقيم int أو تهجئة id ، كما لا تُعير اهتمامًا للفراغات أو فواصل الأسطر. تستخدم القواعد النحوية هذه الرموز الطرفية دون تعريفها. وهي دائمًا عُقد طرفية (في الطرف السفلي المتفرع) لشجرة التحليل.

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

يمكن وصف أي لغة برمجة بعدة قواعد نحوية مختلفة. يستطيع محلل LR(1) التعامل مع العديد من القواعد النحوية الشائعة، ولكن ليس جميعها. عادةً ما يكون من الممكن تعديل القاعدة النحوية يدويًا لتتوافق مع قيود تحليل LR(1) وأداة التوليد.

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

جدول تحليل القواعد النحوية للمثال

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

تكون جداول التحليل أكبر بكثير من القواعد النحوية. يصعب حساب جداول LR بدقة يدويًا للقواعد النحوية الكبيرة. لذلك، يتم اشتقاقها آليًا من القواعد النحوية بواسطة أداة توليد محلل نحوي مثل Bison . ^{[ 6 ]}

بحسب طريقة توليد الحالات وجدول التحليل، يُسمى المحلل الناتج إما محلل SLR (محلل LR بسيط) ، أو محلل LALR (محلل LR استباقي) ، أو محلل LR معياري . تتعامل محللات LALR مع قواعد نحوية أكثر من محللات SLR. أما محللات LR المعيارية فتتعامل مع قواعد نحوية أكثر، ولكنها تستخدم حالات أكثر بكثير وجداول أكبر حجمًا. مثال على ذلك قاعدة SLR.

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

يحتوي النصف الأيسر من الجدول، المخصص للإجراء ، على أعمدة لرموز التوقع النهائي. تحدد هذه الخلايا ما إذا كان إجراء المحلل التالي هو الإزاحة (إلى الحالة n )، أو الاختزال (بحسب قاعدة القواعد النحوية r _n ).

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

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

التيار		نظرة مستقبلية					الجانب الأيسر: انتقل إلى
ولاية	القواعد الحالية	عدد صحيح	بطاقة تعريف	*	+	نهاية الصفحة	المجاميع	منتجات	قيمة
0	الهدف ← • مجموع	8	9				1	4	7
1	الهدف ← المجاميع • نهاية المجاميع ← المجاميع • + النواتج				2	يقبل
2	المجاميع → المجاميع + • النواتج	8	9					3	7
3	المجاميع ← المجاميع + المنتجات • المنتجات ← المنتجات • * القيمة			5	r1	r1
4	المجموع ← المنتجات • المنتجات ← المنتجات • * القيمة			5	r2	r2
5	المنتجات ← المنتجات * • القيمة	8	9						6
6	المنتجات ← المنتجات * القيمة •			r3	r3	r3
7	المنتجات ← القيمة •			r4	r4	r4
8	القيمة → عدد صحيح •			r5	r5	r5
9	القيمة ← المعرف •			r6	r6	r6

في الحالة الثانية أعلاه، وجد المحلل للتو علامة الجمع ( +) لقاعدة القواعد النحوية وأدخلها.

r1: المجاميع → المجاميع + • النواتج

العبارة المتوقعة التالية هي "المنتجات". تبدأ "المنتجات" بالرمزين النهائيين int أو id . إذا كان الرمز المُتوقع هو أيٌّ منهما، يقوم المُحلل بإزاحتهما إلى الداخل وينتقل إلى الحالة 8 أو 9 على التوالي. عند العثور على "المنتجات"، ينتقل المُحلل إلى الحالة 3 لتجميع القائمة الكاملة للأوامر والعثور على نهاية القاعدة r0. يمكن أن تبدأ "المنتجات" أيضًا بالرمز غير النهائي Value. بالنسبة لأي رمز مُتوقع أو غير نهائي آخر، يُعلن المُحلل عن خطأ في بناء الجملة.

في الحالة 3، وجد المحلل للتو عبارة "المنتجات"، والتي يمكن أن تكون من قاعدتين نحويتين محتملتين:

r1: المجاميع → المجاميع + النواتج •

r3: المنتجات → المنتجات • * القيمة

لا يمكن تحديد الخيار بين r1 و r3 بمجرد النظر إلى العبارات السابقة. يجب على المحلل اللغوي التحقق من رمز التنبؤ لتحديد الإجراء المطلوب. إذا كان رمز التنبؤ هو * ، فهذا يعني أنه في القاعدة 3، وبالتالي ينتقل المحلل اللغوي إلى الحالة 5. أما إذا كان رمز التنبؤ هو eof ، فهذا يعني أنه في نهاية القاعدة 1 والقاعدة 0، وبالتالي ينتهي عمل المحلل اللغوي.

في الحالة 9 أعلاه، جميع الخلايا غير الفارغة وغير التي تحتوي على أخطاء تخص نفس عملية الاختزال r6. توفر بعض المحللات الوقت ومساحة الجدول بعدم فحص رمز التنبؤ في هذه الحالات البسيطة. وبالتالي، يتم اكتشاف أخطاء بناء الجملة لاحقًا، بعد بعض عمليات الاختزال غير الضارة، ولكن قبل إجراء عملية الإزاحة التالية أو قرار المحلل.

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

حلقة محلل LR

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

الحالة العليا في مكدس التحليل هي الحالة s ، والحالة المتوقعة الحالية هي الرمز الطرفي t . ابحث عن إجراء المحلل التالي من الصف s والعمود t في جدول إجراءات التوقع. هذا الإجراء هو إما Shift أو Reduce أو Accept أو Error.

Shift n :

انقل الطرفية المطابقة t إلى مكدس التحليل وامسح رمز الإدخال التالي في المخزن المؤقت للتوقع.

قم بدفع الحالة التالية n إلى مكدس التحليل كحالة حالية جديدة.

اختزل rm _: طبّق قاعدة النحو rm _: Lhs → _S1 S2 _... S _L

قم بإزالة رموز L العلوية المطابقة (وأشجار التحليل وأرقام الحالة المرتبطة بها) من مكدس التحليل.

هذا يكشف عن حالة سابقة p كانت تتوقع وجود رمز Lhs.

قم بضم أشجار التحليل L معًا كشجرة تحليل واحدة مع رمز الجذر الجديد Lhs.

ابحث عن الحالة التالية n من الصف p والعمود Lhs من جدول LHS Goto.

ادفع الرمز والشجرة الخاصة بالجانب الأيسر إلى مكدس التحليل.

قم بدفع الحالة التالية n إلى مكدس التحليل كحالة حالية جديدة.

يبقى كل من تدفق البيانات المدخلة وتدفق البيانات المتطلعة دون تغيير.

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

عادةً ما تخزن مكدس محلل LR حالات آلة LR(0) فقط، حيث يمكن اشتقاق رموز القواعد النحوية منها (في الآلة، تُعلَّم جميع انتقالات الإدخال إلى حالة معينة بنفس الرمز، وهو الرمز المرتبط بتلك الحالة). علاوة على ذلك، نادرًا ما تكون هذه الرموز ضرورية لأن الحالة هي كل ما يهم عند اتخاذ قرار التحليل. ^{[ 7 ]}

تحليل مولد LR

يمكن لمعظم مستخدمي مولدات محلل LR تخطي هذا القسم من المقالة.

الولايات ذات المسؤولية المحدودة

الحالة 2 في جدول التحليل المثال مخصصة للقاعدة التي تم تحليلها جزئيًا

r1: المجاميع → المجاميع + • النواتج

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

تُسمى القواعد التي تم تحليلها جزئيًا لحالة ما "بنود LR(0) الأساسية". ويضيف مُولِّد المُحلِّل قواعد أو بنودًا إضافية لجميع الخطوات التالية المُحتملة في بناء المنتجات المتوقعة.

r3: المنتجات → • المنتجات * القيمة

r4: المنتجات → • القيمة

r5: القيمة → • عدد صحيح

r6: القيمة → • المعرف

توجد علامة • في بداية كل قاعدة من هذه القواعد المضافة؛ ولم يقم المحلل اللغوي بعدُ بتأكيد أي جزء منها وتحليله. تُسمى هذه العناصر الإضافية "إغلاق" العناصر الأساسية. لكل رمز غير طرفي يلي علامة • مباشرةً ، يُضيف المُولِّد القواعد التي تُعرِّف ذلك الرمز. يُضيف هذا المزيد من علامات • ، وربما رموزًا تابعة مختلفة. تستمر عملية الإغلاق هذه حتى يتم توسيع جميع الرموز التابعة. تبدأ الرموز غير الطرفية التابعة للحالة 2 بالمنتجات. ثم تُضاف القيمة عن طريق الإغلاق. الرموز الطرفية التابعة هي int و id .

تُظهر عناصر النواة والإغلاق معًا جميع الطرق القانونية الممكنة للانتقال من الحالة الحالية إلى الحالات المستقبلية وإكمال العبارات. إذا ظهر رمز تابع في عنصر واحد فقط، فإنه يؤدي إلى حالة تالية تحتوي على عنصر أساسي واحد فقط مع علامة "•" المتقدمة. لذا ، يؤدي int إلى الحالة التالية 8 مع عنصر أساسي.

r5: القيمة → عدد صحيح •

إذا ظهر رمز التابع نفسه في عدة عناصر، فلن يتمكن المحلل اللغوي بعد من تحديد القاعدة المطبقة. لذا، يؤدي هذا الرمز إلى حالة تالية تُظهر جميع الاحتمالات المتبقية، مع تقدم علامة • مرة أخرى . يظهر "المنتجات" في كل من r1 و r3. لذا، يؤدي "المنتجات" إلى الحالة التالية 3 مع "الأساس".

r1: المجاميع → المجاميع + النواتج •

r3: المنتجات → المنتجات • * القيمة

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

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

تُسمى هذه الحالات "حالات LR(0)" لأنها تستخدم قيمة k = 0 للتنبؤ المسبق، أي بدون تنبؤ مسبق. يتم فحص رموز الإدخال فقط عند إدخال الرمز. ويتم فحص التنبؤات المسبقة للاختزالات بشكل منفصل بواسطة جدول التحليل، وليس بواسطة الحالات المُعدّدة نفسها.

آلة الحالة المحدودة

يصف جدول التحليل جميع حالات LR(0) الممكنة وانتقالاتها. تشكل هذه الحالات آلة حالة محدودة (FSM). آلة الحالة المحدودة هي محرك بسيط لتحليل اللغات البسيطة غير المتداخلة، دون استخدام مكدس. في تطبيق LR هذا، تحتوي "لغة الإدخال" المعدلة لآلة الحالة المحدودة على رموز طرفية وغير طرفية، وتغطي أي لقطة مكدس مُحللة جزئيًا من تحليل LR الكامل.

تذكر الخطوة 5 من مثال خطوات التحليل:

< خطوة	تحليل _{حالة المكدس،}_حالة الرمز ...	انظر إلى الأمام	غير ممسوح ضوئياً
5	₀ منتجات₄ ₅ int* ₈	+	1

يُظهر مكدس التحليل سلسلة من انتقالات الحالة، بدءًا من الحالة الابتدائية 0، مرورًا بالحالة 4، ثم إلى الحالة 5، وصولًا إلى الحالة الحالية 8. الرموز الموجودة على مكدس التحليل هي رموز الإزاحة أو الانتقال لتلك الانتقالات. بمعنى آخر، يمكن لآلة الحالة المحدودة مسح التدفق "Products * int + 1" (دون استخدام مكدس آخر) والعثور على العبارة الكاملة الموجودة في أقصى اليسار والتي يجب اختزالها تاليًا. وهذا هو دورها بالفعل!

كيف يمكن لآلة الحالة المحدودة (FSM) القيام بذلك بينما تحتوي اللغة الأصلية غير المُحللة على تداخلات واستدعاءات متكررة، وتتطلب حتمًا مُحللًا مزودًا بمكدس؟ تكمن الحيلة في أن كل ما يقع على يسار قمة المكدس قد تم اختزاله بالكامل. هذا يُزيل جميع الحلقات والتداخلات من تلك العبارات. تستطيع آلة الحالة المحدودة تجاهل جميع بدايات العبارات القديمة، وتتبع أحدث العبارات التي قد تُستكمل لاحقًا. يُطلق على هذا في نظرية الانحدار اللوجستي اسم "البادئة القابلة للتطبيق".

مجموعات لوك آيد

توفر الحالات والانتقالات جميع المعلومات اللازمة لإجراءات الإزاحة والانتقال في جدول التحليل. كما يحتاج المولد إلى حساب مجموعات التوقع المسبق لكل إجراء اختزال.

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

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

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

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

استعادة أخطاء بناء الجملة

يمكن لمحللات LR توليد رسائل خطأ مفيدة نوعًا ما لأول خطأ في بناء الجملة في البرنامج، وذلك ببساطة عن طريق سرد جميع الرموز النهائية التي كان من الممكن أن تظهر لاحقًا بدلًا من رمز التوقع الخاطئ غير المتوقع. لكن هذا لا يساعد المحلل على معرفة كيفية تحليل بقية البرنامج المدخل للبحث عن أخطاء أخرى مستقلة. إذا تعافى المحلل بشكل سيئ من الخطأ الأول، فمن المرجح جدًا أن يحلل كل شيء آخر بشكل خاطئ وينتج سلسلة من رسائل الخطأ الزائفة غير المفيدة.

في مولدات المحللات اللغوية yacc و bison، يمتلك المحلل آلية مخصصة للتخلي عن العبارة الحالية، وتجاهل بعض العبارات المُحللة ورموز التنبؤ المحيطة بالخطأ، وإعادة مزامنة التحليل عند فاصل موثوق على مستوى العبارة مثل الفاصلة المنقوطة أو الأقواس. غالبًا ما يكون هذا فعالًا للسماح للمحلل اللغوي والمترجم بمراجعة بقية البرنامج.

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

أنواع مختلفة من محللات LR

يُحدد مُولِّد مُحلِّل LR الإجراء المُناسب لكل تركيبة من حالة المُحلِّل ورمز التنبؤ. تُحوَّل هذه القرارات عادةً إلى جداول بيانات للقراءة فقط، تُشغِّل حلقة مُحلِّل عامة مُستقلة عن القواعد والحالة. ولكن توجد أيضًا طرق أخرى لتحويل هذه القرارات إلى مُحلِّل نشط.

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

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

هناك شكل آخر يستبدل جدول التحليل بقواعد مطابقة الأنماط في اللغات غير الإجرائية مثل برولوج .

تستخدم محللات LR المعممة (GLR) تقنيات LR التصاعدية لإيجاد جميع التحليلات الممكنة للنص المدخل، وليس تحليلًا صحيحًا واحدًا فقط. وهذا ضروري للقواعد النحوية الغامضة، كما هو الحال في اللغات البشرية. تُحسب أشجار التحليل الصحيحة المتعددة في آنٍ واحد، دون الحاجة إلى التراجع. تُفيد GLR أحيانًا في لغات البرمجة التي يصعب وصفها بقواعد LALR(1) الخالية من التعارض.

تستخدم محللات الزاوية اليسرى LC تقنيات LR التصاعدية للتعرف على الطرف الأيسر لقواعد النحو البديلة. وعندما يتم حصر البدائل في قاعدة واحدة محتملة، ينتقل المحلل إلى تقنيات LL(1) التنازلية لتحليل بقية تلك القاعدة. تتميز محللات LC بجداول تحليل أصغر من محللات LALR، وبقدرة أفضل على تشخيص الأخطاء. لا توجد مولدات شائعة الاستخدام لمحللات LC الحتمية. تُعد محللات LC متعددة التحليل مفيدة للغات البشرية ذات القواعد النحوية الضخمة.

نظرية

ابتكر دونالد كنوث محللات LR في عام 1965 كتعميم فعال لمحللات الأسبقية . وقد أثبت كنوث أن محللات LR هي أكثر المحللات العامة الممكنة التي ستظل فعالة حتى في أسوأ الحالات.

"يمكن تحليل قواعد LR( k ) بكفاءة مع وقت تنفيذ يتناسب بشكل أساسي مع طول السلسلة." ^{[ 8 ]}

لكل k ≥ 1 ، "يمكن توليد لغة بواسطة قواعد LR( k ) إذا وفقط إذا كانت حتمية [وخالية من السياق]، إذا وفقط إذا كان من الممكن توليدها بواسطة قواعد LR(1)." ^{[ 9 ]}

بمعنى آخر، إذا كانت لغة ما معقولة بما يكفي للسماح بمحلل نحوي فعال ذي تمريرة واحدة، فيمكن وصفها بقواعد نحوية من نوع LR( k ). ويمكن دائمًا تحويل هذه القواعد النحوية آليًا إلى قواعد نحوية مكافئة (لكنها أكبر) من نوع LR(1). لذا، فإن طريقة التحليل النحوي من نوع LR(1) كانت، نظريًا، قوية بما يكفي للتعامل مع أي لغة معقولة. عمليًا، تقترب القواعد النحوية الطبيعية للعديد من لغات البرمجة من أن تكون من نوع LR(1).

كانت محللات LR التقليدية التي وصفها كنوت تحتوي على عدد كبير جدًا من الحالات وجداول تحليل ضخمة للغاية، ما جعلها غير عملية بالنسبة للذاكرة المحدودة لأجهزة الكمبيوتر في ذلك العصر. أصبح تحليل LR عمليًا عندما اخترع فرانك ديريمر محللات SLR و LALR ذات عدد أقل بكثير من الحالات. ^{[ 10 ]}^{[ 11 ]}

للاطلاع على التفاصيل الكاملة حول نظرية LR وكيفية اشتقاق محللات LR من القواعد النحوية، انظر كتاب نظرية التحليل والترجمة والترجمة، المجلد 1 (آهو وأولمان). ^{[ 7 ]}^{[ 2 ]}

تقوم محللات إيرلي بتطبيق تقنيات ورموز محللات LR على مهمة توليد جميع التحليلات الممكنة للقواعد النحوية الغامضة مثل اللغات البشرية.

بينما تتمتع قواعد LR( k ) بقوة توليد متساوية لجميع قيم k ≥ 1، فإن حالة قواعد LR(0) تختلف قليلاً. يُقال إن اللغة L تمتلك خاصية البادئة إذا لم تكن أي كلمة فيها بادئة فعلية لكلمة أخرى في L. ^{[ 12 ]} تمتلك اللغة L قواعد LR(0) إذا وفقط إذا كانت L لغة حتمية خالية من السياق وتتمتع بخاصية البادئة. ^{[ 13 ]} ونتيجة لذلك، تكون اللغة L حتمية خالية من السياق إذا وفقط إذا كانت L $ تمتلك قواعد LR(0) ^، حيث "$" ليس رمزًا من رموز أبجدية L. ^[¹⁴ ]

مثال إضافي 1 + 1

يستخدم هذا المثال لتحليل LR القواعد النحوية الصغيرة التالية مع رمز الهدف E:

(1) E → E * B

(2) E → E + B

(3) هـ → ب

(4) ب → 0

(5) ب → 1

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

1 + 1

جدول الإجراءات والانتقال إلى الجداول

تبدو جداول تحليل LR(0) الخاصة بهذه القواعد النحوية كما يلي:

ولاية	فعل					انتقل إلى
	*	+	0	1	دولار	هـ	ب
0			s1	s2		3	4
1	r4	r4	r4	r4	r4
2	r5	r5	r5	r5	r5
3	s5	s6			حساب
4	r3	r3	r3	r3	r3
5			s1	s2			7
6			s1	s2			8
7	r1	r1	r1	r1	r1
8	r2	r2	r2	r2	r2

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

يشير رمز Shift ، الذي يُكتب على النحو التالي "s n "، إلى أن الحالة التالية هي n
تُكتب كلمة reduce على النحو التالي "r m "، وتشير إلى أنه يجب إجراء عملية اختزال باستخدام قاعدة النحو m.
كلمة accept ، والتي تُكتب على شكل "acc"، تشير إلى أن المحلل يقبل السلسلة في دفق الإدخال.

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

خطوات التحليل

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

ولاية	دفق الإدخال	دفق الإخراج	كومة	الخطوة التالية
0	1 + 1 دولار		[0]	الوردية الثانية
2	+ 1 دولار		[0,2]	قلل 5
4	+ 1 دولار	5	[0,4]	قلل 3
3	+ 1 دولار	5.3	[0,3]	الوردية السادسة
6	1 دولار	5.3	[0,3,6]	الوردية الثانية
2	دولار	5.3	[0,3,6,2]	قلل 5
8	دولار	5،3،5	[0,3,6,8]	خفض 2
3	دولار	5،3،5،2	[0,3]	يقبل

شرح تفصيلي

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

[ 0 ]

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

[ 0 '1' 2 ]

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

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

[ 0 ب 4 ]

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

[ 0 E 3 ]

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

[ 0 E 3 '+' 6 ]

يمكن تفسير المكدس الناتج على أنه تاريخ آلة ذات حالات محدودة قرأت للتو رمزًا غير طرفي E متبوعًا برمز طرفي '+'. يتم تعريف جدول الانتقالات لهذه الآلة من خلال إجراءات الإزاحة في جدول الإجراءات وإجراءات الانتقال في جدول الانتقال.

المحطة الطرفية التالية هي الآن '1' وهذا يعني أن المحلل اللغوي يقوم بعملية إزاحة وينتقل إلى الحالة 2:

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

وكما هو الحال مع الرقم '1' السابق، يتم اختزال هذا الرقم إلى B مما يعطي المكدس التالي:

[ 0 E 3 '+' 6 B 8 ]

يمثل المكدس قائمة حالات آلة محدودة قرأت رمزًا غير طرفي E، متبوعًا بعلامة "+"، ثم رمزًا غير طرفي B. في الحالة 8، يُجري المحلل اللغوي دائمًا عملية اختزال وفقًا للقاعدة 2. تتوافق الحالات الثلاث الأولى في المكدس مع الرموز الثلاثة في الجانب الأيمن من القاعدة 2. في هذه الحالة، نسحب 3 عناصر من المكدس (لأن الجانب الأيمن من القاعدة يحتوي على 3 رموز) ونبحث عن حالة الانتقال للرمزين E و0، وبالتالي نعيد الحالة 3 إلى المكدس.

[ 0 E 3 ]

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

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

يستخدم هذا القسم نفس قواعد النحو المستخدمة في القسم السابق:

(1) E → E * B

(2) E → E + B

(3) هـ → ب

(4) ب → 0

(5) ب → 1

أغراض

يعتمد بناء جداول التحليل هذه على مفهوم عناصر LR(0) (والتي تُسمى هنا ببساطة " عناصر ")، وهي قواعد نحوية مُضاف إليها نقطة خاصة في مكان ما على الجانب الأيمن. على سبيل المثال، تحتوي القاعدة (2) 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) جنوب → شرق eof

حيث S هو رمز البداية الجديد وE هو رمز البداية القديم. سيستخدم المحلل اللغوي هذه القاعدة للاختزال تحديدًا عندما يقبل سلسلة الإدخال كاملةً.

في هذا المثال، يتم توسيع نفس القواعد النحوية المذكورة أعلاه على النحو التالي:

(0) جنوب → شرق eof

(1) E → E * B

(2) E → E + B

(3) هـ → ب

(4) ب → 0

(5) ب → 1

من أجل هذه القواعد النحوية المعززة سيتم تحديد مجموعات العناصر والانتقالات بينها.

بناء الجدول

إيجاد مجموعات العناصر التي يمكن الوصول إليها والانتقالات بينها

تتمثل الخطوة الأولى في بناء الجداول في تحديد الانتقالات بين مجموعات العناصر المغلقة. سيتم تحديد هذه الانتقالات كما لو كنا نتعامل مع آلة حالة محدودة قادرة على قراءة الرموز الطرفية وغير الطرفية. حالة البداية لهذه الآلة هي دائمًا إغلاق العنصر الأول من القاعدة المضافة: S → • E eof:

مجموعة العناصر 0

S → • E eof

+ هـ → • هـ * ب

+ هـ → • هـ + ب

+ هـ → • ب

+ ب → • ٠

+ ب → • 1

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

بدءًا من الحالة الابتدائية (S0)، يتم تحديد جميع الحالات التي يمكن الوصول إليها من هذه الحالة. يمكن إيجاد الانتقالات الممكنة لمجموعة عناصر بالنظر إلى الرموز (النهائية وغير النهائية) الموجودة بعد النقاط؛ في حالة مجموعة العناصر 0، تكون هذه الرموز هي النهائيات '0' و'1' وغير النهائية E وB. لإيجاد مجموعة العناصر التي يمثلها كل رمز ${\textstyle x\in \{0,1,E,B\}}$ ويؤدي ذلك إلى اتباع الإجراء التالي لكل رمز من الرموز:

خذ المجموعة الفرعية S من جميع العناصر في مجموعة العناصر الحالية حيث توجد نقطة أمام الرمز محل الاهتمام x .
لكل عنصر في S ، حرك النقطة إلى يمين x .
أغلق مجموعة العناصر الناتجة.

بالنسبة للطرفية '0' (أي حيث x = '0') ينتج عن ذلك ما يلي:

مجموعة العناصر 1

ب → ٠ •

وبالنسبة للطرفية '1' (أي حيث x = '1') ينتج عن ذلك ما يلي:

مجموعة العناصر 2

ب → 1 •

وبالنسبة للرمز غير النهائي E (أي حيث x = E) ينتج عن ذلك ما يلي:

مجموعة العناصر 3

جنوب ← شرق • نهاية الفصل

E → E • * B

E → E • + B

وبالنسبة للرمز غير الطرفي B (أي حيث x = B)، ينتج عن ذلك ما يلي:

مجموعة العناصر 4

هـ → ب •

لا تضيف عملية الإغلاق عناصر جديدة في جميع الحالات - ففي المجموعات الجديدة أعلاه، على سبيل المثال، لا توجد رموز غير طرفية تتبع النقطة.

تستمر العملية المذكورة أعلاه حتى لا يتم العثور على مجموعات عناصر جديدة. بالنسبة لمجموعات العناصر 1 و2 و4، لن تكون هناك انتقالات لأن النقطة ليست أمام أي رمز. أما بالنسبة لمجموعة العناصر 3، فلدينا نقاط أمام الرموز الطرفية '*' و'+'. بالنسبة للرمز ${\textstyle x={\texttt {*}}}$ ينتقل الانتقال إلى:

مجموعة العناصر 5

E → E * • B

+ ب → • ٠

+ ب → • 1

ولـ ${\textstyle x={\texttt {+}}}$ ينتقل الانتقال إلى:

مجموعة العناصر 6

E → E + • B

+ ب → • ٠

+ ب → • 1

والآن، تبدأ المرحلة الثالثة.

بالنسبة لمجموعة العناصر رقم 5، يجب مراعاة الرموز الطرفية '0' و'1' والرمز غير الطرفي B، ولكن مجموعات العناصر المغلقة الناتجة للرموز الطرفية تساوي مجموعتي العناصر 1 و2 اللتين تم العثور عليهما مسبقًا، على التوالي. أما بالنسبة للرمز غير الطرفي B، فيتم الانتقال إلى:

مجموعة العناصر 7

E → E * B •

بالنسبة لمجموعة العناصر 6، يجب مراعاة الرمزين الطرفيين '0' و'1' والرمز غير الطرفي B، ولكن كما في السابق، فإن مجموعات العناصر الناتجة للرموز الطرفية تساوي مجموعات العناصر 1 و2 التي تم العثور عليها بالفعل. أما بالنسبة للرمز غير الطرفي B، فإن الانتقال يكون كالتالي:

مجموعة العناصر 8

E → E + B •

لا تحتوي مجموعتا العناصر الأخيرتان 7 و8 على أي رموز بعد النقاط، لذا لن تُضاف أي مجموعات عناصر جديدة، وبذلك تكتمل عملية توليد العناصر. يظهر أدناه نموذج الآلة المحدودة، حيث تمثل مجموعات العناصر حالاتها.

أصبح جدول الانتقال الخاص بالآلة الآن كما يلي:

مجموعة العناصر	*	+	0	1	هـ	ب
0			1	2	3	4
1
2
3	5	6
4
5			1	2		7
6			1	2		8
7
8

إنشاء جداول الإجراءات والانتقال

انطلاقاً من هذا الجدول ومجموعات العناصر التي تم العثور عليها، يتم إنشاء جدول الإجراءات وجدول الانتقال على النحو التالي:

يتم نسخ أعمدة الرموز غير الطرفية إلى جدول الانتقال.
يتم نسخ أعمدة المحطات الطرفية إلى جدول الإجراءات كإجراءات تحويل.
تمت إضافة عمود إضافي لرمز "$" (نهاية الإدخال) إلى جدول الإجراءات. تمت إضافة إجراء "acc" إلى عمود "$" لكل مجموعة عناصر تحتوي على عنصر من الشكل S → w • eof.
إذا كانت مجموعة العناصر i تحتوي على عنصر من الشكل A → w • و A → w هي القاعدة m مع m > 0 فإن صف الحالة i في جدول الإجراءات يتم ملؤه بالكامل بإجراء الاختزال r m .

يمكن للقارئ التحقق من أن هذه الخطوات تؤدي إلى الإجراء والانتقال إلى الجدول المعروض سابقًا.

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

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

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

تعارضات في الجداول المُنشأة

تم تصميم الآلة بطريقة تضمن حتميتها. مع ذلك، عند إضافة عمليات اختزال إلى جدول العمليات، قد يحدث أن تُملأ الخلية نفسها بعملية اختزال وعملية إزاحة (تعارض إزاحة-اختزال )، أو بعمليتي اختزال مختلفتين (تعارض اختزال-اختزال ). ومع ذلك، يمكن إثبات أنه في هذه الحالة، لا تكون القواعد النحوية من نوع LR(0). ومن الأمثلة الواقعية الكلاسيكية على تعارض الإزاحة-الاختزال مشكلة "else" المعلقة .

مثال بسيط على قواعد نحوية غير LR(0) مع تعارض بين الإزاحة والاختزال هو:

(1) E → 1 E

(2) E → 1

إحدى مجموعات العناصر التي تم العثور عليها هي:

مجموعة العناصر 1

E → 1 • E

E → 1 •

+ E → • 1 E

+ E → • 1

يوجد تعارض بين الإزاحة والاختزال في مجموعة العناصر هذه: عند إنشاء جدول الإجراءات وفقًا للقواعد المذكورة أعلاه، تحتوي الخلية الخاصة بـ [مجموعة العناصر 1، الطرفية '1'] على s1 (الإزاحة إلى الحالة 1) و r2 (الاختزال باستخدام قاعدة القواعد النحوية 2).

مثال بسيط على قواعد نحوية غير LR(0) مع تعارض في عملية الاختزال-الاختزال هو:

(1) E → A 1

(2) E → B 2

(3) أ → 1

(4) ب → 1

في هذه الحالة، يتم الحصول على مجموعة العناصر التالية:

مجموعة العناصر 1

أ → 1 •

ب → 1 •

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

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

انظر أيضاً

مراجع

1 2 3 كنوت، دي إي (يوليو 1965). "حول ترجمة اللغات من اليسار إلى اليمين" . المعلومات والتحكم . 8 (6): 607-639 . doi : 10.1016/S0019-9958(65)90426-2 .
1 2 أهو، ألفريد ف .؛ أولمان، جيفري د. (1972). نظرية التحليل والترجمة والترجمة (المجلد 1: التحليل). (طبعة مُعاد طباعتها). إنجلوود كليفس، نيوجيرسي : برنتيس هول . ISBN 978-0139145568.
↑ مقارنة نظرية اللغة بين قواعد اللغة LL و LR
↑ هندسة المترجم (الطبعة الثانية)، بقلم كيث كوبر وليندا توركزون، مورغان كوفمان 2011.
↑ الصياغة والترجمة، بقلم تشارلز فيشر، ورون سيترون، وريتشارد لوبلان، أديسون ويسلي 2009.
↑ Flex & Bison: أدوات معالجة النصوص، بقلم جون ليفين، دار نشر أورايلي ميديا 2009.
1 2 المترجمات: المبادئ والتقنيات والأدوات (الطبعة الثانية)، بقلم ألفريد أهو، ومونيكا لام، ورافي سيثي، وجيفري أولمان، برنتيس هول 2006.
↑ كنوت (1965)، ص 638
↑ كنوت (1965)، ص 635. لم يذكر كنوت القيد k ≥ 1 هناك، ولكنه مطلوب بموجب نظرياته التي أشار إليها، أي في الصفحتين 629 و630. وبالمثل، فإن القيد على اللغات الخالية من السياق مفهوم ضمنيًا من السياق.
↑ مترجمون عمليون للغات LR( k )، بقلم فرانك ديريمر، أطروحة دكتوراه من معهد ماساتشوستس للتكنولوجيا 1969.
↑ قواعد LR( k ) البسيطة، بقلم فرانك ديريمر، Comm. ACM 14:7 1971.
↑ هوبكروفت، جون إي.؛ أولمان، جيفري د. (1979). مقدمة في نظرية الأوتوماتا واللغات والحوسبة . أديسون-ويسلي. ISBN 0-201-02988-X.هنا: التمرين 5.8، صفحة 121.
↑ هوبكروفت، أولمان (1979)، النظرية 10.12، ص 260
↑ هوبكروفت، أولمان (1979)، النتيجة ص 260

للمزيد من القراءة

تشابمان، نايجل ب.، تحليل LR: النظرية والتطبيق ، مطبعة جامعة كامبريدج ، 1987. ISBN 0-521-30413-X
بيجر، د.، طريقة عامة عملية لبناء محللات LR(k). أكتا إنفورماتيكا 7، 249 - 268 (1977)
"بناء المترجمات: المبادئ والتطبيق" بقلم كينيث سي. لاودن. رقم ISBN 0-534-939724

روابط خارجية

dickgrune.com ، تقنيات التحليل - دليل عملي، الطبعة الأولى. تتضمن صفحة الويب الخاصة بالكتاب ملف PDF قابل للتنزيل.
محاكي التحليل اللغوي: يُستخدم هذا المحاكي لإنشاء جداول التحليل اللغوي LR ولحل تمارين الكتاب.
تفاصيل داخلية لمحلل LALR(1) تم إنشاؤه بواسطة GNU Bison - مشاكل التنفيذ
ملاحظات الدورة التدريبية حول تحليل LR
تعارضات Shift-reduce و Reduce-reduce في محلل LALR
مثال على محلل LR
بناء محلل LR(k) عملي
خوارزمية هونالي LR(k)

[Knuth_1965-1] 1 2 3 كنوت، دي إي (يوليو 1965). "حول ترجمة اللغات من اليسار إلى اليمين" . المعلومات والتحكم . 8 (6): 607-639 . doi : 10.1016/S0019-9958(65)90426-2 .

[AhoUllman_1972-2] 1 2 أهو، ألفريد ف .؛ أولمان، جيفري د. (1972). نظرية التحليل والترجمة والترجمة (المجلد 1: التحليل). (طبعة مُعاد طباعتها). إنجلوود كليفس، نيوجيرسي : برنتيس هول . ISBN 978-0139145568.

[3] مقارنة نظرية اللغة بين قواعد اللغة LL و LR

[4] هندسة المترجم (الطبعة الثانية)، بقلم كيث كوبر وليندا توركزون، مورغان كوفمان 2011.

[5] الصياغة والترجمة، بقلم تشارلز فيشر، ورون سيترون، وريتشارد لوبلان، أديسون ويسلي 2009.

[6] Flex & Bison: أدوات معالجة النصوص، بقلم جون ليفين، دار نشر أورايلي ميديا 2009.

[Compilers_2006-7] 1 2 المترجمات: المبادئ والتقنيات والأدوات (الطبعة الثانية)، بقلم ألفريد أهو، ومونيكا لام، ورافي سيثي، وجيفري أولمان، برنتيس هول 2006.

[8] كنوت (1965)، ص 638

[9] كنوت (1965)، ص 635. لم يذكر كنوت القيد k ≥ 1 هناك، ولكنه مطلوب بموجب نظرياته التي أشار إليها، أي في الصفحتين 629 و630. وبالمثل، فإن القيد على اللغات الخالية من السياق مفهوم ضمنيًا من السياق.

[10] مترجمون عمليون للغات LR( k )، بقلم فرانك ديريمر، أطروحة دكتوراه من معهد ماساتشوستس للتكنولوجيا 1969.

[11] قواعد LR( k ) البسيطة، بقلم فرانك ديريمر، Comm. ACM 14:7 1971.

[12] هوبكروفت، جون إي.؛ أولمان، جيفري د. (1979). مقدمة في نظرية الأوتوماتا واللغات والحوسبة . أديسون-ويسلي. ISBN 0-201-02988-X.هنا: التمرين 5.8، صفحة 121.

[13] هوبكروفت، أولمان (1979)، النظرية 10.12، ص 260

[14] هوبكروفت، أولمان (1979)، النتيجة ص 260

[ 1 ]

[ 2 ]

[

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

،

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗