موضوع مقاله: پارسر انتقال کاهش | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # پارسر انتقال کاهش | مقدمه: در علوم کامپیوتر، تجزیه انتقال کاهش روش تجزیه‌ای است کارا، پایین به بالا و مبتنی بر جدول که برای زبانهای کامپیوتری و سایر زبانهای فرمال قابل استفاده می‌باشد. | ## بخش 1: پارسر انتقال کاهش | (انواع روش‌های LR) روش‌های تجزیه تقدم نیز که قبل از اختراع LR استفاده می‌شدند از انتقال کاهش بهره می‌بردند. همه پارسرهای انتقال کاهش اثر ظاهری مشابهی به صورت ساخت افزایشی درخت تجزیه یا فراخوانی عمل خروجی خاصی دارند. بررسی ظاهری یک پارسر LR بدون در نظر گرفتن جزییات ریاضی ساخت جدول آن بهترین مثال برای فهمیدن برخی ویژگی‌های عمومی انتقال کاهش است. درخت تجزیه برای مثال A = B + C * ۲ یک پارسر انتقال کاهش رشته ورودی را بدون بازگشت به عقب در یک راستا خوانده و تجزیه می‌کند. (جهت خواندن معمولاً از چپ به راست در هر خط و از پایین به بالا برای چند خط است) پارسر درخت تجزیه را به مرور از پایین به بالا و از چپ به راست بدون حدس یا بازگشت به عقب تشکیل می‌دهد. پارسر در هر نقطه از مسیر یک لیست از زیر درخت‌ها یا رشته‌های تجزیه شده را ذخیره می‌کند. گره‌های اول، دوم، ششم و هفتم ریشه زیر درخت‌های پوشش دهنده گره‌های یک تا هفت هستند. همانگونه که از نام پارسر پیداست، این روش تجزیه بر مبنای یک سری عملیات انتقال و کاهش انجام می‌شود. عمل کاهش باعث تأیید درخت جدید ایجاد شده با گرامر و ترکیب زیردرخت‌ها با هم به وسیله یک ریشه جدید می‌شود. این مراحل تا زمانی که رشته ورودی تمام شود و تمام زیر درخت‌ها به هم متصل شوند و یک درخت کامل با یک گرامر یکسان به وجود آورند توسط پارسر ادامه می‌یابد. گرامر اهمیتی به مقدار int یا نحوه تلفظ id نمی‌دهد، همچنین فاصله، یا افزودن خط جدید نیز برای آن بی‌ارزش است. همیشه در قسمت‌های بالایی درخت تجزیه قرار می‌گیرند و حضور آن‌ها به معنای پذیرفته شدن بعضی از قواعد زبان است. | ## بخش 2: پارسر انتقال کاهش | این گرامرها از قواعد بازگشتی برای پیاده‌سازی برخی عملیات‌های ریاضی استفاده می‌کنند. گرامر زبان‌های کامل از قواعد بازگشتی برای پرانتزگذاری، لیست‌ها، عبارات و جملات تو در تو استفاده می‌کنند. این بدان معنی است که تنها یک راه صحیح برای تأیید یک رشته موجود در زبان وجود دارد، یک درخت تجزیه از آن می‌توان ترسیم کرد و یک دنباله منحصربه‌فرد از عملیات‌های انتقال کاهش باعث تأیید آن شده‌است. یک پارسر مبتنی بر جدول دانش خود از گرامر را به صورت اطلاعاتی کد شده و غیرقابل تغییر در قالب جدولی به نام جدول تجزیه ذخیره می‌کند. کد برنامه پارسر در حقیقت یک حلقه تکراری ساده است که گرامرها و زبان‌های مختلف را با توجه به این اطلاعات غیرقابل تغییر تأیید می‌کند. برای روش LR جدول به وسیله ابزارهای مولد پارسر مثل بیزون به صورت اتوماتیک از گرامر تولید می‌شود. در پارسرهای دیگر که مبتنی بر جدول نیستند همچون کاهشی بازگشتی هر ساختار زبان به وسیله یک زیربرنامه که مخصوص آن دستور نحوی است تجزیه می‌شود. فعالیت‌های پارسر کارایی پارسرهای انتقال کاهش نشات گرفته از عدم وجود عقب‌گرد و بازگشت به عقب است. اما در پارسرهای دیگر که امکان بازگشت وجود دارد در صورت حدس اشتباه از مرتبه N^2 یا N^3 است. برای جلوگیری از حدس اشتباه، پارسرهای انتقال کاهش معمولاً قبل از تصمیم‌گیری برای عنصر قبلی خوانده شده معمولاً عنصر بعدی را از ورودی نگاه می‌کنند. (بعضی از پارسرها از ۲ یا چند نماد lookahead استفاده می‌کنند) پارسر انتقال کاهش قبل از ترکیب ساختار به دست آمده صبر می‌کند تا تمام قسمت‌های یک یا چند گرامر خوانده شده و تجزیه شود سپس به ترکیب آن‌ها می‌پردازد. تصمیم‌گیری برای B فقط بر اساس آنچه که پارسر و اسکنر مشاهده می‌کنند است بی دغدغه از اینکه انتخاب درست است یا خیر. | ## بخش 3: پارسر انتقال کاهش | کاهش جدیدترین عنصر تجزیه شده بلافاصله قبل از lookahead را شناسایی می‌کنند، از این جهت لیست تجزیه شده‌ها بسیار شبیه به پشته عمل می‌کند. کف یا پایه پشته قدیمی‌ترین عنصر تجزیه شده یا به عبارتی سمت چپ‌ترین قسمت را نگهداری می‌کند درحالی که هر عمل کاهش بر روی سمت راست‌ترین یا جدیدترین عنصر تجزیه شده اعمال می‌شود. پارسر عملیات‌های کاهش داده شده را تا زمانی که یک گرامر مشابه دیگر پیدا کند در بالای پشته نگهداری می‌کند. انواع پارسرهای انتقال کاهش جدول تجزیه نشان می‌دهد که برای هر lookahead و عنصر اول پشته مجاز در مرحله بعد چگونه باید عمل شود. (باعث به وجود آمدن محدودیت‌های بیشر برای جلوگیری از ابهام می‌شود) جدول تفاوت میان انواع مختلف پارسرهای انتقال کاهش را نشان می‌دهد. از آنجایی که اولویت هر دو آن‌ها بیشتر از؛ است بنابراین باید به چیزی کاهش یابند که به وسیله؛ دنبال می‌شده‌است. روش‌های متفاوتی از پارسر تقدم وجود دارد که تفاوت آن‌ها در پیدا کردن دستگیره و انتخاب قاعده استفاده شده دارند: پارسر تقدم عملگر یک روش عددی ساده که برای عبارات ساده کاربرد دارد نه دستورها نحوی زبان. پارسر تقدم ساده از یک جدول بزرگ M x N برای یافتن انتهای راست و چپ استفاده می‌کرد. آن‌ها به تمام عبارات مشاهده شده در گرامر توجه نکرده و بیشتر توجه آن‌ها به بالاترین نماد است. تقدم نیازمند شکل و شمایل مشابه در هنگام استفاده و تجزیه است با این حال آن ترکیب بدون در نظر گرفتن متن رخ می‌دهد. پارسرهای LR با استفاده از انتقال کاهش انعطاف‌پذیری بالاتری دارند و گرامرهای بیشتری را پوشش می‌دهند. پارسرهای LR همچون یک ماشین وضعیت هستند که توابع انتقال آن عمل کاهش یا انتقال است. | ## جمع‌بندی | این مکانیسم به پارسر LR اجازه می‌دهد تا به عنوان یک ابرمجموعه پارسرهای تقدم همه گرامرهای مستقل از متن قطعی را در بربگیرد.