بازگشت چپ
در زبان رسمی صوری در علوم کامپیوتر بازگشت چپ یک نوع بازگشت ویژه است.
در گرامرهای مستقل از متن. غیرپایانهٔ r بازگشتی چپ است اگر چپترین نشانه در همهٔ تولیدات r به صورت بیدرنگ (مستقیم / بازگشتی چپ بیدرنگ )جایگزین شود یا غیرترمینالهای دیگر به صورت غیر مستقیم r را دوباره تولید کند.(غیر مستقیم / پنهان سمت چپ بازگشتی) .
توصیف
[ویرایش]یک گرامر بازگشتی چپ است اگر بتوانیم یک غیرپایانه مانند A پیدا کنیم که در نهایت بتوان یک فرم جملهای استخراج کرد که A در آن چپترین نماد باشد.
بازگشتی چپ بیدرنگ
[ویرایش]بازگشتی چپ بیدرنگ در قوانین به صورت زیر است:
در جایی که و دنبالههایی از پایانهها و غیر پایانهها هستند و با شروع نمیشود برای مثال :
یک بازگشتی چپ است و تجزیهگر بازگشتی نزولی برای آن شبیه به کد زیر است:
function Expr()
{
Expr(); match('+'); Term();
}
و یک تجزیه گر نزولی بازگشتی ممکن است هنگام تجزیهٔ گرامری که دارای این قانون است در یک دور بی نهایت بازگشتی بیفتد.
بازگشتی چپ غیر مستقیم
[ویرایش]سادهترین فرم بازگشتی چپ غیر مستقیم:
اشتقاق ممکن:
بهطور کلی تر برای غیرپایانههای ، فرم بازگشتی چپ غیر مستقیم میتواند به صورت زیر تعریف شود
دنبالهای از پایانهها و غیر پایانهها هستند .
تطابق بازگشت چپ در تجزیه بالا به پایین
[ویرایش]یک گرامر رسمی که شمال بازگشتی چپ است نمیتواند با یک تجزیه گر (LL(k یا سایر تجزیه گرهای بازگشتی نزولی تجزیه شود مگر اینه به یک بازگشتی راست ضعیف مشابه تبدیل شود. در مقابل بازگشتی چپ برای تجزیه گرهای LALR بهتر است زیرا نتیجهٔ آن از یک پشتهٔ کوچک تری نسبت فرم بازگشتی راست استفاده میکند. به هر صورت تجزیه گرهای بالا به پایین میتوانند طیف وسیعی از گرامرهای مستقل از متن را با استفاده از کوتاه کردن اجرا کنند. در سال 2006 فراست و حافظ یک الگوریتم که گرامرهای مبهم را با قوانین بازگشتی چپ مستقیم تطابق داد ارائه دادند. الگوریتم برای کامل کردن الگوریتمهای تجزیه گر برای تطابق غیر مستقیم و همچنین مستقیم بازگشتی چپ در یک زمان با پیچیدگی چندجمله ای و اجرای یک ارائهٔ منسجم در سایز چند جملهای برای درختان تجزیه گرامرهای مبهم توسط فراست، حافظ و کالاهان در سال 2007 گسترش یافت . این نویسندگان سپس الگوریتم را به عنوان مجموعهای از تجزیه گرهای ترکیبی نوشته شده در زبان برنامه نویسی هاسکل ارائه دادند.
حذف بازگشتی چپ
[ویرایش]حذف بازگشتی چپ بیدرنگ
[ویرایش]الگوریتم کلی حذف بازگشت فوری چپ شرح زیر است. پیشرفتهای بسیاری در این روش صورت گرفت که شامل مواردی مثل "حذف بازگشتی چپ از گرامرهای مستقل از متن" است که توسط رابرت سی. مور برای هر قانون نوشته شدهاست.
- A یک غیر پایانهٔ بازگشتی چپ است
- دنبالهای از پایانهها و غیرپایانههایی است که null نیستند. ()
- دنبالهای از پایانهها و غیرپایانههایی است که با A شروع نمیشوند.
A با تولید زیر جایگزین شود
و یک غیرپایانه بسازد
نشانهٔ تازه تولید شده دم(دنباله) یا ادامه نام دارد
برای مثال با توجه به این قانون:
می تواند بازنویسی شود تا از بازگشتی چپ جلوگیری کند
آخرین قانون برای ساختن یک فرم مشابه کمی کوتاهتر است:
حذف بازگشتی چپ غیر مستقیم
[ویرایش]اگر گرامر هیج -productions نداشته باشد ( هیچ عملی به فرم ) و دوری نباشد (هیچ اشتقاقی به فرم برای هر غیر پایانهٔ A) این الگوریتم میتواند برای حذف بازگشتی چپ غیر مستقیم استفاده شود:
غیر پایانهها را طبق یک ترتیب مشخص مرتب کنید .
- for i = 1 to n {
- for j = 1 to i – 1 {
- let the current productions be
-
- replace each production by
- }
- remove direct left recursion for
- for j = 1 to i – 1 {
- }
مشکلات
[ویرایش]این تبدیلات بازگشتی چپ را با ساختن یک گرامر بازگشتی راست حذف میکند، ولی خاصیت شرکتپذیری قوانین را عوض میکند. بازگشتی چپ شرکتپذیری چپ را میسازد؛ بازگشتی راست، شرکتپذیری راست را میسازد.
مثال: گرامر را آغاز می کنیم:
پس از انجام تبدیلات استاندارد گرامرهای زیر را داریم:
تجزیهٔ 'a + a + a' با اولین گرامر در تجزیه گر LALR (که گرامرهای بازگشتی چپ را تشخیص میدهد) درخت تجزیه ی زیر را نتیجه میدهد:
Expr / | \ Expr + Term / | \ \ Expr + Term Factor | | | Term Factor Int | | Factor Int | Int
این درخت تجزیه به سمت چپ رشد میکند که حاکی از آن است که عملگر '+' شرکت پذیر چپ است. با نمایش a + a) + a)
با تغییر گرامر درخت تجزیه به صورت زیر است:
Expr ---
/ \
Term Expr' --
| / | \
Factor + Term Expr' ------
| | | \ \
Int Factor + Term Expr'
| | |
Int Factor
|
Int
اگر این عبارت به صورت a + a) + a) نوشته شود. گرامر به صورت بازگشتی راست نوشته میشود.
مشکل این است که علم حساب به شرکتپذیری چپ نیاز دارد. راه حلهای این مشکل عبارتند از
- بازنویسی گرامرها تا بازگشتی چپ شوند.
- بازنویسی گرامرها با تعدادی غیرپایانه که شرکتپذیری را تضمین میکند.
- اگر از YACC یا Bison استفاده کنیم، اعلانهایی %left ، %right و %nonassoc دارند که به تجزیه گر نوع شرکتپذیری را اعلام میکند.