تحويل القواعد الغامضة إلى لا لبس فيه

Question

لم أفهم كيف يتم اشتقاق القواعد النحوية التي لا لبس فيها من قواعد غامضة؟ النظر في المثال في الموقع: مثال. كيف كانت القواعد المستمدة هي مربكة بالنسبة لي.

هل يمكن لأي شخص أن يرشدني؟

Answer 1

المثال يحتوي على قواعد نحوية:

غامض:

E → E + E | E ∗ E | (E) | a

خالية من الغموض:

E → E + T | T
T → T ∗ F | F
F → (E) | a

تم اشتقاق القواعد النحوية التي لا لبس فيها من الغموض باستخدام المعلومات غير المحددة في القواعد الغامضة:

• يرتبط المشغل "*" أكثر تشددًا من المشغل "+".
• يتم ترك كل من المشغلين "*" و "+".

بدون المعلومات الخارجية ، لا توجد طريقة لإجراء التحول.

مع المعلومات الخارجية ، يمكننا معرفة ذلك:

a * a + b * b

تم تجميعها كما لو كانت مكتوبة:

(a * a) + (b * b)

بدلا من:

a * ((a + b) * b)

والثاني يفترض أن "+" يربط أكثر تشددًا من "*" ، وأن المشغلين يربطون من اليمين إلى اليسار بدلاً من اليسار إلى اليمين.

---

تعليق

كيف يمكن أن تأتي الارتباط في الصورة لأمثلة مثل:

    S → aA | Ba
    A → BA | a
    B → aB | epsilon

هذه قواعد غامضة ، فكيف تدور حول تحويلها إلى لا لبس فيها؟

أتساءل عما إذا كانت "epsilon" هي ε ، السلسلة الفارغة ؛ دعونا نحلل القواعد في كلا الاتجاهين.

ε هي السلسلة الفارغة

تقول القاعدة لـ B أن A B هي إما سلسلة فارغة أو A متبوعة ب B ساري المفعول ، والتي تصل إلى سلسلة طويلة غير مسمى من 0 أو أكثر.

تقول قاعدة A A A A إما A أو B تليها A. لذلك ، يمكن أن تكون سلسلة طويلة إلى أجل غير مسمى من A A أيضًا. لذلك ، لا توجد طريقة للاختيار القواعد النحوية ما إذا كانت سلسلة من A هي إما A أو B.

والقاعدة لـ S ليست مساعدة ؛ A S هي إما A تليها سلسلة طويلة إلى أجل غير مسمى من A أو سلسلة طويلة إلى أجل غير مسمى من A تليها A. إنه يتطلب واحدة على الأقل A ، ولكن أي عدد من A من واحد لأعلى هو على ما يرام ، ولكن القواعد لا أساس لها أي أساس لاتخاذ قرار بين البدائل اليمنى واليسرى.

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

ε ليست السلسلة الفارغة

ماذا لو إذا لم تكن السلسلة الفارغة؟

• B هو ε أو A ε.
• A هو إما A أو B متبوعًا بـ A (لذلك إما A أو A A أو A AAε).
• إما: S هو A تليها A (ومن ثم AA ، AAε ، أو AAAε)
• أو: S هو B متبوعًا بـ A (وبالتالي εa أو AεA).

في هذه الحالة ، لا لبس فيها القواعد كما هي (وإن لم يكن بالضرورة LR (1)). من الواضح أن الكثير من المفصلات على معنى "إبسيلون" في التعليق/السؤال.

الارتباط

لا أعتقد أن الارتباط يؤثر على هذه القواعد. يتم تشغيله بشكل عام مع مشغلي Infix (مثل " +" في "A + B").

Answer 2

من ويكيبيديا (على التعرف على القواعد الغامضة):

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

من أجل التوصل إلى القواعد الثانية ، عليك أن تجد قواعد اللغة

1. أي ما يعادل أول واحد: كلاهما يولد نفس اللغة
2. لا لبس فيه: لكل جملة من اللغة ، شجرة التحليل فريدة من نوعها