در این مقاله در مورد تجزیهگر پایین به بالا گفتگو میکنیم.
تجزیهگر پایین به بالا یا جابجایی کاهینه
از برگها شروع میکند و درخت تجزیه را میسازد و به ریشه ختم میشود. تجزیه پایین به بالا بوسیلهی ردیابی اشتقاق راست از معکوس w تلاش میکند تا رشتهی ورودی w را به نماد آغازین یک گرامر محدود کند.
مثلا
دستهبندی تجزیهگرهای پایین به بالا
یک تجزیه جابجایی-کاهینه عمومی تجزیه LR است. L به این معنی که ورودی را از چپ به راست میپوید و R به این معنی که از معکوس اشتقاق راست استفاده میکند.
در اینجا با هر چهار شیوه تجزیه LR به ساخت گراف GOTO از یک گرامر میپردازیم.
تجزیهگر LR(0)
ما به دوتابع نیاز داریم: Closure() و Goto()
گرامر تکمیلی
اگر G یه گرامر با نماد آغازین S باشد آنگاه G' (گرامر تکمیلی G) گرامری با نماد آغازین جدید S' و عبارت تولیدی S' -> S. هدف از افزودن این عبارت تولیدی جدید تشخیص اتمام تجزیه و اعلام پذیرش ورودی است.
گرامر S -> AA را در نظر بگیرید.
A -> aA | b
گرامر تکمیلی گرامر بالا خواهد شد:
S' -> S
S -> AA
A -> aA | b
آیتمهای LR(0)
یک عبارت تولیدی گرامر G با یک نقطه در بخش راست همان عبارت است.
S -> ABC چهار آیتم را حاصل میشود
S -> .ABC
S -> A.BC
S -> AB.C
.S -> ABC
عبارت تولیدی A -> ε فقط یک آیتم A -> .ε را حاصل میکند.
عملیات بستار(Closure)
اگر I یک مجموعه از آیتمهای گرامر G باشد آنگاه closure(I) مجموعهای از آیتمهای ساختهشده از I است که توسط دو قاعده زیر ساخته میشوند.
- ابتدائا همهی آیتمهای I به closure(I) اضافه میشود.
- اگر A -> α.Bβ در closure(I) باشد و B -> γ یک عبارت تولیدی باشد آنگاه آیتم B -> .γ را به I اضافه کن اگر هماکنون نباشد. این قاعده را تا زمانی که هیچ آیتم دیگری را نتوان به closure(I) اضافه کرد ادامه بده.
مثلا
عملیات Goto
برای تابع Goto(I, X) ابتدا با جابجایی نقطه بعد از X به I اضافه کن. سپس عملیات closure را به قدم اول اعمال کن.
ساخت گراف GOTO
- وضعیت I0 - بستار عبارت تکمیلی LR(0) است.
- به کمک I0 تمام مجموعههای آیتمهای LR(0) را به وسیلهی DFA پیدا کن
- DFA حاصله را به جدول LR(0) تبدیل کن
تولید جدول تجزیهی LR(0)
تابع عمل(action) وضعیت I و پایانهی a (یا $ که نماد پایان ورودی است) به عنوان ورودی میگیرد. مقدار ACTION[i, a] میتواند یکی از چهار حالت زیر باشد:
- جابجایی به j، که j خود یک حالت است.
- کاهش A -> β
- پذیرش
- خطا
ما تابع GOTO را گسترش میدهیم. مثلا GOTO[Ii, A] = Ij یعنی حالت i را با پایانهی a به حالت j نگاشت میکند.
مثلا:
گرامر S -> AA را در نظر بگیرید.
A -> aA | b
گرامر تکمیلی گرامر بالا خواهد شد:
S' -> S
S -> AA
A -> aA | b
جدول تجزیه LR(0) برای گراف GOTO بالا خواهد شد:
بخش عمل در جدول شامل همهی پایانههای گرامر میشود در حالی که بخش goto شامل همهی غیرپایانههاست. برای هر حالت گراف goto تمام عملیاتهای goto را در جدول مینویسیم. اگر goto به یک پایانه اعمال شده آن را در بخش action مینویسیم و اگر به یک غیرپایانه اعمال شده در بخش goto در جدول مینویسیم. اگر در اعمال goto در یک عبارت تولیدی کاهش رخ میدهد(مثلا وقتی که نقطه به انتهای عبارت میرسد و بستار دیگری ممکن نیست) آنگاه با نماد Ri نشان میدهیم و اگر جابجایی رخ میدهد Si مینویسیم.
اگر عبارت تولیدی کاهشی است باید زیر تمام پایانههای تجزیهگر LR(0) نوشته شود.
اگر در حالتی نماد آغازین گرامر کاهش یابد، زیر نماد $ پذیرش نوشته میشود.
نکته: اگر در حالتی کاهش و جابجایی یا دو کاهش متفاوت نشان داده شود، گوییم یک برخورد رخ داده است و گرامر LR نیست.
نکته: دو عمل کاهش در یک حالت را برخورد RR مینامند و یک کاهش و یک جابجایی را برخورد SR نامند.
اگر هیچ برخورد SR ویا RR رخ ندهد پس آن گرامر LR(0) است.
نکته: برای تشخیص LR(0) بودن یا نبودن یک گرامر نیازی به رسم جدول نیست. کافیست در گراف goto حالتی یافت که با یک پایانه، دو عمل کاهش یا یک کاهش و یک جابجایی رخ داده باشد که در این صورت گرامر LR(0) نیست. اگر یک جابجایی با یک متغیر رخ دهد برخورد ایجاد نمیشود چون در جدول یکی در بخش action قرار میگیرد و دیگر در بخش action.
اگر قبلا در بیان ثبت نام کرده اید لطفا ابتدا وارد شوید، در غیر این صورت می توانید ثبت نام کنید.