بازگشت چپ کیست؟ توضیح بده.
در زبان رسمی صوری در علوم کامپیوتر بازگشت چپ یک نوع بازگشت ویژه است.در گرامرهای مستقل از متن. غیرپایانهٔ r بازگشتی چپ است اگر چپ‌ترین نشانه در همهٔ تولیدات r به صورت بی‌درنگ (مستقیم / بازگشتی چپ بی‌درنگ )جایگزین شود یا غیرترمینال‌های دیگر به صورت غیر مستقیم r را دوباره تولید کند.(غیر مستقیم / پنهان سمت چپ بازگشتی) .توصیف.یک گرامر بازگشتی چپ است اگر بتوانیم یک غیرپایانه مانند A پیدا کنیم که در نهایت بتوان یک فرم جمله‌ای استخراج کرد که A در آن چپ‌ترین نماد باشد.بازگشتی چپ بی‌درنگ.بازگشتی چپ بی‌درنگ در قوانین به صورت زیر است:در جایی که formula_2 و formula_3 دنباله‌هایی از پایانه‌ها و غیر پایانه‌ها هستند و formula_3 با formula_5 شروع نمی‌شود برای مثال :یک بازگشتی چپ است و تجزیه‌گر بازگشتی نزولی برای آن شبیه به کد زیر است:function Expr() Expr(); match('+'); Term();و یک تجزیه گر نزولی بازگشتی ممکن است هنگام تجزیهٔ گرامری که دارای این قانون است در یک دور بی نهایت بازگشتی بیفتد.بازگشتی چپ غیر مستقیم.ساده‌ترین فرم بازگشتی چپ غیر مستقیم:اشتقاق ممکن: formula_9به‌طور کلی تر برای غیرپایانه‌های formula_10، فرم بازگشتی چپ غیر مستقیم می‌تواند به صورت زیر تعریف شودformula_15 دنباله‌ای از پایانه‌ها و غیر پایانه‌ها هستند .تطابق بازگشت چپ در تجزیه بالا به پایین.یک گرامر رسمی که شمال بازگشتی چپ است نمی‌تواند با یک تجزیه گر (LL(k یا سایر تجزیه گرهای بازگشتی نزولی تجزیه شود مگر اینه به یک بازگشتی راست ضعیف مشابه تبدیل شود. در مقابل بازگشتی چپ برای تجزیه گرهای LALR بهتر است زیرا نتیجهٔ آن از یک پشتهٔ کوچک تری نسبت فرم بازگشتی راست استفاده می‌کند.به هر صورت تجزیه گرهای بالا به پایین می‌توانند طیف وسیعی از گرامرهای مستقل از متن را با استفاده از کوتاه کردن اجرا کنند. در سال 2006 فراست و حافظ یک الگوریتم که گرامرهای مبهم را با قوانین بازگشتی چپ مستقیم تطابق داد ارائه دادند. الگوریتم برای کامل کردن الگوریتم‌های تجزیه گر برای تطابق غیر مستقیم و همچنین مستقیم بازگشتی چپ در یک زمان با پیچیدگی چندجمله ای و اجرای یک ارائهٔ منسجم در سایز چند جمله‌ای برای درختان تجزیه گرامرهای مبهم توسط فراست، حافظ و کالاهان در سال 2007 گسترش یافت . این نویسندگان سپس الگوریتم را به عنوان مجموعه‌ای از تجزیه گرهای ترکیبی نوشته شده در زبان برنامه نویسی هاسکل ارائه دادند.حذف بازگشتی چپ.حذف بازگشتی چپ بی‌درنگ.الگوریتم کلی حذف بازگشت فوری چپ شرح زیر است. پیشرفت‌های بسیاری در این روش صورت گرفت که شامل مواردی مثل "حذف بازگشتی چپ از گرامرهای مستقل از متن" است که توسط رابرت سی. مور برای هر قانون نوشته شده‌است.formula_16A با تولید زیر جایگزین شودformula_20و یک غیرپایانه بسازدformula_21نشانهٔ تازه تولید شده دم(دنباله) یا ادامه نام داردبرای مثال با توجه به این قانون:formula_22می تواند بازنویسی شود تا از بازگشتی چپ جلوگیری کندformula_23formula_24آخرین قانون برای ساختن یک فرم مشابه کمی کوتاه‌تر است:formula_25حذف بازگشتی چپ غیر مستقیم.اگر گرامر هیج formula_26-productions نداشته باشد ( هیچ عملی به فرم formula_27) و دوری نباشد (هیچ اشتقاقی به فرم formula_28 برای هر غیر پایانهٔ A)این الگوریتم می‌تواند برای حذف بازگشتی چپ غیر مستقیم استفاده شود:غیر پایانه‌ها را طبق یک ترتیب مشخص مرتب کنید formula_29.مشکلات.این تبدیلات بازگشتی چپ را با ساختن یک گرامر بازگشتی راست حذف می‌کند، ولی خاصیت شرکت‌پذیری قوانین را عوض می‌کند. بازگشتی چپ شرکت‌پذیری چپ را می‌سازد؛ بازگشتی راست، شرکت‌پذیری راست را می‌سازد. مثال: گرامر را آغاز می کنیم:formula_35formula_36formula_37پس از انجام تبدیلات استاندارد گرامرهای زیر را داریم:formula_38formula_39formula_40formula_41formula_37تجزیهٔ '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 formula_26 Intاگر این عبارت به صورت "a + a) + a)" نوشته شود. گرامر به صورت بازگشتی راست نوشته می‌شود.مشکل این است که علم حساب به شرکت‌پذیری چپ نیاز دارد. راه حل‌های این مشکل عبارتند از