تجرینه کننده پایین به بالای ساده (SLR)
تجزیه کننده پایین به باالی ساده (LR Simple) یا به اختصار SLR یک نوع پایه برای تجزیه LR می‌باشد برای حل مشکل برخورد در آتوماتای (0)LR از مجموعه FOLLOW استفاده می‌کند. به طور خالصه، قاعده کاهش α→A را فقط وقتی استفاده می‌کنیم که توکن بعدی در ورودی، عضو (A)FOLLOW باشد.
- اگر بتوان یک گرامر را با این روش تجزیه کرد
به آن گرامر SLR گفته می‌شود.
- گرامرهای SLR زیر مجموعه گرامرهای (1)LR هستند.
- پیچیدگی الگوریتم SLR برابر با پیچیدگی الگوریتم (1)LL می‌باشد.
بطور مثال، برخورد کاهش – انتقال در حالت ۴ در شکل ۴ – ۶ را می‌توان
با در نظر گرفتن مجموعه (T(FOLLOW حل کرد.
- اگر توکن بعدی ضرب (*) یا پرانتز بسته یا $ باشد،
با قاعده id→T کاهش انجام می‌شود.
- ولی اگر توکن بعدی پرانتز باز باشد،
پرانتز باز به پشته منتقل شده و به حالت ۵ می‌رویم.
- اگر توکن بعدی هیچ‌کدام از این چهار مورد نبود،
توکن ورودی نامعتبر بوده و یک خطای تجزیه اعالم می‌کنیم.
- این تصمیمات در یک جدول که به نام جدول پرش (TO GO)و عمل یا
کُنش(Action)معروف است، کد گذاری می‌شود.
- این الگوریتم یک گرامر G و آتوماتای (0)LR متناسب با آن
را بعنوان ورودی دریافت کرده و جدول‌های کنش [a, s[ACTION GOTO[s, A] پرش و برای تمام حالت‌های s و نمادهای پایانی a و نمادهای ناپایانه A را می‌سازد. برای هر حالت s:
- برای هر جزء مانند β a. α→A در حالت s :
انتقال و رفتن به حالت t براساس آتوماتای بنویس ACTION[s, a] خانه در را LR(0)
- برای هر جزء مانند β B. α→A در حالت s:
پرش به حالت t براساس آتوماتای (0)LR را در خانه [B, s[GOTO بنویس
- برای هر جزء مانند . α→A در حالت s :
برای هر نماد پایانی مانند b عضو (A(FOLLOW : کاهش با قاعده α→A را در خانه [b, s[ACTIONبنویس
- تمام خانه‌های جدول که در نهایت خالی باقی می‌مانند، نشانه خطا هستند
تجزیه ورودی با استفاده از الگوریتم تجزیهS تجزیه کننده نیاز به یک پشته برای نگهداری حاالت آتوماتای (0)LR دارد.
- در ابتدا این پشته حاوی حالت شروع S0 می‌باشد.
- هر بار عنصر باالی پشته و توکن بعدی در نظر گرفته شده
و کنش مشخص شده توسط جدول تجزیه SLR انجام می‌شود.
- برای کنش انتقال،
توکن بعدی دریافت شده و حالت بعدی مشخص شده در پشته درج می‌شود.
- برای کنش کاهش با قاعده تولید β→A،
نمادهای عضو β از پشته برداشته شده و با A جایگزین می‌شود، سپس باتوجه به جدول پرش، حالت مشخص شده در خانه [A, t[GOTO در پشته درج می‌شود.
- این فرایند تا زمانی که بطور موفقیت‌آمیز به نماد شروع کاهش داشته باشیم،
یا به یک حالت خطا برسیم، ادامه می‌یابد. فرض کنید که Sیک پشته برای نگهداری حاالت گرامر (0)LR باشد.
- ابتدا حالت صفر (S0 )در پشته درج می‌شود.
- فرض کنید a اولین توکن ورودی باشد.
- حلقه تکرار :
- فرض کنید حالت S اولین عنصر باالی پشته باشد:
- اگر کنش [a, S[ACTION ،پذیرش یا accept باشد:
عمل تجزیه موفقیت‌آمیز خاتمه می‌یابد.
- اگر کنش [a, S[ACTION برابر انتقال به حالت t باشد:
حالت t در پشته درج می‌شود. و توکن بعدی خوانده شده و در a قرار می‌گیرد. اگر کنش [a, S[ACTION ،کاهش با قاعده β→A باشد: نمادهای β و حاالت متناسب با β از پشته برداشته می‌شوند.
- فرض کنید پس از برداشتن حاالت متناظر با β ، عنصر باالی پشته t باشد:
آنگاه حالت بعدی با توجه به پرش [A, t[GOTO در پشته درج می‌شود.
- در غیراینصورت: توقف با اعالم خطا در تجزیه
This article "تجرینه کننده پایین به بالای ساده (SLR)" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:تجرینه کننده پایین به بالای ساده (SLR). Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.
