موضوع مقاله: تجزیه از پایین به بالا | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # تجزیه از پایین به بالا | مقدمه: در علوم کامپیوتر، تجزیه به عملی گفته می‌شود که قواعد ساختاری یک متن را آشکار می‌کند. | ## بخش 1: تجزیه از پایین به بالا | تجزیه پایین به بالا به یک نوع تجزیه کردن متن ورودی بر اساس ساختار گرامری از پیش تعیین شدهای گفته می‌شود که طی آن از پایین‌ترین بخش درخت تجزیه یعنی برگ‌های آن شروع می‌کنیم و با اعمال قواعد ساخت روی جمله آنقدر ادامه می‌دهیم تا به ریشه درخت برسیم. تجزیه پایین به بالا درخت اشتقاق یک ابزار انتزاعی برای بیان ساختار یک گرامر مستقل از متن است. از کنار هم قرار دادن برگ‌های این درخت یک جمله که در زبان معادل آن گرامر وجود دارد بدست می‌آید. در واقع تجزیه پایین به بالا با خواندن از سمت چپ و آمدن به سمت راست معادل اشتقاق از راست‌ترین متغیر است که یکی از روش‌های اشتقاق در یک گرامر است. در تجزیه پایین به بالا با نگاه کردن به برگ‌های درخت اشتقاق و مقایسه کردن با قواعد ساخت درمی‌یابیم در هر مرحله طبق کدام قاعده بایستی عمل اشتقاق صورت می‌گرفته تا حاصل چنین برگی باشد. به این معنی که تمام ورودی ابتدا خارج از دسترس است سپس به تدریج با عمل شیفت یک نشانه در اختیار تجزیه‌کننده قرار می‌گیرد. انی عمل آنقدر تکرار می‌شود تا جمع نشانه‌های در دسترس از طریق قاعده‌ای در گرامر قابل ساخته شدن باشد. به مجموعه نشانه‌هایی که باعث صورت گرفتن یک کاهش می‌شوند هندل(handle) گفته می‌شود. تجزیه LR در این روش تجزیه برای تجزیه صحیح و استفاده نکردن از قواعد ساخت اشتباه در هر راس درخت از تجزیه LR استفاده می‌کنیم. تجزیه LR به این معنی است که از سمت چپ جمله ورودی شروع می‌کنیم و به سمت راست می‌رویم و پس از پیدا شدن هندل عمل کاهش را انجام می‌دهیم. | ## بخش 2: تجزیه از پایین به بالا | در تصویر متحرک روبرو نحوه ساخته شدن این ماشین حالت متناهی را برای گرامر داده شده مشاهده می‌کنید. پس از ساختن این ماشین حالت متناهی می‌توان یک رشته گرفت و با شروع از سمت چپ به تدریج هندل‌ها را به کمک ماشین ساخته شده پیدا کرد و عمل کاهش را انجام داد. این جدول به تعداد استیت‌های ماشین حالت متناهی ردیف و به تعداد نشانه‌ها ستون دارد. هر استیت ماشین باید بیانگر یک حرکت باشد: شیفت کاهش (عمل قبول کردن رشته به این معنی که درخت اشتقاق آن به دست آمده‌است هم ذیل کاهش در نظر گرفته می‌شود) استیت‌های شیفت استیت‌هایی هستند که نقطه به پایان عبارت نرسیده‌باشد و استیت‌های کاهش استیت‌هایی هستند که نقطه به پایان عبارت تک تک عبارات داخل آن استیت رسیده‌باشد. همانگونه که در شکل روبرو دیده می‌شود به‌طور مثال وضعیت استیت‌های ۰، ۲ و ۴ متناقض است. در این استیت‌ها هم عباراتی وجود دارند که آماده کاهش هستند و هم عباراتی هستند که باید برای رسیدن به هندل مناسب برای آن‌ها عمل شیفت را انجام داد. در این مرحله هم می‌توان ماشین حالت متناهی ساخت و مشابه قبل هر استیت شامل چند عبارت گرامری است که هر عبارت یک نشانه جلوی خود می‌بیند. در شکل روبرو یک نمونه از جدول اشتقاقی که طی این روش ساخته می‌شود را مشاهده می‌کنید. در خانه‌های این جدول مشخص شده با توجه به استیت ماشین حالت متناهی و نشانه پیش‌رو چه عملی انتخاب شود. عبارت [عدد]s در یک خانه به معنی شیفت دادن و رفتن به استیت [عدد] است و [عدد]r به معنی کاهش دادن طبق قاعده شماره [عدد] است. | ## بخش 3: تجزیه از پایین به بالا | (SLR(1 این روش خود نمونه‌ای از روش قبلی است ولی برای جلوگیری از پیچیدگی ماشین حالت متناهی روش قبل و ساده‌سازی معرفی شده‌است. این روش با توجه به اینکه ساده‌ شده روش (LR(1 است به قدرتمندی این روش نیست و ضعف‌هایی دارد. در این روش مجموعه‌ای از نشانه‌ها که طبق قواعد گرامر می‌توانند پس از هر حرف غیرپایانه‌ای بیایند برای هرکدام از این حرف‌ها در نظر گرفته می‌شود. حال به‌جای در نظر گرفتن تمام حالات نشانه پیش‌رو، تنها بررسی می‌کنیم نشانه پیش‌رو حرف غیرپایانه‌ای یک قاعده در مجموعه گفته‌شده حضور دارد یا خیر. همانطور که گفته شد در این روش به دلیل اعمال محدودیت برای جلوگیری از گستردگی ماشین حالت متناهی ضعف‌هایی وجود دارد. (LALR(1 این روش هم برگرفته از روش (LR(1 است ولی برای جلوگیری از گسترده شدن ماشین حالت متناهی در حین ساختن استیت‌ها بررسی صورت می‌گیرد که حتی‌الامکان استیت جدید اضافه نشود. این به دو صورت ظاهر می‌شود: در یک استیت اگر محبور باشیم یک قاعده را بخاطر تفاوت در نشانه پیش‌رو چندبار بنویسیم، آن قاعده را یکبار می‌نویسیم و روبرویش تمام نشانه‌های پیش‌رو را می‌گذاریم. هر گاه از یک استیت با یک تبدیل حرفی بخواهیم به استیتی برویم دقیقا مشابه آن استیت وجود ندارد در بین استیت‌ها می‌گردیم که آیا استیتی وجود دارد که همان قاعده را با نشانه پیش‌رو دیگری داشته باشد یا نه. | ## جمع‌بندی | اگر چنین استیت وجود داشت تبدیل را به همان استیت صورت می‌دهیم و به نشانه‌های پیش‌روی آن نشانه جدید را اضافه می‌کنیم.