۰
subtitle
ارسال: #۱
بازگشتی چپ غیر مستقیم
الله
سلام
خدا قوت
می دانیم که برای تبدیل بازگشتی چپ غیرمستقیم به مستقیم باید از عمل جایگزینی استفاده کرد.
گرامر زیر رو در نظر بگیرید:
[tex]S\rightarrow Aa\mid b[/tex]
[tex]A\rightarrow Ac \mid Sd\mid \epsilon[/tex]
برای تبدیل بازگشتی چپ غیرمستقیم به مستقیم در آن باید S را در A جایگزین کرد یا بالعکس؟
آیا حتما یکی از اینها درسته و دیگری غلط؟
یعنی باید جواب منحصر به فرد بگیریم؟
حالا فرض کنید چندتا بازگشتی چپ غیر مستقیم داشته باشیم . آیا انتخاب عنصری که باید جایگزین شود با عمل آزمون و خطا بدست میاد؟ اینطوری که خیلی سخت می شه!
متشکرم
سلام
خدا قوت
می دانیم که برای تبدیل بازگشتی چپ غیرمستقیم به مستقیم باید از عمل جایگزینی استفاده کرد.
گرامر زیر رو در نظر بگیرید:
[tex]S\rightarrow Aa\mid b[/tex]
[tex]A\rightarrow Ac \mid Sd\mid \epsilon[/tex]
برای تبدیل بازگشتی چپ غیرمستقیم به مستقیم در آن باید S را در A جایگزین کرد یا بالعکس؟
آیا حتما یکی از اینها درسته و دیگری غلط؟
یعنی باید جواب منحصر به فرد بگیریم؟
حالا فرض کنید چندتا بازگشتی چپ غیر مستقیم داشته باشیم . آیا انتخاب عنصری که باید جایگزین شود با عمل آزمون و خطا بدست میاد؟ اینطوری که خیلی سخت می شه!
متشکرم
۰
ارسال: #۲
بازگشتی چپ
هم بازگشتی چپ مستقیم و هم بازگشتی چپ غیر مستقیم دارای الگوریتم هستن تا بشه اون قوانین بازگشتی رو حذف کرد و هیچ کاری براساس آزمون و خطا انجام نمیشه
۰
ارسال: #۳
RE: بازگشتی چپ غیر مستقیم
الگوریتم حذف بازگشتی غیر مستقیم(یا همون بازگشتی ضمنی) توی کتاب Aho اومده و تو کتاب پوران هم شبه کدش آورده شده.
وقتی حلقه داخلی این الگوریتم اجرا بشه، شکل گرامر به صورت زیر در میاد:
حالا نوبت به اجرای حلقه خارجی میرسه تا بازگشتی های چپ مستقیم هم حذف بشن.بعد از اجرای حلقه خارجی، گرامر به صورت زیر در میاد:
وقتی حلقه داخلی این الگوریتم اجرا بشه، شکل گرامر به صورت زیر در میاد:
[tex]S\rightarrow Aa | b[/tex]
[tex]A\rightarrow Ac | Aad | db | \epsilon[/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]
گرامر نهایی دیگه هیچ بازگشتی(چه مستقیم و چه غیر مستقیم) نداره
[tex]A\rightarrow bdA' | A'[/tex]
[tex]A'\rightarrow cA' | adA' | \epsilon[/tex]
۰
ارسال: #۴
بازگشتی چپ
ممنونم
بله . درسته . الگوریتم حذف بازگشتی مستقیم رو بلدم.
اما اشکال من در تبدیل غیرمستقیم به مستقیمه.
اگه ممکنه مثالی رو که در پست اول زدم با این الگوریتم حل کنید.
بله . درسته . الگوریتم حذف بازگشتی مستقیم رو بلدم.
اما اشکال من در تبدیل غیرمستقیم به مستقیمه.
اگه ممکنه مثالی رو که در پست اول زدم با این الگوریتم حل کنید.
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close