تجزیه کننده بازگشتی بازگشتی (Recursive Descent Parser) چیست؟

解析递归下降とは何ですか? (Pars کردن بازگشتی-نزولی چیست؟)

سلام دوستان! امروز میخواهیم درباره‌ی یک موضوع جالب و مهم در دنیای کامپیوتر صحبت کنیم: Pars کردن بازگشتی-نزولی. این یه جور روش برای فهمیدن و آنالیز کردن دستورات و زبان‌هایی هست که ما با کامپیوتر بهشون میگیم. نگران نباشید، با مثال‌های ساده سعی میکنم توضیح بدم که قضیه از چه قراره.

فرض کنید شما میخواید یه ماشین حساب ساده درست کنید. این ماشین حساب باید بتونه عبارت‌های ریاضی مثل "2 + 3 * 4" رو بفهمه و حساب کنه. Pars کردن بازگشتی-نزولی به شما کمک میکنه تا این عبارت رو به اجزای کوچکتر تجزیه کنید و بعد باهاشون یه کاری انجام بدید.

اصول کار Pars کردن بازگشتی-نزولی

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

یکی از مهم‌ترین چیزها در این روش، استفاده از "گرامر" هست. گرامر یه جور مجموعه قوانینه که مشخص میکنه یه زبان چجوری ساخته میشه. مثلا، یه گرامر ساده برای عبارت‌های ریاضی میتونه اینجوری باشه:

Expr   ::= Term  (( "+" | "-" ) Term)*
Term   ::= Factor (( "*" | "/" ) Factor)*
Factor ::= Number | "(" Expr ")"
    

این گرامر میگه که یه عبارت (Expr) میتونه شامل یه سری جمله (Term) باشه که با علامت‌های "+" یا "-" از هم جدا شدن. یه جمله هم میتونه شامل یه سری فاکتور (Factor) باشه که با علامت‌های "*" یا "/" از هم جدا شدن. و فاکتور هم میتونه یه عدد (Number) باشه یا یه عبارت داخل پرانتز (Expr).

مثال عملی

حالا بیایید با یه مثال ببینیم این روش چجوری کار میکنه. فرض کنید میخوایم عبارت "2 + 3 * 4" رو Pars کنیم.

1. اول، Pars کننده (Parser) به دنبال یه عبارت (Expr) میگرده.
2. طبق گرامر، یه عبارت میتونه شامل یه جمله (Term) باشه. پس Parser به دنبال یه جمله میگرده.
3. یه جمله میتونه شامل یه فاکتور باشه. پس Parser به دنبال یه فاکتور میگرده.
4. فاکتور میتونه یه عدد باشه. Parser عدد "2" رو پیدا میکنه.
5. حالا Parser برمیگرده به عقب و میبینه که بعد از "2" یه علامت "+" وجود داره.
6. پس Parser دوباره به دنبال یه جمله میگرده.
7. این بار، جمله شامل فاکتورهای "3" و "4" هست که با علامت "*" از هم جدا شدن.
8. در نهایت، Parser این عبارت رو به این صورت تجزیه میکنه: 2 + (3 * 4)

مزایا و معایب

Pars کردن بازگشتی-نزولی مزایای زیادی داره. ساده است، فهمیدنش آسونه، و نوشتن کدش هم خیلی سخت نیست. اما یه عیب بزرگ هم داره: نمیتونه گرامرهایی که "بازگشت چپ" (Left Recursion) دارن رو Pars کنه. بازگشت چپ یعنی اینکه یه قانون توی گرامر، دوباره خودش رو صدا بزنه، ولی از سمت چپ.

مثلا، گرامر زیر بازگشت چپ داره:

Expr ::= Expr "+" Term | Term
    

این گرامر میگه که یه عبارت میتونه خودش باشه بعلاوه یه جمله. این باعث میشه که Parser توی یه حلقه بی‌نهایت بیفته و نتونه کارش رو تموم کنه. برای حل این مشکل، باید گرامر رو تغییر بدیم و بازگشت چپ رو حذف کنیم. یه تغییرات ساده در گرامر اغلب جواب میده‌. برای مثال، گرامر بالا رو میشه به این صورت تغییر داد:

Expr ::= Term Expr'
Expr' ::= "+" Term Expr' | ε
    

که در اینجا ε به معنی هیچ است.

جدول خلاصه

Expr   ::= Term  (( "+" | "-" ) Term)*
Term   ::= Factor (( "*" | "/" ) Factor)*
Factor ::= Number | "(" Expr ")"
                

خلاصه

Pars کردن بازگشتی-نزولی یه روش خوب و نسبتا ساده برای تجزیه و تحلیل دستورات و زبان‌هاست. با اینکه محدودیت‌هایی داره، ولی برای خیلی از پروژه‌ها و کاربردها مناسبه. امیدوارم با این توضیحات، یه درک کلی از این موضوع پیدا کرده باشید. برای اطلاعات بینشر به مراجع تخصصی برنامه نویسی مراجعه کنید. اگه سوالی دارید، حتما بپرسید!

キーワード

Pars کردن, Parser, بازگشتی-نزولی, گرامر, بازگشت چپ, کامپایلر, زبان‌های برنامه‌نویسی

Pars کردن بازگشتی-نزولی دقیقا چیست؟

Pars کردن بازگشتی-نزولی یه روش برای تجزیه و تحلیل دستورات و زبان‌هاست که از بالای ساختار درختی شروع میشه و به سمت پایین میاد.

چه زمانی باید از Pars کردن بازگشتی-نزولی استفاده کنیم؟

وقتی که میخوایم یه زبان ساده رو Pars کنیم و نیازی به پیچیدگی‌های زیاد نداریم.

بازگشت چپ چه مشکلی ایجاد میکنه؟

بازگشت چپ باعث میشه که Parser توی یه حلقه بی‌نهایت بیفته و نتونه کارش رو تموم کنه.

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

با تغییر گرامر و حذف بازگشت چپ.

آیا Pars کردن بازگشتی-نزولی برای همه زبان‌ها مناسبه؟

نه، برای زبان‌های پیچیده تر، روش‌های دیگه ای مثل Pars کردن LR یا LL مناسب‌تر هستن.