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

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

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

ایده اولیه

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

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

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

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

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

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

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

$term(x,j)={\begin{cases}\left\{\right\},&j\geq \#input\\\left\{j+1\right\},&j^{th}{\mbox{ element of }}input=x\\\left\{\right\},&{\mbox{otherwise}}\end{cases}}$

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

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

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

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

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

$(p\circledast 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 نشان دادند که با مموایز کردن در استفاده از ترکیب کننده‌های تجزیه‌گر می‌توان پیچیدگی زمانی را به چند جمله ای کاهش داد. مدتی بعد فراست از مونادها برای ساخت ترکیب کننده‌ها در ریسه (به انگلیسی: thread)های قاعده دار و درست جدول یادداشت‌ها در طول محاسبه استفاده کرد.

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

منابع

• Burge, William H. (1975). Recursive Programming Techniques. The Systems programming series. Addison-Wesley. ISBN 978-0-201-14450-5.
• Frost, Richard; Launchbury, John (1989). "Constructing natural language interpreters in a lazy functional language" (PDF). The Computer Journal. Special edition on Lazy Functional Programming. 32 (2): 108–121. doi:10.1093/comjnl/32.2.108. Archived from the original on 2013-06-06.{{cite journal}}: نگهداری یادکرد:ربات:وضعیت نامعلوم پیوند اصلی (link)
• Frost, Richard A.; Szydlowski, Barbara (1996). "Memoizing Purely Functional Top-Down Backtracking Language Processors" (PDF). Sci. Comput. Program. 27 (3): 263–288. doi:10.1016/0167-6423(96)00014-7.
• Frost, Richard A. (2003). Monadic Memoization towards Correctness-Preserving Reduction of Search (PDF). Proceedings of the 16th Canadian Society for Computational Studies of Intelligence Conference on Advances in Artificial Intelligence (AI'03). pp. 66–80. ISBN 978-3-540-40300-5.
• Frost, Richard A.; Hafiz, Rahmatullah (2006). "A New Top-Down Parsing Algorithm to Accommodate Ambiguity and Left Recursion in Polynomial Time" (PDF). ACM SIGPLAN Notices. 41 (5): 46–54. doi:10.1145/1149982.1149988. Archived from the original (PDF) on 17 August 2011. Retrieved 1 February 2020.
• Frost, Richard A.; Hafiz, Rahmatullah; Callaghan, Paul (2007). "Modular and Efficient Top-Down Parsing for Ambiguous Left-Recursive Grammars". Proceedings of the 10th International Workshop on Parsing Technologies (IWPT), ACL-SIGPARSE: 109–120. CiteSeerX 10.1.1.97.8915.
• Frost, Richard A.; Hafiz, Rahmatullah; Callaghan, Paul (2008). Parser Combinators for Ambiguous Left-Recursive Grammars. Proceedings of the 10th International Symposium on Practical Aspects of Declarative Languages (PADL). ACM-SIGPLAN. Vol. 4902. pp. 167–181. CiteSeerX 10.1.1.89.2132. doi:10.1007/978-3-540-77442-6_12. ISBN 978-3-540-77441-9.
• Hutton, Graham (1992). "Higher-order functions for parsing" (PDF). Journal of Functional Programming. 2 (3): 323–343. CiteSeerX 10.1.1.34.1287. doi:10.1017/s0956796800000411.
• Okasaki, Chris (1998). "Even higher-order functions for parsing or Why would anyone ever want to use a sixth-order function?". Journal of Functional Programming. 8 (2): 195–199. doi:10.1017/S0956796898003001.
• Swierstra, S. Doaitse (2001). "Combinator parsers: From toys to tools" (PDF). Electronic Notes in Theoretical Computer Science. 41: 38–59. doi:10.1016/S1571-0661(05)80545-6. Archived from the original (PDF) on 4 March 2016. Retrieved 1 February 2020.
• Wadler, Philip (1985). How to replace failure by a list of successes — A method for exception handling, backtracking, and pattern matching in lazy functional languages. Proceedings of a Conference on Functional Programming Languages and Computer Architecture. Lecture Notes in Computer Science. Vol. 201. pp. 113–128. doi:10.1007/3-540-15975-4_33. ISBN 978-0-387-15975-1.

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

• 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