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

در علوم کامپیوتر، تجزیه انتقال کاهش روش تجزیه ای است کارا، پایین به بالا و مبتنی بر جدول که برای زبانهای کامپیوتری و سایر زبانهای فرمال قابل استفاده می باشد. رایج ترین روش تجزیه امروز روش های تجزیه انتقال کاهش هستند. (انواع روش های LR) روش های تجزیه تقدم نیز که قبل از اختراع LR استفاده می شدند از انتقال کاهش بهره می بردند. همه پارسرهای انتقال کاهش اثر ظاهری مشابهی به صورت ساخت افزایشی درخت تجزیه یا فراخوانی عمل خروجی خاصی دارند. بررسی ظاهری یک پارسر LR بدون در نظر گرفتن جزییات ریاضی ساخت جدول آن بهترین مثال برای فهمیدن برخی ویژگی های عمومی انتقال کاهش است.
عمل انتقال باعث پیشرفت در ورودی شده و همچنین به ایجاد یک گره در درخت می انجامد.
عمل کاهش باعث تأیید درخت جدید ایجاد شده با گرامر و ترکیب زیردرخت ها با هم به وسیله یک ریشه جدید می شود.
یک پارسر انتقال کاهش رشته ورودی را بدون بازگشت به عقب در یک راستا خوانده و تجزیه می کند. (جهت خواندن معمولاً از چپ به راست در هر خط و از پایین به بالا برای چند خط است) پارسر درخت تجزیه را به مرور از پایین به بالا و از چپ به راست بدون حدس یا بازگشت به عقب تشکیل می دهد. پارسر در هر نقطه از مسیر یک لیست از زیر درخت ها یا رشته های تجزیه شده را ذخیره می کند. زیر درخت ها تا زمانی که پارسر به به انتهای دست راست عبارت نحوی نرسیده با یکدیگر ترکیب نمی شوند.
همانگونه که در قسمت سایه دار موجود در تصویر معلوم است در مرحله هفتم مثال تجزیه، فقط “A = B +” تجزیه شده است و هیچ یک از گره های هشتم به بالا در این مرحله وجود ندارند. گره های اول، دوم، ششم و هفتم ریشه زیر درخت های پوشش دهنده گره های یک تا هفت هستند. گره یک متغیر A، گره دو عملگر =، گره شش جمع وند B و گره هفتم عملگر + است. این چهار گره ریشه موقتاً در یک پشته تجزیه نگهداری می شوند. قسمت باقی مانده ورودی “C * ۲” است.همانگونه که از نام پارسر پیداست، این روش تجزیه بر مبنای یک سری عملیات انتقال و کاهش انجام می شود.
این مراحل تا زمانی که رشته ورودی تمام شود و تمام زیر درخت ها به هم متصل شوند و یک درخت کامل با یک گرامر یکسان به وجود آورند توسط پارسر ادامه می یابد.