افتح القائمة الرئيسية

العودية اليسرى (بالانجليزية : Left Recursion ) في نظرية اللغة الشكلية لعلوم الكمبيوتر ، فإن العودية اليسرى هي حالة خاصة من العودية ( recursion ) حيث يتم التعرف على سلسلة كجزء من لغة من خلال حقيقة أنها تتحلل إلى سلسلة من تلك اللغة نفسها على اليسار ولاحقة على اليمين. فعلى سبيل المثال ، يمكن التعرف على  (1 + 2 + 3 ) كمجموع لأنه يمكن تقسيمها إلى (1 + 2) ايضا كمجموع و (+ 3) كلاحقة مناسبة.

محتويات

العودية اليسرىعدل

من حيث القواعد النحوية الخالية من السياق (context free grammer) تكون الغير طرفية (nonterminal) متكررة اليسار (left recursive ) إذا كان الرمز الموجود في أقصى اليسار في أحد منتجاته هو نفسه في حالة العودية اليسرى المباشرة (direct left recursion) أو يمكن أن يصنع من خلال بعض تسلسل البدائل في حالة العودية اليسرى الغير مباشرة (indirect left recursion ) .

القواعد النحوية تكون متكررة اليسار فقط اذا وجد رمز غير طرفي يمكن ان يستمد إلى شكل رسومي مع نفسه كرمز في أقصى اليسار [1] على سبيل المثال :

A --> +Aα

حيث ان + تشير إلى عملية إنشاء بدائل أو أكثر ,و α اي تسلسل من الرموز الطرفية والغير طرفية

العودية اليسرى المباشرةعدل

تحدث عندما يكون هناك  استبدال واحد فقط الذي يتطلب قاعدة النموذج التالي

A--> Aα

حيث ان α عبارة عن سلسلة من الرموز الغير طرفية , على سبيل المثال

Expression --> Expression + term

العودية اليسرى الغير مباشرةعدل

تحدث عندما يكون هناك  عدة بدائل وهو يستلزم مجموعة من القواعد التي تتبع النمط التالي

A0 --> β0 A1 α0

A1 --> β1 A2 α2 .....

An --> βn A1 αn

حيث ان α , β عبارة عن سلسلة من الرموز الطرفية والغير طرفية .

المصادرعدل

  1. ^ Notes on Formal Language Theory and Parsing, James Power, Department of Computer Science National University of Ireland, Maynooth Maynooth, Co. Kildare, Ireland.JPR02 نسخة محفوظة 28 أغسطس 2017 على موقع واي باك مشين.
 
هذه بذرة مقالة عن الحاسوب أو العاملين في هذا المجال، بحاجة للتوسيع. شارك في تحريرها.