تجزیه‌کننده ال‌آر ساده

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

تحلیلگر نحوی اس ال ار یکی از روش های تحلیل نحوی پایین به بالا است ،در روش تحلیل نحوی پایین به بالا، مراحل تحلیل از عناصر پایانی درون جمله داده شده آغاز و نهایتاً به سر ترم گرامر خاتمه می یابد.روش های تحلیل پایین به بالا در اصطلاح روش های انتقال-کاهش گفته می شود و به طور کلی به سه دسته تقسیم می شود:پارسینگ تقدم-عملگر،پارسینگ تقدم-ساده و پارسینگ LR.که روش LR نیز خود به سه دسته CLR, تجزیه کننده ال‌ای‌ال‌آر, SLR تقسیم می شوند.

روش (1)SLR[ویرایش]

روش (1)SLR یا(1) Simple LR یکی دیگر از روش های پایین به بالاست که پیاده سازی آن بسیار ساده است،البته نسبت به روش های(1)LR و (1)LALR محدودتر است.در این روش ابتدا کلیه حالات را حساب می کنند، سپس به هنگام تولید جدول ، در جاهایی که عمل کاهش باید صورت بگیرد مثلاً .A→a، درسطر مربوطه به ازای کلیه ی Follow های A در کل گرامر این عمل صورت می گیرد . یعنی به جای اینکه مانند روش (1)LR یا (1)LALR ، در هرمرحلهFollow ها را حساب کنیم، آن ها را به یکباره و در انتها در کل گرامر حساب می کنیم که طبیعتاً ساده تر است.البته چون عمل کاهش را به ازای کل Follow های متغییر سمت چپ قاعده انجام می دهیم،لذا نسبت به روش LR وLALR ، احتمال بروز خطا بیشتر است. از طرفی دیده می شود که اگر گرامری (0)LR باشد، حتماً (1)SLR هم است، چون تنها تفاوت به هنگام کاهش است که در (0)LR به ازای همه عناصر این عمل صورت می گیرد،اما در (1)SLR فقط به ازای Follow های متغییر میانی است.

اصول تحلیل پایین به بالا[ویرایش]

در تحلیل نحوی پایین به بالا از یک پشته استفاده می کنند،در تحلیل پایین به بالا،پس از اینکه تحلیلگر نحوی توکنها را دریافت نمود،دو عمل امکان پذیر است:

الف)توکن دریافت شده از تحلیلگر لغوی را مستقیماً به داخل پشتهpush کند،که به این عمل در اصطلاح عمل انتقال (Shift) گفته می شود.

ب)با توجه به توکن دریافت شده،عناصر بالای پشته که با سمت راست یکی از قواعد گرامر مطابقت دارند را از بالای پشتهPOP کرده ومتغییر میانی سمت چپ قاعدۀ مذکور را به داخل پشته push کند،به این عمل در اصطلاح عمل کاهش(Reduce) گفته می شود.

در روشهای پایین به بالا ابتدا قاعده $S'→S (که S سر ترم گرامر است)را به قاعده اضافه می کنند،سپس هر قاعده را شماره گذاری می کنند،(از صفر)، سپس به هنگام عمل کاهش،بر اساس قاعده ای که کاهش صورت گرفته،آن را Ri نمایش می دهند که i شماره آن قاعده است.معمولاً برای نمایش shift نیز به اختصار از Si استفاده می شود.

مثال[ویرایش]

می خواهیم نشان دهیم گرامر زیر (1)SLR است.

S’→S$
S → CC
C → aC
C → d

ابتدا قواعد رااز 0 شماره گذاری می کنیم.

0)S’→S$
1)S → CC
2)C → aC
3)C → d

در ابتدا همیشه انتظار داریم که سر ترم و بعد از آن علامت $ دیده شود.به عبارت دیگر،در تحلیل پایین به بالا، در آغاز کار،تحلیلگر نحوی در انتظار کاهش ورودی یا به عبارت دیگر برنامه مورد کامپایل به S است.این وضعیت انتظار را به صورت $S'→.S نشان می دهند که علامت . نشان دهنده ترم مورد انتظار است.اما برای تشخیص S،بر اساس قواعد گرامر،انتظار داریم که عناصر دیگری تشخیص داده شود تا پس از Reduce آن ها،به S برسیم.در این مثال برای تشخیص (انتظار S)،بر اساس قاعده ی S → CC،انتظار دیدن C را به شکل S → .CC داریم و برای تشخیص C انتطار داریم یا براساس
C →.aCدیده شود یا بر اساس C →.d ، انتطار d را داریم.این عمل(قرار دادن نقطه و تعیین ترم انتظار)،تا جایی ادامه می یابد که به توکن ها برسیم.(یعنی به a و d برسیم)این مورد را می توان به صورت یک حالت موسوم به I0 نشان داد:

I0

در حالت I0 اگر توکن d از ورودی خوانده شود، می توان آن را به درون پشته shift داد و به حالت دیگر ، I1 رفت.چنان که دیده می شود علامت انتظار نقطه به پایان رسیده و این بدان معنی است که در حالت I1، باید عمل کاهش را بر اساس قاعده 3 و به ازای Follow های item سمت چپ یعنی C انجام دهیم وبا R3 آن را نمایش می دهیم، همچنین عمل شیفت از I0 به I1 بر اساس d را به صورت S1 که 1 نشان دهنده ی حالت بعدی است.

I1

اما در I0 به جای d ممکن است که a از ورودی خوانده شود، که در این حالت آن را به پشته شیفت داده و به یک حالت جدید I2 انتقال می یابد.حالت I2 به صورت C →.aC در می آید،که نقطه نشان دهنده ی این است که پس از a انتظار دیدن C را داریم، امل برای تشخیص C، براساس قواعد آن،انتظار داریم که یا a ویا d در ورودی بخوانیم،پس حالت I2 به صورت زیر است:

HI2.PNG

اما در حالت I0 درS → .CC اگر C تشخیص داده شود به حات جدید I3 انتقال می یابیم که این را با goto 3 نشان می دهیم.(goto برای متغییر میانی استفاده می شود) در این حالت در I3 به وضیعتی مانند S → C.C می رسیم،یعنی C اول تشخیص داده شده و اکنون دوباره انتظار دیدن C دیگری داریم که برای تشخیص آن دوباره یا انتظار aیاd را بر اساس قواعد C داریم،وضعیت I3 در زیر نشان داده شده است:

I3PNG.PNG

و اگر در S,I0 تشخیص داده شود می توان به وضعیت I4 انتقال یافت (goto 4) ،ودر حالت I4 با دیدن $ عمل پذیرش صورت می گیرد:

I4PNG.PNG

اکنون نوبت به حالت I2وI3 است تا مشخص کنیم که چه اتفاقی در آن حالت می افتد،در حالت I2،چنانکه دیده میشود،انتظار توکن d وجود دارد، در صورتی که این توکن خوانده شود ،آن را به درون پشته شیفت داده و به حالت I1 انتقال می دهیم، توجه کنید که در حالت به دست آمده ،نباید حالات تکراری وجود داشته باشد.اما با دیدن توکن a، پس از shift a به درون پشته ،دوباره به همین حالات I2 می رسیم و در نهایت با تشخیص C، به یک حالت جدیدI5 تغییر حالت می دهیم (goto 5)،حالت I5 به صورت مقابل است و معنی آن کاهش بر اساس قاعده شماره 2 می باشد، و به ازایfollow سمت چپ حالت I5 یعنی C عمل R2 را انجام می دهیم.

I5.PNG

اما در حالت I3 مانند حالت I2 به دیدن d،عمل شیفت وانتقال به I1 صورت می گیرد،با دیدن a، عمل شیفت و انتقال به I2 صورت می گیردوبا دیدن C،انتقال به حالت جدیدی I6 صورت می گیرد که به صورت مقابل است: I6.PNG I3PNG.PNG


کل حالات به دست آمده به صورت زیر است:

حالات

سپس Follow های S و C را محاسبه کرده و جدول goto و action را رسم می کنیم:

Follow(S)={$}
Follow(C)={d,a,$}

جدول

منابع[ویرایش]