تجزیه‌کننده ال‌آر ساده
تحلیلگر نحوی اس ال ار یکی از روش‌های تحلیل نحوی پایین به بالا است، در روش تحلیل نحوی پایین به بالا، مراحل تحلیل از عناصر پایانی درون جمله داده شده آغاز و نهایتاً به سر ترم گرامر خاتمه می یابد. روش‌های تحلیل پایین به بالا در اصطلاح روش‌های انتقال-کاهش گفته می‌شود و به‌طور کلی به سه دسته تقسیم می‌شود: پارسینگ تقدم-عملگر، پارسینگ تقدم-ساده و پارسینگ 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 اگر توکن d از ورودی خوانده شود، می‌توان آن را به درون پشته shift داد و به حالت دیگر، I1 رفت. چنان که دیده می‌شود علامت انتظار نقطه به پایان رسیده و این بدان معنی است که در حالت I1، باید عمل کاهش را بر اساس قاعده 3 و به ازای Followهای item سمت چپ یعنی C انجام دهیم و با R3 آن را نمایش می‌دهیم، همچنین عمل شیفت از I0 به I1 بر اساس d را به صورت S1 که 1 نشان دهندهٔ حالت بعدی است.
اما در I0 به جای d ممکن است که a از ورودی خوانده شود، که در این حالت آن را به پشته شیفت داده و به یک حالت جدید I2 انتقال می یابد. حالت I2 به صورت C →.aC در می‌آید، که نقطه نشان دهندهٔ این است که پس از a انتظار دیدن C را داریم، امل برای تشخیص C، براساس قواعد آن، انتظار داریم که یا a یا d در ورودی بخوانیم، پس حالت I2 به صورت زیر است:
اما در حالت I0 درS → .CC اگر C تشخیص داده شود به حات جدید I3 انتقال می یابیم که این را با goto 3 نشان می‌دهیم.(goto برای متغیر میانی استفاده می‌شود) در این حالت در I3 به وضیعتی مانند S → C.C می‌رسیم، یعنی C اول تشخیص داده شده و اکنون دوباره انتظار دیدن C دیگری داریم که برای تشخیص آن دوباره یا انتظار aیاd را بر اساس قواعد C داریم، وضعیت I3 در زیر نشان داده شده‌است:
و اگر در S,I0 تشخیص داده شود می‌توان به وضعیت I4 انتقال یافت (goto 4) ، ودر حالت I4 با دیدن $ عمل پذیرش صورت می‌گیرد:
اکنون نوبت به حالت I2وI3 است تا مشخص کنیم که چه اتفاقی در آن حالت می افتد، در حالت I2، چنانکه دیده می‌شود، انتظار توکن d وجود دارد، در صورتی که این توکن خوانده شود، آن را به درون پشته شیفت داده و به حالت I1 انتقال می‌دهیم، توجه کنید که در حالت به دست آمده، نباید حالات تکراری وجود داشته باشد. اما با دیدن توکن a، پس از shift a به درون پشته، دوباره به همین حالات I2 می‌رسیم و در نهایت با تشخیص C، به یک حالت جدیدI5 تغییر حالت می‌دهیم (goto 5)، حالت I5 به صورت مقابل است و معنی آن کاهش بر اساس قاعده شماره 2 می‌باشد، و به ازایfollow سمت چپ حالت I5 یعنی C عمل R2 را انجام می‌دهیم.
اما در حالت I3 مانند حالت I2 به دیدن d،عمل شیفت و انتقال به I1 صورت می‌گیرد، با دیدن a، عمل شیفت و انتقال به I2 صورت می‌گیردو با دیدن C،انتقال به حالت جدیدی I6 صورت می‌گیرد که به صورت مقابل است:
کل حالات به دست آمده به صورت زیر است:
سپس Followهای S و C را محاسبه کرده و جدول goto و action را رسم می‌کنیم:
منابع[ویرایش]
- http://en.wikipedia.org/wiki/SLR_parser
- کتاب:کامپایلر، مولفین:وحید رافع، حمیدرضامقسمی