تجزیه اولویت ساده
در علوم کامپیوتر تجزیه اولویت ساده یک نوع تجزیه‌کننده پایین به بالا برای گرامر مستقل از متن است که در آن فقط از گرامر اولویت ساده استفاده می‌شود.
ارتباط با تجزیه‌کننده عملگر اولویت
این روش تجزیه بسیار شبیه روش تجزیه‌کننده عملگر اولویت است و در واقع بهبود یافته آن است. در این روش روابط تقدم بین همه عناصر گرامر تعریف شده در حالیکه در روش اولویت عملگر این روابط فقط بین پایانه‌ها تعریف می‌شود. برای استفاده از این روش محدودیت‌های کمتری نسبت به مورد اولویت عملگر وجود دارد که باعث می‌شود که روش اولویت ساده طیف بیشتری از گرامرها را دربر بگیرد.
به عنوان نمونه در اینجا وجود غیرپایانه‌های مجاور درسمت راست قواعد مجاز است لیکن مانند حالت قبل وجود قواعد اپسیلون مجاز نیست. ازآنجا که در تجزیه اولویت ساده برخلاف روش تجزیه‌کننده عملگر اولویت بین غیر پایانه‌ها تمایز قائل می‌شویم در اینجا یک محدودیت جدید داریم که سمت راست هیچ دو قاعده‌ای نباید یکسان باشد. زیرا درغیراینصورت در بعضی از قدم‌ها تداخل کاهش/کاهش پیش خواهد آمد. البته این محدودیت چندان مهمی نیست. درهردومورداین روش‌ها یک محدودیت مشترک وجود دارد که در خانه های جدول تجزیه بایستی حداکثر یک رابطه تقدم وجود داشته باشد. در 'تجزیه اولویت ساده هم برای هدایت عملیات از روابط سه‌گانه تقدم شامل , و استفاده می‌شود. البته در روش تقدم ساده این روابط بین کلیه علائم گرامر(پایانه و غیرپایانه و$) تعریف می‌شود. جدول تجزیه تقدم ساده یک جدول مربع است که به تعداد حاصل جمع تعداد پایانه‌های گرامر به‌علاوه یک (به خاطر علامت $) سطر و ستون دارد.
توابع HEAD و TAIL
برای تعیین روابط اولویت ساده از دو تابع با نام‌های “Head” و “Tail” استفاده می‌شود که تعریف رسمی آن‌ها به صورت زیر است . هردوی این توابع بر روی یک غیرپایانه عمل کرده و حاصل آن‌ها مجموعه‌ای ازعلائم گرامر است.
- HEAD(U)= {X|U → Xa}
- TAIL(U)= {X|U → aX}
بااستفاده ازدوتابع فوق روابط اولویت ساده به صورت زیرتعریف می‌شوند:
- X = Y iff ∃U …XY…
- X <Y iff ∃U → …XA… and Y ∈ HEAD(A)
- X> Y iff ∃U → …AB… and X ∈ TAIL(A) and ( Y ∈ HEAD(B) or Y=B)
مثالی از تحلیل روابط در جدول تجزیه
گرامر زیر را در نظر بگیرید:
* S→ (SS) * S → c
مانند روش تجزیه‌کننده عملگر اولویت ابتدا قاعده‌ای به فرم $N → $S به قواعد گرامر اضافه کرده سپس مطابق روالی که در آنجا ذکر گردید به دنبال قواعدی می‌گردیم که شرایط تعاریف فوق در مورد آن‌ها صدق نماید . حاصل این کار در مورد مثال فوق به صورت جدول تجزیه زیر خواهد بود.
| c | ( | ) | $ | s | |
| > | = | > | = | = | s |
| > | > | = | $ | ||
| > | > | = | ) | ||
| < | < | < | < | ( | |
| < | < | < | < | c |
الگوریتم تجزیه اولویت ساده
در این روش پارسر در هر قدم از تجزیه با استفاده ازتوکن جاری b وعنصر بالای انباره X (که می‌تواند پایانه یا غیر پایانه باشد) به جدول تجزیه مراجعه کرده و به صورت یکی از حالات زیر عمل می‌کند:
۱-درصورتی که رابطه علامت بالای انباره و توکن جاری به صورت X < b باشد پارسر عمل انتقال را انجام می‌دهد. در این مورد ابتدا علامت> و سپس توکن جاری b را به بالای انباره منتقل می‌کند.
۲-درصورتی‌که رابطه به صورت X = b باشد پارسر عمل کاهش را انجام می‌دهد.
۳-در صورتی‌که رابطه به صورت X > b پارسر عمل کاهش را انجام می‌دهد. در این حالت دستگیره رشته بالای انباره تا اولین علامت> است. پارسر ابتدا دستگیره را از بالای انباره حذف می‌کند . اگر عنصر بالای انباره (پس از حذف چپ دستگیره) راTop بنامیم و سمت چپ قاعده‌ای را که پارسر از آن جهت کاهش استفاده می‌کند Lhs بنامیم پارسر رابطه بین Lhs و Top را از جدول استخراج کرده و یکی از اعمال زیر را انجام می‌دهد.
- اگر رابطه Top و Lhs به صورت Top <Lhs باشد پارسرابتدا علامت> * سپس Lhs را وارد انباره می‌کند.
- اگررابطه Top و Lhs به صورت Lhs = Top باشد پارسر فقط Lhs را وارد انباره می‌کند.
- اگر Top و Lhs رابطه‌ای نداشته باشند یک خطای نحوی رخ داده است و بایستی رویه اصلاح خطا فراخوانی شود.
۴-درصورتی‌که عنصر بالای انباره X و ورودی جاری b رابطه‌ای نداشته باشند یک خطای نحوی رخ داده است و بایستی رویه اصلاح خطا فراخوانده شود.
۵-در صورتی که توکن جاری $ و در داخل انباره S) $S علامت شروع گرامر است) باقی‌مانده باشد پارسر پایان موفقیت‌آمیز تجزیه را اعلام می‌کند.
اجرای الگوریتم مثال قبل
| عمل انجام شده | باقی‌مانده ورودی | محتوای انباره |
|---|---|---|
| انتقال | $((c(cc) | $ |
| انتقال | $((c(cc | )>$ |
| کاهش | $((cc) | C>)>$ |
| انتقال | $((cc) | S)>$ |
| انتقال | $((cc | )>S)>$ |
| کاهش | $((c | S<(<c)>$ |
| انتقال | $((c | S<(S)>$ |
| کاهش | $(( | S<(S<c)>$ |
| انتقال | $(( | S<(SS)>$ |
| کاهش | $( | (S<(SS)>$ |
| انتقال | $( | SS)>$ |
| کاهش | $ | (SS)>$ |
| پایان | $ | S$ |
منابع
- "Compiler Construction: Principles and Practice" by Kenneth C. Louden
- درس و کنکور کامپایلر مولفین: حمیدرضا مقسمی و وحید رافع