ترکیب‌کننده تجزیه‌گر کیست؟ توضیح بده.
یک ترکیب کننده تجزیه‌گر در برنامه‌نویسی رایانه ای، یک تابع مرتبه بالا است که چندین تجزیه کننده (یا پارسر) را به عنوان ورودی می‌پذیرد و یک پارسر جدید را به عنوان خروجی برمی‌گرداند. در این زمینه، یک پارسر تابعی است که رشته‌هایی را به عنوان ورودی می‌پذیرد و ساختارهایی را به عنوان خروجی برمی‌گرداند، به عبارتی پارسر یک درخت تجزیه یا مجموعه ای از شاخص‌هایی است که نمایانگر مکان‌هایی در رشته‌است که تجزیه آن با موفقیت متوقف شده‌است. ترکیب کننده‌های پارسر از استراتژی تجزیه کننده کاهشی بازگشتی استفاده می‌کنند که ساخت و آزمایش ماژولار را تسهیل می‌کند. به این تکنیک تجزیه، تجزیه کننده ترکیبی می‌گویند.پارسرهای ساخته شده با استفاده از ترکیب کننده‌ها، خوانا، ماژولار و ساختار یافته و همچنین ساده در مراحل ساخت و نگهداری هستند. از کاربردهای گسترده آن نمونه سازی کامپایلرها و پردازنده‌ها برای زبان‌های خاص دامنه (به انگلیسی: DSL) مانند واسط‌های زبان طبیعی به پایگاه‌داده‌ها، که در آن اقدامات معنایی پیچیده و متنوعی به همراه پردازش نحوی انجام می‌شوند، می‌باشد. در سال ۱۹۸۹، ریچارد فراست و جان لانچبروری نشان دادند که از ترکیب کننده‌های تجزیه گر می‌توان برای ساختن مفسرهای زبان طبیعی استفاده‌کرد. همچنین گراهام هاتن در سال ۱۹۹۲ از توابع مرتبه بالا در تجزیه کننده‌های پایه استفاده کرد. به علاوه S.D. Swierstra جنبه‌های عملی ترکیب کنندهٔ تجزیه گر را در سال ۲۰۰۱ به نمایش گذاشت. در سال ۲۰۰۸، فراست، هافیز و کالاهان مجموعه ای از ترکیب کننده‌های تجزیه گر را در زبان هسکل که مشکل دیرینه تطابق بازگشت چپ را حل می‌کرد، و به عنوان یک ابزار کامل تجزیه کننده از بالا به پایین در زمان و فضای چند جمله ای کار می‌کرد را تعریف کردند.ایده اولیه.در هر زبان برنامه‌نویسی دارای توابع کلاس اول، می‌توان از ترکیب کننده‌های تجزیه گر با ترکیب پارسرهای پایه برای ساخت پارسرهایی با قوانین پیچیده‌تر استفاده کرد. به عنوان مثال، یک قاعده تولید از یک دستور زبان مستقل از متن (به انگلیسی: CFG) ممکن است یک یا چند جایگزین دیگر داشته باشد و هر جایگزین ممکن است شامل یک توالی از غیرپایانه(ها) و پایانه(ها) باشد یا این که می‌تواند یک غیرپایانه یا پایانه یا یک رشته خالی باشد. اگر یک پارسر ساده برای هر یک از این جایگزین‌ها وجود داشته باشد، می‌توان از یک ترکیب کنندهٔ تجزیه‌گر برای ترکیب هر یک از این پارسرها استفاده کرد و یک پارسر جدید که می‌تواند هر جایگزینی را تشخیص دهد را برگرداند.در زبانهایی که از سربارگذاری عملگرها پشتیبانی می‌کنند، یک ترکیب کننده تجزیه‌گر می‌تواند به صورت یک عملگر میانود که برای به‌هم پیوستن چند پارسر مختلف که جهت ایجاد یک قانون کامل از آن استفاده می‌شود، به کار برود. بدین جهت ترکیب کننده‌های تجزیه‌گر پارسرها را به سبکی تعبیه شده، مشابه ساختار قواعد دستور زبان صوری تعریف می‌کنند.ترکیب کننده‌ها.برای ساده نگه داشتن بحث، ترکیب کننده‌های تجزیه‌گر را فقط به عنوان تشخیص‌دهنده‌ها بررسی می‌کنیم. اگر رشته ورودی از طول codice_1 و حرف‌های آن از طریق شاخص codice_2 قابل دسترسی باشند، تشخیص دهنده یک پارسر است که به عنوان خروجی مجموعه ای از شاخص‌هایی را برمی‌گرداند که نمایانگر موقعیت‌هایی هستند که پارسر دنباله‌ای از توکن‌ها را که از شاخص j شروع می‌شود را با موفقیت تشخیص داده‌است؛ بنابراین اگر خروجی یک مجموعهٔ خالی باشد، نشان می‌دهد که تشخیص دهنده نتوانسته هیچ دنباله ای را که از شاخص codice_2 شروع می‌شود، تشخیص دهد. در غیر این صورت خروجی نشان‌دهندهٔ آن است که تشخیص دهنده در موقعیت‌های متفاوت به پایان می‌رسد.باید در نظر گرفت که ممکن است چندین روش متمایز برای تجزیه یک رشته وجود داشته باشد به صورتی که به یک شاخص مشترک منتهی می‌شوند؛ این اتفاق نشان می‌دهد گرامر مبهم است. تشخیص دهنده‌های ساده این ابهامات را نمی‌توانند شناسایی کنند چون هر شاخص انتهایی احتمالی فقط یک بار می‌تواند در مجموعه نتایج خروجی ذکر شود؛ به همین دلیل برای داشتن نتایج کامل تر، باید یک ساختار پیچیده‌تر مانند یک درخت تجزیه به عنوان خروجی برگردانده شود.در ادامه دو ترکیب کننده تجزیه گر برای جایگزینی و توالی یابی تعریف کنیم، ابتدا فرض می‌کنیم codice_10 و codice_11 ، دو تشخیص دهنده پایه باشند:مثال.یک گرامر مستقل از متن مبهم را در نظر بگیرید، codice_18 . با استفاده از ترکیب کننده ای که بالاتر تعریف کردیم، می‌توانیم به صورت ماژولار، نمادهای اجرایی این دستور زبان را با استفاده از یک زبان کاربردی مدرن (مثلاً هسکل) به صورت codice_19 تعریف کنیم. وقتی که تشخیص دهنده codice_20 بر روی یک دنباله ورودی codice_21 در موقعیت codice_22 اعمال شود با توجه به تعاریف فوق، خروجی codice_23 را برمی‌گرداند.کاستی‌ها و راه حل‌ها.ترکیب کننده‌های تجزیه‌گر، مانند همه تجزیه کننده‌های کاهشی بازگشتی، محدود به دستور زبان‌های مستقل از متن نیستند، بنابراین هیچ جستجوی سراسری برای ابهامات موجود در مجموعه Firstk و Followk در تجزیه کننده ال ال انجام نمی‌دهد؛ بنابراین، ابهامات فقط در زمان اجرا و زمانی که ورودی‌ها مقدار دهی می‌شوند، مشخص می‌شوند. در چنین مواردی، تجزیه کننده کاهشی بازگشتی می‌تواند به صورت پیش فرض (که ممکن است برای طراح گرامر ناشناخته باشد) به یکی از مسیرهای مبهم احتمالی منجر شود و باعث سردرگمی معنایی در استفاده از زبان شود. این موضوع باعث ایجاد اشکالاتی توسط کاربران زبان‌های برنامه‌نویسی مبهم می‌شود، که در زمان کامپایل گزارش نشده‌اند، و به‌عنوان خطای انسانی معرفی نمی‌شوند بلکه به‌عنوان دستور زبان مبهم معرفی می‌شوند. تنها راه حلی که این اشکالات را از بین می‌برد، رفع ابهامات و استفاده ازدستور زبان‌های مستقل از متن است.پیاده‌سازی‌های ساده ترکیب کننده‌های تجزیه‌گر دارای کاستی‌هایی هستند که در تجزیه کنندهٔ بالا به پایین هم رایج است. تجزیه‌کننده ترکیبی ساده (به انگلیسی: Naïve combinatory parsing)، هنگام تجزیهٔ دستور زبان مستقل از متن مبهم به زمان و فضای نمایی نیاز دارد. در سال ۱۹۹۶، فراست و Szydlowski نشان دادند که با مموایز کردن در استفاده از ترکیب کننده‌های تجزیه‌گر می‌توان پیچیدگی زمانی را به چند جمله ای کاهش داد. مدتی بعد فراست از مونادها برای ساخت ترکیب کننده‌ها در ریسه (به انگلیسی: thread)های قاعده دار و درست جدول یادداشت‌ها در طول محاسبه استفاده کرد. مانند هر تجزیه کننده کاهشی بازگشتی از بالا به پایین، ترکیب کننده‌های تجزیه‌گر معمولی (مانند ترکیب کننده‌های ذکر شده در بالا) در هنگام پردازش یک دستور زبان بازگشتی چپ خاتمه نمی‌یابند (به عنوان مثال codice_24). در سال ۲۰۰۶ یک الگوریتم تشخیص که دستور زبان مبهم را با قوانین مستقیم بازگشتی چپ تطبیق می‌داد ارائه شد. این الگوریتم تجزیه جداکننده بازگشتی چپ که نامتنهی است با تحمیل محدودیت‌های عمق، ساده کرد. در سال ۲۰۰۷، فراست، هفیز و کالاهااین الگوریتم را به یک الگوریتم تجزیه کننده کامل توسعه دادند، که در آن بازگشتی چپ غیرمستقیم مانند مستقیم در زمان چندجمله ای تطبیق می‌دهد، و هم چنین تعداد نمایی ای از درختان تجزیه برای گرامرهای مبهم را در فضای چندجمله ای و متراکم نمایش می‌دهد. این الگوریتم گسترش یافته، بازگشتی چپ غیرمستقیم را با مقایسه «متن محاسبه شده» با «متن فعلی»، مطابقت می‌دهد. همین نویسندگان همچنین پیاده‌سازی خود را در مورد مجموعه ای از ترکیب کننده‌های تجزیه‌گر که به زبان برنامه‌نویسی هسکل نوشته شده بودند رابر اساس همان الگوریتم توصیف کردند.