پارسر انتقال کاهش

در علوم کامپیوتر، تجزیه انتقال کاهش روش تجزیه‌ای است کارا، پایین به بالا و مبتنی بر جدول که برای زبانهای کامپیوتری و سایر زبانهای فرمال قابل استفاده می‌باشد. رایج‌ترین روش تجزیه امروز روش‌های تجزیه انتقال کاهش هستند. (انواع روش‌های LR) روش‌های تجزیه تقدم نیز که قبل از اختراع LR استفاده می‌شدند از انتقال کاهش بهره می‌بردند. همه پارسرهای انتقال کاهش اثر ظاهری مشابهی به صورت ساخت افزایشی درخت تجزیه یا فراخوانی عمل خروجی خاصی دارند. بررسی ظاهری یک پارسر LR بدون در نظر گرفتن جزییات ریاضی ساخت جدول آن بهترین مثال برای فهمیدن برخی ویژگی‌های عمومی انتقال کاهش است.

گرامری برای مثال

گرامر مجموعه‌ای از الگوها یا قواعد نحوی برای زبان ورودی است که همه قواعد از جمله اندازه اعداد، استفاده مداوم از اسم و تعاریف آن و … را پوشش نمی‌دهد. پارسر انتقال کاهش از یک گرامر مستقل از متن استفاده می‌برد.

گرامر استفاده شده به عنوان مثال یک زیرمجموعه کوچک از دستورات زبان جاوا یا 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 جدید پیدا می‌کند و مجدداً از اول شروع می‌کند.