بازگشت چپ

یک گرامر بازگشتی چپ است اگر بتوانیم یک غیرپایانه مانند A پیدا کنیم که در نهایت بتوان یک فرم جمله‌ای استخراج کرد که A در آن چپ‌ترین نماد باشد.

بازگشتی چپ بی‌درنگ

بازگشتی چپ بی‌درنگ در قوانین به صورت زیر است:

${\displaystyle A\to A\alpha \mid \beta }$

در جایی که ${\displaystyle \alpha }$

${\displaystyle \mathit{E}\mathit{x}\mathit{p}\mathit{r}\to \mathit{E}\mathit{x}\mathit{p}\mathit{r}+\mathit{T}\mathit{e}\mathit{r}\mathit{m}}$

یک بازگشتی چپ است و تجزیه‌گر بازگشتی نزولی برای آن شبیه به کد زیر است:

function Expr()
{ 
    Expr();  match('+');  Term();
}

و یک تجزیه گر نزولی بازگشتی ممکن است هنگام تجزیهٔ گرامری که دارای این قانون است در یک دور بی نهایت بازگشتی بیفتد.

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

ساده‌ترین فرم بازگشتی چپ غیر مستقیم:

${\displaystyle A\to B\alpha \mid C}$

${\displaystyle B\to A\beta \mid D,}$

اشتقاق ممکن: ${\displaystyle A\Rightarrow B\alpha \Rightarrow A\beta \alpha \Rightarrow \dots }$

به‌طور کلی تر برای غیرپایانه‌های ${\displaystyle A_0,A_1,\dots ,A_n}$

${\displaystyle A_0\to A_1{\alpha }_1\mid \dots }$

${\displaystyle A_1\to A_2{\alpha }_2\mid \dots }$

${\displaystyle \cdots }$

${\displaystyle A_n\to A_0{\alpha }_{n+1}\mid \dots }$

${\displaystyle {\alpha }_1,{\alpha }_2,\dots ,{\alpha }_n}$

یک گرامر رسمی که شمال بازگشتی چپ است نمی‌تواند با یک تجزیه گر (LL(k یا سایر تجزیه گرهای بازگشتی نزولی تجزیه شود مگر اینه به یک بازگشتی راست ضعیف مشابه تبدیل شود. در مقابل بازگشتی چپ برای تجزیه گرهای LALR بهتر است زیرا نتیجهٔ آن از یک پشتهٔ کوچک تری نسبت فرم بازگشتی راست استفاده می‌کند. به هر صورت تجزیه گرهای بالا به پایین می‌توانند طیف وسیعی از گرامرهای مستقل از متن را با استفاده از کوتاه کردن اجرا کنند. در سال 2006 فراست و حافظ یک الگوریتم که گرامرهای مبهم را با قوانین بازگشتی چپ مستقیم تطابق داد ارائه دادند. الگوریتم برای کامل کردن الگوریتم‌های تجزیه گر برای تطابق غیر مستقیم و همچنین مستقیم بازگشتی چپ در یک زمان با پیچیدگی چندجمله ای و اجرای یک ارائهٔ منسجم در سایز چند جمله‌ای برای درختان تجزیه گرامرهای مبهم توسط فراست، حافظ و کالاهان در سال 2007 گسترش یافت . این نویسندگان سپس الگوریتم را به عنوان مجموعه‌ای از تجزیه گرهای ترکیبی نوشته شده در زبان برنامه نویسی هاسکل ارائه دادند.

حذف بازگشتی چپ بی‌درنگ

الگوریتم کلی حذف بازگشت فوری چپ شرح زیر است. پیشرفت‌های بسیاری در این روش صورت گرفت که شامل مواردی مثل "حذف بازگشتی چپ از گرامرهای مستقل از متن" است که توسط رابرت سی. مور برای هر قانون نوشته شده‌است.

${\displaystyle A\to A{\alpha }_1|\dots |A{\alpha }_n|{\beta }_1|\dots |{\beta }_m}$

• A یک غیر پایانهٔ بازگشتی چپ است
• ${\displaystyle \alpha }$
  دنباله‌ای از پایانه‌ها و غیرپایانه‌هایی است که null نیستند. (${\displaystyle \alpha \ne ϵ}$
  )
• ${\displaystyle \beta }$
  دنباله‌ای از پایانه‌ها و غیرپایانه‌هایی است که با A شروع نمی‌شوند.

A با تولید زیر جایگزین شود ${\displaystyle A\to {\beta }_1{A}^{\mathrm{\prime }}|\dots |{\beta }_m{A}^{\mathrm{\prime }}}$

و یک غیرپایانه بسازد

${\displaystyle A^{\mathrm{\prime }}\to ϵ|{\alpha }_1{A}^{\mathrm{\prime }}|\dots |{\alpha }_n{A}^{\mathrm{\prime }}}$

نشانهٔ تازه تولید شده دم(دنباله) یا ادامه نام دارد

برای مثال با توجه به این قانون:

${\displaystyle Expr\to Expr+Expr|Int|String}$

می تواند بازنویسی شود تا از بازگشتی چپ جلوگیری کند

${\displaystyle Expr\to IntExprRest|StringExprRest}$

${\displaystyle ExprRest\to ϵ|+ExprExprRest}$

آخرین قانون برای ساختن یک فرم مشابه کمی کوتاه‌تر است:

${\displaystyle ExprRest\to ϵ|+Expr}$

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

اگر گرامر هیج ${\displaystyle ϵ}$

غیر پایانه‌ها را طبق یک ترتیب مشخص مرتب کنید ${\displaystyle A_1,\dots A_n}$

این تبدیلات بازگشتی چپ را با ساختن یک گرامر بازگشتی راست حذف می‌کند، ولی خاصیت شرکت‌پذیری قوانین را عوض می‌کند. بازگشتی چپ شرکت‌پذیری چپ را می‌سازد؛ بازگشتی راست، شرکت‌پذیری راست را می‌سازد.

مثال: گرامر را آغاز می کنیم:

${\displaystyle Expr\to Expr+Term|Term}$

${\displaystyle Term\to Term\ast Factor|Factor}$

${\displaystyle Factor\to (Expr)|Int}$

پس از انجام تبدیلات استاندارد گرامرهای زیر را داریم:

${\displaystyle Expr\to TermExp{r}^{\prime }}$

${\displaystyle Exp{r}^{\prime }\to +TermExp{r}^{\prime }|ϵ}$

${\displaystyle Term\to FactorTer{m}^{\prime }}$

${\displaystyle Ter{m}^{\prime }\to \ast FactorTer{m}^{\prime }|ϵ}$

${\displaystyle Factor\to (Expr)|Int}$

تجزیهٔ '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   ${\displaystyle ϵ}$

                                                 |
                                                Int

اگر این عبارت به صورت a + a) + a) نوشته شود. گرامر به صورت بازگشتی راست نوشته می‌شود.

مشکل این است که علم حساب به شرکت‌پذیری چپ نیاز دارد. راه حل‌های این مشکل عبارتند از

1. بازنویسی گرامرها تا بازگشتی چپ شوند.
2. بازنویسی گرامرها با تعدادی غیرپایانه که شرکت‌پذیری را تضمین می‌کند.
3. اگر از YACC یا Bison استفاده کنیم، اعلانهایی %left ، %right و %nonassoc دارند که به تجزیه گر نوع شرکت‌پذیری را اعلام می‌کند.