الله
سلام
خدا قوت
می دانیم که برای تبدیل بازگشتی چپ غیرمستقیم به مستقیم باید از عمل جایگزینی استفاده کرد.
گرامر زیر رو در نظر بگیرید:
[tex]S\rightarrow Aa\mid b[/tex]
[tex]A\rightarrow Ac \mid Sd\mid \epsilon[/tex]
برای تبدیل بازگشتی چپ غیرمستقیم به مستقیم در آن باید S را در A جایگزین کرد یا بالعکس؟
آیا حتما یکی از اینها درسته و دیگری غلط؟
یعنی باید جواب منحصر به فرد بگیریم؟
حالا فرض کنید چندتا بازگشتی چپ غیر مستقیم داشته باشیم . آیا انتخاب عنصری که باید جایگزین شود با عمل آزمون و خطا بدست میاد؟ اینطوری که خیلی سخت می شه!
متشکرم
هم بازگشتی چپ مستقیم و هم بازگشتی چپ غیر مستقیم دارای الگوریتم هستن تا بشه اون قوانین بازگشتی رو حذف کرد و هیچ کاری براساس آزمون و خطا انجام نمیشه
ممنونم
بله . درسته . الگوریتم حذف بازگشتی مستقیم رو بلدم.
اما اشکال من در تبدیل غیرمستقیم به مستقیمه.
اگه ممکنه مثالی رو که در پست اول زدم با این الگوریتم حل کنید.
الگوریتم حذف بازگشتی غیر مستقیم(یا همون بازگشتی ضمنی) توی کتاب 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]