قواعد بازگشتی

در علوم کامپیوتر، به‌طور کلی گرامری بازگشتی نامیده می‌شود که شامل قواعد تولید بازگشتی باشد، بدین معنی که گسترش یک عبارت غیر پایانی بر اساس این قواعد،  در نهایت منجر به رشته ای گردد که مجدداً شامل همان عبارت غیر پایانی باشد. در غیراین صورت، گرامر غیر بازگشتی نامیده می‌شود.

به‌طور مثال، یک گرامر برای زبان مستقل از متن، گرامر بازگشتی (از چپ) نامیده می‌شود که دارای نماد غیر پایانی A  باشد به طوری که بتوان آن را در  قواعد تولید قرار داد تا رشته ای با A  تولید کند (به عنوان سمت چپ‌ترین  نماد). انواع گرامرها در سلسله مراتب چامسکی می‌توانند بازگشتی باشند و این خاصیت بازگشتی است که اجازهٔ تولید مجموعه‌های نامحدود از کلمات را می‌دهد.

ویژگی 
یک گرامر غیر بازگشتی تنها می‌تواند یک زبان محدود ایجاد کند و هر زبان محدود می‌تواند توسط یک گرامر غیر بازگشتی ایجاد شود.
به‌طور مثال، یک گرامر خط مستقیم تنها یک کلمهٔ منفرد ایجاد می‌کند.

یک گرامر بازگشتی که هیچ قاعدهٔ غیرقابل استفاده ای را در بر نداشته باشد، ضرورتاً یک زبان نامحدود ایجاد می‌کند.

منابع 

زبان‌های صوری