قواعد بازگشتی
در علوم کامپیوتر، به‌طور کلی گرامری بازگشتی نامیده می‌شود که شامل قواعد تولید بازگشتی باشد، بدین معنی که گسترش یک عبارت غیر پایانی بر اساس این قواعد، در نهایت منجر به رشته ای گردد که مجدداً شامل همان عبارت غیر پایانی باشد. در غیراین صورت، گرامر غیر بازگشتی نامیده می‌شود.
به‌طور مثال، یک گرامر برای زبان مستقل از متن، گرامر بازگشتی (از چپ) نامیده می‌شود که دارای نماد غیر پایانی A باشد به طوری که بتوان آن را در قواعد تولید قرار داد تا رشته ای با A تولید کند (به عنوان سمت چپ‌ترین نماد). انواع گرامرها در سلسله مراتب چامسکی می‌توانند بازگشتی باشند و این خاصیت بازگشتی است که اجازهٔ تولید مجموعه‌های نامحدود از کلمات را می‌دهد.
ویژگی
یک گرامر غیر بازگشتی تنها می‌تواند یک زبان محدود ایجاد کند و هر زبان محدود می‌تواند توسط یک گرامر غیر بازگشتی ایجاد شود. به‌طور مثال، یک گرامر خط مستقیم تنها یک کلمهٔ منفرد ایجاد می‌کند.
یک گرامر بازگشتی که هیچ قاعدهٔ غیرقابل استفاده ای را در بر نداشته باشد، ضرورتاً یک زبان نامحدود ایجاد می‌کند.
منابع
- ↑ Nederhof, Mark-Jan; Satta, Giorgio (2002), "Parsing Non-recursive Context-free Grammars", Proceedings of the 40th Annual Meeting on Association for Computational Linguistics (ACL '02), Stroudsburg, PA, USA: Association for Computational Linguistics, pp. 112–119, doi:10.3115/1073083.1073104.
- ↑ Notes on Formal Language Theory and Parsing بایگانی‌شده در ۲۸ اوت ۲۰۱۷ توسط Wayback Machine, James Power, Department of Computer Science National University of Ireland, Maynooth Maynooth, Co. Kildare, Ireland.
- ↑ Moore, Robert C. (2000), "Removing Left Recursion from Context-free Grammars", Proceedings of the 1st North American Chapter of the Association for Computational Linguistics Conference (NAACL 2000), Stroudsburg, PA, USA: Association for Computational Linguistics, pp. 249–255.