در علوم کامپیوتر، تجزیه به عملی گفته می شود که قواعد ساختاری یک متن را آشکار می کند. این گام مقدمه معنی کردن آن متن است. تجزیه پایین به بالا به یک نوع تجزیه کردن متن ورودی بر اساس ساختار گرامری از پیش تعیین شدهای گفته می شود که طی آن از پایین ترین بخش درخت تجزیه یعنی برگ های آن شروع می کنیم و با اعمال قواعد ساخت روی جمله آنقدر ادامه می دهیم تا به ریشه درخت برسیم.
درخت اشتقاق یک ابزار انتزاعی برای بیان ساختار یک گرامر مستقل از متن است. ریشه این درخت متغیر شروع گرامر و برگ های آن ثوابت این گرامر هستند. از کنار هم قرار دادن برگ های این درخت یک جمله که در زبان معادل آن گرامر وجود دارد بدست می آید. در تجزیه پایین به بالا برخلاف تجزیه بالا به پایین که در ابتدا بدون هیچ دانشی صرفاً با حدس زدن براساس اولین نشانه عمل تجزیه آغاز می شود، با نگاه کردن به برگ های درخت در واقع نسبت به اعمال اشتقاق می توان شهود گرفت[ ۱] . در واقع تجزیه پایین به بالا با خواندن از سمت چپ و آمدن به سمت راست معادل اشتقاق از راست ترین متغیر است که یکی از روش های اشتقاق در یک گرامر است. در تجزیه پایین به بالا با نگاه کردن به برگ های درخت اشتقاق و مقایسه کردن با قواعد ساخت درمی یابیم در هر مرحله طبق کدام قاعده بایستی عمل اشتقاق صورت می گرفته تا حاصل چنین برگی باشد.
تجزیه پایین به بالا از طریق شیفت و کاهش دادن صورت می گیرد. به این معنی که تمام ورودی ابتدا خارج از دسترس است سپس به تدریج با عمل شیفت یک نشانه در اختیار تجزیه کننده قرار می گیرد. تجزیه کننده تعیین می کند آیا قاعده اشتقاقی برای این نشانه وجود دارد یا نه. اگر قاعده ای وجود نداشت دوباره عمل شیفت دادن صورت می گیرد. انی عمل آنقدر تکرار می شود تا جمع نشانه های در دسترس از طریق قاعده ای در گرامر قابل ساخته شدن باشد. در آن صورت عمل کاهش دادن صورت می گیرد. به مجموعه نشانه هایی که باعث صورت گرفتن یک کاهش می شوند هندل ( handle ) گفته می شود.
در این روش تجزیه برای تجزیه صحیح و استفاده نکردن از قواعد ساخت اشتباه در هر راس درخت از تجزیه LR استفاده می کنیم. [ ۲] تجزیه LR به این معنی است که از سمت چپ جمله ورودی شروع می کنیم و به سمت راست می رویم و پس از پیدا شدن هندل عمل کاهش را انجام می دهیم. نام LR هم واقف بر همین دو موضوع است ( L برای Left to right و R برای Reduce ) . این روش ابتدایی با نام ( LR ( 0 شناخته می شود که روش ناقصی است. سه نوع تجزیه گر صحیح تر که از این روش مشتق می شوند به ترتیب قدرتشان عبارتند از: ( LR ( 1 ) ، LALR ( 1 و ( SLR ( 1.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفدرخت اشتقاق یک ابزار انتزاعی برای بیان ساختار یک گرامر مستقل از متن است. ریشه این درخت متغیر شروع گرامر و برگ های آن ثوابت این گرامر هستند. از کنار هم قرار دادن برگ های این درخت یک جمله که در زبان معادل آن گرامر وجود دارد بدست می آید. در تجزیه پایین به بالا برخلاف تجزیه بالا به پایین که در ابتدا بدون هیچ دانشی صرفاً با حدس زدن براساس اولین نشانه عمل تجزیه آغاز می شود، با نگاه کردن به برگ های درخت در واقع نسبت به اعمال اشتقاق می توان شهود گرفت[ ۱] . در واقع تجزیه پایین به بالا با خواندن از سمت چپ و آمدن به سمت راست معادل اشتقاق از راست ترین متغیر است که یکی از روش های اشتقاق در یک گرامر است. در تجزیه پایین به بالا با نگاه کردن به برگ های درخت اشتقاق و مقایسه کردن با قواعد ساخت درمی یابیم در هر مرحله طبق کدام قاعده بایستی عمل اشتقاق صورت می گرفته تا حاصل چنین برگی باشد.
تجزیه پایین به بالا از طریق شیفت و کاهش دادن صورت می گیرد. به این معنی که تمام ورودی ابتدا خارج از دسترس است سپس به تدریج با عمل شیفت یک نشانه در اختیار تجزیه کننده قرار می گیرد. تجزیه کننده تعیین می کند آیا قاعده اشتقاقی برای این نشانه وجود دارد یا نه. اگر قاعده ای وجود نداشت دوباره عمل شیفت دادن صورت می گیرد. انی عمل آنقدر تکرار می شود تا جمع نشانه های در دسترس از طریق قاعده ای در گرامر قابل ساخته شدن باشد. در آن صورت عمل کاهش دادن صورت می گیرد. به مجموعه نشانه هایی که باعث صورت گرفتن یک کاهش می شوند هندل ( handle ) گفته می شود.
در این روش تجزیه برای تجزیه صحیح و استفاده نکردن از قواعد ساخت اشتباه در هر راس درخت از تجزیه LR استفاده می کنیم. [ ۲] تجزیه LR به این معنی است که از سمت چپ جمله ورودی شروع می کنیم و به سمت راست می رویم و پس از پیدا شدن هندل عمل کاهش را انجام می دهیم. نام LR هم واقف بر همین دو موضوع است ( L برای Left to right و R برای Reduce ) . این روش ابتدایی با نام ( LR ( 0 شناخته می شود که روش ناقصی است. سه نوع تجزیه گر صحیح تر که از این روش مشتق می شوند به ترتیب قدرتشان عبارتند از: ( LR ( 1 ) ، LALR ( 1 و ( SLR ( 1.
wiki: تجزیه از پایین به بالا