ترکیب‌کننده تجزیه‌گر

یک ترکیب کننده تجزیه‌گر در برنامه‌نویسی رایانه ای، یک تابع مرتبه بالا است که چندین تجزیه کننده (یا پارسر) را به عنوان ورودی می‌پذیرد و یک پارسر جدید را به عنوان خروجی برمی‌گرداند. در این زمینه، یک پارسر تابعی است که رشته‌هایی را به عنوان ورودی می‌پذیرد و ساختارهایی را به عنوان خروجی برمی‌گرداند، به عبارتی پارسر یک درخت تجزیه یا مجموعه ای از شاخص‌هایی است که نمایانگر مکان‌هایی در رشته‌است که تجزیه آن با موفقیت متوقف شده‌است. ترکیب کننده‌های پارسر از استراتژی تجزیه کننده کاهشی بازگشتی استفاده می‌کنند که ساخت و آزمایش ماژولار را تسهیل می‌کند. به این تکنیک تجزیه، تجزیه کننده ترکیبی می‌گویند.

پارسرهای ساخته شده با استفاده از ترکیب کننده‌ها، خوانا، ماژولار و ساختار یافته و همچنین ساده در مراحل ساخت و نگهداری هستند. از کاربردهای گسترده آن نمونه سازی کامپایلرها و پردازنده‌ها برای زبان‌های خاص دامنه (به انگلیسی: DSL) مانند واسط‌های زبان طبیعی به پایگاه‌داده‌ها، که در آن اقدامات معنایی پیچیده و متنوعی به همراه پردازش نحوی انجام می‌شوند، می‌باشد. در سال ۱۹۸۹، ریچارد فراست و جان لانچبروری الگو:Sfn نشان دادند که از ترکیب کننده‌های تجزیه گر می‌توان برای ساختن مفسرهای زبان طبیعی استفاده‌کرد. همچنین گراهام هاتن در سال ۱۹۹۲ از توابع مرتبه بالا در تجزیه کننده‌های پایه استفاده کرد. الگو:Sfn به علاوه S.D. Swierstra جنبه‌های عملی ترکیب کنندهٔ تجزیه گر را در سال ۲۰۰۱ به نمایش گذاشت. الگو:Sfn در سال ۲۰۰۸، فراست، هافیز و کالاهان الگو:Sfn مجموعه ای از ترکیب کننده‌های تجزیه گر را در زبان هسکل که مشکل دیرینه تطابق بازگشت چپ را حل می‌کرد، و به عنوان یک ابزار کامل تجزیه کننده از بالا به پایین در زمان و فضای چند جمله ای کار می‌کرد را تعریف کردند.

ایده اولیه

در هر زبان برنامه‌نویسی دارای توابع کلاس اول، می‌توان از ترکیب کننده‌های تجزیه گر با ترکیب پارسرهای پایه برای ساخت پارسرهایی با قوانین پیچیده‌تر استفاده کرد. به عنوان مثال، یک قاعده تولید از یک دستور زبان مستقل از متن (به انگلیسی: CFG) ممکن است یک یا چند جایگزین دیگر داشته باشد و هر جایگزین ممکن است شامل یک توالی از غیرپایانه(ها) و پایانه(ها) باشد یا این که می‌تواند یک غیرپایانه یا پایانه یا یک رشته خالی باشد. اگر یک پارسر ساده برای هر یک از این جایگزین‌ها وجود داشته باشد، می‌توان از یک ترکیب کنندهٔ تجزیه‌گر برای ترکیب هر یک از این پارسرها استفاده کرد و یک پارسر جدید که می‌تواند هر جایگزینی را تشخیص دهد را برگرداند.

در زبانهایی که از سربارگذاری عملگرها پشتیبانی می‌کنند، یک ترکیب کننده تجزیه‌گر می‌تواند به صورت یک عملگر میانود که برای به‌هم پیوستن چند پارسر مختلف که جهت ایجاد یک قانون کامل از آن استفاده می‌شود، به کار برود. بدین جهت ترکیب کننده‌های تجزیه‌گر پارسرها را به سبکی تعبیه شده، مشابه ساختار قواعد دستور زبان صوری تعریف می‌کنند.

ترکیب کننده‌ها

برای ساده نگه داشتن بحث، ترکیب کننده‌های تجزیه‌گر را فقط به عنوان تشخیص‌دهنده‌ها بررسی می‌کنیم. اگر رشته ورودی از طول #input و حرف‌های آن از طریق شاخص j قابل دسترسی باشند، تشخیص دهنده یک پارسر است که به عنوان خروجی مجموعه ای از شاخص‌هایی را برمی‌گرداند که نمایانگر موقعیت‌هایی هستند که پارسر دنباله‌ای از توکن‌ها را که از شاخص j شروع می‌شود را با موفقیت تشخیص داده‌است؛ بنابراین اگر خروجی یک مجموعهٔ خالی باشد، نشان می‌دهد که تشخیص دهنده نتوانسته هیچ دنباله ای را که از شاخص j شروع می‌شود، تشخیص دهد. در غیر این صورت خروجی نشان‌دهندهٔ آن است که تشخیص دهنده در موقعیت‌های متفاوت به پایان می‌رسد.

• تشخیص دهنده خالی (empty) رشته خالی را تشخیص می‌دهد. این پارسر همیشه جواب دارد و یک مجموعه یک عضوی حاوی موقعیت فعلی را برمی‌گرداند.

$empty(j)=\{j\}$

• تشخیص دهنده واژه x، پایانه x را تشخیص می‌دهد. اگر توکن در موقعیت j از رشته ورودی x باشد، این پارسر یک مجموعه تک عضوی حاوی j + 1 را برمی‌گرداند. در غیر این صورت، خروجی یک مجموعه خالی است.

$term(x,j)=\{\begin{array}{cc}\left\{\right\},& j\ge \mathrm{\#}input\\ \{j+1\},& j^{th}\text{ element of }input=x\\ \left\{\right\},& \text{otherwise}\end{array}$

باید در نظر گرفت که ممکن است چندین روش متمایز برای تجزیه یک رشته وجود داشته باشد به صورتی که به یک شاخص مشترک منتهی می‌شوند؛ این اتفاق نشان می‌دهد گرامر مبهم است. تشخیص دهنده‌های ساده این ابهامات را نمی‌توانند شناسایی کنند چون هر شاخص انتهایی احتمالی فقط یک بار می‌تواند در مجموعه نتایج خروجی ذکر شود؛ به همین دلیل برای داشتن نتایج کامل تر، باید یک ساختار پیچیده‌تر مانند یک درخت تجزیه به عنوان خروجی برگردانده شود.

در ادامه دو ترکیب کننده تجزیه گر برای جایگزینی و توالی یابی تعریف کنیم، ابتدا فرض می‌کنیم p و q ، دو تشخیص دهنده پایه باشند:

• ترکیب دهنده تجزیه گر جایگزین، ⊕، دو تشخیص دهنده را در موقعیت ورودی j گرفته و خروجی برگردانده شده از دو مشخص کننده را جمع می‌کند و به عنوان نتیجه نهایی برمی‌گرداند.

$(p\oplus q)(j)=p(j)\cup q(j)$

• توالی یابی مشخص کننده‌ها به وسیله ترکیب دهنده تجزیه گر ⊛ انجام می‌شود. ابتدا مشخص کننده p را در موقعیت ورودی j گرفته و اگر نتیجه ناتهی باشد، مشخص کننده q برای هر عنصر از مجموعه نتیجه برگردانده شده توسط مشخص کننده p، اعمال می‌شود. در آخر ⊛، اجتماع خروجی‌های حاصل از مشخص کننده q را برمی‌گرداند.

$(p⊛q)(j)=\bigcup \{q(k):k\in p(j)\}$

مثال

یک گرامر مستقل از متن مبهم را در نظر بگیرید، s ::= 'x' s s | ε . با استفاده از ترکیب کننده ای که بالاتر تعریف کردیم، می‌توانیم به صورت ماژولار، نمادهای اجرایی این دستور زبان را با استفاده از یک زبان کاربردی مدرن (مثلاً هسکل) به صورت s = term ‘x’ <*> s <*> s <+> empty تعریف کنیم. وقتی که تشخیص دهنده s بر روی یک دنباله ورودی ..... در موقعیت 1 اعمال شود با توجه به تعاریف فوق، خروجی {5,4،3,2} را برمی‌گرداند.

کاستی‌ها و راه حل‌ها

ترکیب کننده‌های تجزیه‌گر، مانند همه تجزیه کننده‌های کاهشی بازگشتی، محدود به دستور زبان‌های مستقل از متن نیستند، بنابراین هیچ جستجوی سراسری برای ابهامات موجود در مجموعه First_k و Follow_k در تجزیه کننده ال ال انجام نمی‌دهد؛ بنابراین، ابهامات فقط در زمان اجرا و زمانی که ورودی‌ها مقدار دهی می‌شوند، مشخص می‌شوند. در چنین مواردی، تجزیه کننده کاهشی بازگشتی می‌تواند به صورت پیش فرض (که ممکن است برای طراح گرامر ناشناخته باشد) به یکی از مسیرهای مبهم احتمالی منجر شود و باعث سردرگمی معنایی در استفاده از زبان شود. این موضوع باعث ایجاد اشکالاتی توسط کاربران زبان‌های برنامه‌نویسی مبهم می‌شود، که در زمان کامپایل گزارش نشده‌اند، و به‌عنوان خطای انسانی معرفی نمی‌شوند بلکه به‌عنوان دستور زبان مبهم معرفی می‌شوند. تنها راه حلی که این اشکالات را از بین می‌برد، رفع ابهامات و استفاده ازدستور زبان‌های مستقل از متن است.

پیاده‌سازی‌های ساده ترکیب کننده‌های تجزیه‌گر دارای کاستی‌هایی هستند که در تجزیه کنندهٔ بالا به پایین هم رایج است. تجزیه‌کننده ترکیبی ساده (به انگلیسی: Naïve combinatory parsing)، هنگام تجزیهٔ دستور زبان مستقل از متن مبهم به زمان و فضای نمایی نیاز دارد. در سال ۱۹۹۶، فراست و Szydlowski نشان دادند که با مموایز کردن در استفاده از ترکیب کننده‌های تجزیه‌گر می‌توان پیچیدگی زمانی را به چند جمله ای کاهش داد. الگو:Sfn مدتی بعد فراست از مونادها برای ساخت ترکیب کننده‌ها در ریسه (به انگلیسی: thread)های قاعده دار و درست جدول یادداشت‌ها در طول محاسبه استفاده کرد. الگو:Sfn

مانند هر تجزیه کننده کاهشی بازگشتی از بالا به پایین، ترکیب کننده‌های تجزیه‌گر معمولی (مانند ترکیب کننده‌های ذکر شده در بالا) در هنگام پردازش یک دستور زبان بازگشتی چپ خاتمه نمی‌یابند (به عنوان مثال s ::= s <*> term 'x'|empty). در سال ۲۰۰۶ یک الگوریتم تشخیص که دستور زبان مبهم را با قوانین مستقیم بازگشتی چپ تطبیق می‌داد ارائه شد. الگو:Sfn این الگوریتم تجزیه جداکننده بازگشتی چپ که نامتنهی است با تحمیل محدودیت‌های عمق، ساده کرد. در سال ۲۰۰۷، فراست، هفیز و کالاهااین الگوریتم را به یک الگوریتم تجزیه کننده کامل توسعه دادند، که در آن بازگشتی چپ غیرمستقیم مانند مستقیم در زمان چندجمله ای تطبیق می‌دهد، و هم چنین تعداد نمایی ای از درختان تجزیه برای گرامرهای مبهم را در فضای چندجمله ای و متراکم نمایش می‌دهد. این الگوریتم گسترش یافته، بازگشتی چپ غیرمستقیم را با مقایسه «متن محاسبه شده» با «متن فعلی»، مطابقت می‌دهد. همین نویسندگان همچنین پیاده‌سازی خود را در مورد مجموعه ای از ترکیب کننده‌های تجزیه‌گر که به زبان برنامه‌نویسی هسکل نوشته شده بودند رابر اساس همان الگوریتم توصیف کردند. الگو:Sfn

منابع

• الگو:Cite book
• الگو:Cite journal
• الگو:Cite journal
• الگو:Cite book
• الگو:Cite journal
• الگو:Cite journal
• الگو:Cite book
• الگو:Cite journalالگو:پیوند مرده
• الگو:Cite journal
• الگو:Cite journal
• الگو:Cite book

پیوند به بیرون

• parser-combinator: پیاده‌سازی ترکیب کننده تجزیه گر Common Lips
• Parsec: کتابخانه ترکیب کننده تجزیه گر برای هاسکل
• parsec: نسخه [./https://en.wikipedia.org/wiki/Go%20(programming%20language) Go] از Parsec
• FParsec: اقتباس F# از Parsec
• csharp-monad: پرت C# برای Parsec
• Jparsec: درگاه جاوای Parsec
• Bennu: کتابخانه ترکیب کننده تجزیه گر Javascript
• Ramble: پیاده‌سازی ترکیب کننده تجزیه گر R
• nom: پیاده‌سازی ترکیب کننده تجزیه گر rust با استفاده از بدون کپی است.
• pyparsing: ترکیب کننده تجزیه گر پایتون
• ts-parsec: کتابخانه ترکیب کننده تجزیه گر TypeScript