التكرار الأيسر

الموسوعة الحرة

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

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

تعريف

تكون القواعد النحوية ذات استدعاء ذاتي من اليسار إذا وفقط إذا وُجد رمز غير طرفيأ{\displaystyle A}يمكن اشتقاق ذلك إلى شكل جملة يكون فيه نفسه هو الرمز الأيسر. [ 1 ] رمزياً،

أ⇒+أα{\displaystyle A\Rightarrow ^{+}A\alpha }،

أين⇒+{\displaystyle \Rightarrow ^{+}}يشير إلى عملية إجراء استبدال واحد أو أكثر، وα{\displaystyle \alpha }هي أي سلسلة من الرموز الطرفية وغير الطرفية.

التكرار المباشر لليسار

يحدث الاستدعاء الذاتي المباشر من اليسار عندما يمكن تحقيق التعريف باستبدال واحد فقط. ويتطلب ذلك قاعدة من الشكل التالي:

أ→أα{\displaystyle A\to A\alpha }

أينα{\displaystyle \alpha }هي سلسلة من الرموز غير الطرفية والطرفية. على سبيل المثال، القاعدة

هـxصرهـssأناoن→هـxصرهـssأناoن+تيهـرم{\displaystyle {\mathit {Expression}}\to {\mathit {Expression}}+{\mathit {Term}}}

هي دالة تكرارية مباشرة من اليسار. قد يبدو محلل الانحدار التكراري من اليسار إلى اليمين لهذه القاعدة كما يلي:

void Expression () { Expression (); match ( '+' ); Term (); }

وسيؤدي تنفيذ مثل هذا الكود إلى حدوث تكرار لا نهائي.

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

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

أ0→β0أ1α0{\displaystyle A_{0}\to \beta _{0}A_{1}\alpha _{0}}
أ1→β1أ2α1{\displaystyle A_{1}\to \beta _{1}A_{2}\alpha _{1}}
⋯{\displaystyle \cdots }
أن→βنأ0αن{\displaystyle A_{n}\to \beta _{n}A_{0}\alpha _{n}}

أينβ0،β1،...،βن{\displaystyle \beta _{0},\beta _{1},\ldots ,\beta _{n}}هي متواليات يمكن أن ينتج عن كل منها سلسلة فارغة ، بينماα0،α1،...،αن{\displaystyle \alpha _{0},\alpha _{1},\ldots ,\alpha _{n}}قد تكون أي سلسلة من الرموز الطرفية وغير الطرفية. لاحظ أن هذه السلاسل قد تكون فارغة. الاشتقاق

أ0⇒β0أ1α0⇒+أ1α0⇒β1أ2α1α0⇒+⋯⇒+أ0αن...α1α0{\displaystyle A_{0}\Rightarrow \beta _{0}A_{1}\alpha _{0}\Rightarrow ^{+}A_{1}\alpha _{0}\Rightarrow \beta _{1}A_{2}\alpha _{1}\alpha _{0}\Rightarrow ^{+}\cdots \Rightarrow ^{+}A_{0}\alpha _{n}\dots \alpha _{1}\alpha _{0}}

ثم يعطيأ0{\displaystyle A_{0}}كما هو الحال في أقصى اليسار في شكله النهائي للجملة.

الاستخدامات

يُستخدم الاستدعاء الذاتي الأيسر عادةً كمصطلح لجعل العمليات تجميعية من اليسار : أي أن التعبير a+b-c-d+eيُقيّم على أنه (((a+b)-c)-d)+e. في هذه الحالة، يمكن تحقيق ترتيب التقييم هذا من خلال القواعد النحوية الثلاث.

هـxصرهـssأناoن→تيهـرم{\displaystyle {\mathit {Expression}}\to {\mathit {Term}}}
هـxصرهـssأناoن→هـxصرهـssأناoن+تيهـرم{\displaystyle {\mathit {Expression}}\to {\mathit {Expression}}+{\mathit {Term}}}
هـxصرهـssأناoن→هـxصرهـssأناoن-تيهـرم{\displaystyle {\mathit {Expression}}\to {\mathit {Expression}}-{\mathit {Term}}}

هذه لا تسمح إلا بتحليلهـxصرهـssأناoن{\displaystyle {\mathit {Expression}}}a+b-c-d+eباعتبارها تتكون منهـxصرهـssأناoن{\displaystyle {\mathit {Expression}}}a+b-c-dوتيهـرم{\displaystyle {\mathit {Term}}}e، والتي a+b-c-dبدورها تتكون منهـxصرهـssأناoن{\displaystyle {\mathit {Expression}}}a+b-cوتيهـرم{\displaystyle {\mathit {Term}}}d، بينما a+b-cيتكون منهـxصرهـssأناoن{\displaystyle {\mathit {Expression}}}a+bوتيهـرم{\displaystyle {\mathit {Term}}}c، إلخ.

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

غالباً ما يُشكّل الاستدعاء الذاتي الأيسر مشكلةً للمحللات النحوية، إما لأنه يُؤدي بها إلى استدعاء ذاتي لا نهائي (كما هو الحال في معظم المحللات النحوية من أعلى إلى أسفل )، أو لأنها تتوقع وجود قواعد في صيغة طبيعية تمنعه ​​(كما هو الحال في العديد من المحللات النحوية من أسفل إلى أعلى ). لذلك، غالباً ما تُجرى معالجة مسبقة للقواعد النحوية للتخلص من الاستدعاء الذاتي الأيسر.

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

فيما يلي الخوارزمية العامة لإزالة الاستدعاء الذاتي المباشر من اليسار. وقد أُدخلت عدة تحسينات على هذه الطريقة. [ 2 ] بالنسبة للرمز غير الطرفي ذي الاستدعاء الذاتي من اليسارأ{\displaystyle A}تجاهل أي قواعد من هذا القبيلأ→أ{\displaystyle A\rightarrow A}وانظر إلى أولئك الذين بقوا:

أ→أα1|...|أαن|β1|...|βم{\displaystyle A\rightarrow A\alpha _{1}\mid \ldots \mid A\alpha _{n}\mid \beta _{1}\mid \ldots \mid \beta _{m}}

أين:

  • كلα{\displaystyle \alpha }هي سلسلة غير فارغة من الرموز غير الطرفية والطرفية، و
  • كلβ{\displaystyle \beta }هي سلسلة من الرموز غير الطرفية والطرفية التي لا تبدأ بـأ{\displaystyle A}.

استبدل هذه بمجموعتين من الإنتاجات، مجموعة واحدة لـأ{\displaystyle A}:

أ→β1أ′|...|βمأ′{\displaystyle A\rightarrow \beta _{1}A^{\prime }\mid \ldots \mid \beta _{m}A^{\prime }}

ومجموعة أخرى للطرفية غير النهائية الجديدةأ′{\displaystyle A'}(يُطلق عليها غالبًا اسم "الذيل" أو "الباقي"):

أ′→α1أ′|...|αنأ′|ϵ{\displaystyle A^{\prime }\rightarrow \alpha _{1}A^{\prime }\mid \ldots \mid \alpha _{n}A^{\prime }\mid \epsilon }

كرر هذه العملية حتى لا يتبقى أي تكرار مباشر من اليسار.

على سبيل المثال، ضع في اعتبارك مجموعة القواعد

هـxصرهـssأناoن→هـxصرهـssأناoن+هـxصرهـssأناoن|أنانتهـزهـر|Sترأنانز{\displaystyle {\mathit {Expression}}\rightarrow {\mathit {Expression}}+{\mathit {Expression}}\mid {\mathit {Integer}}\mid {\mathit {String}}}

يمكن إعادة كتابة هذا لتجنب الاستدعاء الذاتي الأيسر كما يلي:

هـxصرهـssأناoن→أنانتهـزهـرهـxصرهـssأناoن′|Sترأنانزهـxصرهـssأناoن′{\displaystyle {\mathit {Expression}}\rightarrow {\mathit {Integer}}\,{\mathit {Expression}}'\mid {\mathit {String}}\,{\mathit {Expression}}'}
هـxصرهـssأناoن′→+هـxصرهـssأناoن هـxصرهـssأناoن′|ϵ{\displaystyle {\mathit {Expression}}'\rightarrow {}+{\mathit {Expression}}{\text{ }}{\mathit {Expression}}'\mid \epsilon }

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

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

المدخلات : قواعد اللغة: مجموعة من الرموز غير الطرفيةأ1،...،أن{\displaystyle A_{1},\ldots ,A_{n}}وإنتاجاتهم
الناتج: قواعد نحوية معدلة تولد نفس اللغة ولكن بدون استدعاء ذاتي يساري
  1. لكل رمز غير طرفيأأنا{\displaystyle A_{i}}:
    1. كرر العملية حتى لا يتغير التركيب النحوي:
      1. لكل قاعدةأأنا→αأنا{\displaystyle A_{i}\rightarrow \alpha _{i}}، الαأنا{\displaystyle \alpha _{i}}كونها سلسلة من الرموز الطرفية وغير الطرفية:
        1. لوαأنا{\displaystyle \alpha _{i}}يبدأ برمز غير طرفيأج{\displaystyle A_{j}}وج<أنا{\displaystyle j<i}:
          1. يتركβأنا{\displaystyle \beta _{i}}يكونαأنا{\displaystyle \alpha _{i}}بدون قيادتهاأج{\displaystyle A_{j}}.
          2. قم بإزالة القاعدةأأنا→αأنا{\displaystyle A_{i}\rightarrow \alpha _{i}}.
          3. لكل قاعدةأج→αج{\displaystyle A_{j}\rightarrow \alpha _{j}}:
            1. أضف القاعدةأأنا→αجβأنا{\displaystyle A_{i}\rightarrow \alpha _{j}\beta _{i}}.
    2. قم بإزالة التكرار المباشر من اليسار لـأأنا{\displaystyle A_{i}}كما هو موضح أعلاه.

تتمثل الخطوة 1.1.1 في توسيع الرمز غير الطرفي الأوليأج{\displaystyle A_{j}}في الجانب الأيمن من بعض القواعدأأنا→أجβ{\displaystyle A_{i}\to A_{j}\beta }ولكن فقط إذاج<أنا{\displaystyle j<i}. لوأأنا→أجβ{\displaystyle A_{i}\to A_{j}\beta }كانت خطوة واحدة في دورة من الإنتاج تؤدي إلى تكرار يساري، ثم قام هذا بتقصير تلك الدورة بخطوة واحدة، ولكن غالبًا على حساب زيادة عدد القواعد.

يمكن النظر إلى الخوارزمية على أنها تُنشئ ترتيبًا طوبولوجيًا على الرموز غير الطرفية: بعد ذلك لا يمكن أن يكون هناك سوى قاعدةأأنا→أجβ{\displaystyle A_{i}\to A_{j}\beta }لوج>أنا{\displaystyle j>i}لاحظ أن هذه الخوارزمية حساسة للغاية لترتيب الرموز غير الطرفية؛ وغالبًا ما تركز عمليات التحسين على اختيار هذا الترتيب بشكل جيد.

المخاطر

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

تُعدّ خاصية التجميع عرضة للتأثر بشكل خاص؛ إذ تظهر عوامل التجميع اليسرى عادةً في ترتيبات شبيهة بعوامل التجميع اليمنى في ظل القواعد النحوية الجديدة. على سبيل المثال، بدءًا من هذه القواعد النحوية:

هـxصرهـssأناoن→هـxصرهـssأناoن-تيهـرم|تيهـرم{\displaystyle {\mathit {Expression}}\rightarrow {\mathit {Expression}}\,-\,{\mathit {Term}}\mid {\mathit {Term}}}
تيهـرم→تيهـرم*Fأجتoر|Fأجتoر{\displaystyle {\mathit {Term}}\rightarrow {\mathit {Term}}\,*\,{\mathit {Factor}}\mid {\mathit {Factor}}}
Fأجتoر→(هـxصرهـssأناoن)|أنانتهـزهـر{\displaystyle {\mathit {Factor}}\rightarrow ({\mathit {Expression}})\mid {\mathit {Integer}}}

تؤدي التحويلات القياسية لإزالة الاستدعاء الذاتي الأيسر إلى ما يلي:

هـxصرهـssأناoن→تيهـرم هـxصرهـssأناoن′{\displaystyle {\mathit {Expression}}\rightarrow {\mathit {Term}}\ {\mathit {Expression}}'}
هـxصرهـssأناoن′→-تيهـرم هـxصرهـssأناoن′|ϵ{\displaystyle {\mathit {Expression}}'\rightarrow {}-{\mathit {Term}}\ {\mathit {Expression}}'\mid \epsilon }
تيهـرم→Fأجتoر تيهـرم′{\displaystyle {\mathit {Term}}\rightarrow {\mathit {Factor}}\ {\mathit {Term}}'}
تيهـرم′→*Fأجتoر تيهـرم′|ϵ{\displaystyle {\mathit {Term}}'\rightarrow {}*{\mathit {Factor}}\ {\mathit {Term}}'\mid \epsilon }
Fأجتoر→(هـxصرهـssأناoن)|أنانتهـزهـر{\displaystyle {\mathit {Factor}}\rightarrow ({\mathit {Expression}})\mid {\mathit {Integer}}}

كان تحليل السلسلة "1 - 2 - 3" باستخدام القواعد النحوية الأولى في محلل LALR (الذي يمكنه التعامل مع القواعد النحوية ذات الاستدعاء الذاتي الأيسر) سيؤدي إلى شجرة التحليل التالية:

التحليل التكراري الأيسر لعملية طرح مزدوج
التحليل التكراري الأيسر لعملية طرح مزدوج

تقوم شجرة التحليل هذه بتجميع المصطلحات على اليسار، مما يعطي الدلالات الصحيحة (1 - 2) - 3 .

يؤدي التحليل باستخدام القواعد النحوية الثانية إلى

التحليل التكراري الأيمن لعملية طرح مزدوج
التحليل التكراري الأيمن لعملية طرح مزدوج

وهذا، عند تفسيره بشكل صحيح، يعني 1 + (-2 + (-3)) ، وهو صحيح أيضاً، ولكنه أقل دقة في تمثيل المدخلات وأصعب بكثير في التنفيذ لبعض العمليات. لاحظ كيف تظهر الحدود الموجودة على اليمين في عمق الشجرة، تماماً كما تفعل القواعد النحوية التكرارية اليمنى في حالة 1 - (2 - 3) .

استيعاب الاستدعاء الذاتي الأيسر في التحليل من أعلى إلى أسفل

لا يمكن تحليل القواعد النحوية الرسمية التي تحتوي على استدعاء ذاتي يساري بواسطة محلل LL(k) أو أي محلل تنازلي استدعائي بسيط آخر إلا بعد تحويلها إلى شكل استدعاء ذاتي يميني مكافئ ضعيفًا . في المقابل، يُفضل الاستدعاء الذاتي اليساري لمحللات LALR لأنه يؤدي إلى استخدام أقل للمكدس مقارنةً بالاستدعاء الذاتي اليميني . مع ذلك، يمكن لمحللات التنازل الأكثر تطورًا تنفيذ قواعد نحوية عامة خالية من السياق باستخدام التقليص. في عام 2006، وصف فروست وحافظ خوارزمية تستوعب القواعد النحوية الغامضة ذات قواعد الإنتاج الاستدعائية اليسارية المباشرة . [ 3 ] تم توسيع هذه الخوارزمية لتصبح خوارزمية تحليل كاملة لاستيعاب الاستدعاء الذاتي المباشر وغير المباشر من اليسار في وقت متعدد الحدود ، ولتوليد تمثيلات مضغوطة بحجم متعدد الحدود لعدد أشجار التحليل المحتملة، والتي قد تصل إلى أسّي، للقواعد النحوية شديدة الغموض، وذلك بواسطة فروست وحافظ وكالاغان في عام 2007. [ 4 ] ثم قام المؤلفون بتنفيذ الخوارزمية كمجموعة من مُركِّبات التحليل المكتوبة بلغة البرمجة هاسكل . [ 5 ]

انظر أيضاً

مراجع

  1. ↑ "ملاحظات حول نظرية اللغة الرسمية والتحليل النحوي" (ملف PDF) . مؤرشف من الأصل بتاريخ 27-11-2007 . تم الاطلاع عليه بتاريخ 30-10-2023 .{{cite web}}: CS1 maint: bot: حالة عنوان URL الأصلي غير معروفة ( رابط ) . جيمس باور، قسم علوم الحاسوب، الجامعة الوطنية الأيرلندية، ماينوث، مقاطعة كيلدير، أيرلندا. JPR02
  2. ↑ مور، روبرت سي. (مايو 2000). "إزالة الاستدعاء الذاتي الأيسر من القواعد النحوية الخالية من السياق" (ملف PDF) . المؤتمر السادس لمعالجة اللغات الطبيعية التطبيقية : 249-255 .
  3. ↑ فروست، ر.؛ وحافظ، ر. (2006). "خوارزمية تحليل نحوي جديدة من أعلى إلى أسفل لمعالجة الغموض والاستدعاء الذاتي الأيسر في وقت متعدد الحدود" . إشعارات ACM SIGPLAN . 41 (5): 46-54 . doi : 10.1145/1149982.1149988 . S2CID 8006549 . متاح من المؤلف على الرابط التالي: http://hafiz.myweb.cs.uwindsor.ca/pub/p46-frost.pdf مؤرشف بتاريخ 8 يناير 2015 في أرشيف الإنترنت (Wayback Machine).
  4. ↑ فروست، ر.؛ ر. حافظ؛ ب. كالاغان (يونيو 2007). "تحليل نحوي معياري وفعال من أعلى إلى أسفل للقواعد النحوية اليسارية الغامضة" (ملف PDF) . ورشة العمل الدولية العاشرة حول تقنيات التحليل النحوي (IWPT)، ACL-SIGPARSE : 109-120 . مؤرشف من الأصل (ملف PDF) بتاريخ 27-05-2011.
  5. ↑ فروست، ر.؛ ر. حافظ؛ ب. كالاغان (يناير 2008). "مُركِّبات المُحلِّل النحوي للقواعد النحوية اليسارية المُبهمة". الجوانب العملية للغات التصريحية (ملف PDF) . سلسلة محاضرات في علوم الحاسوب. المجلد 4902. الصفحات 167-181 . doi : 10.1007/978-3-540-77442-6_12 . ISBN   978-3-540-77441-9تمت أرشفة النسخة الأصلية (PDF) بتاريخ 21-12-2008.