انواع تجزیه در طراحی کامپایلر — راهنمای جامع

در مرحله تحلیل نحوی برنامه ورودی از نظر دستوری بررسی می‌شود. در این نوشته به بررسی و معرفی انواع تجزیه موجود در تحلیل نحوی می‌پردازیم. تحلیلگر نحوی یا تجزیه‌کننده، برنامه ورودی را كه به صورت دنباله‌ای از توکن‌ها است، از اسکنر گرفته و تعین می‌کند که آیا این جمله‌بندی می‌تواند به وسیله گرامر زبان مورد نظر تولید شود یا نه. رابطه تحلیلگر و اسکنر به صورت تصویر زیر است:

تحلیل‌گرهای نحوی از قواعد ترکیب که به وسیله گرامر مستقل از متن تعریف شده‌اند، بهره می‌گیرند. روش پیاده‌سازی قواعد ترکیبی (اشتقاق) باعث می‌شود که دو نوع تجزیه داشته باشیم:

1. تجزیه بالا به پایین
2. تجزیه پایین به بالا

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

تجزیه بالا به پایین

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

فیلم آموزش طراحی کامپایلر – جامع و با مفاهیم کلیدی در فرادرس

کلیک کنید

• تجزیه پایین‌گرد (Recursive descent parsing): این نوع از تجزیه که تجزیه بازگشتی-کاهشی نیز نامیده می‌شود، از جمله روش‌های تجزیه بالا به پایین رایج است. دلیل این که این تجزیه بازگشتی (Recursive) نامیده شده، این است که از رویه‌های بازگشتی برای پردازش ورودی استفاده می‌کند. تجزیه پایین‌گرد از مشکل پس‌گرد (Backtracking) رنج می‌برد.
• پس‌گرد (Backtracking): منظور از پس‌گرد این است که اگر اشتقاق یک ترکیب ناموفق باشد، تحلیل‌گر نحوی فرایند کاری خود را با استفاده از قواعد متفاوت از همان ترکیب مجدداً شروع می‌کند. در این تکنیک برای تعیین ترکیب صحیح ممکن است رشته ورودی بیش از یک بار پردازش شود.

تجزیه پایین به بالا

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

مثال

رشته ورودی: a + b *c

قواعد ترکیب:

S → E
E → E + T
E → E * T
E → T
T → id

تجزیه پایین به بالا به صورت زیر است:

a + b * c

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

a + b * c
T + b * c
E + b * c
E + T * c
E * c
E * T
E
S

پس متوجه شدیم که به طور کلی در نوع تجزیه برای تحلیل نحوی وجود دارد. در بخش های بعدی این سلسله مطالب به بررسی تفصیلی این دو روش تجزیه یعنی «بالا به پایین» و «پایین به بالا» می پردازیم.

اگر این نوشته مورد توجه شما قرار گرفته است، پیشنهاد می‌کنیم موارد زیر را نیز ملاحظه نمایید:

• آموزش طراحی کامپایلر
• مجموعه آموزش‌های دروس مهندسی کامپیوتر
• آموزش گرامرها در طراحی کامپایلر
• کامپایلر، طراحی و معماری آن — به زبان ساده
• ساختار داده و الگوریتم‌ ها — راهنمای مقدماتی
• مجموعه آموزش‌های علوم کامپیوتر

==