سلام و وقت بخیر خدمت همراهان وب سایت آموزشی پی وی لرن. با دوره کامل آموزش طراحی کامپایلر در خدمت شما عزیزان خواهیم بود. بررسی تجزیه گر پایین به بالا و طراحی کامپایلر را در این بخش از آموزش نیز ادامه خواهیم داد. با ما همراه باشید.
بررسی تجزیه گر پایین به بالا و طراحی کامپایلر
تجزیه پایین به بالا از گره های برگ یک درخت شروع می شود و تا رسیدن به گره ریشه ، در جهت بالا حرکت می کند. در این روش ، ما از یک جمله شروع می کنیم و سپس قوانین ترکیب را به روش معکوس اعمال می کنیم تا به نماد آغازین برسیم. تصویری که در زیر آورده شده پارسرهای پایین به بالای موجود را نشان می دهد.
بررسی تجزیه گر پایین به بالا و طراحی کامپایلر
روش تجزيه انتقال – كاهش (shift-reduce)
روش تجزيه انتقال – كاهش از دو مرحله منحصر به فرد برای تجزیه پایین به بالا استفاده می کند. این مراحل به عنوان shift-step و reduce-step شناخته می شوند.
مرحله Shift یا انتقال: مرحله انتقال به پیشروی اشاره گر ورودی به نماد ورودی بعدی اشاره دارد که به آن نماد انتقالی گفته می شود. این نماد روی پشته وارد می شود. نماد انتقالی به صورت یک گره واحد یا منفرد از درخت تجزیه است.
مرحله Reduce یا کاهش : وقتی تجزیه کننده یک قانون گرامری کامل (RHS) را پیدا کرد و آن را به (LHS) جایگزین کرد ، به عنوان reduce-step یا گام کاهشی شناخته می شود. این فرایند وقتی اتفاق می افتد که عنصر بالایی پشته حاوی یک دستگیره یا handle باشد. برای کاهش ، یک عملکرد POP روی پشته اجرا می شود که دستگیره را از پشته خارج می کند و آن را با نماد غیر پایانی LHS جایگزین می کند.
تجزیه گر LR یک تجزیه کننده غیر بازگشتی ، shift-reduce (انتقالی-کاهشی) و پایین به بالا است. تجزیه گر LR از کلاس گسترده ای از گرامر مستقل از متن استفاده می کند که آن را به کار آمدترین روش تجزیه نحوی تبدیل می کند. تجزیه گرهای LR همچنین به عنوان تجزیه کننده (LR (k شناخته می شود ، که L مخفف اسکن از چپ به راست (left-to-right) جریان ورودی است. R مخفف ساختار راست ترین اشتقاق به صورت معکوس است و k علامت تعدادی نمادهای رو به جلو برای تصمیم گیری را مشخص می کند.
به طور گسترده سه الگوریتم استفاده شده ، برای ساخت یک تجزیه گر LR موجود است:
(SLR (1 – پارسر LR ساده:
- روی کوچک ترین کلاس گرامر کار می کند.
- تعداد کم وضعیت ها، از این رو جدول بسیار کوچکی دارد.
- ساختار ساده و سریع
(LR (1 – پارسر LR :
- کار بر روی مجموعه کاملی از گرامر (LR (1
- جدول بزرگی ایجاد می کند و تعداد وضعیت ها زیاد است.
- ساخت آهسته دارد.
(LALR (1 – پارسر LR رو به جلو
- روی گرامرهایی با اندازه متوسط کار می کند.
- تعداد وضعیت ها همانند الگوریتم (۱)SLR است.
الگوریتم تجزیه LR
در این جا ما یک الگوریتم ساختمان تجزیه کننده LR را شرح می دهیم:
مثال :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | token = next_token() repeat forever s = top of stack if action[s, token] = “shift si” then PUSH token PUSH si token = next_token() else if action[s, token] = “reduce A::= β“ then POP 2 * |β| symbols s = top of stack PUSH A PUSH goto[s,A] else if action[s, token] = “accept” then return else error() |
مقایسه LL و LR
| LL | LR |
|---|
| اشتقاق چپ ترین | اشتقاق راست ترین را بطور معکوس انجام می دهد. |
| با ریشه غیر پایانی روی پشته شروع می کند. | با ریشه غیر پایانی روی پشته پایان می یابد. |
| وقتی پشته خالی شود به پایان می رسد. | با یک پشته خالی شروع می شود. |
| از پشته برای تعیین این که چه چیزی هنوز باقی مانده است استفاده می کند. | از پشته برای تعیین این که چه چیزی قبلا دیده است استفاده می کند. |
| درخت تجزیه بالا به پایین را می سازد. | درخت تجزیه پایین به بالا را می سازد. |
| به طور مداوم غیر پایانه را از پشته بر می دارد و سمت راست مربوطه را وارد پشته می کند. | سعی می کند طرف راست را روی پشته تشخیص دهد، آن را بردارد و غیر پایانی متناظر را وارد پشته نماید. |
| غیر پایانی ها را گسترش می دهد. | غیر پایانی ها را کاهش می دهد. |
| پایانی ها را می خواند وقتی یک عنصر را از پشته بر می دارد. | پایانی ها را می خواند همزمانی که آن ها را روی پشته وارد می دهد. |
| درخت تجزیه پیمایش پیش ترتیبی دارد. | درخت تجزیه پیمایش پس ترتیبی دارد. |
بررسی تجزیه گر پایین به بالا و طراحی کامپایلر را به پایان می رسانیم.
کلام پایانی
در این بخش از آموزش طراحی کامپایلر با بررسی تجزیه گر پایین به بالا آشنا شدیم. در بخش بعدی به بررسی اصلاح خطا خواهیم پرداخت. با ما همراه باشبد.
فروشگاه
فیلم های آموزشی
کتاب های آموزشی
مقالات آموزشی
وردپرس
