العودية اليسرى
العودية اليسرى (بالانجليزية : 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
حيث ان α , β عبارة عن سلسلة من الرموز الطرفية وغير الطرفية .
المصادر
[عدل]- ^ 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 على موقع واي باك مشين.
