کمک در تشخیص نوع گرامر

[mehdi2388]

سلام بچه ها
کسی میتونه بگه توی درس کامپایلر چطوری میشه بدون رسم جدول پارسیک تشخیص داد گرامر LR یا SLR یا LALR هست یا نه؟ http://www.manesht.ir/forum/images/smilies/huh.gif
منظورم راه حل تستی اونه؟ من چندتا کتاب در این مورد خوندم ولی همشون خیلی گنگ و بد گفتن http://www.manesht.ir/forum/images/smilies/confused.gif
هیچی از جدول پارسینگ سردر نمیارم http://www.manesht.ir/forum/images/smilies/sad.gif
خواهشاً هر کی نظری داره بگه
شما سر کنکور چطور می فهمین؟ http://www.manesht.ir/forum/images/smilies/huh.gif
:عصبانی++::عصبانی++:

[pesar irooni]

جدول تجزیه که مفهوم ساده ایه
ببین تو تست ها یا گرامر مبهم میدن که کلا LR نیست یا LL(1 میدن
LL که مشکلی نداره
شما باید state ها رو تشکیل بدی و یه تناقض کاهش/کاهش یا کاهش/انتقال پیدا کنی که تو تست ها اینقدر گرامر ساده و کوچیکه که سریع پیدا میشه
اما بیشتر گیر میدن به مبهم بودن

[mehdi2388]

خیلی ممنون بابت جوابتون...پس یعنی قبل از تجزیه ببینم گرامر مبهم نباشه؟در مورد LL1، اگه گرامر LL 1 باشه حتما LR هم هست. درسته؟

[mehdi2388]

به نظرتون اصلاً لازمه که کشیدن جدول تجزیه رو برای همه نوع گرامرها بلد باشیم یا همین که بتونیم بفهمیم نوع گرامر چیه کفایت میکنه؟ :متفکر:
منظورم توی کنکور ارشده...

[pesar irooni]

ر مورد LL1، اگه گرامر LL 1 باشه حتما LR هم هست. درسته؟
این سوال که پرسیدن نداره
http://cs.fit.edu/%7Eryan/figures/grammar.gif

[mehdi2388]

:قهقهه:
آره راست می گید.
خیلی ممنون بابت راهنمایی هاتون.
خیلی بهم کمک کرد.

[taranom20]

سلام به دوستان
کسی میتونه مفهوم LR و SLR و LALR رو به زبون ساده و عامیانه بگه؟ جوری که بشه راحت فهمید.
مثلاً میدونم LL(1) یعنی اینکه با نگاه کردن به اولین کاراکتر از سمت چپ بتوان تشخیص داد از کدوم قانون باید استفاده بشه.
یه سوال دیگه: چطور میشه فهمید گرامری LL(0) است؟
ببخشید من کامپایلر پاس نکردم که این سوالات شاید پیش پا افتاده رو می پرسم. :ناراحت:
اگه کسی بتونه جوابم رو بده خیلی خوشحال میشم.

[taranom20]

کسی نیست بتونه جواب منو بده؟ :متفکر:
:اشتباه:

[pesar irooni]

LL(0 یعنی بدون دیدن کاراکتر پیش بینی کننده بدونی از کدوم قانون استفاده کنی (کدوم قانون رو جایگزین کنی) و این زمانی پیش میاد که هر قانون سمت راست خودش فقط یه قانون داشته باشه مثل :

A -> B
B -> C
C -> D

اگه بیش از یه قانون باشه نیاز به کاراکتر پیش بینی کننده داریم

A -> B | C

الان بعد از دیدن A نمیدونیم که به B بریم یا به C پس LR(0 نیست و باید کاراکتر بعدی رو ببینیم تا تصمیم بگیریم که به B بریم یا C
در مورد LR(1) هم یعنی اینکه با دیدن اولین کاراکتر از سمت چپ به کدوم قانون کاهش کرد. چون داریم برعکس LL پیمایش میکنیم میشه کاهش

[taranom20]

با تشکر از پاسختون
با این حساب هر گرامری که هر کدام از قوانین آن فقط یک قانون داشته باشند جزء همه ی گرامرها می شود. :لبخند:

ولی باز جمله ی آخر را متوجه نشدم:

{در مورد LR(1) هم یعنی اینکه با دیدن اولین کاراکتر از سمت چپ به کدوم قانون کاهش کرد. }

معنی کاهش رو توی این جمله متوجه نمیشم؟؟ :افسرده:

[pesar irooni]

بحث handle ها توی تجزیه پایین به بالا همین جا مطرح میشه. در اصل به قانونی کاهش پیدا میکنه که معادل سمت راست اون قانونه. مثل:

A->aA|B
B->b

چون تجزیه پایین به بالاست میخواهیم از رشته ای مثل aab به سرگرامر که A هست برسیم.
میبینیم که a معادل سمت راست هیچ قانونی نیست. aa هست. aab هم نیست. میریم سراغ a دوم تا اینکه به b میرسیم. b شبیه سمت راست یه قانون هست یعنی B->b پس b رو به B کاهش میدیم
نمیخوام پیچیده اش کنم اما به همین راحتی نمیشه دستگیره (handle) رو پیدا کرد باید از جدول تجزیه استفاده کرد. مثلا در گرامر

S->AB
A->aA|a
B->bB|b

با داشتن رشته aab دیگه b دستگیره نیست. a اول هم نیست. بلکه a وسط دستگیره هست و با کاهش داریم: aAb با توجه به سمت راست ترین اشتقاق به صورت معکوس (پایین به بالا یا تو اینجا راست به چپ) میبینیم که تو هر مرحله دستگیره چی بوده و به چی کاهش پیدا کرده

S->AB->Ab->aAb->aab

[pesar irooni]

با این حساب هر گرامری که هر کدام از قوانین آن فقط یک قانون داشته باشند جزء همه ی گرامرها می شود. :لبخند:
این سوالت که جوابش تو شکل هست.
جزء همه گرامرهای غیر مبهم

[taranom20]

خیلی ممنون
متوجه شدم
زحمت کشیدید.