سلام و وقت بخیر خدمت همراهان وب سایت آموزشی پی وی لرن. با دوره کامل آموزش طراحی کامپایلر در خدمت شما عزیزان خواهیم بود. در این بخش به بررسی تجزیه گر بالا به پایین در طراحی کامپایلر می پردازیم. در این راستا به مواردی چون تجزیه‌کننده کاهشی بازگشتی (Recursive descent parser) ، ردیابی عقبگرد (Back-tracking) ، پارسر پیشگویانه ، الگوریتم تجزیه LL و پارسر LL می پردازیم. با ادامه ی آموزش ها با ما همراه باشید.
بررسی تجزیه گر بالا به پایین در طراحی کامپایلر
در بخش قبلی با انواع تکنیک های تجزیه ی ساختار نحوی آشنا شدیم و دیدیم که در تکنیک تجزیه بالا به پایین ورودی را تجزیه می کند و تجزیه کننده شروع به ساختن یک درخت تجزیه از گره ریشه می کند که به تدریج به سمت گره های برگ حرکت می کند. انواع تجزیه بالا به پایین در زیر نشان داده شده است:
بررسی تجزیه بالا به پایین در طراحی کامپایلر
تجزیه‌کننده کاهشی بازگشتی یا پایین گرد (Recursive descent parser)
تجزیه کاهشی بازگشتی یک روش تجزیه بالا به پایین است که درخت تجزیه را از بالا ساخته و ورودی از چپ به راست خوانده می شود. این روش ها برای هر موجودیت پایانی و غیر پایانی استفاده می شود. این تکنیک تجزیه به صورت بازگشتی ورودی را تجزیه می کند تا یک درخت تجریه ایجاد کند ، که ممکن است نیاز به پس گرد (back-tracking) داشته باشد. اما گرامر مرتبط با آن (اگر فاكتورگیری چپ نشده باشد) نمی تواند از پس گرد جلوگیری كند. نوعی از تجزیه پایین گرد که نیازی به پس گرد ندارد ، به عنوان تجزیه پیشگو (predictive) شناخته می شود.
این تکنیک تجزیه به عنوان بازگشتی در نظر گرفته می شود زیرا از گرامر مستقل از متن استفاده می کند که ماهیتی بازگشتی است.
ردیابی پس گردی (Back-tracking)
تجزیه گرهای بالا به پایین از گره ریشه (نماد شروع) کار را شروع می کنند و رشته ی ورودی را با قوانین ترکیب برای جایگزینی مطابقت می دهند. برای درک این موضوع ، مثال (مستقل از متن) CFG زیر را در نظر بگیرید:
مثال :
| S → rXd | rZd X → oa | ea Z → ai |
تجزیه کننده ورودی برای یک رشته ی ورودی، این گونه رفتار خواهد کرد:
تجزیه کننده از S شروع می کند و با بررسی قواعد ترکیب، خروجی را با چپ ترین حرف ورودی بعدی یعنی “r” مطابقت می دهد. اولین ترکیبد (S (S → rXd با آن مطابقت دارد. بنابراین تجزیه کننده بالا به پایین به سمت حرف ورودی بعدی (یعنی “e”) پیش می رود. تجزیه گر سعی دارد X غیر پایانی را بسط داده و ترکیب آن را از سمت چپ (X->oa) بررسی کند. این عبارت با نماد ورودی بعدی مطابقت ندارد. بنابراین تجزیه کننده بالا به پایین برای به دست آوردن قانون ترکیب بعدی (X ، (X →ea پس گرد می کند. (backtrack).
اکنون که تجزیه کننده تمام حروف ورودی را به شکلی مرتب شده مطابقت داده. رشته پذیرفته شده است.
ردیابی عقبگرد (Back-tracking)
بررسی تجزیه بالا به پایین در طراحی کامپایلر
پارسر پیشگو (Predictive Parser)
تجزیه گر پیشگو یک تجزیه کننده کاهشی بازگشتی یا پایین گرد (Recursive descent parser) است ، که قابلیت پیشگویی این که کدام ترکیب برای استفاده با رشته ورودی جایگزین خواهد شد. تجزیه کننده پیشگو از پس گردی backtracking رنج نمی برد.
برای انجام وظایف خود ، تجزیه گر پیشگو از یک اشاره گر رو به جلو (look-ahead) استفاده می کند ، که به نمادهای ورودی بعدی اشاره دارد. برای این که تجزیه کننده دارای پس گردی نباشد ، تجزیه گر پیشگو برخی محدودیت ها را بر روی گرامر قرار می دهد و فقط یک کلاس از گرامر معروف به (LL (k گرامر را می پذیرد.
بررسی تجزیه بالا به پایین در طراحی کامپایلر – پارسر پیشگویانه (Predictive Parser)
تجزیه ی پیشگو از یک پشته و یک جدول تجزیه برای تجزیه ورودی و تولید یک درخت تجزیه استفاده می کند. هر دو پشته و ورودی حاوی نماد پایانی $ هستند که نشان می دهد پشته خالی می باشد و ورودی مصرف شده است. تجزیه کننده برای تصمیم گیری در مورد ترکیب عنصر ورودی و پشته ، از جدول تجزیه استفاده می کند.
بررسی تجزیه بالا به پایین در طراحی کامپایلر – پارسر پیشگویانه (Predictive Parser)
در تجزیه کاهشی بازگشتی یا پایین گرد (Recursive descent parser) ، تجزیه كننده ممكن است بیش از انتخاب در مورد یک ورودی منفرد داشته باشد ، در حالی كه در تجزیه كننده پیشگو، در هر مرحله حداكثر یك ترکیب را می توان انتخاب نمود. ممکن است مواردی وجود داشته باشد که هیچ ترکیبی مطابق با رشته ورودی وجود نداشته باشد ، و این امر باعث می شود که رویه تجزیه fail یا شکست بخورد.
پارسر LL
یک پارسر یا تجزیه گر LL گرامر LL را می پذیرد. گرامر LL زیر مجموعه ای از گرامر مستقل از متن است اما محدودیت هایی برای آن اعمال شده است تا پیاده سازی ساده تری داشته باشد و می توان گفت نسخه ی ساده شده ای از CFG محسوب می شود. گرامر LL می تواند با استفاده از هر دو الگوریتم یعنی کاهشی بازگشتی یا پایین گرد (Recursive descent parser) یا مطابق جدول پیاده سازی کرد.
تجزیه گر LL به صورت (LL (k مشخص شده است. L در LL اول (k) ورودی را از چپ به راست تجزیه می کند، L دوم در (LL (k برای اشتقاق از چپ است و k خودش نشان دهنده ی تعداد حروفی می باشد که رو به جلو بررسی می شوند. به طور کلی فرض می شود k = 1 ، بنابراین (LL (k نیز ممکن است به صورت (LL (1 نوشته شود.
بررسی تجزیه گر بالا به پایین در طراحی کامپایلر – پارسر LL
با بررسی تجزیه گر بالا به پایین در طراحی کامپایلر همراهیم.
الگوریتم تجزیه LL
ممکن است برای توضیح تجزیه از (LL (1 قطعی استفاده نمود، زیرا اندازه جدول بصورت نمایی با مقدار k رشد می کند. ثانیا ، اگر یک گرامر معین (LL (1 باشد، پس معمولاً ، برای هیچ مقدار k به صورت (LL (k نیست.
برای درک بیش تر مطالب مربوطه در ادامه یک الگوریتم تجزیه (LL (1 آورده شده است به این الگوریتم توجه نمایید:
مثال :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | 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 باشد.
مبحث بررسی تجزیه گر بالا به پایین در طراحی کامپایلر را در این جا به پایان می رسانیم.
کلام پایانی
امیدواریم تا این بخش از مباحث مربوط به آموزش طراحی کامپایلر مفید واقع شده باشد. در این بخش از آموزش طراحی کامپایلر به بررسی تجزیه گر بالا به پایین در طراحی کامپایلر پرداختیم و با مباحثی چون تجزیه‌کننده کاهشی بازگشتی (Recursive descent parser) ، ردیابی عقبگرد (Back-tracking) ، پارسر پیشگویانه ، الگوریتم تجزیه LL و پارسر LL آشنا شدیم. در جلسه آینده به بررسی تجزیه پایین به بالا می پردازیم. با وب سایت آموزشی پی وی لرن همراه باشید.
فروشگاه
فیلم های آموزشی
کتاب های آموزشی
مقالات آموزشی
وردپرس
