زمان کنونی: ۱۳ آذر ۱۴۰۳, ۱۱:۱۹ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

بازگشتی چپ غیر مستقیم

ارسال:
  

- rasool - پرسیده:

بازگشتی چپ غیر مستقیم

الله

سلام
خدا قوت
می دانیم که برای تبدیل بازگشتی چپ غیرمستقیم به مستقیم باید از عمل جایگزینی استفاده کرد.
گرامر زیر رو در نظر بگیرید:
[tex]S\rightarrow Aa\mid b[/tex]
[tex]A\rightarrow Ac \mid Sd\mid \epsilon[/tex]

برای تبدیل بازگشتی چپ غیرمستقیم به مستقیم در آن باید S را در A جایگزین کرد یا بالعکس؟

آیا حتما یکی از اینها درسته و دیگری غلط؟
یعنی باید جواب منحصر به فرد بگیریم؟
حالا فرض کنید چندتا بازگشتی چپ غیر مستقیم داشته باشیم . آیا انتخاب عنصری که باید جایگزین شود با عمل آزمون و خطا بدست میاد؟ اینطوری که خیلی سخت می شه!

متشکرم
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

mfXpert پاسخ داده:

بازگشتی چپ

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

۰
ارسال:
  

mfXpert پاسخ داده:

RE: بازگشتی چپ غیر مستقیم

الگوریتم حذف بازگشتی غیر مستقیم(یا همون بازگشتی ضمنی) توی کتاب Aho اومده و تو کتاب پوران هم شبه کدش آورده شده.
وقتی حلقه داخلی این الگوریتم اجرا بشه‌، شکل گرامر به صورت زیر در میاد:
[tex]S\rightarrow Aa | b[/tex]
[tex]A\rightarrow Ac | Aad | db | \epsilon[/tex]
توی گرامر بالا همونطور که مشخصه دیگه بازگشتی غیر مستقیم وجود نداره.
حالا نوبت به اجرای حلقه خارجی میرسه تا بازگشتی های چپ مستقیم هم حذف بشن.بعد از اجرای حلقه خارجی‌، گرامر به صورت زیر در میاد:
[tex]S\rightarrow Aa | b[/tex]
[tex]A\rightarrow bdA' | A'[/tex]
[tex]A'\rightarrow cA' | adA' | \epsilon[/tex]
گرامر نهایی دیگه هیچ بازگشتی(چه مستقیم و چه غیر مستقیم) نداره
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

- rasool - پاسخ داده:

بازگشتی چپ

ممنونم
بله . درسته . الگوریتم حذف بازگشتی مستقیم رو بلدم.

اما اشکال من در تبدیل غیرمستقیم به مستقیمه.
اگه ممکنه مثالی رو که در پست اول زدم با این الگوریتم حل کنید.
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  شیوه های دانلود مقالات غیر رایگان goodzila ۳۰ ۴۲,۸۱۰ ۲۱ فروردین ۱۳۹۸ ۰۶:۳۶ ب.ظ
آخرین ارسال: ryaghobi2050
  [دانلود] ویدئوهای هوش مصنوعی رامین رهنمون با لینک مستقیم Amir V ۵۵ ۵۹,۵۵۵ ۱۲ دى ۱۳۹۷ ۰۴:۵۷ ب.ظ
آخرین ارسال: Amir V
  دانشگاه غیر انتفاعی علم و فرهنگ تهران برای ارشد نرم افزار خوبه؟ اساتیدش خوبن؟ rhf261 ۰ ۲,۱۹۳ ۱۳ شهریور ۱۳۹۷ ۱۲:۳۹ ق.ظ
آخرین ارسال: rhf261
  درخواست(محاسبه پیچیدگی زمانی)(بخش روابط بازگشتی) Saman ۶ ۷,۵۴۵ ۲۷ خرداد ۱۳۹۷ ۰۳:۲۴ ب.ظ
آخرین ارسال: saeed_vahidi
  مفهوم انواع آنتروپی و ویژگی های غیر خطی سیگنال مغز baharkhanoom ۰ ۱,۹۷۲ ۲۶ خرداد ۱۳۹۷ ۱۰:۲۷ ب.ظ
آخرین ارسال: baharkhanoom
  دانشگاه آزاد یا غیر انتفاعی؟ nabisobhi ۴۲ ۱۰۰,۵۷۴ ۲۴ بهمن ۱۳۹۶ ۰۹:۴۷ ب.ظ
آخرین ارسال: Hadis.hp93@yahoo.com
  درخواست ژورنال معتبر غیر ISI و رایگان ehsan_ei ۱۵ ۱۸,۸۶۹ ۲۲ دى ۱۳۹۶ ۰۶:۰۳ ب.ظ
آخرین ارسال: elitesjournal
  رسم درخت بازگشتی برای t(n)=9t(n/3)+n jumper ۶ ۶,۷۴۵ ۱۷ دى ۱۳۹۶ ۰۶:۱۶ ب.ظ
آخرین ارسال: jumper
  حل روابط بازگشتی درجه ۳ rahkaransg ۲ ۳,۱۱۹ ۱۴ دى ۱۳۹۶ ۰۵:۲۴ ب.ظ
آخرین ارسال: rahkaransg
  جواب رابطه های بازگشتی rahkaransg ۰ ۱,۸۶۱ ۱۴ دى ۱۳۹۶ ۱۲:۲۴ ق.ظ
آخرین ارسال: rahkaransg

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close