الاستدعاء الذاتي الايسر
الاستدعاء الذاتي الايسر (بالانجليزية:left recursion) في اللغة الرسمية لعلم الحاسوب الاستدعاء الذاتي الأيسر عبارة عن حالة خاصة يُعرف فيها المقطع على أنه جزء من اللغة وهذا من خلال الحقيقة القائلة أنه يتم تحليل نفس اللغة (على اليسار) واللاحقة (على اليمين)، فعلى سبيل المثال 1+2+3 يمكن التعرف عليها على أنها محصلة حيث تم تفكيكها إلى 1 + 2 وهي محصلة و + 3 لاحقة مناسبة. بلغة القواعد النحوية يقوم الرمز غير الطرفي باستدعاء ذاتي أيسر إذا كان الرمز الموجود أقصى اليسار في أحد منتجاته هو نفسه (في حالة الاستدعاء الذاتي الأيسر المباشر) أو يمكن أن يحدث بنفسه من خلال سلسلة من البدائل (في حالة الاستدعاء الذاتي الأيسر غير المباشر)
التعريف[عدل]
يحدث للقواعد النحوية استدعاء ذاتي أيسر إذا وجد رمز غير طرفي A والذي يكون شكل جملة بنفسه مثل الرمز الموجود في أقصى اليسار – فرمزيا[1]
A → + Aa,
حيث → + يعني العملية التي يتم فيها عمل بديل واحد أو أكثر و a عبارة عن أي سلسلة من الرموز الطرفية وغير الطرفية.
الاستدعاء الذاتي الايسر المباشر[عدل]
يحدث الاستدعاء الذاتي الأيسر عندما يمكن إشباع التعريف ببديل واحد وهذا يتطلب قاعدة من الشكل A → Aa, حيث أن a عبارة عن سلسلة من الرموز الطرفية وغير الطرفية فعلى سبيل المثال فإن القاعدة: - Expression → expression + term تعبير ← تعبير + مصطلح عبارة عن استدعاء ذاتي أيسر مباشر وقد يبدو المحلل اللغوي الهابط ذو الاستدعاء الذاتي من اليسار إلى اليمين هكذا
== الاستدعاء الذاتي الايسر الغير مباشر ==
يحدث الاستدعاء الذاتي الأيسر غير المباشر عندما يتم تعرف الاستدعاء الذاتي من خلال بدائل عديدة وهذا يستلزم مجموعة من القواعد تتبع النمط A→ B0 A1 a0 A1 →B1 A2 a1 An → Bn A0 an حيث أن B0, B1 , ……… Bn و a0, a1, ….., an عبارة عن أي سلسلة من الرموز الطرفية وغير الطرفية، وينبغي ملاحظة أن هذه السلاسل يمكن أن تكون فارغة – الاستنتاج A0→ B0A1a0 → + A1 a0 → b1 A2 a1a0 → + …. → + A0an ….a1 a0
ثم يعطي A0 كأقصى يسار في شكله الجملة النهائي
إزالة الاستدعاء الذاتي[عدل]
الاستدعاء الذاتي الأيسر يطرح عادة مشاكل على المحللات اللغوية لأنه إما يؤدي بهم إلى استدعاء ذاتي مطلق وغير محدد (كما في حالة المحللات اللغوية النزولية من القمة للأسفل) لأنهم يتوقعون قواعد في شكل عادي يمنع هذا (كما في حالة العديد من المحللات اللغوية الصاعدة من القاع للقمة والذي يشمل لوغاريتم CYK، وبناء عليه تعالج القواعد النحوية مسبقا لإزالة الاستدعاء الذاتي الأيسر. إزالة الاستدعاء الذاتي الأيسر المباشر إن اللوغاريتم العام بإزالة الاستدعاء الذاتي الأيسر المباشر يتبع وسائل تحسين عديدة لهذه الطريقة[2]، وبالنسبة لـ A غير الطرفي للاستدعاء الذاتي الأيسر فيطرح أية قواعد للشكل→ A A ويعتبر الباقي: A→Aa1 │….│Aan │B1│…│Bm حيث أن -كل a عبارة عن سلسلة غير فارغة من الرموز الطرفية وغير الطرفية و - كل B عبارة عن سلسلة من الرموز الطرفية وغير الطرفية التي لا تبدأ بـ A ويستبدل هذا بمجموعتين من النتائج حيث توجد مجموعة واحدة لـ A A→B 1 A' │….│Bm A' ومجموعة أخر لرمز A' غير الطرفي (ويسمى عادة «الذيل» أو «الباقي»): A'→ a1 A' │…. │an A' │∈ كرر هذه العملية حتى تتخلص من أي استدعاء ذاتي أيسر وكمثال فكر في القاعدة Expression→ Expression + Expression │integer │string تعبير ←تعبير + تعبير │العدد الصحيح │مقطع ويمكن إعادة كتابة هذ ا لتجنب الاستدعاء الذاتي مثل Expression → integer Expression' │string Expression' Expression' → + Expression Expression' │∈ التعبير ← تعبير بالعدد الصحيح │تعبير بالمقطع التعبير ← + تعبير التعبير │∈ إزالة جميع الاستدعاء الذاتي الأيسر من خلال تأسيس ترتيب طوبولوجي على الرموز غير الطرفية فإن العملية المذكورة أعلاه يمكن أن تمتد لإزالة الاستدعاء الذاتي الأيسر غير المباشر. المدخلات- النحو: مجموعة من الرموز الطرفية A1…..An وصياغاتها. المخرج: النحو المعدل يقوم إحداث نفس اللغة ولكن بدون استدعاء ذاتي أيسر 1. لكل رمز غير طرفي Ai 1- كرر حتى يترك التعدد النحو بدون تغيير. 1- لكل قاعدة Ai →ai, ai تكون سلسلة لكل الرموز الطرفية وغير الطرفية: 1. إذا كان ai يبدأ بالرمز الطرفي Aj وi> j 1- فلنترك Bi ليكون ai بدون قيادته Aj 2. أزل القاعدة Ai → ai 3. لكل قاعدة Aj →aj 1- أضف القاعدة Ai →ajBi 2. أزل الاستدعاء الذاتي الأيسر المباشر كما هو مبين أعلاه ولنلاحظ أن اللوغاريتم حساسة بدرجة عالية للترتيب غير الطرفي وتركز عمليات الوصول للحلول المثلى على اختيار هذا الترتيب بشكل جيد
المصادر[عدل]
- ^ 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 على موقع واي باك مشين.
- ^ Moore، Robert C. (مايو 2000). "Removing Left Recursion from Context-Free Grammars" (PDF). 6th Applied Natural Language Processing Conference: 249–255. مؤرشف من الأصل (PDF) في 2016-03-04.
