تجزیه پایین به بالا – طراحی کامپایلر

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

تجزیه‌کننده انتقالی-کاهشی (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

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

• آموزش طراحی کامپایلر
• آموزش گرامرها در طراحی کامپایلر
• مجموعه آموزش‌های علوم کامپیوتر
• تحلیل واژه‌ای (Lexical Analysis) در طراحی کامپایلر — راهنمای جامع
• مجموعه آموزش‌های دروس مهندسی کامپیوتر
• آموزش تجزیه انتقال (کاهش) در طراحی کامپایلر

==