پارسر انتقال کاهش
در علوم کامپیوتر، تجزیه انتقال کاهش روش تجزیه‌ای است کارا، پایین به بالا و مبتنی بر جدول که برای زبانهای کامپیوتری و سایر زبانهای فرمال قابل استفاده می‌باشد. رایج‌ترین روش تجزیه امروز روش‌های تجزیه انتقال کاهش هستند. (انواع روش‌های LR) روش‌های تجزیه تقدم نیز که قبل از اختراع LR استفاده می‌شدند از انتقال کاهش بهره می‌بردند. همه پارسرهای انتقال کاهش اثر ظاهری مشابهی به صورت ساخت افزایشی درخت تجزیه یا فراخوانی عمل خروجی خاصی دارند. بررسی ظاهری یک پارسر LR بدون در نظر گرفتن جزییات ریاضی ساخت جدول آن بهترین مثال برای فهمیدن برخی ویژگی‌های عمومی انتقال کاهش است.
درخت تجزیه برای مثال A = B + C * ۲
یک پارسر انتقال کاهش رشته ورودی را بدون بازگشت به عقب در یک راستا خوانده و تجزیه می‌کند. (جهت خواندن معمولاً از چپ به راست در هر خط و از پایین به بالا برای چند خط است) پارسر درخت تجزیه را به مرور از پایین به بالا و از چپ به راست بدون حدس یا بازگشت به عقب تشکیل می‌دهد. پارسر در هر نقطه از مسیر یک لیست از زیر درخت‌ها یا رشته‌های تجزیه شده را ذخیره می‌کند. زیر درخت‌ها تا زمانی که پارسر به به انتهای دست راست عبارت نحوی نرسیده با یکدیگر ترکیب نمی‌شوند.
همانگونه که در قسمت سایه دار موجود در تصویر معلوم است در مرحله هفتم مثال تجزیه، فقط “A = B +” تجزیه شده‌است و هیچ‌یک از گره‌های هشتم به بالا در این مرحله وجود ندارند. گره‌های اول، دوم، ششم و هفتم ریشه زیر درخت‌های پوشش دهنده گره‌های یک تا هفت هستند. گره یک متغیر A، گره دو عملگر =، گره شش جمع وند B و گره هفتم عملگر + است. این چهار گره ریشه موقتاً در یک پشته تجزیه نگهداری می‌شوند. قسمت باقی‌مانده ورودی “C * ۲” است.
همانگونه که از نام پارسر پیداست، این روش تجزیه بر مبنای یک سری عملیات انتقال و کاهش انجام می‌شود.
- عمل انتقال باعث پیشرفت در ورودی شده و همچنین به ایجاد یک گره در درخت می‌انجامد.
- عمل کاهش باعث تأیید درخت جدید ایجاد شده با گرامر و ترکیب زیردرخت‌ها با هم به وسیله یک ریشه جدید می‌شود.
این مراحل تا زمانی که رشته ورودی تمام شود و تمام زیر درخت‌ها به هم متصل شوند و یک درخت کامل با یک گرامر یکسان به وجود آورند توسط پارسر ادامه می‌یابد.
گامهای تجزیه برای مثال A = B + C * ۲
در هر مرحله از تجزیه رشته ورودی به سه قسمت تقسیم می‌شود: پشته تجزیه، نماد فعلی lookahead و متن خوانده نشده. کار بعدی پارسر با توجه به راست‌ترین عنصر پشته و lookahead مشخص می‌شود. کار از جدولی که تمام ترکیبات مجاز عناصر پشته و lookahead را دربردارد خوانده می‌شود.
<tbody>
| مرحله | پشته تجزیه | Look Ahead | اسکن نشده | عمل تجزیه |
|---|---|---|---|---|
| 0 | empty | id | = B + C*۲ | انتقال |
| 1 | id | = | B + C*۲ | انتقال |
| 2 | id = | id | + C*۲ | انتقال |
| 3 | id = id | + | C*۲ | کاهش به وسیله Value ← id |
| 4 | id = Value | + | C*۲ | کاهش به وسیله Products ← Value |
| 5 | id = Products | + | C*۲ | کاهش به وسیله Sums ← Products |
| 6 | id = Sums | + | C*۲ | انتقال |
| 7 | id = Sums + | id | *۲ | انتقال |
| 8 | id = Sums + id | * | 2 | کاهش به وسیله Value ← id |
| 9 | id = Sums + Value | * | 2 | کاهش به وسیله Products ← Value |
| 10 | id = Sums + Products | * | 2 | انتقال |
| 11 | id = Sums + Products * | int | eof | انتقال |
| 12 | id = Sums + Products * int | eof | کاهش به وسیله Value ← int | |
| 13 | id = Sums + Products * Value | eof | کاهش به وسیله Products ← Products * Value | |
| 14 | id = Sums + Products | eof | کاهش به وسیله Sums ← Sums + Products | |
| 15 | id = Sums | eof | کاهش به وسیله Assign ← id = Sums | |
| 16 | Assign | eof | تمام
</tbody> |
گرامری برای مثال
گرامر مجموعه‌ای از الگوها یا قواعد نحوی برای زبان ورودی است که همه قواعد از جمله اندازه اعداد، استفاده مداوم از اسم و تعاریف آن و … را پوشش نمی‌دهد. پارسر انتقال کاهش از یک گرامر مستقل از متن استفاده می‌برد.
گرامر استفاده شده به عنوان مثال یک زیرمجموعه کوچک از دستورها زبان جاوا یا C است:
Assign ← id = Sums Sums ← Sums + Products Sums ← Products Products ← Products * Value Products ← Value Value ← int Value ← id
نماد پایانه‌های این گرامر نمادهایی چندحرفی یا «توکن» هستند که به وسیله یک تحلیلگر لغوی در رشته ورودی قابل شناسایی هستند. مثال فوق شامل *+= و int برای اعداد صحیح و id برای شناسه هاست. گرامر اهمیتی به مقدار int یا نحوه تلفظ id نمی‌دهد، همچنین فاصله، یا افزودن خط جدید نیز برای آن بی‌ارزش است. پارسر از نماد پایانه‌ها بی آنکه آن‌ها را تعریف کند استفاده می‌کند. این نمادها همیشه پایین‌ترین قسمت یک درخت تجزیه هستند.
عناصر با حروف بزرگ همچون Sums نماد غیرپایانه هستند. این نام‌ها برای تعریف مفاهم و الگوهای زبان به کار می‌روند. اینها در گرامر زبان تعریف می‌شوند و هیچ‌گاه در ورودی اتفاق نخواهند افتاد. همیشه در قسمت‌های بالایی درخت تجزیه قرار می‌گیرند و حضور آن‌ها به معنای پذیرفته شدن بعضی از قواعد زبان است. بعضی از پایانه‌ها می‌توانند توسط یک یا چند الگو تعریف شوند. همچنین قواعد می‌توانند به خودشان بازگردند. این گرامرها از قواعد بازگشتی برای پیاده‌سازی برخی عملیات‌های ریاضی استفاده می‌کنند. گرامر زبانهای کامل از قواعد بازگشتی برای پرانتزگذاری، لیست‌ها، عبارات و جملات تو در تو استفاده می‌کنند.
هر زبان کامپیوتری را می‌توان به وسیله چندین گرامر تشریح کرد. یک گرامر برای پارسر انتقال کاهش می‌بایست بی ابهام باشد یا با قواعد اولویت tie-breakingتقویت شده باشد. این بدان معنی است که تنها یک راه صحیح برای تأیید یک رشته موجود در زبان وجود دارد، یک درخت تجزیه از آن می‌توان ترسیم کرد و یک دنباله منحصربه‌فرد از عملیات‌های انتقال کاهش باعث تأیید آن شده‌است.
یک پارسر مبتنی بر جدول دانش خود از گرامر را به صورت اطلاعاتی کد شده و غیرقابل تغییر در قالب جدولی به نام جدول تجزیه ذخیره می‌کند. کد برنامه پارسر در حقیقت یک حلقه تکراری ساده است که گرامرها و زبانهای مختلف را با توجه به این اطلاعات غیرقابل تغییر تأیید می‌کند. برای روش‌های تقدم می‌توان جدول را به راحتی با دست پیاده‌سازی کرد. برای روش LR جدول به وسیله ابزارهای مولد پارسر مثل بیزون به صورت اتوماتیک از گرامر تولید می‌شود. جدول تجزیه معمولاً از گرامرهای زبان بزرگتر است. در پارسرهای دیگر که مبتنی بر جدول نیستند همچون کاهشی بازگشتی هر ساختار زبان به وسیله یک زیربرنامه که مخصوص آن دستور نحوی است تجزیه می‌شود.
فعالیت‌های پارسر
کارایی پارسرهای انتقال کاهش نشات گرفته از عدم وجود عقب‌گرد و بازگشت به عقب است. زمان کل رابطه خطی با اندازه ورودی و اندازه درخت تجزیه کامل شده دارد. اما در پارسرهای دیگر که امکان بازگشت وجود دارد در صورت حدس اشتباه از مرتبه N^2 یا N^3 است.
برای جلوگیری از حدس اشتباه، پارسرهای انتقال کاهش معمولاً قبل از تصمیم‌گیری برای عنصر قبلی خوانده شده معمولاً عنصر بعدی را از ورودی نگاه می‌کنند. تحلیل گر لغوی یک واحد جلوتر از پارسر را پردازش می‌کند. عنصر lookahead دست راست‌ترین قسمت از مطالب تجزیه شده‌است. (بعضی از پارسرها از ۲ یا چند نماد lookahead استفاده می‌کنند)
پارسر انتقال کاهش قبل از ترکیب ساختار به دست آمده صبر می‌کند تا تمام قسمت‌های یک یا چند گرامر خوانده شده و تجزیه شود سپس به ترکیب آن‌ها می‌پردازد. در مثال درخت تجزیه بالا در گامهای سوم تا ششم مادامی که عنصر lookahead مقدار + است، عبارت B ابتدا به Value سپس Products و در آخر به Sums کاهش می‌یابد. تصمیم‌گیری برای B فقط بر اساس آنچه که پارسر و اسکنر مشاهده می‌کنند است بی دغدغه از اینکه انتخاب درست است یا خیر.
کاهش جدیدترین عنصر تجزیه شده بلافاصله قبل از lookahead را شناسایی می‌کنند، از این جهت لیست تجزیه شده‌ها بسیار شبیه به پشته عمل می‌کند. این پشته از سمت راست رشد می‌کند. کف یا پایه پشته قدیمی‌ترین عنصر تجزیه شده یا به عبارتی سمت چپ‌ترین قسمت را نگهداری می‌کند درحالی که هر عمل کاهش بر روی سمت راست‌ترین یا جدیدترین عنصر تجزیه شده اعمال می‌شود.
هنگامی که قواعد یک گرامر شبیه
تأیید می‌شود پشته درخت تجزیه “…. Products * Sums” را در بالاترین قسمت پشته تجزیه نگه می‌دارد. این نمونه پیدا شده از قواعد دست راست را دستگیره گویند. عمل کاهش دستگیره پیدا شده “…. Products * Sums” را با غیرپایانه سمت چپ که همان Large Products است جایگزین می‌کند. اگر پارسر درخت تجزیه را کامل کرد، هر سه درخت داخلی Products و *و Valueرا ترکیب کرده و به ریشه جدیدی متصل می‌کند. به عبارت دیگر جزییات معنایی درخت داخلی Products و Values خروجی برای مسیر دیگر کامپایلر است.
پارسر عملیات‌های کاهش داده شده را تا زمانی که یک گرامر مشابه دیگر پیدا کند در بالای پشته نگهداری می‌کند. هرگاه که دیگر نتوانست عمل کاهش دیگر انجام دهد lookahead را به داخل پشته انتقال می‌دهد، یک lookahead جدید پیدا می‌کند و مجدداً از اول شروع می‌کند.
انواع پارسرهای انتقال کاهش
جدول تجزیه نشان می‌دهد که برای هر lookahead و عنصر اول پشته مجاز در مرحله بعد چگونه باید عمل شود. عمل می‌بایست منحصربه‌فرد باشد، چه کاهش باشد، چه انتقال اما نه هردو. (باعث به وجود آمدن محدودیت‌های بیشر برای جلوگیری از ابهام می‌شود) جدول تفاوت میان انواع مختلف پارسرهای انتقال کاهش را نشان می‌دهد.
در پارسرهای تقدم، دستگیره از مقایسه تقدم اولویت عنصر روی پشته و عنصر lookahead به دست می‌آید. در مثال بالا int و id متعلق به زیردرخت داخلی هستند و با؛ مقایسه می‌شوند. از آنجایی که اولویت هر دو آن‌ها بیشتر از؛ است بنابراین باید به چیزی کاهش یابند که به وسیله؛ دنبال می‌شده‌است. روش‌های متفاوتی از پارسر تقدم وجود دارد که تفاوت آن‌ها در پیدا کردن دستگیره و انتخاب قاعده استفاده شده دارند:
- پارسر تقدم عملگر یک روش عددی ساده که برای عبارات ساده کاربرد دارد نه دستورها نحوی زبان.
- پارسر تقدم ساده از یک جدول بزرگ M x N برای یافتن انتهای راست و چپ استفاده می‌کرد. این روش قادر به پاسخگویی به زبانهای برنامه‌نویسی رایج نیست.
- پارسر تقدم ضعیف از یک جدول تقدم برای پیدا کردن دستگیره سمت راست استفاده می‌کرد. این روش نسبت به تقدم ساده از قدرت بیشتری برخوردار است.
- پارسر تقدم توسعه یافته.
- پارسر تقدم راهکار ترکیبی از SLR ضعیف تر است.
پارسرهای تقدم گرامرهای اندکی را پاسخگو هستند. آن‌ها هنگام تصمیم‌گیری بسیاری از حالات پشته تجزیه را نادیده می‌گیرند. آن‌ها به تمام عبارات مشاهده شده در گرامر توجه نکرده و بیشتر توجه آن‌ها به بالاترین نماد است. تقدم نیازمند شکل و شمایل مشابه در هنگام استفاده و تجزیه است با این حال آن ترکیب بدون در نظر گرفتن متن رخ می‌دهد.
پارسرهای LR با استفاده از انتقال کاهش انعطاف‌پذیری بالاتری دارند و گرامرهای بیشتری را پوشش می‌دهند. پارسرهای LR همچون یک ماشین وضعیت هستند که توابع انتقال آن عمل کاهش یا انتقال است. آن‌ها از یک پشته استفاده می‌کنند که عنصر lookahead را با عمل انتقال به آن می‌فرستند. این پشته به وسیله عمل کاهش مصرف می‌شود. این مکانیسم به پارسر LR اجازه می‌دهد تا به عنوان یک ابرمجموعه پارسرهای تقدم همه گرامرهای مستقل از متن قطعی را در بربگیرد. پارسر LR به صورت کامل توسط Canonical LR پیاده‌سازی شده‌است. پارسرهایLook-Ahead LR و Simple LRبه سادگی پیاده‌سازی می‌شوند تا به حافظه کمی نیازمند باشند.