موضوع مقاله: تجزیه‌کننده ال‌آر ساده | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # تجزیه‌کننده ال‌آر ساده | مقدمه: تحلیلگر نحوی اس ال ار یکی از روش‌های تحلیل نحوی پایین به بالا است، در روش تحلیل نحوی پایین به بالا، مراحل تحلیل از عناصر پایانی درون جمله داده شده آغاز و نهایتاً به سر ترم گرامر خاتمه می یابد. | ## بخش 1: تجزیه‌کننده ال‌آر ساده | روش‌های تحلیل پایین به بالا در اصطلاح روش‌های انتقال-کاهش گفته می‌شود و به‌طور کلی به سه دسته تقسیم می‌شود: پارسینگ تقدم-عملگر، پارسینگ تقدم-ساده و پارسینگ LR. در این روش ابتدا کلیه حالات را حساب می‌کنند، سپس به هنگام تولید جدول، در جاهایی که عمل کاهش باید صورت بگیرد مثلاً .A→a، در سطر مربوطه به ازای کلیهٔ Followهای A در کل گرامر این عمل صورت می‌گیرد. یعنی به جای اینکه مانند روش (1)LR یا (1)LALR، در هر مرحله Followها را حساب کنیم، آن‌ها را به یکباره و در انتها در کل گرامر حساب می‌کنیم که طبیعتاً ساده‌تر است. از طرفی دیده می‌شود که اگر گرامری (0)LR باشد، حتماً (1)SLR هم است، چون تنها تفاوت به هنگام کاهش است که در (0)LR به ازای همه عناصر این عمل صورت می‌گیرد، اما در (1)SLR فقط به ازای Followهای متغیر میانی است. | ## بخش 2: تجزیه‌کننده ال‌آر ساده | اصول تحلیل پایین به بالا در تحلیل نحوی پایین به بالا از یک پشته استفاده می‌کنند، در تحلیل پایین به بالا، پس از اینکه تحلیلگر نحوی توکن‌ها را دریافت نمود، دو عمل امکان‌پذیر است: الف)توکن دریافت شده از تحلیلگر لغوی را مستقیماً به داخل پشتهpush کند، که به این عمل در اصطلاح عمل انتقال (Shift) گفته می‌شود. ب)با توجه به توکن دریافت شده، عناصر بالای پشته که با سمت راست یکی از قواعد گرامر مطابقت دارند را از بالای پشتهPOP کرده و متغیر میانی سمت چپ قاعدهٔ مذکور را به داخل پشته push کند، به این عمل در اصطلاح عمل کاهش(Reduce) گفته می‌شود. در روش‌های پایین به بالا ابتدا قاعده $S'→S (که S سر ترم گرامر است)را به قاعده اضافه می‌کنند، سپس هر قاعده را شماره‌گذاری می‌کنند،(از صفر)، سپس به هنگام عمل کاهش، بر اساس قاعده‌ای که کاهش صورت گرفته، آن را Ri نمایش می‌دهند که i شماره آن قاعده است. به عبارت دیگر، در تحلیل پایین به بالا، در آغاز کار، تحلیلگر نحوی در انتظار کاهش ورودی یا به عبارت دیگر برنامه مورد کامپایل به S است. | ## بخش 3: تجزیه‌کننده ال‌آر ساده | اما برای تشخیص S، بر اساس قواعد گرامر، انتظار داریم که عناصر دیگری تشخیص داده شود تا پس از Reduce آن‌ها، به S برسیم. این عمل(قرار دادن نقطه و تعیین ترم انتظار)، تا جایی ادامه می یابد که به توکن‌ها برسیم.(یعنی به 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 به صورت زیر است: بی‌قاب اما در حالت 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 انتقال می‌دهیم، توجه کنید که در حالت به دست آمده، نباید حالات تکراری وجود داشته باشد.