کامپیوتر ۲۷۷۹ بازدید

فرایند تجزیه پایین به بالا از گره‌های برگ یک درخت آغاز می‌شود و به سمت بالا تا رسیدن به گره ریشه ادامه می‌یابد. در این روش ما از یک جمله آغاز می‌کنیم و سپس قواعد ترکیب را به روش معکوس برای رسیدن به نماد آغازین ادامه می‌دهیم. در تصویر زیر تجزیه‌کننده‌های پایین به بالا به تصویر کشیده شده‌اند.

تجزیه‌کننده انتقالی-کاهشی (Shift-Reduce Parsing)

در این روش تجزیه از دو مرحله منحصر به فرد برای تجزیه پایین به بالا استفاده می‌شود. این مراحل به نام گام انتقال و گام کاهش نامیده می‌شوند.

  • گام انتقال: منظور از انتقال، پیش‌روی اشاره‌گر ورودی به نماد ورودی بعدی است که نماد انتقالی نامیده می‌شود. این نماد به پشته وارد می‌شود و با نماد انتقالی به صورت یک گره منفرد در درخت تجزیه برخورد می‌شود.
  • گام کاهشی: وقتی تجزیه‌کننده یک قاعده گرامری کامل (RHS) بیابد و آن را با (LHS) تعویض کند به نام گام کاهشی شناخته می‌شود. این فرایند زمانی رخ می‌دهد که عنصر فوقانی پشته شامل یک دستگیره (handle) باشد. برای کاهش، یک کارکرد POP روی پشته اجرا می‌شود که handle را از پشته خارج می‌کند و آن را با نماد غیر پایانی LHS جایگزین می‌کند.

تجزیه‌کننده LR

تجزیه‌کننده LR یک تجزیه‌کننده غیر بازگشتی، انتقالی-کاهشی و پایین به بالا محسوب می‌شود. این تجزیه‌کننده از دسته گسترده‌ای از گرامرهای مستقل از متن استفاده می‌کند که باعث می‌شود کارآمدترین تکنیک تحلیل نحوی به حساب آید. تجزیه‌کننده‌های LR به نام تجزیه‌کننده‌های (LR(k نیز شناخته می‌شوند که در آن حرف L به معنی اسکن کردن چپ به راست (left-to-right scanning) جریان ورودی؛ حرف R به معنی ساخت اشتقاق راست‌ترین (right-most derivation) به طور معکوس و حرف k نشان دهنده تعداد نمادهای رو به جلو برای تصمیم‌گیری است.

سه الگوریتم هستند که به طور گسترده‌ای برای ساخت تجزیه‌کننده LR استفاده می‌شوند:

  • (SLR(1 – تجزیه‌کننده LR ساده:
    • بر روی دسته کوچک‌ترین گرامرها کار می‌کند
    • تعداد حالت‌ها معدود است و از این رو جدول بسیار کوچکی دارد
    • ساخت ساده و آسانی دارد
  • (LR(1 – تجزیه‌کننده LR
    • بر روی مجموعه کاملی از گرامرهای (LR(1 کار می‌کند.
    • جدول بزرگی ایجاد می‌کند و تعداد حالت‌ها زیاد است.
    • ساخت کندی دارد
  • (LALR(1 – تجزیه‌کننده LR رو به جلو
    • بر روی گرامرهای با اندازه متوسط کار می‌کند
    • تعداد حالت‌ها همانند الگوریتم (SLR(1 است.

الگوریتم تجزیه LR

در ادامه الگوریتم یک تجزیه‌کننده LR را توصیف می‌کنیم:

token = next_token()

repeat forever
   s = top of stack
   
   if action[s, token] = “shift si” then
      PUSH token
      PUSH si 
      token = next_token()
      
   else if action[s, token] = “reduce A::= β“ then 
      POP 2 * |β| symbols
      s = top of stack
      PUSH A
      PUSH goto[s,A]
      
   else if action[s, token] = “accept” then
      return
      
   else
      error()

مقایسه LL با LR

LL LR
اشتقاق چپ‌ترین دارد. اشتقاق راست‌ترین را به طور معکوس انجام می‌دهد
با ریشه غیر پایانی روی پشته آغاز می‌کند با ریشه غیر پایانی روی پشته خاتمه می‌یابد
زمانی که پشته خالی شود پایان می‌یابد با یک پشته خالی آغاز می‌کند
از پشته برای تعیین این که چه چیزی هنوز باقی مانده است استفاده می‌کند از پشته برای تعیین این که چه چیزی را قبلاً دیده است، استفاده می‌کند
درخت تجزیه را از بالا به پایین می‌سازد درخت تجزیه را از پایین به بالا می‌سازد
به طور مداوم غیر پایانی‌ها را از پشته بر می‌دارد و سمت راست متناظر را وارد پشته می‌کند تلاش می‌کند تا سمت راست را روی پشته تشخیص داده، آن را بردارد و غیر پایانی متناظر را وارد پشته کند
غیر پایانی‌ها را بسط می‌دهد غیر پایانی‌ها را کاهش می‌دهد
پایانی‌ها را زمانی که یک عنصر را از پشته بر می‌دارد، می‌خواند پایانی‌ها را می‌خواند و همزمان آن‌ها را وارد پشته می‌کند
درخت تجزیه پیمایش پیش‌ترتیبی دارد. درخت تجزیه پیمایش پس‌ترتیبی دارد

اگر به این نوشته علاقه‌مند بودید، موارد زیر نیز احتمالاً مورد توجه شما قرار خواهند گرفت:

==

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

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

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

  • سلام
    خسته نباشید
    وقت بخیر

    پاسخ این سوال چی میشه ؟

    * برای تکه برنامه زیر ، کد سه آدرسه بنویسید : ؟

    a=3; b=4;

    for (i=0; i<n; i++)

    a=b+1;
    a=a*a;

    while ( x+y*d)

    x=x+y;

    if (y-x)
    x=x*d;

    {
    {
    c=a;

    ممنون

نظر شما چیست؟

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

مشاهده بیشتر