عمل
تجزیه پایین به بالا بصورت عکس اشتقاق
راست انجام میشود چون برنامه مبدا از چپ
به راست پردازش میشود.
انتقال:
توکن
جاری وارد پشته میشود.
همیشه
پس از انتقال اسکنر برای دریافت توکن بعدی
صدا زده میشود.
کاهش:
دستگیره
ای بالای پشته یافت شده و باید عمل کاهش
صورت گیرد.
پس
از عمل کاهش روال تولید کد فراخوانی میشود.
در
تجزیه گر پایین به بالا دو نوع تداخل داریم
انتقال/کاهش
و کاهش/کاهش
برای
تجزیه تقدم عملگر شرایط زیر لازم است:
۱.
قاعده
لاندا نداشته باشیم.
۲.
در
سمت راست هیچ قاعده ای دو متغیر کنار هم
نباشند.
۳.
بین
هر دو متغیر حداکثر یک رابطه تقدم وجود
داشته باشد.
در
تقدم عملگر لزوما تعداد کاهشها برابر با
تعداد قدمهای اشتقاق راست نیست.
اندازه
جدول تقدم عملگر (|T|+1)^2
است.
اگر
دور وجود داشته باشد توابع f
و
g
وجود
ندارند.
در
روش توابع f
g حافظه
نگهداری O(T)
است.
تجزیه
عملگر ممکن است خطا را پیدا نکند(چون
فقط بین پایانه ها رابطه دارد.)
عملگرهایی
که هم یکتایی هستند و هم دودویی باعث
میشوند نشود از این روش استفاده نمود.
شروط
تقدم ساده:
۱.
نباید
قاعده لاندا داشته باشد.
۲.
سمت
راست هیچ دو قاعده ای نباید مانند هم باشد.
۳.
بین
هر دو نماد یا علامت حداکثر یک رابطه وجود
داشته باشد.
در
تقدم ساده رابطه top>
lhs امکان
ندارد.
اندازه
جدول تقدم ساده (V+T+1)^2
است.
اگر
بازگشتی چپ در تقدم ساده وجود داشته باشد
ممکن است مشکل ایجاد شود.
اندازه
جدول LR
برابر
تعداد حالات *
)V+T+1) است.
در
SLR
تداخل
s/r
وقتی
پیش میاد که follow
قانونی
که reduce
داره
با first
تیکه
ای که میخواد شیفت بخوره اشتراک داشته
باشه و وقتی r/r
پیش
میاد که دو یا بیشتر دستگیره پیدا بشه.
مجموعه
پیشبینی CLR(1)
از
رفتن از یک حالت به حالت دیگه عوض نمیشه.
و
فقط موقعیت نقطه عوض میشه.
SLR
و
LALR
و
CLR
در
تشخیص خطا دقت خوبی دارند و در محل وقوع
خطا هیچ انتقال اضافی انجام نمیدهند و
CLR
هیچ
کاهش اضافی هم ندارد.
سرعت
به ترتیب توی CLR
بعد
تو LALR
و
بعد تو SLR
بیشتره
اندازه
جدول SLR
و
LALR
برابر
است اما تعداد کاهش های SLR
احتمالا
بیشتر است و در نتیجه تعداد خانه های خطای
LALR
احتمالا
بیشتره و بخش goto
و
انتقالهای بخش action
جفتشون
یکیه.
اگر
گرامری CLR
باشه
ولی LALR
نباشه
در تجزیه LALR
فقط
تداخل r/r
داره.(s/r
ندارد!)
گرامر
SLR
و
LALR
و
CLR
باید
غیر مبهم باشد و گرامر مبهم حتما تداخل
دارد و نوع تداخل در هر سه جدول بالا یکسان
است.
اما
از گرامرهای مبهم استفاده میکنند چون
تعداد مراحل اشتقاقشون کمتره.
خانواده
زبانهای مستقل از متن قطعی با خانواده
زبانهای LR(1)
برابر
است!
برای
هر LR(K)
یک
LR(1)
معادل
وجود دارد!
در
تقدم عملگر اگر تقدم عملگرهای a
, b مساوی
بود و عملگرها شرکتپذیری چپ داشته باشند
قرار میدهیم a>b
و
b>a
چیزهایی
که باید از کتاب خوانده شود:
first
term/last term. رابطه
کوچکتر بزرگتری در تقدم عملگر.
الگوریتم
تقدم عملگر.توابع
f
و
g.
روال
اصلاح خطا در تقدم ساده.
Head و
Tail.
الگوریتم
تقدم ساده.
SLR(1). LR(0) . استفاده
از گرامرهای مبهم و برطرف کردن تداخلها
با استفاده از اولویت.
شکل
معروف شمول LL(k)
و
LR(k)
ها
که رابطه اونها رو با هم نشون میده.
کشف
و برخورد با خطا در LR
ها!
هیچ نظری موجود نیست:
ارسال یک نظر