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

گرامرهای عملگر اولویت نوعی از گرامرهای زبان رسمی است.
گرامر عملگر اولویت یک گرامر مستقل از متن است ) که در مقایسه با دیگر گرامرها ویژگی‌ای دارد که در هیچ تولیدی از آن دو متغیر مجاور در سمت راست کنار هم نیستند و سمت راست تهی نیست. این ویژگی سبب می‌شود تا میان ترمینال‌های گرامر روابط اولویت تعریف شود.تجزیه‌کننده‌ای که از روابط اولویت استفاده می‌کند بسیار ساده‌تر از تجزیه‌کننده‌های عام مانند LALR هستند. تجزیه‌کننده‌های عملگر اولویت می‌توانند برای کلاس بزرگی از گرامرهای مستقل از متن ساخته شوند.
روابط اولویت
گرامرهای عملگر اولویت بر سه رابطه اولویت بین ترمینال‌ها که در زیر آمده‌است تکیه دارند.
رابطه
معنا
a b
اولویت a از b بیشتر است
ما می‌توانیم بین ترمبنال‌های مختلف تنها یک رابط اولویت درنظر بگیریم و فرض می‌کنیم همیشه $ در پایان رشته قرار دارد. پس می‌توانیم تمامی ترمینال‌هایی که اولویتشان از $ بیشتر یا کمتر است را پیدا کنیم. اگر همه متغیرها و محل رابطه اولویتشان را حذف کنیم تنها روابط میان ترمینال‌ها( ) باقی می‌ماند که به راحتی توسط تجزیه‌کننده‌های پایین به بالا تجزیه می‌شوند.
مثال
به عنوان مثال می‌توان روابط عملگر اولویت زیر را برای یک عبارت ساده پیدا کرد.
id
id
آنها از واقعیت زیر پیروی می‌کنند:
+ همیشه اولویت پایین‌تری از * دارد (بنابراین * اولویت بیشتری از جمع دارد)
هم * و هم + شرکت پذیری چپ دارند (بنابراین + اولویت بیشتری از + دارد و * هم اولویت بیشتری از * دارد)
رشته ورودی را id 1 + id 2 * id 3 در نظر می‌گیریم:
پس ار اضافه کردن علامت پایان و قرار دادن روابط اولویت به صورت زیر خواهد شد:
$ 1 •> + 2 •> * 3 •> $
تجزیه عملگر اولویت
داشتن روابط اولویت این امکان را به ما می‌دهد تا 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 then
repeat
pop the stack
until the top stack terminal is related by
f(a به معنای ان است که اولویت a از b کمتر است.
هر جدول روابط اولویت حتما توابع اولویت ندارد اما در عمل برای بسیاری از گرامرها می‌توان چنین توابعی را طراحی کرد.
الگوریتم ساخت توابع اولویت
برای هر ترمینال گرامر و برای سیمبل پایان رشته($) توابع 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
۵
۱
۳
۰
زبان‌های عملگر اولویت
کلاس زبان توسط گرامرهای عملگر اولویت شرح داده شد.
زبان‌های عملگر اولویت بسیار در کلاس زبان‌های مستقل از متن قطعی موجودند.
زبان عملگر اولویت بسیاری از خواص بسته شدن را مانند اتحاد، متمم، الحاق و … را دارد و بزرگترین کلاس شامل همه عملیات بسته شدن است.
یکی دیگر از ویژگی‌های عجیب زبان‌های عملگر اولویت توانایی تجزیه محلی خود است و می‌تواند موازی و کارآمد تجزیه کند.