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

العودية اليسرى (بالانجليزية : 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.