تجزیه اولویت ساده

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در علوم کامپیوتر تجزیه اولویت ساده یک نوع تجزیه کننده پایین به بالا برای گرامر مستقل از متن است که در آن فقط از گرامر اولویت ساده استفاده میشود.

ارتباط با تجزیه کننده عملگر اولویت[ویرایش]

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

به عنوان نمونه در اینجا وجود غیرپایانه های مجاور درسمت راست قواعد مجاز است لیکن مانند حالت قبل وجود قواعد اپسیلون مجاز نیست. ازآنجا که در تجزیه اولویت ساده برخلاف روش تجزیه‌کننده عملگر اولویت بین غیر پایانه ها تمایز قائل می شویم در اینجا یک محدودیت جدید داریم که سمت راست هیچ دو قاعده ای نباید یکسان باشد. زیرا درغیراینصورت در بعضی از قدمها تداخل کاهش/کاهش پیش خواهد آمد. البته این محدودیت چندان مهمی نیست. درهردومورداین روشها یک محدودیت مشترک وجود دارد که در خانه های جدول تجزیه بایستی حداکثر یک رابطه تقدم وجود داشته باشد. در 'تجزیه اولویت ساده هم برای هدایت عملیات از روابط سه گانه تقدم شامل \lessdot , \dot = و \gtrdot استفاده می شود. البته در روش تقدم ساده این روابط بین کلیه علائم گرامر(پایانه و غیرپایانه و$) تعریف می شود. جدول تجزیه تقدم ساده یک جدول مربع است که به تعداد حاصل جمع تعداد پایانه های گرامر بعلاوه یک (به خاطر علامت $) سطر و ستون دارد.

توابع 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
  • درس و کنکور کامپایلر مولفین: حمیدرضا مقسمی و وحید رافع