تجزیه کننده کاهشی بازگشتی ( انگلیسی: Recursive descent parser ) یک تجزیه کننده بالا به پایین است که درخت تجزیه را از بالا و حالت اولیه می سازد تا به رشته ورودی کاربر برسد. این تجزیه کننده به صورت بازگشتی، ورودی را تجزیه می کند تا درخت تجزیه را بسازد. [ ۱]
با ساختن درخت از بالا به پایین، احتمال وجود عقب گردی در مراحل وجود دارد که نقطه ضعف این روش برشمرده می شود ولی با نوع پیش بینی کننده آن که از رشته ورودی برای پیش بینی اقدام بعدی استفاده می کند، می توان عقب گرد را از میان برداشت.
این تجزیه کننده از گرامر مستقل از متن که به صورت بازگشتی پیاده سازی می شود، استفاده می کند. [ ۲] تجزیه کننده های کاهشی بازگشتی نمی توانند دستور زبان های چپ گرد را تجزیه کنند ( چون در حلقهٔ بی نهایت گیر می کنند ) و ابتدا باید این چپ گردی را رفع نمود.
برای این تجزیه ابتدا برای همهٔ نمادهای ناپایانی گرامر از جمله نماد شروع، یک تابع در نظر می گیریم، که در واقع روند تجزیه آن را شامل می شود و همهٔ رشته هایی که از آن مشتق می شوند در این تابع صدق می کنند.
در صورتی که نماد ناپایانی N فقط یک قاعده را در گرامر داشته باشد ( در سمت چپ فقط یک قاعده آمده باشد ) تابع تجزیه آن آسان خواهد بود و به ترتیب نمادها در سمت راست آن پیش می رویم. اگر نماد بعدی یک نماد پایانی بود آن را نماد پیش رو در ورودی چک می کنیم اگر یکسان بود، هم در ورودی و هم در سمت راست قاعده یک نماد جلوتر می رویم و اگر نبود، خطا گزارش می دهیم. اگر نماد بعد یک نماد ناپایانی بود، تابع متناظر آن نماد ناپایانی را فراخوانی می کنیم به این صورت ادامه می دهیم تا به انتهای سمت راست قاعده می رسیم.
در صورتی که نماد ناپایانی N، در سمت چپ چندین قاعده بود، تابع تجزیه نیاز دارد تصمیم بگیرد از کدام قاعده استفاده کند. در صورتی که تجزیه ما پیش بینی کننده نباشد یکی از قاعده ها را انتخاب می کند و در صورت بروز خطا در اجرای این قاعده، قاعده دیگر مشتق شده از N را فراخوانی می کند. تا زمانی که یکی از قاعده ها به درستی اجرا شود.
ولی در صورتی که تجزیه کننده ما قابلیت پیش بینی کنندگی داشته باشد، براساس نماد پیش رو ورودی و مقایسه قواعد مشتق شده، یک قاعده را انتخاب می کند. [ ۳]
N ( ) { if ( lookahead can start first rule for N ) { match rule 1 for N } else if ( lookahead can start second rule for N ) { match rule 2 for N } . . . . . . else if ( lookahead can start n' th rule for N ) { match rule n for N else { error ( ) ; } } پیاده سازی در جاوا مثال ساده روبرو که گرامر ساده ای از عبارت های ریاضی با پرانتز کامل، را نشان می دهد. در ادامه طبق تجزیه کننده کاهشی بازگشتی به زبان جاوا پیاده سازی شده است.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفبا ساختن درخت از بالا به پایین، احتمال وجود عقب گردی در مراحل وجود دارد که نقطه ضعف این روش برشمرده می شود ولی با نوع پیش بینی کننده آن که از رشته ورودی برای پیش بینی اقدام بعدی استفاده می کند، می توان عقب گرد را از میان برداشت.
این تجزیه کننده از گرامر مستقل از متن که به صورت بازگشتی پیاده سازی می شود، استفاده می کند. [ ۲] تجزیه کننده های کاهشی بازگشتی نمی توانند دستور زبان های چپ گرد را تجزیه کنند ( چون در حلقهٔ بی نهایت گیر می کنند ) و ابتدا باید این چپ گردی را رفع نمود.
برای این تجزیه ابتدا برای همهٔ نمادهای ناپایانی گرامر از جمله نماد شروع، یک تابع در نظر می گیریم، که در واقع روند تجزیه آن را شامل می شود و همهٔ رشته هایی که از آن مشتق می شوند در این تابع صدق می کنند.
در صورتی که نماد ناپایانی N فقط یک قاعده را در گرامر داشته باشد ( در سمت چپ فقط یک قاعده آمده باشد ) تابع تجزیه آن آسان خواهد بود و به ترتیب نمادها در سمت راست آن پیش می رویم. اگر نماد بعدی یک نماد پایانی بود آن را نماد پیش رو در ورودی چک می کنیم اگر یکسان بود، هم در ورودی و هم در سمت راست قاعده یک نماد جلوتر می رویم و اگر نبود، خطا گزارش می دهیم. اگر نماد بعد یک نماد ناپایانی بود، تابع متناظر آن نماد ناپایانی را فراخوانی می کنیم به این صورت ادامه می دهیم تا به انتهای سمت راست قاعده می رسیم.
در صورتی که نماد ناپایانی N، در سمت چپ چندین قاعده بود، تابع تجزیه نیاز دارد تصمیم بگیرد از کدام قاعده استفاده کند. در صورتی که تجزیه ما پیش بینی کننده نباشد یکی از قاعده ها را انتخاب می کند و در صورت بروز خطا در اجرای این قاعده، قاعده دیگر مشتق شده از N را فراخوانی می کند. تا زمانی که یکی از قاعده ها به درستی اجرا شود.
ولی در صورتی که تجزیه کننده ما قابلیت پیش بینی کنندگی داشته باشد، براساس نماد پیش رو ورودی و مقایسه قواعد مشتق شده، یک قاعده را انتخاب می کند. [ ۳]
N ( ) { if ( lookahead can start first rule for N ) { match rule 1 for N } else if ( lookahead can start second rule for N ) { match rule 2 for N } . . . . . . else if ( lookahead can start n' th rule for N ) { match rule n for N else { error ( ) ; } } پیاده سازی در جاوا مثال ساده روبرو که گرامر ساده ای از عبارت های ریاضی با پرانتز کامل، را نشان می دهد. در ادامه طبق تجزیه کننده کاهشی بازگشتی به زبان جاوا پیاده سازی شده است.
