نگاهی عمیق به الگوریتم تحلیلگر Pratt Parsing از طریق پیاده‌سازی در C

مقدمه

در مسیر سنتی یادگیری علوم کامپیوتر و طراحی کامپایلرها، نام برخی از الگوریتم‌ها کمتر به گوش می‌خورد. یکی از این موارد Pratt Parsing است که معمولاً در کتاب‌های مرجع کلاسیک مانند Dragon Book جایی ندارد و بیشتر در حلقه‌های توسعه کامپایلر و زبان‌های برنامه‌نویسی مطرح می‌شود. نویسنده پس از آشنایی با این روش از طریق کتاب معروف Crafting Interpreters و مقاله اصلی Pratt، تصمیم گرفته تجربیات و درک خود را به صورت کدهای ساده در زبان C مستند کند.

از Shunting Yard تا پشته صریح

برای درک بهتر Pratt Parsing، ابتدا باید الگوریتم Shunting Yard را مرور کرد. این الگوریتم از یک صف خروجی و یک پشته برای عملگرها استفاده می‌کند. عملگرها دارای قدرت چسبندگی یا همان Binding Power هستند و عملگرهای با اولویت بالاتر زودتر اعمال می‌شوند.

نمونه‌ای ساده از این الگوریتم در C نشان می‌دهد که چگونه عملگرها براساس اولویت روی پشته قرار می‌گیرند یا خارج می‌شوند:

int get_bindpower(char op) {
    static const int bps[] = { ['+'] = 1, ['-'] = 1, ['*'] = 2, ['/'] = 2 };
    return bps[op];
}

با اینکه Shunting Yard برای محاسبه عبارات ساده کارآمد است، اما با افزودن پیچیدگی‌هایی مانند عملگرهای تک‌عملوندی (Unary)، تساوی‌های راست‌گرا یا توابع با آرگومان متغیر، کدهای آن بسیار شلوغ و مدیریت پشته دشوار می‌شود. مشکل اصلی این است که Shunting Yard مفهوم زیرعبارت‌ها (Subexpressions) را به شکل بازگشتی درک نمی‌کند.

انتقال به Pratt Parsing

بزرگ‌ترین تحول در تبدیل Shunting Yard به یک تحلیلگر Pratt در این است که پشته صریح عملگرها حذف شده و از پشته فراخوانی تابع (Call Stack) برای مدیریت زیرعبارت‌ها استفاده می‌شود.

در این رویکرد، چپ‌ترین قدرت چسبندگی (Left Binding Power) به فراخوانی‌های بازگشتی تزریق می‌شود. هر زمان که به یک عملگر با قدرت چسبندگی کمتر برخورد کنیم، تابع بازگشتی پایان می‌یابد که دقیقاً معادل خالی کردن پشته در الگوریتم Shunting Yard است.

در مقاله اصلی Pratt، این مفاهیم با اصطلاحات زیر شناخته می‌شوند:

• توابع پیشوند یا nuds (مثل اعداد یا عملگرهای پیشوند)
• توابع میانوند/پسوند یا leds (مثل عملگرهای دوتایی)

توسعه‌پذیری و افزودن پرانتز

یکی از مزایای بزرگ Pratt Parsing این است که به شما اجازه می‌دهد برای هر عملگر، منطق و کدهای دلخواهی را مستقیماً متصل کنید (مشابه Recursive Descent). به عنوان مثال، افزودن پشتیبانی از پرانتزها بسیار تمیزتر انجام می‌شود:

void expr(Parser *parser, int left_bindpower) {
    if (cur(parser) == '(') {
        bump(parser);
        expr(parser, get_bindpower('('));
        // بررسی بسته شدن پرانتز
    } else if (isdigit(cur(parser))) {
        printf("EMIT '%c'\n", cur(parser));
    }
    // بقیه منطق عملگرها...
}

چرا این موضوع برای مهندسین نرم‌افزار مهم است؟

اگر روزی تصمیم به ساخت یک زبان اسکریپت‌نویسی، مفسر یا کامپایلر شخصی بگیرید، نوشتن یک تحلیلگر عبارات (Expression Parser) تمیز و قابل نگهداری اهمیت زیادی دارد. الگوریتم Pratt Parsing در عین سادگی کدهای پایه، قدرت بسیار بالایی در مدیریت اولویت عملگرها بدون نیاز به نوشتن توابع تو در تو برای هر سطح از اولویت دارد و ترکیب آن با ساختارهای داده‌ای تمیز، کدی بسیار خوانا و قابل توسعه به دست می‌دهد.