گرامر عملگر اولویت
گرامرهای عملگر اولویت نوعی از گرامرهای زبان رسمی است.
گرامر عملگر اولویت یک گرامر مستقل از متن است[1]) که در مقایسه با دیگر گرامرها ویژگی ای دارد که در هیچ تولیدی از آن دو متغیر مجاور در سمت راست کنار هم نیستند و سمت راست تهی نیست. این ویژگی سبب می‌شود تا میان ترمینال‌های گرامر روابط اولویت تعریف شود.تجزیه‌کننده‌ای که از روابط اولویت استفاده می‌کند بسیار ساده‌تر از تجزیه‌کننده‌های عام مانند LALR هستند. تجزیه‌کننده‌های عملگر اولویت می‌توانند برای کلاس بزرگی از گرامرهای مستقل از متن ساخته شوند.
روابط اولویت
گرامرهای عملگر اولویت بر سه رابطه اولویت بین ترمینال‌ها که در زیر آمده‌است تکیه دارند.
| رابطه | معنا |
|---|---|
| a <• b | اولویت a از b کمتر است. |
| a =• b | a و b اولویت یکسانی دارند |
| a •> b | اولویت a از b بیشتر است. |
ما می‌توانیم بین ترمبنال‌های مختلف تنها یک رابط اولویت در نظر بگیریم و فرض می‌کنیم همیشه $ در پایان رشته قرار دارد. پس می‌توانیم تمامی ترمینال‌هایی که اولویتشان از $ بیشتر یا کمتر است را پیدا کنیم. اگر همه متغیرها و محل رابطه اولویتشان را حذف کنیم تنها روابط میان ترمینال ها(<•, =•, •>) باقی می‌ماند که به راحتی توسط تجزیه‌کننده‌های پایین به بالا تجزیه می‌شوند.
مثال
به عنوان مثال می‌توان روابط عملگر اولویت زیر را برای یک عبارت ساده پیدا کرد.[2]
| id | + | * | $ | |
|---|---|---|---|---|
| id | •> | •> | •> | |
| + | <• | •> | <• | •> |
| * | <• | •> | •> | •> |
| $ | <• | <• | <• |
آن‌ها از واقعیت زیر پیروی می‌کنند:
- + همیشه اولویت پایین تری از * دارد (بنابراین * اولویت بیشتری از جمع دارد)
- هم * و هم + شرکت پذیری چپ دارند (بنابراین + اولویت بیشتری از + دارد و * هم اولویت بیشتری از * دارد)
رشته ورودی را id1 + id2 * id3 در نظر می‌گیریم:[2] پس ار اضافه کردن علامت پایان و قرار دادن روابط اولویت به صورت زیر خواهد شد: $ <• id1 •> + <• id2 •> * <• id3 •> $
تجزیه عملگر اولویت
داشتن روابط اولویت این امکان را به ما می‌دهد تا handleها را به شرح زیر پیدا کنیم:[2]
- رشته را تا جایی که علامت <• را دیدیم اسکن می‌کنیم
- اسکن به عقب (از راست به چپ) بیشتر از هر•= تا زمانی که •> دیده شود
- هر چیزی که بین <• و •> ایت مانند ترمینال‌های بین یا اطراف فرمی از 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 کمتر است. هر جدول روابط اولویت حتماً توابع اولویت ندارد اما در عمل برای بسیاری از گرامرها می‌توان چنین توابعی را طراحی کرد.[3]
الگوریتم ساخت توابع اولویت
- برای هر ترمینال گرامر و برای سیمبل پایان رشته($) توابع 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 | ۵ | ۱ | ۳ | ۰ |
زبان‌های عملگر اولویت
کلاس زبان توسط گرامرهای عملگر اولویت شرح داده شد.[5]
زبان‌های عملگر اولویت بسیار در کلاس زبان‌های مستقل از متن قطعی موجودند. زبان عملگر اولویت بسیاری از خواص بسته شدن را مانند اتحاد، متمم، الحاق و ... را دارد و بزرگترین کلاس شامل همه عملیات بسته شدن است.[6]
یکی دیگر از ویژگی‌های عجیب زبان‌های عملگر اولویت توانایی تجزیه محلی خود است و می‌تواند موازی و کارآمد تجزیه کند.[7]
منابع
- Aho, Sethi & Ullman 1988, p. 203.
- Aho, Sethi & Ullman 1988, p. 205.
- Aho, Sethi & Ullman 1988, p. 209.
- Aho, Sethi & Ullman 1988, p. 206.
- Crespi Reghizzi & Mandrioli 2012
- Crespi Reghizzi, Mandrioli & Martin 1978
- Barenghi et al. 2013
- Aho, Alfred V. , Sethi, Ravi, and Ullman, Jeffrey D. (1988). Compilers — Principles, Techniques, and Tools. Addison-Wesley.
- Floyd, Robert W. (1963). "Syntactic Analysis and Operator Precedence". Journal of the ACM. 10 (3): 316–333. doi:10.1145/321172.321179. ISSN 0004-5411.
- Crespi Reghizzi, Stefano; Mandrioli, Dino (2012). "Operator precedence and the visibly pushdown property". Journal of Computer and System Sciences. 78 (6): 1837–1867. doi:10.1016/j.jcss.2011.12.006.
- Crespi Reghizzi, Stefano; Mandrioli, Dino; Martin, David F. (1978). "Algebraic Properties of Operator Precedence Languages". Information and Control. 37 (2). doi:10.1016/S0019-9958(78)90474-6.
- Barenghi, Alessandro; Crespi Reghizzi, Stefano; Mandrioli, Dino; Pradella, Matteo (2013). "Parallel parsing of operator precedence grammars". Information Processing Letters. 113 (7): 245–249. doi:10.1016/j.ipl.2013.01.008.
- Lonati, Violetta; Mandrioli, Dino; Pradella, Matteo (2011). Precedence Automata and Languages. The 6th International Computer Science Symposium in Russia (CSR), LNCS. 6651. pp. 291–304. doi:10.1007/978-3-642-20712-9_23.
- Lonati, Violetta; Mandrioli, Dino; Pradella, Matteo (2013). Logic Characterization of Invisibly Structured Languages: the Case of Floyd Languages. SOFSEM, LNCS. 7741. pp. 307–318. doi:10.1007/978-3-642-35843-2_27.
پیوند به بیرون
- Nikolay Nikolaev: IS53011A Language Design and Implementation, Course notes for CIS ۳۲۴, ۲۰۱۰.