كيفية تحديد ما إذا كانت اللغة هي LL(1) LR(0) SLR(1)

Question

هل هناك طريقة بسيطة لتحديد ما إذا كانت القواعد النحوية هي LL(1)، LR(0)، SLR(1)...فقط من النظر إلى القواعد دون القيام بأي تحليل معقد؟

على سبيل المثال:لتحديد ما إذا كانت قواعد BNF هي LL(1) أم لا، يتعين عليك حساب المجموعتين الأولى والمتابعة - الأمر الذي قد يستغرق وقتًا طويلاً في بعض الحالات.

هل لدى أي شخص فكرة عن كيفية القيام بذلك بشكل أسرع؟أي مساعدة سيكون حقا موضع تقدير!

Answer 1

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

مع هذا للخروج من الطريق:

• يمكنك كتابة محلل للقواعد والحصول على برنامج يحسب أولاً ويتبع المجموعات والخصائص الأخرى لك.بعد كل شيء، هذه هي الميزة الكبيرة لقواعد BNF، فهي مفهومة آليًا.

• تفحص النحو وابحث عنه الانتهاكات من قيود الأنواع النحوية المختلفة.على سبيل المثال:يسمح LL(1) بالتكرار لليمين وليس لليسار، وبالتالي فإن القواعد النحوية التي تحتوي على التكرار لليسار ليست LL(1).(بالنسبة للخصائص النحوية الأخرى، سيتعين عليك قضاء بعض الوقت الجيد في التعرف على التعريفات، لأنني لا أستطيع تذكر أي شيء آخر يدور في ذهني الآن :)).

Answer 2

في الإجابة على السؤال الرئيسي: لالنحوي بسيط جدا، فإنه قد يكون من الممكن تحديد ما إذا كان هو LL (1) دون بناء أول وتابع مجموعات، منها مثلا

<اقتباس فقرة>   

وA → A + A | و

     

وليس LL (1)، في حين

     

وA → ل| ب

وهو.

ولكن عندما تحصل على أكثر تعقيدا من ذلك، سوف تحتاج إلى القيام ببعض التحليل.

<اقتباس فقرة>   

وA → B | و
  B → A + A

وهذا ليس يرة (1)، لكنه قد لا يكون واضحا على الفور

ووالقواعد النحوية لالحسابية بسرعة الحصول على معقد جدا:

<اقتباس فقرة>   

وEXPR → المدى { '+' المدى}
  عامل → المدى { '*' عامل}
  عامل عدد → | '(' EXPR ')'

وهذه القواعد يعالج الوحيد الضرب وبالإضافة إلى ذلك، وبالفعل انها لم يتضح على الفور ما إذا كانت القواعد هو LL (1). فإنه لا يزال من الممكن لتقييم ذلك من خلال النظر من خلال قواعد اللغة، ولكن مع نمو قواعد يصبح أقل feasable. إذا نحن تحديد النحوي للغة برمجة كاملة، فإنه يكاد يكون من المؤكد سوف يستغرق بعض التحليلات المعقدة.

وقال ذلك، هناك عدد قليل من علامات منبهة واضحة أن القواعد ليست LL (1) - مثل A → A + A فوق - وإذا كان يمكنك العثور على أي من هذه في قواعد اللغة الخاصة بك، عليك أن تعرف أنه يحتاج إلى إعادة صياغة إذا كنت تكتب محلل النسب العودية. ولكن ليس هناك اختصار للتحقق من أن قواعد <م> هو LL (1).

Answer 3

وأحد الجوانب، "هي اللغة / قواعد غامضة"، هو href="http://en.wikipedia.org/wiki/Ambiguous_grammar#Recognizing_an_ambiguous_grammar" سؤال undecidable المعروفة مثل المشاركة المراسلات و <لأ href = "http://en.wikipedia.org/ ويكي / Halting_problem "يختلط =" noreferrer "> وقف المشاكل.

Answer 4

مباشرة من كتاب "المجمعون:المبادئ والتقنيات والأدوات" بقلم Aho وآخرون.آل.

الصفحة 223:

القواعد G هي LL(1) إذا وفقط إذا كلما أ-> ألفا | بيتا هما إنتاجان متميزان لـ G، وتتوافر الشروط التالية:

1. لعدم وجود محطة "أ" افعل كلا الأمرين ألفا و بيتا اشتقاق سلاسل تبدأ بـ "a"
2. على الأكثر واحدة من ألفا و بيتا يمكن استخلاص السلسلة الفارغة
3. لو بيتا يمكن الوصول إلى الانتقال الفارغ عبر انتقالات صفرية أو أكثر ألفا لا يشتق أي سلسلة تبدأ بمحطة في FOLLOW(A).وكذلك إذا ألفا يمكن الوصول إلى الانتقال الفارغ عبر انتقالات صفرية أو أكثر بيتا لا يشتق أي سلسلة تبدأ بمحطة في FOLLOW(A)

يتعلق الأمر بشكل أساسي بالتحقق من اجتياز القواعد النحوية لاختبار الانفصال الزوجي وأيضًا لا تتضمن العودية اليسرى.أو بشكل أكثر إيجازًا، لا يمكن أن تكون القواعد النحوية G التي تكون متكررة أو غامضة LL(1).

Answer 5

وتحقق ما إذا كان قواعد غير واضحة أو لا. إذا كان كذلك، ثم قواعد اللغة لا يرة (1) لأنه لا يوجد قواعد غامضة غير LL (1).

Answer 6

ويا هناك طرق مختصرة ليرة لبنانية (1) قواعد اللغة

1) إذا A-> B1 | B2 | ....... | مليار دولار     ثم أول (B1) تقاطع الأول (B2) تقاطع. أولا (مليار دولار) = مجموعة فارغة فمن ليرة لبنانية (1) قواعد اللغة

2) إذا A-> B1 | إبسيلون      ثم تقاطع B1 متابعة (A) هي مجموعة فارغة

و3) إذا G هو أي قواعد هذا أن كل محطة غير مستمد إنتاج واحد فقط ثم قواعد اللغة هو LL (1)

Answer 7

p0 S' → E
p1 E → id
p2 E → id ( E )
p3 E → E + id

• قم بإنشاء LR(0) DFA، ومجموعة FOLLOW لـ E وجداول الإجراء/الانتقال إلى SLR.
• هل هذه قواعد نحوية LR(0)؟أثبت إجابتك.
• باستخدام جداول SLR، اعرض الخطوات (التحولات، التخفيضات، القبول) لتحليل محلل LR:
  id ( id + id )