گرامر اس‌ال‌آر
در علوم کامپیوتر گرامرهای SLR کلاسی از گرامرهای رسمی هستندکه توسط پارسرهای LR ساده پذیرفته می‌شوند. همه گرامرهای (LR(0 زیر مجموعه گرامرهای SLR هستند و گرامرهای SLRزیر مجموعه همه گرامرهای (LALR(1 و (LR(1 هستند. وقتی که پردازش با پارسر SLR تمام شد گرامر SLR به جدول تجزیه تبدیل می‌شود که هیچ‌کدام از اختلالات کاهش-کاهش یا کاهش- انتقال را برای هیچ یک از ترکیبات حالتهای تجزیه کننده (LR(0 و سیمبل lookahead مورد نظر ندارد. اگر گرامر SLR نباشد جدول تجزیه اختلالات کاهش-کاهش یا انتقال-کاهش را برای تعدادی از حالت‌ها و سیمبل‌های lookahead دارد.
تجزیه کننده نمی‌تواند تصمیم بگیرد که انتقال انجام دهد یا کاهش یا از بین کاندیدای کاهش کدام را انجام دهد. پارسر SLR با استفاده از محاسبه (FOLLOW(A سیمبل‌های lookahead مورد نظر را برای هر متغیر کامل شده انتخاب می‌کند. گرامری که مبهم باشد با هر روشی از تجزیه LR اختلالات کاهش-کاهش یا انتقال-کاهش را خواهد داشت. یک راه مرسوم برای گرامرهای زبان ماشین مبهم این است که برخی از متغیرها هم بازگشتی چپ داشته باشد هم بازگشتی راست:
- Expr → Expr * Val
- Expr → Val + Expr
- Expr → Val
تعریف ویرایش
قانون .B → y در داخل یک حالت از ماشین (SLR(1 گفته می‌شود غیرقابل کاهش یا در حالت کاهش یافته‌است زیرا گسترشش کامل شده و با هر تابع انتقالی نمی‌تواند به جایی برود. قوانین در این حالت یک نقطه دارند که نشان دهنده موقعیت lookahead فعلی است که تعیین کننده سمت راست‌ترین پایان از RHS می‌باشد.
قوانین ویرایش
گرامری را (SLR(1 می‌گویند اگر و تنها اگر برای هر حالت s هیج یک از قوانین زیر نقض نشود:
۱. برای هر کاهش قانون A → a.Xb در حالت s (جایی که X هر ترمینالی باشد) نباید چند قانون کاهش وجود داشته باشد. .B → a در حالت s به طوری که مجموعه(FOLLOE(B شامل ترمینال X باشد. در اصطلاح رسمی تر اشتراک مجموعه حاوی ترمینال X و محموعه (FOLLOW(B تهی باشد. قانون اختلالات -انتقال-کاهش نقش می‌شود.
۲. برای هر دو قانون .A → a و .B → b اشتراک مجموعه (FOLLOW(A و (FOLLOW(B تهی باشد. قانون اختلالات کاهش-کاهش نقض می‌شود.
الگوریتم تجزیه ویرایش
به گرامری (SLR(1 می‌گوییم اگر در پیروی از نتایج LR ساده هیچ ابهامی وجود نداشته باشد.
۱. اگر حالت s شامل هر تعدادی item از فرم A -> a.Xb اگر X یک ترمینال و token بعدی از رشته ورودی باشد، token ورودی فعلی به پشته انتقال داده می‌شود و حالتی که A -> a.Xb در آن قرار دارد هم در پشته قرار داده می‌شود.
۲. اگر حالت s شامل آیتم کامل شده .A -> y و token بعدی از رشته ورودی هم در(FOLLOW(A وجود داشته باشد، سپس عمل کاهش توسط قانون A -> .y انجام می‌شود. کاهش توسط قانون S' -> S اگر s حالت شروع کننده باشد، به معنای پذیرش است. این حالت تنها زمانی اتفاق می‌افتد که تنها token باقی مانده از رشته ورودی علامت $ باشئ. در موارد دیگر حالت جدید توسط FOLLOW محاسبه می‌شود. حذف شروع y و همهٔ حالتهای مرتبط با آن از پشته تجزیه.
۳. در صورتی که token بعدی از رشته ورودی به گونه‌ای باشد که با دو مورد بالا اجرا نشود، خطا اعلام بشود.
همچنین ببینید ویرایش
منابع ویرایش
- "Compiler Construction: Principles and Practice" by Kenneth C. Louden.