کامپیوتر ۲۲۶۴ بازدید

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

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

  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

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

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

==

بر اساس رای ۴ نفر
آیا این مطلب برای شما مفید بود؟
شما قبلا رای داده‌اید!
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.

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

یک نظر ثبت شده در “انواع تجزیه در طراحی کامپایلر — راهنمای جامع

  • علی بهرامی — says: ۱۰ دی، ۱۴۰۰ در ۱۱:۴۳ ب٫ظ

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

    برای رشته id-id*id

    طبق این گرامر:

    E —> E-T | T
    T —> T*U | U
    U —> (E) | id

    تشکر.

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد.

مشاهده بیشتر