موضوع مقاله: ترکیب‌کننده تجزیه‌گر | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # ترکیب‌کننده تجزیه‌گر | مقدمه: یک ترکیب کننده تجزیه‌گر در برنامه‌نویسی رایانه ای، یک تابع مرتبه بالا است که چندین تجزیه کننده (یا پارسر) را به عنوان ورودی می‌پذیرد و یک پارسر جدید را به عنوان خروجی برمی‌گرداند. | ## بخش 1: ترکیب‌کننده تجزیه‌گر | در این زمینه، یک پارسر تابعی است که رشته‌هایی را به عنوان ورودی می‌پذیرد و ساختارهایی را به عنوان خروجی برمی‌گرداند، به عبارتی پارسر یک درخت تجزیه یا مجموعه ای از شاخص‌هایی است که نمایانگر مکان‌هایی در رشته‌است که تجزیه آن با موفقیت متوقف شده‌است. ترکیب کننده‌های پارسر از استراتژی تجزیه کننده کاهشی بازگشتی استفاده می‌کنند که ساخت و آزمایش ماژولار را تسهیل می‌کند. پارسرهای ساخته شده با استفاده از ترکیب کننده‌ها، خوانا، ماژولار و ساختار یافته و همچنین ساده در مراحل ساخت و نگهداری هستند. از کاربردهای گسترده آن نمونه سازی کامپایلرها و پردازنده‌ها برای زبان‌های خاص دامنه (به انگلیسی: DSL) مانند واسط‌های زبان طبیعی به پایگاه‌داده‌ها، که در آن اقدامات معنایی پیچیده و متنوعی به همراه پردازش نحوی انجام می‌شوند، می‌باشد. در سال ۱۹۸۹، ریچارد فراست و جان لانچبروری نشان دادند که از ترکیب کننده‌های تجزیه گر می‌توان برای ساختن مفسرهای زبان طبیعی استفاده‌کرد. همچنین گراهام هاتن در سال ۱۹۹۲ از توابع مرتبه بالا در تجزیه کننده‌های پایه استفاده کرد. در سال ۲۰۰۸، فراست، هافیز و کالاهان مجموعه ای از ترکیب کننده‌های تجزیه گر را در زبان هسکل که مشکل دیرینه تطابق بازگشت چپ را حل می‌کرد، و به عنوان یک ابزار کامل تجزیه کننده از بالا به پایین در زمان و فضای چند جمله ای کار می‌کرد را تعریف کردند. ایده اولیه در هر زبان برنامه‌نویسی دارای توابع کلاس اول، می‌توان از ترکیب کننده‌های تجزیه گر با ترکیب پارسرهای پایه برای ساخت پارسرهایی با قوانین پیچیده‌تر استفاده کرد. به عنوان مثال، یک قاعده تولید از یک دستور زبان مستقل از متن (به انگلیسی: CFG) ممکن است یک یا چند جایگزین دیگر داشته باشد و هر جایگزین ممکن است شامل یک توالی از غیرپایانه(ها) و پایانه(ها) باشد یا این که می‌تواند یک غیرپایانه یا پایانه یا یک رشته خالی باشد. اگر یک پارسر ساده برای هر یک از این جایگزین‌ها وجود داشته باشد، می‌توان از یک ترکیب کنندهٔ تجزیه‌گر برای ترکیب هر یک از این پارسرها استفاده کرد و یک پارسر جدید که می‌تواند هر جایگزینی را تشخیص دهد را برگرداند. در زبانهایی که از سربارگذاری عملگرها پشتیبانی می‌کنند، یک ترکیب کننده تجزیه‌گر می‌تواند به صورت یک عملگر میانود که برای به‌هم پیوستن چند پارسر مختلف که جهت ایجاد یک قانون کامل از آن استفاده می‌شود، به کار برود. | ## بخش 2: ترکیب‌کننده تجزیه‌گر | بدین جهت ترکیب کننده‌های تجزیه‌گر پارسرها را به سبکی تعبیه شده، مشابه ساختار قواعد دستور زبان صوری تعریف می‌کنند. ترکیب کننده‌ها برای ساده نگه داشتن بحث، ترکیب کننده‌های تجزیه‌گر را فقط به عنوان تشخیص‌دهنده‌ها بررسی می‌کنیم. اگر رشته ورودی از طول #input و حرف‌های آن از طریق شاخص j قابل دسترسی باشند، تشخیص دهنده یک پارسر است که به عنوان خروجی مجموعه ای از شاخص‌هایی را برمی‌گرداند که نمایانگر موقعیت‌هایی هستند که پارسر دنباله‌ای از توکن‌ها را که از شاخص j شروع می‌شود را با موفقیت تشخیص داده‌است؛ بنابراین اگر خروجی یک مجموعهٔ خالی باشد، نشان می‌دهد که تشخیص دهنده نتوانسته هیچ دنباله ای را که از شاخص j شروع می‌شود، تشخیص دهد. در غیر این صورت خروجی نشان‌دهندهٔ آن است که تشخیص دهنده در موقعیت‌های متفاوت به پایان می‌رسد. اگر توکن در موقعیت j از رشته ورودی x باشد، این پارسر یک مجموعه تک عضوی حاوی j + 1 را برمی‌گرداند. باید در نظر گرفت که ممکن است چندین روش متمایز برای تجزیه یک رشته وجود داشته باشد به صورتی که به یک شاخص مشترک منتهی می‌شوند؛ این اتفاق نشان می‌دهد گرامر مبهم است. تشخیص دهنده‌های ساده این ابهامات را نمی‌توانند شناسایی کنند چون هر شاخص انتهایی احتمالی فقط یک بار می‌تواند در مجموعه نتایج خروجی ذکر شود؛ به همین دلیل برای داشتن نتایج کامل تر، باید یک ساختار پیچیده‌تر مانند یک درخت تجزیه به عنوان خروجی برگردانده شود. در ادامه دو ترکیب کننده تجزیه گر برای جایگزینی و توالی یابی تعریف کنیم، ابتدا فرض می‌کنیم p و q ، دو تشخیص دهنده پایه باشند: ترکیب دهنده تجزیه گر جایگزین، ⊕، دو تشخیص دهنده را در موقعیت ورودی j گرفته و خروجی برگردانده شده از دو مشخص کننده را جمع می‌کند و به عنوان نتیجه نهایی برمی‌گرداند. ابتدا مشخص کننده p را در موقعیت ورودی j گرفته و اگر نتیجه ناتهی باشد، مشخص کننده q برای هر عنصر از مجموعه نتیجه برگردانده شده توسط مشخص کننده p، اعمال می‌شود. با استفاده از ترکیب کننده ای که بالاتر تعریف کردیم، می‌توانیم به صورت ماژولار، نمادهای اجرایی این دستور زبان را با استفاده از یک زبان کاربردی مدرن (مثلاً هسکل) به صورت s = term ‘x’ <*> s <*> s <+> empty تعریف کنیم. کاستی‌ها و راه حل‌ها ترکیب کننده‌های تجزیه‌گر، مانند همه تجزیه کننده‌های کاهشی بازگشتی، محدود به دستور زبان‌های مستقل از متن نیستند، بنابراین هیچ جستجوی سراسری برای ابهامات موجود در مجموعه Firstk و Followk در تجزیه کننده ال ال انجام نمی‌دهد؛ بنابراین، ابهامات فقط در زمان اجرا و زمانی که ورودی‌ها مقدار دهی می‌شوند، مشخص می‌شوند. | ## بخش 3: ترکیب‌کننده تجزیه‌گر | در چنین مواردی، تجزیه کننده کاهشی بازگشتی می‌تواند به صورت پیش فرض (که ممکن است برای طراح گرامر ناشناخته باشد) به یکی از مسیرهای مبهم احتمالی منجر شود و باعث سردرگمی معنایی در استفاده از زبان شود. این موضوع باعث ایجاد اشکالاتی توسط کاربران زبان‌های برنامه‌نویسی مبهم می‌شود، که در زمان کامپایل گزارش نشده‌اند، و به‌عنوان خطای انسانی معرفی نمی‌شوند بلکه به‌عنوان دستور زبان مبهم معرفی می‌شوند. تنها راه حلی که این اشکالات را از بین می‌برد، رفع ابهامات و استفاده ازدستور زبان‌های مستقل از متن است. پیاده‌سازی‌های ساده ترکیب کننده‌های تجزیه‌گر دارای کاستی‌هایی هستند که در تجزیه کنندهٔ بالا به پایین هم رایج است. در سال ۱۹۹۶، فراست و Szydlowski نشان دادند که با مموایز کردن در استفاده از ترکیب کننده‌های تجزیه‌گر می‌توان پیچیدگی زمانی را به چند جمله ای کاهش داد. مدتی بعد فراست از مونادها برای ساخت ترکیب کننده‌ها در ریسه (به انگلیسی: thread)های قاعده دار و درست جدول یادداشت‌ها در طول محاسبه استفاده کرد. مانند هر تجزیه کننده کاهشی بازگشتی از بالا به پایین، ترکیب کننده‌های تجزیه‌گر معمولی (مانند ترکیب کننده‌های ذکر شده در بالا) در هنگام پردازش یک دستور زبان بازگشتی چپ خاتمه نمی‌یابند (به عنوان مثال s ::= s <*> term 'x'|empty). در سال ۲۰۰۶ یک الگوریتم تشخیص که دستور زبان مبهم را با قوانین مستقیم بازگشتی چپ تطبیق می‌داد ارائه شد. این الگوریتم تجزیه جداکننده بازگشتی چپ که نامتنهی است با تحمیل محدودیت‌های عمق، ساده کرد. در سال ۲۰۰۷، فراست، هفیز و کالاهااین الگوریتم را به یک الگوریتم تجزیه کننده کامل توسعه دادند، که در آن بازگشتی چپ غیرمستقیم مانند مستقیم در زمان چندجمله ای تطبیق می‌دهد، و هم چنین تعداد نمایی ای از درختان تجزیه برای گرامرهای مبهم را در فضای چندجمله ای و متراکم نمایش می‌دهد. این الگوریتم گسترش یافته، بازگشتی چپ غیرمستقیم را با مقایسه «متن محاسبه شده» با «متن فعلی»، مطابقت می‌دهد. | ## جمع‌بندی | همین نویسندگان همچنین پیاده‌سازی خود را در مورد مجموعه ای از ترکیب کننده‌های تجزیه‌گر که به زبان برنامه‌نویسی هسکل نوشته شده بودند رابر اساس همان الگوریتم توصیف کردند.