فرادرستجزیه بالا به پایین — طراحی کامپایلر
در بخشهای قبلی این سلسله مطالب راهنما با انواع تکنیکهای تجزیه ساختار نحوی زبان آشنا شدیم و دیدیم که در روش تجزیه بالا به پایین تجزیهکننده یا پارسر شروع به ساخت درخت تجزیه از گره ریشه به تدریج به سمت پایین و گرههای برگ میکند. در این بخش این روش تجزیه را بیشتر توضیح میدهیم. این نوع از تجزیه در تصویر زیر قابل مشاهده است:
تجزیه پایینگرد (Recursive Descent Parsing)
پایینگرد نوعی از تجزیه بالا به پایین است که درخت تجزیه را از بالا شروع به ساخت میکند و ورودی از چپ به راست خوانده میشود. این روش از هر گزاره پایانی و غیر پایانی استفاده میکند. این تکنیک تجزیه به طور بازگشتی ورودی را تجزیه میکند تا یک درخت تجزیه بسازد که ممکن است به پسگرد نیاز داشته باشد. اما گرامر مربوط به آن (اگر فاکتورگیری چپ نشده باشد) نمیتواند از پسگرد اجتناب کند. شکلی از تجزیه پایینگرد که نیازمند پسگرد نباشد به نام تجزیه پیشگو (predictive parsing) نامیده میشود.
این تکنیک تجزیه به این دلیل بازگشتی تلقی میشود که از گرامر مستقل از متن که ماهیتی بازگشتی دارد بهره میگیرد.
پسگردی (Back-tracking)
تجزیهکنندههای بالا به پایین از گره ریشه (نماد آغازین) کار خود را آغاز میکنند و رشته ورودی را با قواعد ترکیب جهت جایگزینی مطابقت میدهند. برای درک این وضعیت به مثال مستقل از متن زیر توجه کنید:
S → rXd | rZd X → oa | ea Z → ai
تجزیهکننده ورودی برای یک رشته ورودی، رفتاری مانند آن چه در ادامه توصیف کردهایم خواهد داشت:
تجزیهکننده از S شروع میکند و با بررسی قواعد ترکیب خروجی را با سمت چپترین حرف ورودی یعنی r مطابقت میدهد. اولین ترکیب (S (S → rXd با آن مطابقت دارد. بنابراین تجزیهکننده بالا به پایین به حرف سمت ورودی بعدی یعنی e پیش میرود. تجزیهکننده تلاش میکند تا X غیر پایانی را بسط دهد و ترکیب آن را از چپ بررسی میکند (X → oa). این عبارت با نماد ورودی بعدی مطابقت ندارد. از این رو تجزیهکننده بالا به پایین پسگرد میکند تا قاعده ترکیب بعدی x یعنی (X → ea) را بیابد. اینک که تجزیهکننده همه حروف ورودی را با روش مرتبی مطابقت داد، رشته پذیرفته میشود.
تجزیهکننده پیشگو
تجزیهکننده پیشگو یک تجزیهکننده پایینگرد است که میتواند پیشگویی کند کدام ترکیب با رشته ورودی جایگزین خواهد شد. تجزیهکننده پیشگو دچار مشکل پسگردی نمیشود.
تجزیهکننده پیشگو برای انجام وظایف خود از اشارهگر رو به جلو استفاده میکند که به نمادهای ورودی بعدی اشاره میکند. برای این که تجزیهکننده دارای پسگردی نباشد، تجزیهکننده پیشگو برخی قیود در مورد گرامر اعمال میکند و تنها دستهای از گرامرها را میپذیرد که به نام گرامر (KK(k نامیده میشوند.
تجزیه پیشگو از پشته و جدول تجزیه برای تجزیه ورودی و تولید درخت تجزیه استفاده میکند. هر دو مورد پشته و ورودی شامل نماد پایانی $ هستند تا نشان دهند که پشته خالی است و ورودی مصرف شده است. تجزیهکننده از جدول تجزیه برای تصمیمگیری در مورد ترکیب ورودی و عناصر پشته استفاده میکند.
در یک تجزیه پایینگرد، تجزیهکننده ممکن است بیش از یک ترکیب برای انتخاب در مورد یک ورودی منفرد داشته باشد؛ در حالی که در تجزیه پیشگو در هر مرحله حداکثر یک ترکیب میتوان انتخاب کرد. ممکن است نمونههایی وجود داشته باشند که برای آن هیچ ترکیبی برای مطابقت با رشته ورودی نباشد و رویه تجزیه شکست بخورد.
تجزیهکننده LL
تجزیهکننده LL گرامر LL را میپذیرد. گرامر LL زیرمجموعهای از گرامر مستقل از متن است؛ اما برخی محدودیتها بر آن اعمال شده تا پیادهسازی سادهتری داشته باشد و میتوان گفت نسخه سادهشدهای از CFG محسوب میشود. گرامر LL را میتوان به کمک هر دو الگوریتم پایینگرد و مطابق جدول پیادهسازی کرد.
تجزیهکننده LL به صورت (LL(k نمایش داده میشود. حرف L نخست در این عبارت به معنی تجزیه از ورودی به صورت چپ به راست (left to right) و حرف L دوم به معنی اشتقاق چپترین (left-most derivation) است. حرف k نیز نشان دهنده تعداد حروفی است که رو به جلو بررسی میشوند. به طور کلی k=1 فرض میشود بنابراین (LL(k را میتوان به صورت (LL(1 نیز نوشت.
الگوریتم تجزیه LL
میتوان از (LL(1 قطعی برای توضیح تجزیه استفاده کرد، چرا که اندازه جدول به طور نمایی نسبت به مقدار k افزایش مییابد. دوما اگر یک گرامر مفروض به صورت (LL(1 باشد، در این صورت به طور معمول برای هیچ مقدار K به صورت (LL(k نیست.
در ادامه الگوریتم تجزیه (LL(1 ارائه شده است:
Input:
string ω
parsing table M for grammar G
Output:
If ω is in L(G) then left-most derivation of ω,
error otherwise.
Initial State : $S on stack (with S being start symbol)
ω$ in the input buffer
SET ip to point the first symbol of ω$.
repeat
let X be the top stack symbol and a the symbol pointed by ip.
if X∈ Vt or $
if X = a
POP X and advance ip.
else
error()
endif
else /* X is non-terminal */
if M[X,a] = X → Y1, Y2,... Yk
POP X
PUSH Yk, Yk-1,... Y1 /* Y1 on top */
Output the production X → Y1, Y2,... Yk
else
error()
endif
endif
until X = $ /* empty stack */
گرامر G در صورتی (LL(1 است که اگر A → α | β باشد در این صورت دو ترکیب متمایز از G وجود داشته باشد که:
- برای غیر پایانی، هر دو α و β رشتههایی داشته باشند که با a شروع شود.
- حداکثر یکی از α و β بتوانند رشتهای خالی به دست دهند.
- اگر β → t در این صورت از α هیچ رشتهای مشتق نشود که دارای a پایانی در (Follow(A باشد.
اگر این نوشته مورد توجه شما قرار گرفته است، پیشنهاد میکنیم موارد زیر را نیز بررسی کنید:
- مجموعه آموزشهای علوم کامپیوتر
- آموزش طراحی کامپایلر
- مجموعه آموزشهای دروس مهندسی کامپیوتر
- آموزش تجزیه انتقال (کاهش) در طراحی کامپایلر
- کامپایلر، طراحی و معماری آن — به زبان ساده
- آموزش طراحی کامپایلر (مرور و حل تست های کنکور کارشناسی ارشد)
==
