گرامر عملگر اولویت

گرامرهای عملگر اولویت نوعی از گرامرهای زبان رسمی است.

گرامر عملگر اولویت یک گرامر مستقل از متن استAho, Sethi & Ullman 1988, p.  203.) که در مقایسه با دیگر گرامرها ویژگی ای دارد که در هیچ تولیدی از آن دو متغیر مجاور در سمت راست کنار هم نیستند و سمت راست تهی نیست. این ویژگی سبب می‌شود تا میان ترمینال‌های گرامر روابط اولویت تعریف شود.تجزیه‌کننده‌ای که از روابط اولویت استفاده می‌کند بسیار ساده‌تر از تجزیه‌کننده‌های عام مانند LALR هستند. تجزیه‌کننده‌های عملگر اولویت می‌توانند برای کلاس بزرگی از گرامرهای مستقل از متن ساخته شوند.

 روابط اولویت 
گرامرهای عملگر اولویت بر سه رابطه اولویت بین ترمینال‌ها که در زیر آمده‌است تکیه دارند.

 رابطه معنا a <• b اولویت a از b کمتر است. a =• b a و b اولویت یکسانی دارند a •> bاولویت a از b بیشتر است.

ما می‌توانیم بین ترمبنال‌های مختلف تنها یک رابط اولویت در نظر بگیریم و فرض می‌کنیم همیشه $ در پایان رشته قرار دارد. پس می‌توانیم تمامی ترمینال‌هایی که اولویتشان از $ بیشتر یا کمتر است را پیدا کنیم. اگر همه متغیرها و محل رابطه اولویتشان را حذف کنیم تنها روابط میان ترمینال ها(<•, =•, •>) باقی می‌ماند که به راحتی توسط  تجزیه‌کننده‌های پایین به بالا تجزیه می‌شوند.

 مثال 
به عنوان مثال می‌توان روابط عملگر اولویت زیر را برای یک عبارت ساده پیدا کرد.Aho, Sethi & Ullman 1988, p.  205.

 id + * $ id •> •> •> + <• •> <• •> * <• •> •> •> $ <• <• <•

آن‌ها از واقعیت زیر پیروی می‌کنند:
 + همیشه اولویت پایین تری از * دارد (بنابراین * اولویت بیشتری از جمع دارد)
 هم * و هم + شرکت پذیری چپ دارند (بنابراین + اولویت بیشتری از + دارد و * هم اولویت بیشتری از * دارد)
رشته ورودی را id1 + id2 * id3 در نظر می‌گیریم:
پس ار اضافه کردن علامت پایان و قرار دادن روابط اولویت به صورت زیر خواهد شد:
$ <• id1 •> + <• id2 •> * <• id3 •> $

 تجزیه عملگر اولویت 
داشتن روابط اولویت این امکان را به ما می‌دهد تا handle‌ها را به شرح زیر پیدا کنیم:
 رشته را تا جایی که علامت <• را دیدیم اسکن می‌کنیم
 اسکن به عقب (از راست به چپ) بیشتر از هر•= تا زمانی که •> دیده شود
 هر چیزی که بین <• و  •> ایت مانند ترمینال‌های بین یا اطراف فرمی از handle است.
به‌طور کلی لازم نیست برای اسکن همه فرم‌های جمله‌ای handle را پیدا کنیم.

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

 Initialize: Set ip to point to the first symbol of w$
 Repeat:
   If $ is on the top of the stack and ip points to $ then return
   else
     Let a be the top terminal on the stack, and b the symbol pointed to by ip
     if a <• b or a =• b then
       push b onto the stack
       advance ip to the next input symbol
     else if a •> b then
       repeat
         pop the stack
       until the top stack terminal is related by <• to the terminal most recently popped
     else error()
   end

 توابع اولویت 
تجزیه‌کننده عملگر اولویت معمولاً جدول اولویت و روابطش را که می‌تواند آن را تا اندازه‌ای بزرگ کند ذخیره نمی‌کند و در عوض توابع اولویت f و g را تعریف می‌کند. تجزیه‌کننده عملگر اولویت سیمبل‌های ترمینال را به اعداد نگاشت می‌کند و به همین ترتیب روابط اولویت بین سیمبل‌های اجرا شده توسط مقایسه عددی پیدا می‌کند. (g(b)>f(a به معنای ان است که اولویت a از b کمتر است.
هر جدول روابط اولویت حتماً توابع اولویت ندارد اما در عمل برای بسیاری از گرامرها می‌توان چنین توابعی را طراحی کرد.Aho, Sethi & Ullman 1988, p.  209.
 الگوریتم ساخت توابع اولویت 
Aho, Sethi & Ullman 1988, p.  206.
 برای هر ترمینال گرامر و برای سیمبل پایان رشته($) توابع f و g را ایجاد می‌کنیم.
 اگر اولویت a و b برابر بود توابع (f(a و (g(b  را در یک گروه قرار می‌دهیم.
 یک گراف جهت دار ایجاد می‌کنیم که گره‌هایش گروه‌ها هستند و برای هر زوج (b و a) اگر اولویت a از b بیشتر بود یالی از گروه (f(a به گروه (g(b وصل می‌کنیم و در غیر این صورت اگر اولویت b  از a بیشتر بود یالی از گروه (g(b به گروه (f(a وصل می‌کنیم.
 اگر گراف حاصل دور داشت پس توابع اولویت نداریم و اگر دور تداشت پس توابع اولویت داریم و طول (f(a  برابر است با طولاتی‌ترین مسیر از گروه (f(a  و طول (g(a را هم طولانی‌ترین مسیر از گروه (g(a قرار می‌دهیم.

 مثال 
دوباره همین جدول را در نظر می‌گیریم
 id + * $ id •> •> •> + <• •> <• •> * <• •> •> •> $ <• <• <•

یا استفاده از الگوریتم به گراف زیر می‌رسیم:

    gid
   \
  *fid   f
    /   \
      g*
     /
      f+
    \  |
    g+ |
    |  |
   $g$  f

که از گراف بدون دور توابع اولویت با حداکثر ارتفاع را پیدا می‌کنیم.

 id + * $ f ۴ ۲ ۴ ۰ g ۵ ۱ ۳ ۰

 زبان‌های عملگر اولویت 
کلاس زبان توسط گرامرهای عملگر اولویت شرح داده شد.

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

یکی دیگر از ویژگی‌های عجیب زبان‌های عملگر اولویت توانایی تجزیه محلی خود است و می‌تواند موازی و کارآمد تجزیه کند.

 منابع 

 Aho, Alfred V. , Sethi, Ravi, and Ullman, Jeffrey D. (1988). Compilers — Principles, Techniques, and Tools.  Addison-Wesley.







 پیوند به بیرون 

 Nikolay Nikolaev: IS53011A Language Design and Implementation , Course notes for CIS ۳۲۴, ۲۰۱۰.

رده:مقاله‌های ایجادشده توسط ایجادگر
رده:زبان‌های صوری