مرجع
آخر الزيارات

الاستدعاء الذاتي الايسر

698 كلمة•0 مشاهدة•🗒️ منذ 3 أيام
باختصار: الاستدعاء الذاتي الايسر (بالانجليزية:left recursion). تتناول المقالة 16 قسماً، منها «إزالة الاستدعاء الذاتي الأيسر المباشر»، «الاستدعاء الذاتي الايسر الغير مباشر» و«حيث أن».
المحتويات
  1. إزالة الاستدعاء الذاتي الأيسر المباشر
  2. الاستدعاء الذاتي الايسر الغير مباشر
  3. حيث أن
  4. التعريف
  5. 1- أضف القاعدة Ai →ajBi
  6. إزالة جميع الاستدعاء الذاتي الأيسر
  7. A→B 1 A' │….│Bm A'
  8. الاستدعاء الذاتي الايسر المباشر
  9. A → Aa,
  10. 1. لكل رمز غير طرفي Ai
  11. تعبير ←تعبير + تعبير │العدد الصحيح │مقطع
  12. A → + Aa,
  13. إزالة الاستدعاء الذاتي
  14. An → Bn A0 an
  15. تعبير ← تعبير + مصطلح
  16. A'→ a1 A' │…. │an A' │∈

الاستدعاء الذاتي الايسر (بالانجليزية:left recursion)

ومن ناحية أخرى، بلغة القواعد النحوية يقوم الرمز غير الطرفي باستدعاء ذاتي أيسر إذا كان الرمز الموجود أقصى اليسار في أحد منتجاته هو نفسه (في حالة الاستدعاء الذاتي الأيسر المباشر) أو يمكن أن يحدث بنفسه من خلال سلسلة من البدائل (في حالة الاستدعاء الذاتي الأيسر غير المباشر)

من جانب آخر، في اللغة الرسمية لعلم الحاسوب الاستدعاء الذاتي الأيسر عبارة عن حالة خاصة يُعرف فيها المقطع على أنه جزء من اللغة وهذا من خلال الحقيقة القائلة أنه يتم تحليل نفس اللغة (على اليسار) واللاحقة (على اليمين)، فمثلًا 1+2+3 يمكن التعرف عليها على أنها محصلة حيث تم تفكيكها إلى 1 + 2 وهي محصلة و + 3 لاحقة مناسبة.

إزالة الاستدعاء الذاتي الأيسر المباشر

وفي السياق ذاته، إن اللوغاريتم العام بإزالة الاستدعاء الذاتي الأيسر المباشر يتبع وسائل تحسين عديدة لهذه الطريقة، وبالنسبة لـ A غير الطرفي للاستدعاء الذاتي الأيسر فيطرح أية قواعد للشكل→ A A ويعتبر الباقي:

A→Aa1 │….│Aan │B1│…│Bm

الاستدعاء الذاتي الايسر الغير مباشر

A→ B0 A1 a0

A1 →B1 A2 a1

كذلك، يحدث الاستدعاء الذاتي الأيسر غير المباشر عندما يتم تعرف الاستدعاء الذاتي من خلال بدائل عديدة وهذا يستلزم مجموعة من القواعد تتبع النمط

حيث أن

  • -كل a عبارة عن سلسلة غير فارغة من الرموز الطرفية وغير الطرفية و
  • - كل B عبارة عن سلسلة من الرموز الطرفية وغير الطرفية التي لا تبدأ بـ A
  • ويستبدل هذا بمجموعتين من النتائج حيث توجد مجموعة واحدة لـ A

التعريف

كذلك، يحدث للقواعد النحوية استدعاء ذاتي أيسر إذا وجد رمز غير طرفي A والذي يكون شكل جملة بنفسه مثل الرمز الموجود في أقصى اليسار – فرمزيا

1- أضف القاعدة Ai →ajBi

2. أزل الاستدعاء الذاتي الأيسر المباشر كما هو مبين أعلاه

إضافةً إلى ذلك، ولنلاحظ أن اللوغاريتم حساسة بدرجة عالية للترتيب غير الطرفي وتركز عمليات الوصول للحلول المثلى على اختيار هذا الترتيب بشكل جيد

إزالة جميع الاستدعاء الذاتي الأيسر

وفي هذا الصدد، المدخلات- النحو: مجموعة من الرموز الطرفية A1…..An وصياغاتها.

إضافةً إلى ذلك، المخرج: النحو المعدل يقوم إحداث نفس اللغة ولكن بدون استدعاء ذاتي أيسر

علاوةً على ذلك، من خلال تأسيس ترتيب طوبولوجي على الرموز غير الطرفية فإن العملية المذكورة أعلاه يمكن أن تمتد لإزالة الاستدعاء الذاتي الأيسر غير المباشر.

A→B 1 A' │….│Bm A'

من جهة ثانية، ومجموعة أخر لرمز A' غير الطرفي (ويسمى عادة «الذيل» أو «الباقي»):

الاستدعاء الذاتي الايسر المباشر

في هذا الإطار، يحدث الاستدعاء الذاتي الأيسر عندما يمكن إشباع التعريف ببديل واحد وهذا يتطلب قاعدة من الشكل

A → Aa,

Expression → expression + term

إضافةً إلى ذلك، حيث أن a عبارة عن سلسلة من الرموز الطرفية وغير الطرفية فمثلًا فإن القاعدة: -

1. لكل رمز غير طرفي Ai

  • 1- كرر حتى يترك التعدد النحو بدون تغيير.
  • 1- لكل قاعدة Ai →ai, ai تكون سلسلة لكل الرموز الطرفية وغير الطرفية:
  • 1. إذا كان ai يبدأ بالرمز الطرفي Aj وi> j
  • 1- فلنترك Bi ليكون ai بدون قيادته Aj
  • 2. أزل القاعدة Ai → ai
  • 3. لكل قاعدة Aj →aj

تعبير ←تعبير + تعبير │العدد الصحيح │مقطع

  • ويمكن إعادة كتابة هذ ا لتجنب الاستدعاء الذاتي مثل
  • Expression → integer Expression' │string Expression'
  • Expression' → + Expression Expression' │∈
  • التعبير ← تعبير بالعدد الصحيح │تعبير بالمقطع
  • التعبير ← + تعبير التعبير │∈

A → + Aa,

وفي هذا السياق، حيث → + يعني العملية التي يتم فيها عمل بديل واحد أو أكثر و a عبارة عن أي سلسلة من الرموز الطرفية وغير الطرفية.

إزالة الاستدعاء الذاتي

وفي هذا السياق، الاستدعاء الذاتي الأيسر يطرح عادة مشاكل على المحللات اللغوية لأنه إما يؤدي بهم إلى استدعاء ذاتي مطلق وغير محدد (كما في حالة المحللات اللغوية النزولية من القمة للأسفل) لأنهم يتوقعون قواعد في شكل عادي يمنع هذا (كما في حالة الكثير من المحللات اللغوية الصاعدة من القاع للقمة والذي يشمل لوغاريتم CYK، وبناء عليه تعالج القواعد النحوية مسبقا لإزالة الاستدعاء الذاتي الأيسر.

An → Bn A0 an

وفي هذا السياق، حيث أن B0, B1 , ……… Bn و a0, a1, ….., an عبارة عن أي سلسلة من الرموز الطرفية وغير الطرفية، وينبغي ملاحظة أن هذه السلاسل يمكن أن تكون فارغة – الاستنتاج

ثم يعطي A0 كأقصى يسار في شكله الجملة النهائي

A0→ B0A1a0 → + A1 a0 → b1 A2 a1a0 → + …. → + A0an ….a1 a0

تعبير ← تعبير + مصطلح

ومن ناحية أخرى، عبارة عن استدعاء ذاتي أيسر مباشر وقد يبدو المحلل اللغوي الهابط ذو الاستدعاء الذاتي من اليسار إلى اليمين هكذا

A'→ a1 A' │…. │an A' │∈

  • كرر هذه العملية حتى تتخلص من أي استدعاء ذاتي أيسر
  • وكمثال فكر في القاعدة
  • Expression→ Expression + Expression │integer │string

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.