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

العودية اليسرى (بالانجليزية : 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 على موقع واي باك مشين.
    • بوابة علم الحاسوب
    • بوابة فلسفة
    • بوابة منطق
    • بوابة برمجة الحاسوب
    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.