تجزیه‌کننده عملگر اولویت
در علوم کامپیوتر تجزیه‌گر عملگر اولویت یک تجزیه‌کننده پایین به بالا است که گرامر عملگر اولویت را تفسیر می‌کند. برای مثال بسیاری از ماشین‌حساب‌ها از تجزیه‌کنندهٔ عملگر اولویت برای تبدیل از نشانه‌گذاری میانوندی که برای انسان قابل خواندن است، با توجه به ترتیب عملگرها به فرمتی که برای محاسبات بهینه است تبدیل می‌کند، مانند نشانه‌گذاری معکوس لهستانی.
معمولاً الگوریتم Shunting yard که توسط ادسخر دیکسترا ارائه شد، برای تجزیه عملگر اولویت استفاده می‌شود و الگوریتم‌های دیگر شامل روش بالا رفتن اولویت و روش پالا به پایین عملگر اولویت می‌باشند.[۱]
ارتباط با سایر تجزیه‌کننده‌ها[ویرایش]
تجزیه‌کننده عملگر اولویت یک تجزیه‌کننده انتقال - کاهش است که قادر به تجزیه زیر مجموعه گرامرهای (LR(1 نیست. به‌طور دقیق تر تجزیه‌کننده‌های عملگر اولویت می‌توانند تنها آن دسته از گرامرهای (LR(1 که در آن‌ها هیچ دو متغیر کنار هم نیستند را تجزیه کنند و همچنین گرامر فاقد تهی باشد (لاندا - اپسیلون).
اگر چه گرامرهای عملگر اولویت ویژگی‌هایی دارند که آن‌ها را برای طرح خای بزرگتر مفید می‌کند ولی در عمل از آن‌ها استفاده نمی‌شود. اول آنکه آن‌ها به قدری ساده هستند که می‌توان آن‌ها را با دست نوشت به‌طوری‌که آن‌ها در موارد تجزیه‌کننده‌های انتقال - کاهش با پیچیدگی زیاد عمومی نیستند. دوم آنکه تجزیه‌کننده‌های عملگر اولویت با کمک جدول عملگرها در زمان اجرا نوشته می‌شوند و آن‌ها را برای زبان‌هایی که امکان تغییر یا افزودن عملگرهایشان را در زمان تحلیل دارند مناسب می‌کند. (به عنوان مثال هسکل (زبان برنامه‌نویسی) که اپراتور عملگر اولویت باید در برنامه بعد از تجزیه همه ماژول‌های مرجع اجرا شود)
روش اولویت بالا رفتن[ویرایش]
الگوریتم روش اولویت بالارفتن پیوسته، کارآمد است و برای تجزیه عباراتی که اولین بار توسط ریچارد و کولین تعریف شده‌اند انعطاف‌پذیر است.[۲]
گرامر عبارت نشانه‌گذاری میانوندی در فرمت EBNF عموماً مانند زیر خواهد بود:
expression ::= equality-expression
equality-expression ::= additive-expression (('==' | '!=') additive-expression) *
additive-expression ::= multiplicative-expression (('+' | '-') multiplicative-expression) *
multiplicative-expression ::= primary (('*' | '/') primary) *
primary ::= '(' expression ')' | NUMBER | VARIABLE | '-' primary</sub><sub>right hand side''=3''</sub>
با بسیاری از سطوح اولویت امکان دارد اجرای این گرامر با تجزیه‌کننده پیشگوی بازگشتی نزولی غیر کارآمد شود. به عنوان مثال تجزیه یک عدد می‌تواند به پنج تابع نیاز داشته باشد. یکی برای هر متغیر تا رسیدن به متغیر ابتدایی. تجزیه‌کننده عملگر اولویت می‌تواند می‌تواند بسیار کارآمدتر باشد.[۳]
ایده این است که ما می‌توانیم بگذاریم تا عملگرهای حسابی کار کنند تا زمانی که عملگرهای با اولویت یکسان پیدا کنیم. اما ما باید نتایج موقت را برای ارزیابی عملگرهای اولویت بالاتر نگه داریم. الگوریتمی که در اینجا ارائه شد به یک پشته ساده نیاز ندارد در عوض از یک روش بازگشتی برای اجرای پشته استفاده می‌کند.
این الگوریتم یک تجزیه‌کننده عملگر اولویت خاص مثل الگوریتم shunting yard ادسخر دیکسترا نیست. این تصور به وجود می‌آید که متغیر ابتدایی با یک روال جداگانه مانند تجزیه‌کننده بازگشتی نزولی تجزیه می‌شود.
شبه کد[ویرایش]
شبه کد برای الگوریتم به شرح زیر است. تجزیه‌کننده در تابع عبارت تجزیه شروع می‌شود. سطح اولویت بیشتر یا برابر با ۰ است.
parse_expression () return parse_expression_1 (parse_primary (), 0)
parse_expression_1 (lhs, min_precedence) while the next token is a binary operator whose precedence is>= min_precedence op := next token rhs := parse_primary () while the next token is a binary operator whose precedence is greater than op's, or a right-associative operator whose precedence is equal to op's lookahead := next token rhs := parse_expression_1 (rhs, lookahead's precedence) lhs := the result of applying op with operands lhs and rhs return lhs
مثال اجرای الگوریتم[ویرایش]
به عنوان مثال اجرای عبارت ۱۹==۵+۴*۳+۲ به شرح زیر است. به عبارت مساوی اولویت ۰ و به عبارت جمع اولویت ۱ و به عبارت ضرب اولویت ۲ رااختصاص می‌دهیم.
عبارت تجزیه 1(left hand side=۲ و کمترین اولویت =۰)
- توکن بعدی + است با اولویت ۱ (پس وارد حلقه while می‌شود)
- عملگر + با اولویت ۱
- right hand side=۳
- توکن بعدی * است با اولویت ۲ پس فراخوانی بازگشتی داریم.
عبارت تجزیه 1(right hand side=۲ و کمترین اولویت =۲ است) - توکن بعدی * با اولویت ۲ (پس وارد حلقه می‌شود)
- عملگر * با اولویت ۲
- right hand side=۴
- توکن بعدی + با اولویت ۱ (پس فراخوانی بازگشتی نداریم)
- به left hand side اختصاص داده می‌شود ۱۲=۴*۳
- توکن بعدی + با اولویت ۱ است (حلقه while را ترک می‌کند)
- ۱۲ را برمی‌گرداند.
- توکن بعدی + است با اولویت ۱(پس فراخوانی بازگشتی نداریم)
- به left hand side اختصاص داده می‌شود ۱۴=۱۲+۲
- توکن بعدی + است با اولویت ۱ (حلقه while را ترک نمی‌کند)
- عملگر + با اولویت ۱
- right hand side=۵
- توکن بعدی== است با اولویت ۰ (پس فراخوانی بازگشتی نداریم)
- به left hand side اختصاص داده می‌شود ۱۹=۵+۱۴
- توکن بعدی == است با اولویت ۰ (حلقه while رو ترک نمی‌کند)
- عملگر == (اولویت ۰)
- right hand side=۱۹
- توکن بعدی آخر خط است، عملگری نداریم پس فراخوانی بازگشتی هم نداریم.
- نتیجه ارزیابی ۱۹==۱۹ به left hand side اختصاص داده شده‌است.
- توکن بعدی آخر خط است و هیچ عملگری نداریم پس حلقه while را ترک می‌کند.
۱ را برمی‌گرداند.
روش‌های جایگزین[ویرایش]
روش‌های مختلفی برای اجرای قوانین عملگر اولویت وجود دارد. یکی از راه‌ها ساختن درخت از عبارت اصلی و اجرای درخت و بازنویسی قوانین آن است. چنین درختانی لزوماً برای اجرا نباز به ساختمان داده‌های متداول که برای درختان مورد استفاده قرار می‌گیرند ندارند. در عوض توکن می‌تواند در ساختارهای مسطح مانند جدول‌ها به‌طور هم‌زمان توسط ایجاد یک لیست اولویت که مشخص می‌کند که عناصر با چه ترتیبی پردازش شوند.
روش دیگر این است که اول به‌طور کامل عبارت را پرانتزگذاری کنیم و اطراف هر عملگر تعدادی پرانتز قرار دهیم. به‌طوری‌که آن‌ها حتی زمانی که به صورت خطی تجزیه می‌شوند و پارسرهای چپ به راست هم با اولویت درست هدایت شوند. این الگوریتم در کامپایلرهای فورترن اولیه استفاده شده‌است.[نیازمند منبع]
کد نمونه‌ای از یک برنامه ساده به زبان c است که عملیات پرانتزگذاری عملگرهای اصلی ریاضی(* + - / ^ پرانتز) را handle می‌کند.
#include <stdio.h>
#include <string.h>
int main(int argc, char *argv[]){
int i;
printf("((((");
for(i=1;i!=argc;i++){
if(argv[i] && !argv[i][1]){
switch(*argv[i]){
case '(': printf("(((("); continue;
case ')': printf("))))"); continue;
case '^': printf(")^("); continue;
case '*': printf("))*(("); continue;
case '/': printf("))/(("); continue;
case '+':
if (i == 1 || strchr("(^*/+-", *argv[i-1]))
printf("+");
else
printf(")))+(((");
continue;
case '-':
if (i == 1 || strchr("(^*/+-", *argv[i-1]))
printf("-");
else
printf(")))-(((");
continue;
}
}
printf("%s", argv[i]);
}
printf("))))\n");
return 0;
}
به عنوان مثال زمانی که کامپایل به اتمام رسید، از خط فرمان و پارامترهایش خواسته می‌شود که خروجی را در کنسول تولید کند.
a * b + c ^ d / e
((((a))*((b)))+(((c)^(d))/((e))))
محدودیتی که در این استراتژی وجود دارد این است که همیشه عملگرهای یگانی اولویت بالاتری نسبت به عملگرهای میانی دارند. در اجرای برنامه با ورودی زیر می‌بینیم که عملگر منفی اولویت بالتری نسبت به عملگر توان دارد.
- a ^ 2
و این خروجی را تولید می‌کند. که احتمالاً همان چیزی است که در نظر گرفته می‌شود.
((((-a)^(2))))
منابع[ویرایش]
- ↑ Norvell, Theodore (2001). "Parsing Expressions by Recursive Descent". Retrieved 2012-01-24.
- ↑ Richards, Martin; Whitby-Stevens, Colin (1979). BCPL — the language and its compiler. Cambridge University Press. ISBN 978-0-521-21965-5.
- ↑ Harwell, Sam (2008-08-29). "Operator precedence parser". ANTLR3 Wiki. Archived from the original on 11 October 2013. Retrieved 2012-01-24.
پیوند به بیرون[ویرایش]
- Clarke, Keith (1992-05-26). "Re: compact recursive-descent parsing of expressions". Retrieved 2012-01-24.
- Example C++ code by Keith Clarke for parsing infix expressions using the precedence climbing method
- Samelson, Klaus (1960). "Sequential formula translation". Communications of the ACM. 3 (2): 76–83. doi:10.1145/366959.366968.
{{cite journal}}: Unknown parameter|coauthors=ignored (|author=suggested) (help); Unknown parameter|month=ignored (help)